Advent of Code: Day 3

This is the third notebook in my posts on the Advent of Code challenges. The notebook in its original format can be found on my github.

Day 3: Spiral Memory

Numbers are arranged in a spiral

17  16  15  14  13
18   5   4   3  12
19   6   1   2  11
20   7   8   9  10
21  22  23---> ...

Given an integer n, what is its Manhattan Distance from the center (1) of the spiral? For instance, the distance of 3 is $2 = 1 + 1$, since it’s one space to the right and one space up from the center.

Here’s my idea. The bottom right corner of the $k$th layer is the integer $(2k+1)^2$, since that’s how many integers are contained within that square. The other three corners in that layer are $(2k+1)^2 – 2k, (2k+1)^2 – 4k$, and $(2k+1)^2 – 6k$. Finally, the closest spot on the $k$th layer to the origin is at distance $k$: these are the four “axis locations” halfway between the corners, at $(2k+1)^2 – k, (2k+1)^2 – 3k, (2k+1)^2 – 5k$, and $(2k+1)^2 – 7k$.

For instance when $k = 1$, the bottom right is $(2 + 1)^2 = 9$, and the four “axis locations” are $9 – 1, 9 – 3, 9-5$, and $9-7$. The “axis locations” are $k$ away, and the corners are $2k$ away.

So I will first find which layer the number is on. Then I’ll figure out which side it’s on, and then how far away it is from the nearest “axis location” or “corner”.

My given number happens to be 289326.

In [1]:
import math

def find_lowest_larger_odd_square(n):
    upper = math.ceil(n**.5)
    if upper %2 == 0:
        upper += 1
    return upper
In [2]:
assert find_lowest_larger_odd_square(39) == 7
assert find_lowest_larger_odd_square(26) == 7
assert find_lowest_larger_odd_square(25) == 5
In [3]:
find_lowest_larger_odd_square(289326)
Out[3]:
539
In [4]:
539**2 - 289326
Out[4]:
1195

It happens to be that our integer is very close to an odd square.
The square is $539^2$, and the distance to that square is $538$ from the center.

Note that $539 = 2(269) + 1$, so this is the $269$th layer of the square.
The previous corner to $539^2$ is $539^2 – 538$, and the previous corner to that is $539^2 – 2\cdot538 = 539^2 – 1076$.
This is the nearest corner.
How far away from the square is this corner?

In [5]:
539**2 - 2*538 - 289326
Out[5]:
119

That’s really close to the corner. The corner is $538$ from the center, and the square is $119$ steps closer to the center. So the distance in this case is $538 – 119$.

In [6]:
538 - 119
Out[6]:
419

And so we solved the first part quickly with a mixture of function and handiwork.

Part 2

In part two, the spiral has changed significantly. Build the spiral iteratively. Initially, start with 1. Then in the next square of the spiral, put in the integer that is the sum of the adjacent (including diagonal) numbers in the spiral. This spiral is

147  142  133  122   59
304    5    4    2   57
330   10    1    1   54
351   11   23   25   26
362  747  806--->   ...

What is the first value that’s larger than 289326?

My plan is to construct this spiral. The central 1 will have coordinates (0,0), and the spiral will be stored in a dictionary whose key is the tuple of the location.

To construct the spiral, we note that the direction of adding goes in the pattern RULLDDRRRUUULLLLDDDD. The order is right, up, left, down: the number of times each direction is repeated goes in the sequence 1,1,2,2,3,3,4,4,….

In [7]:
spiral = {}
spiral[(0,0)] = 1

NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]
DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down

def spiral_until_at_least(n):
    spiral = {}               # Spiral dictionary
    spiral[(0,0)] = 1
    x,y = 0,0
    steps_in_row = 1          # times spiral extends in same direction
    second_direction = False  # spiral extends in same direction twice: False if first leg, True if second
    nstep = 0                 # number of steps in current direction
    step_direction = 0        # index of direction in DIRECTION
    
    while True:
        dx, dy = DIRECTION[step_direction]
        x, y = x + dx, y + dy
        total = 0
        for neighbor in NEIGHBORS:
            nx, ny = neighbor
            if (x+nx, y+ny) in spiral:
                total += spiral[(x+nx, y+ny)]
                
        print("X: {}, Y:{}, Total:{}".format(x,y,total))
        
        if total > n:
            return total
        spiral[(x,y)] = total
        nstep += 1
        if nstep == steps_in_row:
            nstep = 0
            step_direction = (step_direction + 1)% 4
            if second_direction:
                second_direction = False
                steps_in_row += 1
            else:
                second_direction = True
