First post in months! Now that school is done with I should be able to bang out some more of these. Let's get right down to it then, shall we?
Problem 13:
Work out the first ten digits of the sum of the following one-hundred 50-digit numbers:
37107287533902102798797998220837590246510135740250, 46376937677490009712648124896970078050417018260538, 74324986199524741059474233309513058123726617309629 ...
Straightforward enough. Summing lists of numbers is nothing new to us, and it turns out that we only need the first 11 digits or so to get the accuracy we need:
problem13= take 10 .show .sum $ numberswhere numbers= [37107287533, 46376937677, 74324986199, ... ]
Now for a much more interesting problem:
Problem 14:
A Collatz chain is an iterative sequence that obeys the following rules:
- n → n/2 (if n is even)
- n → 3n + 1 (if n is odd)
- The sequence ends when n = 1
Which starting number, under one million, produces the longest Collatz chain?
What is the best way to approach this problem? One method would be to write a function that produces the next value in the Collatz chain. We could then use
to generate the full sequence:
nextCollatz n| even n= n`div` 2| odd n= 3*n + 1 collatzChain n= takeWhile (/= 1)$ iterate nextCollatz n
and use a list comprehension to obtain the longest chain:
problem14 =maximum [ (length (collatzChain x), x)| x<- [1.. 1000000] ]
Alternatively, we could rewrite our nextCollatz function to do the list-generating itself. Then we wouldn't need a separate chaining function to string the values together:
collatzChain 1= [1] collatzChain n| even n= n: collatzChain (n`div` 2)| odd n= n: collatzChain (3*n + 1)
However, it turns out that the former version runs just a hair faster.
Next problem:
Problem 15:
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. How many such routes are there through a 20×20 grid?
Oh boy. This is an interesting one. If you're a functional programmer, your first instinct should be to model this as a recursive problem. At each intersection, the number of paths to the bottom right corner is just the sum of the value below and the value to the right, so we can work backwards to find the total sum at the top left corner. On the other hand, the more mathematically inclined may notice that the value at each intersection can be computed without the need for recursion, using the formula factorial n
.
If you are a true Haskell wizard, though, there is another solution:
problem15= (iterate (scanl1 (+) ) (repeat 1))!! 20!! 20
It should blow your mind that we can compress this problem down to essentially just a
and an
. Note the array indices: we are actually constructing an infinite grid of route numbers and then extracting the value for a 20x20 grid. We can shed some light on how it works by examining just the subset of the infinite grid that we're interested in:
take 20$ iterate (scanl1 (+) )$ take 20 (repeat 1)[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] [1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91,105,120,136,153,171,190,210] ...
The
and
combine to implement the "sum" that we discussed earlier. In a way, you can think of
as adding the left value, and
as adding the above value. Super cool!