SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#

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

noun_project_8551 It can be exchanged to three other coins, i.e., coins. Thus,  coin  yields value in bytelandian gold coins.
noun_project_8551 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.

image

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.

image

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)
view raw spoj_COINS.fsx hosted with ❤ by GitHub

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
view raw spoj_COINS.fsx hosted with ❤ by GitHub

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! noun_project_6324

2 thoughts on “SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s