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.

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!

thnx for clarifying the top down vs bottom up thing…i did in bottom up which was wrong…thnx