60 Days of Euler in F# - Problem 20

The Problem

Sum the digits in 100! (factorial of 100).

The Solution

.NET's BigInteger to the rescue. Again.

First, let's compute the factorial.

let rec factorial (n : BigInteger) =
    if (n = 1I) 
    then 1I
    else n * factorial (n - 1I)

The above is the classic, recursive implementation of the factorial function.

With that in hand, finding the answer is trivial.

(factorial 100I).ToString()
|> Seq.map (fun c -> int32(string c))
|> Seq.sum

The above converts 100! to a string, then converts that into digits and then, finally, sums those digits.

60 Days of Euler in F# - Problem 19

A Confession, Before We Begin

I'm skipping problem 18. I solved it under the 1-minute time limit, but I wasn't happy with it. Problem 67 is the same as problem 18, but with a much larger input. My code ran for a long, long time and never came up with the answer. If you're interest in a really good F# solution to that problem, look here. You can compare it to my non-optimal solution:

let splitBy (c : char) (s : string) = 
    s.Split([|c|], System.StringSplitOptions.RemoveEmptyEntries)

let input = [|
    "75"
    "95 64"
    "17 47 82"
    "18 35 87 10"
    "20 04 82 47 65"
    "19 01 23 75 03 34"
    "88 02 77 73 07 63 67"
    "99 65 04 28 06 16 70 92"
    "41 41 26 56 83 40 80 70 33"
    "41 48 72 33 47 32 37 16 94 29"
    "53 71 44 65 25 43 91 52 97 51 14"
    "70 11 33 28 77 73 17 78 39 68 17 57"
    "91 71 52 38 17 14 91 43 58 50 27 29 48"
    "63 66 04 68 89 53 67 30 73 16 69 87 40 31"
    "04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
    |]

let lineToArray l =
    l 
    |> splitBy ' ' 
    |> Seq.map int 
    |> Array.ofSeq

let values = input |> Array.map lineToArray
let penRow = values.Length - 2
for y in penRow..(-1)..0 do
    for x in 0..values.[y].Length-1 do
        values.[y].[x] <- values.[y].[x] + 
            max values.[y+1].[x] values.[y+1].[x+1]
values.[0].[0]

So, with that behind us, let's move on.

The Problem

You are given the following information, but you may prefer to do some research for yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

The Solution

It may feel like cheating, but I'm not above using the .NET Framework's features to solve these problems. For example, I reduced a couple of problems down to using the BigInteger type. I am learning F# for all the advantages it gives me. I want to learn F# and everything about it. To me, that means not solving problems the language and framework have already solved for me. And that includes dates.

open System

let last = DateTime(2000,12,31)
let first = DateTime(1901,1,1)

let rec countSundays (day : DateTime) total =
    let dayValue() =
        if day.Day = 1 && day.DayOfWeek = DayOfWeek.Sunday
        then 1
        else 0

    if day > last then total
    else
        let next = day.AddDays(1.0)
        let newTotal = total + dayValue()
        countSundays next newTotal

countSundays first 0

The recursive function countSundays takes a day parameter and an accumulator total. When it reaches the last day, it returns the total it has accumulated. Otherwise, it increments the day and adds 1 to the total if the day is a Sunday and also the first day of the month.

60 Days of Euler in F# - Problem 17

The Problem

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

The Solution

Ah, the classics. Converting numbers to words.

I've written dozens of variations of this algorithm in the last 25+ years. It seems every programming class and every language book has a variation of this exercise.

Let's start by making a Map that we can use to convert numbers to words.

let words = [
    1, "one"
    2, "two"
    3, "three"
    4, "four"
    5, "five"
    6, "six"
    7, "seven"
    8, "eight"
    9, "nine"
    10, "ten"
    11, "eleven"
    12, "twelve"
    13, "thirteen"
    14, "fourteen"
    15, "fifteen"
    16, "sixteen"
    17, "seventeen"
    18, "eighteen"
    19, "nineteen"
    20, "twenty"
    30, "thirty"
    40, "forty"
    50, "fifty"
    60, "sixty"
    70, "seventy"
    80, "eighty"
    90, "ninety"
    1000, "one thousand"]

let wordMap = words |> Map.ofList

