Advent of Code – Day 3

I struggled to code today’s problem – I saw it more as a problem I’d set students in my maths classroom and solved it much like I would have done that.

Part 1:

Each square on the grid is allocated in a spiral pattern starting at a location marked 1 and then counting up while spiraling outward. For example, the first few squares are allocated like this:

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

While this is very space-efficient (no squares are skipped), requested data must be carried back to square 1 (the location of the only access port for this memory system) by programs that can only move up, down, left, or right. They always take the shortest path: the Manhattan Distance between the location of the data and square 1.

from math import sqrt
target = 289326

# in an nxn spiral - bottom right is the largest outside value 
# and is equal to n squared
print(sqrt(target)) # 537.890...
# this must be a 538x538 square

n = 538
bottom_left = n*n - n + 1
print(bottom_left < target) # true

# target is on the bottom row of a 538 x 538 grid
middle = (n - 1)/2
print(target - bottom_left - middle)

Having encountered a problem similar to this in the past, I knew that the bottom left corner of the spiral in an nxn square was n-squared.  So, I square rooted the target to find out how big the spiral was.  Knowing the spiral was 538×538, I needed to know which side of the spiral it was on.  I checked to see if the bottom left was smaller than the target, it was – so now I know that the target is along the bottom.  But, where?

I worked out the middle of a row and checked if the sum of the bottom_left and middle was less than the target – it was.  I worked out how far along from the middle it was – 151.  I know it takes 151 to travel along the bottom to the middle, now I just need to add on another middle to get to the center vertically.

I did attempt to write a function to do this but it got jumbled somewhere in the middle.  It’s over on my GitHub if you care.

Part 2

in the same allocation order as shown above, they store the sum of the values in all adjacent squares, including diagonals.

So, the first few squares’ values are chosen as follows:

  • Square 1 starts with the value 1.
  • Square 2 has only one adjacent filled square (with value 1), so it also stores 1.
  • Square 3 has both of the above squares as neighbors and stores the sum of their values, 2.
  • Square 4 has all three of the aforementioned squares as neighbors and stores the sum of their values, 4.
  • Square 5 only has the first and fourth squares as neighbors, so it gets the value 5.

Once a square is written, its value does not change. Therefore, the first few squares would receive the following values:

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 written that is larger than your puzzle input?

I puzzled with this for a bit – I thought there was probably an elegant recursion tactic to be able to solve it but I wasn’t seeing it.  I decided to brute force it with a spreadsheet.


Again, there are definitely better ways to do this but the numbers were small enough that I didn’t think it was much of a hassle.  This is a timed thing and so I went with the solution that would get me there quickest.


My background is maths and spreadsheets and teaching problem solving – that’s going to be helpful sometimes but it may also make it harder for me to spot a programming solution because I have a solution in my head already.  Saying that, the right tool for the right job, eh?

Leave a Reply