Advent of Code 2017, day 3

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

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 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`

To generate the spiral, simply generate the infinite sequence of rings starting from ring 0 --- an anamorphism^{2}. `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
```