Recently, Tomas Petricek gave a talk on the topic of internal DSL development with F#. In particular, he discussed the motivation behind DSL development, and demonstrated a number of example DSLs using F#. If you are interested, please check it out —
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.
This post focuses on Collatz problem, which is also known as, among others, the 3n+1 problem, and the Syracuse problem.
Outline. We begin by introducing Collatz conjecture; afterwards, we presents an algorithm to solve the problem (UVa 100 or SPOJ 4073) published in both UVa and SPOJ. The primary advantage of having it in SPOJ is that we can use F# to derive a simple and elegant solution; at the same time, we can verify it via SPOJ’s online judge.
Background: Collatz Conjecture
Collatz problem, also known as problem, concerns the iterates generated by the repeated applications of following the function: Given a positive integer, —
which implies that if is even, it returns , otherwise . This function is called Collatz function. Consider, for instance, , the generated iterates are following:. This sequence is referred to as Collatz sequence, or hailstone numbers.
Collatz conjecture, which is credited to Luther Collatz at the University of Hamburg, asserts that for any positive integer , the repeated applications of the Collatz function, i.e., eventually produces value ; that is, , where denotes application of . Considering , it follows: .
The generated sequence of iterates: is called the Collatz-trajectory of . For instance, beginning from , the resulted sequence converged to as follows: . Therefore, Collatz-trajectory of 26 is . Note that, although Collatz problem is based on this simple concept, it is intractably hard. So far, it has been verified for by Leaven and Vermeluen.
Algorithm Design: 3n+1 problem
In the rest of this post, we intend to solve the problem, which is essentially a restricted or bounded version of the Collatz problem.
Interpretation. It restricts the iteration by exiting as soon as the Collatz sequence reaches to value 1 at . For = 26, the resulting Collatz sequence is therefore: , and length of the sequence is i.e., 11. This problem asks to compute the largest Collatz sequence that results from any integer between and , which are provided as inputs. Note that, the value of and are both positive integers: .
Implementation. We first apply a naïve brute-force algorithm to solve this problem, which computes the length of the sequence for each integer from to , and returns the maximum length found. It is worth noting that-
As we shall see next, we have optimized the naïve implementation considering the above observations. First, we define function,
nextCollatz, that returns next integer of the Collatz sequence, given an integer . In effect, it computes from as follows.
|let nextCollatz (n:int64) =|
|if n%2L = 0L then n/2L else 3L*n+1L|
Using the algorithm outlined in
collatzSeqLength, the length of the Collatz sequence is computed for any given integer .
|let max = 1000001L|
|let memo = Array.create (max|>int) 0L|
|// Computes Collatz sequence length, given a|
|// positive integer, x.|
|let rec collatzSeqLength (x:int64):int64 =|
|let rec seqLength' (n:int64) contd =|
|match n with|
|| 1L -> contd 1L // initalizing sequence length with 1|
|| _ ->|
|if n < max && memo.[n|>int] <> 0L then|
|seqLength' (nextCollatz n) (fun x ->|
|let x' = x+1L //incrementing length and storing it in memo.|
|if n<max then|
|memo.[n|>int] <- x'|
|x|>(fun i -> seqLength' i id)|
It includes the following optimizations over the naïve implementation we stated earlier:
Memorization has been incorporated to effectively optimize the algorithm by avoiding redundant computations of the sequence and its length, which in turn provides a faster algorithm than its naïve counterpart, albeit with the cost of additional space.
Tail-recursive algorithm enables computation of Collatz sequence with larger .
Continuation-passing-style has been applied in this algorithm to accommodate, and to combine tail-call optimization with memorization.
The following snippet demonstrates how the maximum sequence length is obtained by invoking collatzSeqLength for each integer between the given and .
|let maxCollazSeqLength (x:int64,y:int64) =|
|let x',y' = System.Math.Min(x,y), System.Math.Max(x,y)|
||> Seq.fold (fun max x ->|
|let r = collatzSeqLength x|
|if r > max then r else max) 0L|
Complete source code of this problem can be found in this gist. Following IDEONE page (with sample inputs and outputs) has been provided to further play with the code (in case of the unavailability of F# in local system). Java source code is also available for this problem.
Try solving Euler Problem 14, which resembles this problem and based on these stated concepts. Please leave a comment if you have any question/suggestion regarding this post. Happy coding!
The Party Schedule problem, published in SPOJ website, is about deriving an optimal set of parties that maximizes fun value, given a party budget: and parties: where each party have an entrance cost , and is associated with a fun value .
This problem is a special case of Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed .
More formally, we are given a budget as the bound. All parties have costs and values . We have to select a subset such that is as large as possible, and subject to the following restriction —
Furthermore, an additional constraint: “do not spend more money than is absolutely necessary” is applied, which implies following. Consider two parties and ; if and , then we must select instead of .
The definition of this problem suggests a recursive solution. However, a naïve recursive solution is quite impractical in this context, as it requires exponential time due to the following reason: a naïve recursive implementation applies a top-down approach that solves the subproblems again and again.
Next, we select dynamic programming technique to solve this problem. So, we have to define a recurrence that expresses this problem in terms of its subproblems, and therefore it begs the answer of the following question:
What are the subproblems? We have two variants: and , i.e. available budget and number of parties. We can derive smaller subproblems, by modifying these variants; accordingly, we define-
It returns the maximum value over any subset where . Our final objective is to compute , which refers to the optimal solution, i.e., maximal achievable fun value from budget and parties.
To define the recurrence, we describe in terms of its smaller subproblems.
How can we express this problem using its subproblems? Let’s denote to be the optimal subset that results in . Consider party and note following.
- It , then . Thus, using the remaining budget and the parties , we seek the optimal solution.
- Otherwise, then . Since is not included, we haven’t spent anything from .
Obviously, when , we apply the 2nd case. Using the above observations, we define the recurrence as follows–
Using the above recurrence, we can compute for all parties and for costs . In essence, we build the OPT table, which consists of rows and columns, using a bottom-up approach as stated in the following algorithm.
|Initialize OPT[0,c] = 0, for c = 0..C and OPT[i,0], for i= 0..n|
|For i = 1,...,n do|
|For c = 1,..,C do|
|Use above recurrence to compute OPT(i,c)|
Following code builds the OPT table using the stated algorithm.
|let computeOptPartySchedule (budget,N,(costs:int),(funValues:int)) =|
|let OPT = Array2D.zeroCreate (N+1) (budget+1)|
|for i = 1 to N do|
|for j = 0 to budget do|
|let c_i = costs.[i-1] //cost for the ith party|
|let f_i = funValues.[i-1] // fun value associated with ith party|
|match j,c_i with|
|| _ when j<c_i -> OPT.[i-1,j]|
|| _ -> Math.Max(OPT.[i-1,j],f_i + OPT.[i-1, j-c_i])|
|// returning (1) summation of all entrance fee or costs,|
|// (2) summation of fun values|
In effect, it does two things: builds OPT table and afterwards, returns the OPT(n,C) and associated optimal cost (due to the constraint “do not spend more money than is absolutely necessary” discussed in background section) as a tuple (see Line 16). Following function computes the optimal cost.
|let computeOptCost (budget,N,(opt:int [,]),optFunValue) =|
|let mutable optCost = 0|
|for c=budget downto 0 do|
|if opt.[N,c] = optFunValue then|
|optCost <- c|
Complexity. as each requires time.
For the complete source code, please check out this gist, or visit its IDEONE page to play with the code. Please leave a comment if you have any question or suggestion regarding the algorithm/implementation.
Available at Sum square difference
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025-385 = 2640.Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
|let squareOfSum n =|
|let i = n*(n+1)/2|
|let sumOfSquare n =|
||> List.fold (fun acc x -> acc + x*x) 0|
|let solveEuler6 N =|
|(squareOfSum N)- (sumOfSquare N)|