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.
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
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(middle) print(bottom_left+middle<target) print(target - bottom_left - middle) print(151+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.
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:
1starts with the value
2has only one adjacent filled square (with value
1), so it also stores
3has both of the above squares as neighbors and stores the sum of their values,
4has all three of the aforementioned squares as neighbors and stores the sum of their values,
5only has the first and fourth squares as neighbors, so it gets the value
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?