Since we only have to deal with numbers up to 1000, the algorithm is simple enough:

  • If the number exists in our map, return that
  • If the number is less than 100, return the word for tens portion and the word for the ones portion.
  • Otherwise, the number is > 100 and < 1000. The range is exclusive because the map lookup already covered both 100 and 1000. Thus, all that remains is to compute the word for the hundreds place, and call then call the function recursively for what's left.
let rec toWords n =
    match wordMap.TryFind n with
    | Some v -> v
    | _ ->
        if n < 100 then
            let ones = n%10
            wordMap.[n-ones] + "-" + wordMap.[ones]
        else
            let hundreds = n/100
            let tens = n%100
            if tens = 0 then
                wordMap.[hundreds] + " hundred"
            else
                wordMap.[hundreds] + " hundred and " + (toWords tens)

With that in place, we get our answer:

let charCount s =
    s |> Seq.filter (fun c -> c <> ' ' && c <> '-') |> Seq.length

seq { 1..1000 }
|> Seq.map toWords
|> Seq.sumBy charCount

60 Days of Euler in F# - Problem 16

The Problem

Compute 21000 and sum its digits.

The Solution

Like Problem 13, this problem is trivially easy because of .NET's BigInteger data type.

(pown 2I 1000).ToString()
|> Seq.map (fun c -> int32(c) - int32('0'))
|> Seq.sum

The pown function returns 21000 as a BigInteger. (Suffixing a numeric literal with I means it is a BigInteger literal)

Strings can be treated as Seq<char> and that's what we do here. We convert each digit into an integer and then finally sum the result.

60 Days of Euler in F# - Problem 15

The Problem

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

Grid

How many such routes are there through a 20×20 grid?

A Note Before We Begin

I have seen several, more clever solutions to this problem. I've seen one that starts at the bottom and works up, and another that manages to reduce the problem to a simple equation (the math of which is beyond me). So this isn't the best solution by any stretch, but it's the one that works for me.

The Solution

This is another problem where pure bute force doesn't do the trick. But let's look at that approach first.

[<Literal>]
let GridSize = 20

let countRoutesTo sourceX sourceY destX destY =

    let rec count sx sy =
        if sx = destX && sy = destY then 
            1L
        elif sx < GridSize && sy < GridSize then
            (count (sx+1) sy) + (count sx (sy+1))
        elif sx < GridSize then
            (count (sx+1) sy)
        else
            (count sx (sy+1))

    let result = count 0 0 
    result

#time
countRoutesTo 0 0 GridSize GridSize
#time

The internal count function is a recursive function that computes all of the routes to destX,destY. It works like this:

  • If we've hit the bottom right corner, the result is always 1 since we had to have made it there from one of the points adjacent to the bottom corner.
  • If we're somewhere in the interior of the grid, we return count for a move right plus a count for a move down.
  • If we're at the bottom edge, we return count for a move right.
  • Otherwise, we must be at the right edge, so we return count for a move down.

The problem with this function is that it takes way too long to execute. I stopped it running after 20 minutes. I know it works in principle because if I reduce GridSize to 10, it executes in under a second. The problem is that the number of calls to count is a factorial of the GridSize. In fact, you can get the answer to the problem by computing (2n)!/n!2, but I didn't know that when I was writing this :)

My (ahem!) genius solution to the problem was to cache the answers for the lower right 100 squares of the grid, and then apply my brute force algorithm. If the algorithm hits a cached position, it doesn't have to do any more work and just returns the value it's currently computed plus the value from the cache.

This algorithm finds the answer in 22 seconds on my machine.

let countRoutesToCached sourceX sourceY destX destY =

    let cachePos = GridSize / 2
    let cache = System.Collections.Generic.Dictionary<int*int,int64>()

    let rec count sx sy =
        match cache.TryGetValue((sx,sy)) with
        | true,v -> v
        | _ ->
            if sx = destX && sy = destY then 
                1L
            elif sx < GridSize && sy < GridSize then
                (count (sx+1) sy) + (count sx (sy+1))
            elif sx < GridSize then
                (count (sx+1) sy)
            else
                (count sx (sy+1))

    for x in cachePos..GridSize do
        for y in cachePos..GridSize do
            cache.Add((x,y),(count x y)) |> ignore

    let result = count 0 0 
    result

