While continuing my journey in F#, after playing with Project Eulero problems for a few weeks, I have come across another excellent excercise site which goes under the name of Programming Praxis.
The first exercise requires to implement a simple calculator using Reverse Polish Notation (RPN).
Here follows a simple solution to the problem. Operands are pushed onto the stack until an operator is found: at that point the last two operands are popped from the stack, the operator is applied to them and the result is pushed back on the stack.
#light
let is_operator c =
match c with
| "+" | "-" | "*" | "/" -> true
| _ -> false
let calculate left operator right =
match operator with
| "+" -> left + right
| "-" -> left - right
| "*" -> left * right
| "/" -> left / right
| _ -> failwith "Unknown operator"
let proc (item:string) (stack:System.Collections.Generic.Stack<double>) =
if is_operator item then
let r = stack.Pop()
let l = stack.Pop()
let result = calculate l item r
stack.Push result
else
stack.Push(System.Convert.ToDouble(item))
let evaluate (expression:string) =
let stack = new System.Collections.Generic.Stack<double>()
let items = expression.Split([|' ' |])
Array.iter (fun i -> proc i stack) items
stack.Pop()
- We first define a simple function to check whether a given string is to be interpreted as an arithmetic operand. As you can see, we only support basic operators, nothing too fancy.
- We then define a function which takes a double, a string (representing an operator) and another double, and returns the result of applying the given operator to the two numbers.
- The
procfunction takes a string, which represent either an operand or an operator, and a stack of operands.
If the item contained in the string is an operator, two operands are popped from the stack: the first pop is for the right side operand and the second pop is for the left operand; hence, the operator is applied to the two operands and the result is pushed back onto the stack.
Otherwise, if it's an operand, it's first converted from the string format and pushed onto the stack. - Finally, the entrance point to the program is defined with the
evaluatefunction, which- accepts a string containing the overall expression (such as "1 2 + 4 / 5 * 6 -")
- splits the string into an array of token strings
- feed each token into the
procfunction - finally pops the stack with the last operand to yield the result of the operation.
Project Euler Problem 11 is an interesting one; when addressed with a functional approach it lends itself to be solved using function composition. Let's have a look at the question and then a possible solution:
In the 20×20 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 The product of these numbers is 26 × 63 × 78 × 14 = 1788696. What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 20×20 grid?
#light
let numbers =
array2D [|
[|08;02;22;97;38;15;00;40;00;75;04;05;07;78;52;12;50;77;91;08|];
[|49;49;99;40;17;81;18;57;60;87;17;40;98;43;69;48;04;56;62;00|];
[|81;49;31;73;55;79;14;29;93;71;40;67;53;88;30;03;49;13;36;65|];
[|52;70;95;23;04;60;11;42;69;24;68;56;01;32;56;71;37;02;36;91|];
[|22;31;16;71;51;67;63;89;41;92;36;54;22;40;40;28;66;33;13;80|];
[|24;47;32;60;99;03;45;02;44;75;33;53;78;36;84;20;35;17;12;50|];
[|32;98;81;28;64;23;67;10;26;38;40;67;59;54;70;66;18;38;64;70|];
[|67;26;20;68;02;62;12;20;95;63;94;39;63;08;40;91;66;49;94;21|];
[|24;55;58;05;66;73;99;26;97;17;78;78;96;83;14;88;34;89;63;72|];
[|21;36;23;09;75;00;76;44;20;45;35;14;00;61;33;97;34;31;33;95|];
[|78;17;53;28;22;75;31;67;15;94;03;80;04;62;16;14;09;53;56;92|];
[|16;39;05;42;96;35;31;47;55;58;88;24;00;17;54;24;36;29;85;57|];
[|86;56;00;48;35;71;89;07;05;44;44;37;44;60;21;58;51;54;17;58|];
[|19;80;81;68;05;94;47;69;28;73;92;13;86;52;17;77;04;89;55;40|];
[|04;52;08;83;97;35;99;16;07;97;57;32;16;26;26;79;33;27;98;66|];
[|88;36;68;87;57;62;20;72;03;46;33;67;46;55;12;32;63;93;53;69|];
[|04;42;16;73;38;25;39;11;24;94;72;18;08;46;29;32;40;62;76;36|];
[|20;69;36;41;72;30;23;88;34;62;99;69;82;67;59;85;74;04;36;16|];
[|20;73;35;29;78;31;90;01;74;31;49;71;48;86;81;16;23;57;05;54|];
[|01;70;54;71;83;51;54;69;16;92;33;48;61;43;52;01;89;19;67;48|];
|]
let dimensions = (Array2D.length1 numbers, Array2D.length2 numbers)
let horizontal_traverser (i, j) (iMax, jMax) f_4 =
if (i > iMax) || (j + 4> jMax) then 0
else f_4 numbers.[i,j] numbers.[i, j+1] numbers.[i,j+2] numbers.[i,j+3]
let vertical_traverser (i,j) (iMax, jMax) f_4 =
if (i + 4 > iMax) || (j > jMax) then 0
else f_4 numbers.[i,j] numbers.[i+1, j] numbers.[i+2, j] numbers.[i+3,j]
let diagonal_traverser_left_right (i, j) (iMax, jMax) f_4 =
if (i + 4 > iMax) || (j + 4 > jMax) then 0
else f_4 numbers.[i,j] numbers.[i+1, j+1] numbers.[i+2, j+2] numbers.[i+3,j+3]
let diagonal_traverser_right_left (i, j) (iMax, jMax) f_4 =
if (i - 3 < 0) || (j + 4 > jMax) then 0
else f_4 numbers.[i,j] numbers.[i-1, j+1] numbers.[i-2, j+2] numbers.[i-3,j+3]
let max_in_direction traverser f_4 =
seq { for i in 0..fst dimensions - 1 do
for j in 0..snd dimensions - 1 do
yield traverser (i,j) dimensions f_4 }
|> Seq.max
let maximum f_4 =
[| max_in_direction horizontal_traverser f_4;
max_in_direction vertical_traverser f_4;
max_in_direction diagonal_traverser_left_right f_4;
max_in_direction diagonal_traverser_right_left f_4 |]
|> Array.max
let problem_11 () =
maximum (fun a b c d -> a * b * c * d)
- We first declare a two-dimensions array containing the 20×20 numbers that we need to explore. To do this we use F# Array2D Module. The same module is used also to compute a tuple containing the size of the two dimension arrays, which we'll use later on.
- We then proceed to define four traverser functions, one for each of these directions: horizontal, vertical, diagonal top-left to bottom-right and diagonal bottom-left to top-right. Each traverser takes as input a given item of the array and applies the supplied 4-parameters function to the starting item plus the next 3 items in a direction. Note how at this point we are not talking about a specific operation (product or sum) yet and we are concentrating on 4 items of the array at a time.
- Next we define the
max_in_directionfunction that takes a traverser and a 4-parameters function and finds the maximum value in that particular direction (whatever it might be applying the given function). - We are getting closer to the solution by defining the
maximumone-dimension array, where each item is the maximum value in each of the four directions and then taking the highest one. - We finally solve the problem by invoking the
maximumfunction passing to it the product of four items as a lambda.
Note how easy it is to change the particular function that we use to aggregate the 4 items: suppose for example that we are interested in the 4 items giving the maximum sum, we could simply invoke:
maximum (fun a b c d -> a + b + c + d)
See all Project Euler problems solutions.
Project Euler Problem 10 asks a very simple question, again dealing with prime numbers:
Calculate the sum of all the primes below two million.
I am giving here two solutions, using two different approaches:
#light
open System.Collections.Generic
// SOLUTION 1: TRIAL DIVISION
let is_prime (x:int64) =
let rec check i =
double i > sqrt (double x) || (x % i <> 0L && check (i + 1L))
check 2L
let trial_division (n:int64) =
seq { for i in 2L .. n do
if is_prime i then yield i }
|> Seq.takeWhile (fun x -> x < n)
|> Seq.sum
// SOLUTION 2: USE THE SIEVE
let sieve (n:int64) =
let candidatePrimes = new Dictionary<int64, bool>()
for i in 2L .. n do candidatePrimes.Add(i, true)
for i in 2L .. n/2L do
if candidatePrimes.[i] = true then
let mutable j = i
while (j + i <= n) do
j <- j + i
candidatePrimes.[j] <- false
seq { for i in 2L .. n do
if candidatePrimes.[i] = true then
yield i }
|> Seq.sum
- The first solution uses trial division to create a sequence of all primes under a certain threshold. It's the easiest method to understand.
- The second solution is a naive implementation of the Sieve of Erathostenes. I first mark all the numbers as candidate primes; then starting from 2 I mark off all the multiples, move to the next candidate prime, until only primes are left (you can refer to the Wikipedia article for all the details).
As you can see, this second solution looks has a more imperative feel to it, using mutable data (a dictionary and a counter). Based on my tests for numbers from 1 to 10 millions, it's at least twice as fast as the trial division method.
See all Project Euler problems solutions.
