I would like to recount one of the favourite pieces of code that I've written, my solution to the spiral memory problem from day 3 of Advent of Code 2017.
There is an infinite spiral sequence that unfolds starting at 1, where each subsequent number is the sum of the adjacent numbers already produced (e.g. 133 = 122 + 4 + 2 + 5). You are to find the first value in the sequence larger than some target number t.
147 142 133 122 59
304 5 4 2 57
330 10 1 1 54
351 11 23 25 26
362 747 806---> ...
Since I can't be fussed to work out a closed form solution,1 I'll generate the entire sequence as an unfold, then consume the list until we hit t.
Let us first define some conceptual machinery.
A ring is a square slice of the spiral. The first three rings are:
147 142 133 122 59
5 4 2 304 57
1 10 1 330 54
11 23 25 351 26
362 747 806---> ...
The key insight is that ring n+1 can be computed from ring n. Rings are represented as plain Haskell lists.
The size of a ring is the number of values in it. It has a closed form solution: \[size(0) = 1, size(n) = (2n+1)^2 - (2n-1)^2 = 8n\]
ringsize :: Int -> Int
ringsize 0 = 1
ringsize n = 8 * nThe side length of a ring is the nth odd number (starting at 1).
sidelen :: Integral a => a -> a
sidelen n = 2*n + 1A ring can be decomposed into four sides. We'll follow the convention that we always enumerate starting from the right vertical, anticlockwise.
5 4 2 vals [[25, 1, 2], [2, 4, 5], [5, 10, 11], [11, 23, 25]]
10 1 =>
11 23 25 idxs [[8, 0, 1], [1, 2, 3], [3, 4, 5], [5, 6, 7]]
Note the indices: a ring always starts from the second number of the right side, since that's where the previous ring ends.
The sides n function gives the four sides of ring n, as a list of the corresponding indices in the ring. (idxs above is computed by sides 1).
sides :: Int -> [[Int]]
sides n = take 4 $ unfoldr go indexes
where
go = Just . (take slen &&& drop (slen-1))
indexes = drop (rs-1) $ cycle (take rs [0..])
slen = sidelen n
rs = ringsize nIt splits the sequence [ringsize n, 0, .., (ringsize n) - 1], into four windows of length sidelen n, where the first number in the next window with the last number in the previous window.
Every number in a ring is the sum of numbers from two places: the current ring and the previous ring. In the below example, 133 is the sum of the numbers 5,4,2 from the previous ring, and 122, the previous number generated in the current ring.
... 133 122 ...
... 5 4 2 ...
The key idea is that for each indexed position in sides n, we can compute the indices in the previous ring that it is adjacent to, by adding their sides.
Take, for instance, the top sides of rings 1 and 2.
147 142 133 122 59
5 4 2
We get the following neighbour set: 59 -> {2}, 122 -> {4,2}, 133 -> {5,4,2}, 142 -> {5,4}, 147 -> {5}
Note that each position can have at most three adjacents in the previous ring.
If you widen the side of ring 1,
147 142 133 122 59
X X 5 4 2 X X
you can get a uniform neighbour set size: 59 -> {X, X, 2}, 122 -> {X, 4, 2}, 133 -> {5,4,2}, 142 -> {X, 5, 4}, 147 -> {X, X, 5}
The prevNeighbours function does exactly this: It first pairs the sides of the current and previous rings (ns), then for each side pair, it pairs the index of the outer ring with three indices of the inner ring. The inner ring indices are drawn from a sliding window of size 3, using the above trick to take care of corners and missing elements.
-- (indicies of) neighbours of (indicies of) this ring in previous ring.
prevNeighbours :: Int -> [(Int, [Int])]
prevNeighbours n = concatMap (tail . go) ns
where
go (ps,ts) = map (fmap catMaybes) $ zip ts ws
where
ws = window 3 $ [Nothing, Nothing] ++ map Just ps ++ [Nothing, Nothing]
ns = zip (sides (n-1)) (sides n)Now, supposing that you had prevRing = ring n, you can compute (parts of) numbers in ring n+1, by getting the neighbour indices in prevRing for each position ring n+1, picking those elements out of prevRing, and summing them.
prevNeighbourSums = map (fmap (sum . map (prevRing !!))) $ prevNeighbours n'Next we need to figure out what numbers in the current ring to add to the skeletal current ring prevNeighbourSums.
In the current ring being generated, nextRing = ring (n+1), the previous number generated is always adjacent to the current number being generated (aside from the first number in the ring). So to each number in prevNeighbourSums, we add
if i > 0 then nextRing !! (i-1) else 0where i is the index in the current ring of the element we are scrutinising.
If you have a number following a corner, though, it will be adjacent to the two previous numbers. See, for example, the number 122 in ring 2.
122 59
57
In this case, we add
if i `elem` afterCorners then nextRing !! (i-2) else 0where
corners :: Int -> [Int]
corners = map head . sides
afterCorners = tail $ map (+1) (corners n')afterCorners is the tail of corners, because this case only applies to the top left, top right, and bottom left corners.
The bottom right corner is a special case: the adjacency wraps around to the beginning of the current ring.
For example, 25, the last number of ring 1, is adjacent to the first element of ring 1.
Also, 23, the second last number in ring 1, is adjacent to the first element of ring 1. (But not 25, because that has not been produced yet.)
1
23 25
The condition to add is therefore
if i >= ringsize n' - 2 then nextRing !! 0 else 0To generate the spiral, simply generate the infinite sequence of rings starting from ring 0 --- an anamorphism2. nextRing is the assembly of the the components discussed above.
seq2 :: [Integer]
seq2 = concat $ go 0 [1]
where
go n prevRing = prevRing : go n' nextRing
where
n' = n+1
nextRing = [ (if i > 0 then nextRing !! (i-1) else 0)
+ (if i `elem` afterCorners then nextRing !! (i-2) else 0)
+ (if i >= ringsize n' - 2 then nextRing !! 0 else 0)
+ pns
| (i, pns) <- prevNeighbourSums
]
afterCorners = tail $ map (+1) (corners n')
prevNeighbourSums = map (fmap (sum . map (prevRing !!))) $ prevNeighbours n'Finally, the solution is simply
solve2 :: Integer -> Integer
solve2 t = head $ dropWhile (<= t) seq2