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

--

It can be exchanged to three other coins, i.e.,

coins. Thus,  coin

yields

value in bytelandian gold coins.

Alternatively,

coin can be exchanged for

dollars.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. [gist]5035234[/gist]

The following code snippet outlines the implementation of Memo. [gist]5035253[/gist]

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!