valerio.net

This week at the F# for Scientists Book Club we got onto the topic of Project Euler, problem 11. 

To restate the problem:

In the 20×20 grid below, four numbers along a diagonal line have been bolded.

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×63x78×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?

We started down the path of how to extract all of the possible sequences of 4 numbers from the 20×20 grid using sequence expressions.  However, it occurred to me that pattern matching might be a good fit for this, so I decided to try out an alternative approach using pattern matching.

The first step is to create a pattern-matchable structure containing our 20×20 grid of numbers. I decided to use an “int list list” — a list of a list of integers.  This is easy enough to do if we split the text into lines, then split each line into number strings, and then convert each number string into an integer:

In F#-ese, we take the text, and “pipe” (using the |> operator) it into the String.split operation that splits the string on newlines.  This gives us a list of strings (string list) that we can then “pipe” into a List.map operation that applies the given function to each string in the list (each row).  This mapping function splits each row string on spaces and then converts each number string to an integer.  I’m using function composition here (the >> operator), since the string split happens, and then the integer conversion happens.

As we’re hunting through all of the possible 4-number combinations (left-right, up-down, diagonal-left, and diagonal-right), we need to store some information.  We need 1) the product of the 4 numbers and 2) the 4 numbers themselves.  This seems like a good place to use a tuple, where we can store two things — the product and the 4-number list.  We can write a function that takes 4 numbers and creates this tuple for us:

The signature of this method is “val makeTuple : int -> int -> int -> int -> int * int list”, which says that we take 4 integers and create an (int * int list), i.e. a 2-element tuple with an integer and an integer list.

Now we come to the pattern matching aspect of the problem.  We need to apply a 4×4 filter to the 20×20 cell array, look for 4 patterns, and then repeat the process for the remaining cells.

Pattern matching in F# can easily dissect a list into its head (first element) and its tail (whatever’s left). This is denoted as “head::tail”.  You can also match with more than one element out of the front of the list, using “h1::h2::h3::tail”. In addition, you can ignore things if you don’t want to explicitly give them a name by using the “I don’t care” symbol, _, e.g. “h1::h2::_”.  And, you can group elements together and give them a new name, for example “h1::(h2::h3::_ as tail)”.

So, here’s the code for our pattern finding algorithm:

The findPatterns function takes our cells (a list of list of integers) and performs a pattern match over them.  The syntax is a little odd at first, so I made a picture to show what is matched with what:

If the cells match the pattern (that is, a 4×4 square has been found), then the 4-length sequences are stored as a tuple, and the method is recursively called again, twice. 

The first recursive invocation is called with a new 2-d list containing the 4 tails from the previous match. In this loop, [t1; t2; t3; t4] keep getting their leftmost elements stripped out until there isn’t a 4×4 square left, in which case the pattern match fails, _ is matched, an empty “list list” ([[]]) is returned, and the recursion stops.  So basically we are walking left-to-right matching patterns and storing the results.

The second recursive invocation is called with the tail t5.  This is the input cells without the first row.  With this invocation we’re recursively walking the cells from top to bottom.

So, once we are able to find all of the patterns, then to solve the problem we just need to find the maximum value of the tuples returned:

Here we invoke findPatterns with the cells (returning a list list), concatenate that down to a list (of int * int list), and then find the maximum using the first value of the tuple (the product of the 4 numbers).

The result is:

> result;;
val it : int * int list = (70600674, [87; 97; 94; 89])

Cool!  It doesn’t take any time at all to execute on my machine — well below the “1 minute rule” for Project Euler.

I’m sure there are ways to improve this algorithm.  It uses the stack quite heavily, and the list concatenation (@ operator) is expensive. Also, storing all of the results for all combinations wastes memory — a fold would be more efficient, allowing you to compare as you move along.

Despite these potential problems, I really like this solution because it is so concise.

You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.