The Bytelandian Gold Coins problem, officially published in SPOJ, concerns computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.

# Interpretation¶

The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin —

Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin .

# Algorithm¶

From the above interpretation, it is evident that the maximum achievable dollars, (from the exchange of coin ) can be computed as follows.

It effectively demonstrates an optimal substructure and therefore, hints to a dynamic programming (DP) technique to solve it. That is, for a coin , the optimal value of dollar is given by the following function.

We employ a top-down DP approach, as it seems more efficient than a bottom-up approach in this context. It is due to the fact that a bottom-up approach generally requires an OPT table to persist results of smaller subproblems. As in this case, the value of can be very large (i.e., , a bottom-up DP would require a very large array, and performs more computations. Hence, for the overlapping subproblems, we employ memoization.

The following code snippet outlines the implementation of `Memo`

.

Full source code of the solution can be downloaded from this gist. Please leave a comment if you have any question/suggestion regarding this post.

Happy problem-solving!

Pingback: F# Weekly #9, 2013 | Sergey Tihon's Blog