← back

Spiral memory
Advent of Code 2017, day 3

18 July 2018

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.

Problem

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.

Definitions

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 * n

The side length of a ring is the nth odd number (starting at 1).

sidelen :: Integral a => a -> a
sidelen n = 2*n + 1

A 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 n

It 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.

Computing the next ring from the previous ring

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'

A corner case

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 0

where 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 0

where

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 0

Unfold!

To 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

  1. Is this even possible?

  2. You might recognise this as a dynamic programming-ish approach. This only occurred to me after I put the whole thing together.