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#.
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 .
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|
|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|
The following code snippet outlines the implementation of
|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.