#time
countRoutesToCached 0 0 GridSize GridSize
#time

60 Days of Euler in F# - Problem 14

The Problem

The following iterative sequence is defined for the set of positive integers:

    *n → n/2* (*n* is even)
    *n → 3n + 1* (*n* is odd)

Using the rule above and starting with 13, we generate the following sequence:

    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

The Solution

I had some fun with this one.

I originally wrote the solution to this on an Alienware laptop with a 2GHz processor and 8 cores. By default, most languages use only one of those cores at a time, so most of my solutions were running on a single core. Most of the time, that’s good enough.

My original solution, however, took long enough to execute that I had enough time to go inside and make a sandwich.

My current laptop has a 3.8Ghz processor and solves the problem in about 3.5 seconds. There has to be some other difference in play here, but I’ll be damned if I can figure out what it is.

Here’s the “purely functional” solution.

let isEven i = i &&& 1L = 0L
let (|Even|Odd|) i = if isEven i then Even else Odd

let next n =
    match n with
    | Even -> n/2L
    | Odd -> 3L*n+1L

let collatz n = 
    let rec c n length = 
        if n = 1L then length
        else c (next n) (length+1L)
    c n 1L 

#time
seq { 1L..999999L } |> Seq.maxBy collatz
#time

We start with a helper function, isEven and an active pattern matching function that will return Even or Odd for a given number.

The next function finds the next number in the sequence based on the rules in the problem definition.

The collatz function uses a tail-recursive function to generate the length of the sequence.

Back when this was taking forever to execute, I tried three more solutions to the problem. I’ll outline them here as a learning experience.

Attempt #2

Since the functional approach wasn’t working for me, I tried a solution that uses mutables.

let collatzWithMutables start = 
    let mutable count = 1L
    let mutable current = start
 
    while current > 1L do
        current <- next current
        count <- count + 1L
    count

#time
seq { 1L..999999L } |> Seq.maxBy collatzLength
#time

That executes in 3.3 seconds on my machine. I’m not happy about a 5.7% reduction in speed. I think we can do better.

Attempt #3

The length of the sequence starting with n is constant. I figured that it was highly likely I would be encountering the same values over and over. If you encounter an n for which you’ve already computed the length, it’s not necessary to compute it again. Just add what you have now to the already-computed length for n.

Let’s try that:

let cache = System.Collections.Generic.Dictionary<int64,int64>()

let collatzWithMutablesCached start =
    let mutable count = 1L
    let mutable current = start

    while current > 1L do
        match cache.TryGetValue current with
        | true,cachedCount ->
            count <- count + cachedCount
            current <- 1L
        | _ ->
            current <- next current
            count <- count + 1L

    cache.Add(start,count)
    count

#time
seq { 1L..999999L} |> Seq.maxBy collatzWithMutablesCached
#time

That brings our time down to 0.7 seconds. I’m totally happy with that. That’s an 80% reduction.

I went back and added some code to count the number of cache hits and cache misses. There are 999,997 cache hits vs. 5,226,259 misses. So the cache hits only 16% of the time. However, those hits eliminate a whopping 150,522,402 calls to next which is why this is so much faster.

Attempt #4

I’m still feeling experimental. There’s one more approach I’d like to try.

I have 8 cores. Let’s use all of them!

let collatzAsync startNum endNum = async {
    return 
        seq { startNum..endNum }
        |> Seq.map (fun i -> i,collatzWithMutables i)
        |> Seq.maxBy snd
}

let ranges = 
	[ 
	1L,125000L
	125001L,250000L
	250001L,375000L
	375001L,500000L
	500001L,625000L
	625001L,750000L
	750001L,875000L
	875001L,999999L
	]

#time
ranges
|> Seq.map (fun (s,e) -> collatzAsync s e)
|> Async.Parallel
|> Async.RunSynchronously
|> Seq.maxBy snd
|> fst
#time

I broke the problem up into 8 chunks of 125000 each. collatzAsync is an asynchronous function that works out the answer to the chunk using the collatzWithMutables function we used before.

The main body executes all those chunks in parallel and then returns the biggest answer found.

This runs in 0.9 seconds on my machine. Not as fast as the cached solution, but quite fun to write.