In [8]:
spiral_until_at_least(55)
X: 1, Y:0, Total:1
X: 1, Y:1, Total:2
X: 0, Y:1, Total:4
X: -1, Y:1, Total:5
X: -1, Y:0, Total:10
X: -1, Y:-1, Total:11
X: 0, Y:-1, Total:23
X: 1, Y:-1, Total:25
X: 2, Y:-1, Total:26
X: 2, Y:0, Total:54
X: 2, Y:1, Total:57
Out[8]:
57
In [9]:
spiral_until_at_least(289326)
X: 1, Y:0, Total:1
X: 1, Y:1, Total:2
X: 0, Y:1, Total:4
X: -1, Y:1, Total:5
X: -1, Y:0, Total:10
X: -1, Y:-1, Total:11
X: 0, Y:-1, Total:23
X: 1, Y:-1, Total:25
X: 2, Y:-1, Total:26
X: 2, Y:0, Total:54
X: 2, Y:1, Total:57
X: 2, Y:2, Total:59
X: 1, Y:2, Total:122
X: 0, Y:2, Total:133
X: -1, Y:2, Total:142
X: -2, Y:2, Total:147
X: -2, Y:1, Total:304
X: -2, Y:0, Total:330
X: -2, Y:-1, Total:351
X: -2, Y:-2, Total:362
X: -1, Y:-2, Total:747
X: 0, Y:-2, Total:806
X: 1, Y:-2, Total:880
X: 2, Y:-2, Total:931
X: 3, Y:-2, Total:957
X: 3, Y:-1, Total:1968
X: 3, Y:0, Total:2105
X: 3, Y:1, Total:2275
X: 3, Y:2, Total:2391
X: 3, Y:3, Total:2450
X: 2, Y:3, Total:5022
X: 1, Y:3, Total:5336
X: 0, Y:3, Total:5733
X: -1, Y:3, Total:6155
X: -2, Y:3, Total:6444
X: -3, Y:3, Total:6591
X: -3, Y:2, Total:13486
X: -3, Y:1, Total:14267
X: -3, Y:0, Total:15252
X: -3, Y:-1, Total:16295
X: -3, Y:-2, Total:17008
X: -3, Y:-3, Total:17370
X: -2, Y:-3, Total:35487
X: -1, Y:-3, Total:37402
X: 0, Y:-3, Total:39835
X: 1, Y:-3, Total:42452
X: 2, Y:-3, Total:45220
X: 3, Y:-3, Total:47108
X: 4, Y:-3, Total:48065
X: 4, Y:-2, Total:98098
X: 4, Y:-1, Total:103128
X: 4, Y:0, Total:109476
X: 4, Y:1, Total:116247
X: 4, Y:2, Total:123363
X: 4, Y:3, Total:128204
X: 4, Y:4, Total:130654
X: 3, Y:4, Total:266330
X: 2, Y:4, Total:279138
X: 1, Y:4, Total:295229
Out[9]:
295229

Mathematical Outerlude

The sequence in the part 2 grows really, really quickly. The sequence starts 1,1,2,4,5,10,11,23…
Many mathematicians (recreational, amateur, and professional alike) often delight in properties of sequences of integers. And sometimes they put them in Sloane’s Online Encyclopedia of Integer Sequences, the OEIS. Miraculously, the sequence from part 2 appears in the OEIS.
It’s OEIS A141481.

But I’ve never seen this sequence before.
I wonder: how quickly does it grow? This is one of the most fundamantal questions one can ask about a sequence.
Clearly it grows quickly — the entries are strictly increasing, and after each corner they roughly double (since the adjacent and diagonal are each there and roughly the same size).
But does this capture most of the growth?

In [10]:
spiral = {}
spiral[(0,0)] = 1

NEIGHBORS = [(1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1)]
DIRECTION = [(1,0), (0,1), (-1,0), (0,-1)] #Right Up Left Down

CORNERS = [1]

