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., Alternatively, 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.
| let computeMaxDollars (n:int) (memo:Dictionary<int64,int64>)= | |
| let rec computeMaxDollars' (ni:int64) = | |
| if ni = 0L || ni = 1L then // base case | |
| ni | |
| else | |
| match memo|> Memo.tryFind ni with | |
| | Some (nx) -> nx // found in memo. Returning Result. | |
| | None -> | |
| let f = computeMaxDollars' | |
| let nx = | |
| (ni/2L, ni/3L, ni/4L) | |
| |> (fun (x,y,z) -> (f x) + (f y) + (f z)) | |
| |> (fun nx -> Math.Max(ni,nx)) | |
| memo|> Memo.add ni nx |> ignore // storing the result in memo | |
| nx | |
| computeMaxDollars' (n|>int64) |
The following code snippet outlines the implementation of Memo.
| module Memo = | |
| let empty () = new Dictionary<int64,int64>() | |
| let add k v (memo:Dictionary<int64,int64>) = | |
| memo.[k] <- v; memo | |
| let tryFind k (memo:Dictionary<int64,int64>) = | |
| match memo.TryGetValue(k) with | |
| | true, v -> Some(v) | |
| | false,_ -> None |
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! 
adilakhter λ 
thnx for clarifying the top down vs bottom up thing…i did in bottom up which was wrong…thnx