60 Days of Euler in F# - Problem 13

The Problem

Work out the first 10 digits of the sum of a lot of really large numbers.

I won’t duplicate the list of numbers here since they exist in code form in the solution

The Solution

The problem requires us to sum 100 50-digit integers.

This might cause problems in other languages, but thanks to the .NET Framework’s big integer type, the problem is almost trivially easy. We simply parse the input into bigint and then take the sum. We could even skip the parsing step by specifying the numbers as bigint literals (e.g. 1234I), but where’s the sport in that?

open System.Numerics

let input = [
    "37107287533902102798797998220837590246510135740250"
    "46376937677490009712648124896970078050417018260538"
    "74324986199524741059474233309513058123726617309629"
    "91942213363574161572522430563301811072406154908250"
    "23067588207539346171171980310421047513778063246676"
    "89261670696623633820136378418383684178734361726757"
    "28112879812849979408065481931592621691275889832738"
    "44274228917432520321923589422876796487670272189318"
    "47451445736001306439091167216856844588711603153276"
    "70386486105843025439939619828917593665686757934951"
    "62176457141856560629502157223196586755079324193331"
    "64906352462741904929101432445813822663347944758178"
    "92575867718337217661963751590579239728245598838407"
    "58203565325359399008402633568948830189458628227828"
    "80181199384826282014278194139940567587151170094390"
    "35398664372827112653829987240784473053190104293586"
    "86515506006295864861532075273371959191420517255829"
    "71693888707715466499115593487603532921714970056938"
    "54370070576826684624621495650076471787294438377604"
    "53282654108756828443191190634694037855217779295145"
    "36123272525000296071075082563815656710885258350721"
    "45876576172410976447339110607218265236877223636045"
    "17423706905851860660448207621209813287860733969412"
    "81142660418086830619328460811191061556940512689692"
    "51934325451728388641918047049293215058642563049483"
    "62467221648435076201727918039944693004732956340691"
    "15732444386908125794514089057706229429197107928209"
    "55037687525678773091862540744969844508330393682126"
    "18336384825330154686196124348767681297534375946515"
    "80386287592878490201521685554828717201219257766954"
    "78182833757993103614740356856449095527097864797581"
    "16726320100436897842553539920931837441497806860984"
    "48403098129077791799088218795327364475675590848030"
    "87086987551392711854517078544161852424320693150332"
    "59959406895756536782107074926966537676326235447210"
    "69793950679652694742597709739166693763042633987085"
    "41052684708299085211399427365734116182760315001271"
    "65378607361501080857009149939512557028198746004375"
    "35829035317434717326932123578154982629742552737307"
    "94953759765105305946966067683156574377167401875275"
    "88902802571733229619176668713819931811048770190271"
    "25267680276078003013678680992525463401061632866526"
    "36270218540497705585629946580636237993140746255962"
    "24074486908231174977792365466257246923322810917141"
    "91430288197103288597806669760892938638285025333403"
    "34413065578016127815921815005561868836468420090470"
    "23053081172816430487623791969842487255036638784583"
    "11487696932154902810424020138335124462181441773470"
    "63783299490636259666498587618221225225512486764533"
    "67720186971698544312419572409913959008952310058822"
    "95548255300263520781532296796249481641953868218774"
    "76085327132285723110424803456124867697064507995236"
    "37774242535411291684276865538926205024910326572967"
    "23701913275725675285653248258265463092207058596522"
    "29798860272258331913126375147341994889534765745501"
    "18495701454879288984856827726077713721403798879715"
    "38298203783031473527721580348144513491373226651381"
    "34829543829199918180278916522431027392251122869539"
    "40957953066405232632538044100059654939159879593635"
    "29746152185502371307642255121183693803580388584903"
    "41698116222072977186158236678424689157993532961922"
    "62467957194401269043877107275048102390895523597457"
    "23189706772547915061505504953922979530901129967519"
    "86188088225875314529584099251203829009407770775672"
    "11306739708304724483816533873502340845647058077308"
    "82959174767140363198008187129011875491310547126581"
    "97623331044818386269515456334926366572897563400500"
    "42846280183517070527831839425882145521227251250327"
    "55121603546981200581762165212827652751691296897789"
    "32238195734329339946437501907836945765883352399886"
    "75506164965184775180738168837861091527357929701337"
    "62177842752192623401942399639168044983993173312731"
    "32924185707147349566916674687634660915035914677504"
    "99518671430235219628894890102423325116913619626622"
    "73267460800591547471830798392868535206946944540724"
    "76841822524674417161514036427982273348055556214818"
    "97142617910342598647204516893989422179826088076852"
    "87783646182799346313767754307809363333018982642090"
    "10848802521674670883215120185883543223812876952786"
    "71329612474782464538636993009049310363619763878039"
    "62184073572399794223406235393808339651327408011116"
    "66627891981488087797941876876144230030984490851411"
    "60661826293682836764744779239180335110989069790714"
    "85786944089552990653640447425576083659976645795096"
    "66024396409905389607120198219976047599490197230297"
    "64913982680032973156037120041377903785566085089252"
    "16730939319872750275468906903707539413042652315011"
    "94809377245048795150954100921645863754710598436791"
    "78639167021187492431995700641917969777599028300699"
    "15368713711936614952811305876380278410754449733078"
    "40789923115535562561142322423255033685442488917353"
    "44889911501440648020369068063960672322193204149535"
    "41503128880339536053299340368006977710650566631954"
    "81234880673210146739058568557934581403627822703280"
    "82616570773948327592232845941706525094512325230608"
    "22918802058777319719839450180888072429661980811197"
    "77158542502016545090413245809786882778948721859617"
    "72107838435069186155435662884062257473692284509516"
    "20849603980134001723930671666823555245252804609722"
    "53503534226472524250874054075591789781264330331690"
    ]