def spiral_until_at_least_print_corners(n):
    spiral = {}               # Spiral dictionary
    spiral[(0,0)] = 1
    x,y = 0,0
    steps_in_row = 1          # times spiral extends in same direction
    second_direction = False  # spiral extends in same direction twice: False if first leg, True if second
    nstep = 0                 # number of steps in current direction
    step_direction = 0        # index of direction in DIRECTION
    
    while True:
        dx, dy = DIRECTION[step_direction]
        x, y = x + dx, y + dy
        total = 0
        for neighbor in NEIGHBORS:
            nx, ny = neighbor
            if (x+nx, y+ny) in spiral:
                total += spiral[(x+nx, y+ny)]
                
        if total > n:
            return total
        spiral[(x,y)] = total
        nstep += 1
        if nstep == steps_in_row:
            print("X: {}, Y:{}, Total:{}".format(x,y,total))
            CORNERS.append(total)
            nstep = 0
            step_direction = (step_direction + 1)% 4
            if second_direction:
                second_direction = False
                steps_in_row += 1
            else:
                second_direction = True
In [11]:
spiral_until_at_least_print_corners(10**15)
X: 1, Y:0, Total:1
X: 1, Y:1, Total:2
X: -1, Y:1, Total:5
X: -1, Y:-1, Total:11
X: 2, Y:-1, Total:26
X: 2, Y:2, Total:59
X: -2, Y:2, Total:147
X: -2, Y:-2, Total:362
X: 3, Y:-2, Total:957
X: 3, Y:3, Total:2450
X: -3, Y:3, Total:6591
X: -3, Y:-3, Total:17370
X: 4, Y:-3, Total:48065
X: 4, Y:4, Total:130654
X: -4, Y:4, Total:369601
X: -4, Y:-4, Total:1026827
X: 5, Y:-4, Total:2957731
X: 5, Y:5, Total:8391037
X: -5, Y:5, Total:24612291
X: -5, Y:-5, Total:71138314
X: 6, Y:-5, Total:211906819
X: 6, Y:6, Total:622599690
X: -6, Y:6, Total:1881661363
X: -6, Y:-6, Total:5614313360
X: 7, Y:-6, Total:17197809473
X: 7, Y:7, Total:52035339395
X: -7, Y:7, Total:161377186945
X: -7, Y:-7, Total:494675470203
X: 8, Y:-7, Total:1552158495650
X: 8, Y:8, Total:4816175781069
X: -8, Y:8, Total:15277743850220
X: -8, Y:-8, Total:47947180112774
X: 9, Y:-8, Total:153672147749041
X: 9, Y:9, Total:487485542154934
Out[11]:
1009266205008841

In this version, I’ve added in a print statement at each corner, to see the growth. The sequence grows really, really quickly.

In [12]:
CORNERS
Out[12]:
[1,
 1,
 2,
 5,
 11,
 26,
 59,
 147,
 362,
 957,
 2450,
 6591,
 17370,
 48065,
 130654,
 369601,
 1026827,
 2957731,
 8391037,
 24612291,
 71138314,
 211906819,
 622599690,
 1881661363,
 5614313360,
 17197809473,
 52035339395,
 161377186945,
 494675470203,
 1552158495650,
 4816175781069,
 15277743850220,
 47947180112774,
 153672147749041,
 487485542154934]
In [13]:
for a, b in zip(CORNERS, CORNERS[1:]):
    print(b/a)
1.0
2.0
2.5
2.2
2.3636363636363638
2.269230769230769
2.4915254237288136
2.4625850340136055
2.643646408839779
2.560083594566353
2.690204081632653
2.635411925352754
2.7671272308578008
2.7182773327785292
2.8288533072083517
2.7782040633006946
2.8804569805819287
2.8369844992664985
2.933164399108239
2.890357260931134
2.978800130123972
2.9380823747819083
3.022265178127538
2.9837001866525545
3.0632079775824983
3.025695771120955
3.101299786285366
3.065337050221315
3.137730874371112
3.102889166645396
3.1721732230522837
3.1383678495227265
3.2050299389369084
3.1722439576431065

It appears that the size of the $(n+1)$st corner is roughly $\lambda$ times the size of the $n$th corner, where $\lambda \geq 2.5$. It actually appears like $\lambda$ grows slowly with $n$ (which makes some sense, as the lengths between each corner is increasing with each layer of the spiral). It would be interesting if one could actually show that this growth rate appears to be consistent, and if one could grasp how $\lambda$ behaves with $n$. But I’m not sure how to do that.

This entry was posted in Expository, Programming, Python and tagged , , . Bookmark the permalink.

Leave a Reply