let sum = 
    input
    |> Seq.map BigInteger.Parse
    |> Seq.sum

sum.ToString().Substring(0, 10)

60 Days of Euler in F# - Problem 12

The Problem

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

The Solution

This one is a little tricky. Note that the factor examples the problem definition specifies include composite numbers (i.e., multiples of more than one prime). In most of the Euler problems I’ve worked on, factors are limited to primes.

Thus, to find the number of divisors for n, we need to check all numbers up to the square root of n.

let intsqrt i = int(sqrt(float i))

let numDivisors n =

    let factorsOver3() =
        let sr = intsqrt n
        seq { 3..sr }
        |> Seq.filter (fun e -> n % e = 0)
        |> Seq.length

    match n with
    | 1 -> 1
    | 2 -> 2
    | x when (x &&& 1) = 0 -> (2 + factorsOver3()) * 2
    | _ -> (1 + factorsOver3()) * 2
  • If n is 1, then there’s only 1 divisors
  • If n is 2, there’s 2 divisors (1 and 2)
  • If n is even, the number of divisors is 2 (2 and n itself) plus the number of factors it has > 3, times 2. Why do we multiply by two? Because if we only test up to the square root of n, then if we find a factor then n/x is also a factor.
  • If n is odd, the number of divisors is 1 (the number 1 is a divisor) plus the number of factors over 3. We also multiply by two for the same reason as in the even case.

With that in hand, we can look for the solution:

let rec getOver500 t n =
    if numDivisors t >= 500 then
        t
    else
        getOver500 (t + n + 1) (n + 1)

getOver500 1 1

The getOver500 function takes two parameters, t which is the accumulator for the triangle number value, and n which is the nth natural number. If it finds a t with >= 500 divisors, it returns t, otherwise it computes the next triangle number (t + n + 1) and the next natural number (n + 1) and recurses.

Full disclosure: While I was writing this blog post, I discovered a very subtle bug. The code finds the correct answer to this problem, but it is flawed. Consider the case of 36. 36 has 9 divisors (1, 2, 3, 4, 6, 9, 12, 18, and 36) but numDivisors actually returns 10 for that. The numDivisors function, as written, will always return an even number, even though that is (in hindsight) clearly wrong. I’m leaving it here as a reminder that just because code works today, that doesn’t mean you won’t find a bug tomorrow when the inputs are different.

Looking back, I see that I was trying to be too clever by considering different cases for odd and even. There is a much simpler way that executes in almost exactly the same amount of time. Just replace the numDivisors function with this one:

let numDivisors n =
    let sr = intsqrt n
    seq { 1..sr }
    |> Seq.filter (fun e -> n % e = 0)
    |> Seq.collect (fun e -> [e; n/e])
    |> Seq.distinct
    |> Seq.length

60 Days of Euler in F# - Problem 11

The Problem

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 the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

The Solution

First, we need that input grid in a format we can use.

open System

let runLength = 4
let gridSize = 20

let input = [|
    "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 splitBy (c : char) (s : string) =
	s.Split([|c|], StringSplitOptions.RemoveEmptyEntries)

let ints =
    input
    |> Array.map (fun s -> 
        s
        |> splitBy ' '
        |> Array.map int32
    )
	
let product arr =
    arr |> Array.reduce (fun acc elem -> acc*elem)
	

We define a couple of values that tell us about the problem we’re solving. We’re looking for groups of runLength digits. gridSize tells us the grid is 20x20. input contains the grid itself, copy/pasted from the problem definition.

The ints function turns our input into an array of arrays, which allows us to reference rows and columns like so: ints.[row].[col]

Finally, similar to what we used in Problem 8, the product function uses Array.reduce to return the product of all the elements of an array.

Next, we need to figure out how to break this grid up into chunks of 4 numbers each. Let’s start with the easiest case: breaking each row up into groups of 4.

let byRows() =
    ints
    |> Seq.collect (fun r -> r |> Array.windowed runLength)

The function above uses Array.windowed to break up each row (which is an array itself) into groups of 4. For the first row of the grid, this function returns a sequence that looks like this:

[|8; 2; 22; 97|]
[|2; 22; 97; 38|]
[|22; 97; 38; 15|]
[|97; 38; 15; 0|]
[|38; 15; 0; 40|]
[|15; 0; 40; 0|]
[|0; 40; 0; 75|]
[|40; 0; 75; 4|]
[|0; 75; 4; 5|]
[|75; 4; 5; 7|]
[|4; 5; 7; 78|]
[|5; 7; 78; 52|]
[|7; 78; 52; 12|]
[|78; 52; 12; 50|]
[|52; 12; 50; 77|]
[|12; 50; 77; 91|]
[|50; 77; 91; 8|]

That’s the magic of the windowed function.

Next, we’ll tackle the problem of breaking up each column into groups of 4.

let byCols() =
    let getCol c =
        seq {
            for r in 0..gridSize-1 do
                yield ints.[r].[c]
        }
        |> Array.ofSeq
        |> Array.windowed runLength

    seq {
        for c in 0..gridSize-1 do
            yield! getCol c
    }

The function above first turns the grid into arrays of columns, then uses Array.windowed to, once again, created groups of 4 numbers.

Now, onto diagonals, which are the most complicated case.

let byDiagonals() =
    let getDownhill r c =
        seq {
            for i in 0..runLength - 1 do
                yield ints.[r+i].[c+i]
        } |> Array.ofSeq

    let getUphill r c =
        seq {
            for i in 0..runLength - 1 do
                yield ints.[r+i].[c-i]
        } |> Array.ofSeq

    seq {
        for r in 0..gridSize - 1 do
            for c in 0..gridSize - 1 do
                if (r + runLength) < gridSize && (c + runLength) < gridSize then
                    yield getDownhill r c
                if (r + runLength) < gridSize && (c - runLength) >= 0 then
                    yield getUphill r c
    }

This function contains two functions inside it, getDownhill and getUphill. These return an array of 4 numbers either moving downhill (where both row and column increase) or uphill (where row increases and column decreases).

The main function body simply generates each possible position in the grid and, if possible, yields a downhill and an uphill sequence from that position.

With all that in place, we can finally get our answer:

[ byRows(); byCols(); byDiagonals() ]
|> Seq.concat
|> Seq.map product
|> Seq.max

The code above:

  • Uses our three byXxx functions to generate all possible sequences of 4 numbers.
  • Concatenates that into a single sequence consisting of 4-number arrays.
  • Uses Seq.map to compute the product of each array
  • Uses Seq.max to return the answer.

60 Days of Euler in F# - Problem 10

The Problem

Sum the primes below 2 million.

The Solution

We already wrote a function to generate primes below a certain number for Problem 3.

We can just use Seq.sum to sum those and we’re done.

getPrimesBelow64 2000000
|> Seq.sum