My solution for star 2 can be found here, but without the four pages of diagramming I did to get there, itβs largely indecipherable, so hereβs some explanation on the mental process.
Star 1
The spirals of the grid can be divided into βlayersβ:
βββββββββββββββββββββββ
β 17 16 15 14 13 β layer 2
β βββββββββββββ β
β 18 β 5 4 3 β 12 β layer 1
β β βββββ β β
β 19 β 6 β 1 β 2 β 11 β layer 0
β β βββββ β β
β 20 β 7 8 9 β 10 β layer 1
β βββββββββββββ β
β 21 22 23 24 25 β layer 2
βββββββββββββββββββββββ
The lower-right corner of each layer is the square of an odd number, so each layer consists of the range of boxes ((2lβββ1)^2, (2l + 1)^2], where l is the layer number. Given the nth box, we have n <= (2l + 1)^2, or l >= (sqrt(x)βββ1)/2; the layer is the smallest of these values, so l = ceiling((sqrt(x)βββ1)/2).
l is also the distance from the centre of the spiral to the middle box of any edge of a layer (e.g. boxes 11, 15, 19, and 23 are 2 away from box 1). The Manhattan distance of any box is then the layer number + its distance from the middle box. We start by finding d, the distance of any given box from the corner box to its left.
βββββββββββββββββββββββ
β 17 β16 15 14 13 β
β ββββββββββββββββββ
β 18 β 5 β 4 3 β 12 β
β β βββββββββ β
β 19 β 6 β 1 β 2 β 11 β
β βββββββββ β β
β 20 β 7 8 β 9 β 10 β
ββββββββββββββββββ β
β 21 22 23 24 β 25 β
βββββββββββββββββββββββ
0 1 2 3 = d
The possible distances range from 0 (the corner) to 2l-1 (box before the next corner), giving d = (nβββ1) % 2l . Finally, the distance from the middle box is given by |dβββl| , so the final Manhattan distance of any box is then
D = |d β l| + l
= |((n β 1) % 2l) β l| + l
where
l = ceiling((sqrt(n) - 1)/2)
For the puzzle input 368078, this yields 371.
Star 2
The grid of values can also be divided into layers:
βββββββββββββββ
β 5 4 2 β The initial grid with which we will calculate
β βββββ β the values of subsequent layers.
β 10 β 1 β 1 β
β βββββ β
β 11 23 25 β
βββββββββββββββ
The first task is to divide the boxes into different types depending on which neighbouring boxes they need to access. The following diagrammes use β for boxes that need to be retrieved, x for boxes that donβt yet exist, and n for the current box. In the notation below, s(n) will retrieve the value of the nth box, while d(n) will retrieve the number of the box directly below (layer-wise) the nth box, so for instance s(d(23)) retrieves the value of box 8, which is 23. Iβve found seven different cases, six of which are distinct:
β β x β "Normal" (all others, including bottom-right pre-corner)
β β n β s(n) = s(n-1) + s(d(n)-1) + s(d(n)) + s(d(n)+1)
β β β β
βββββββ
x n β "Corner" (top-right, top-left, bottom-left)
βββ β s(n) = s(n-1) + s(d(n-1))
β β β β
β β β β
βββ β "Last corner" (bottom-right)
β n β s(n) = s(n-1) + s(d(n-1)) + s(d(n-1) + 1)
βββββββ
βββββββ
x x β "Pre-corner" (top-right, top-left, bottom-left)
βββ β s(n) = s(n-1) + s(d(n)) + s(d(n) - 1)
β β n β
β β β β
ββββββββββ
x n β β "Post-corner" (top-right, top-left, bottom-left)
ββββββ β s(n) = s(n-1) + s(n-2) + s(d(n)) + s(d(n) + 1)
β β β β β
β β x β
β β n β "First post-corner" (bottom-right)
βββ β s(n) = s(n-1) + s(d(n-1))
x x β
βββββββ
β β x β
β β n β "First post-post-corner" (bottom-right)
β β β β s(n) = s(n-1) + s(n-2) + s(d(n)) + s(d(n) + 1)
βββ β (Note that this equation is the same as post-corner)
x x β
βββββββ
Any box can be sorted into one of these categories using its level number. Corners are given by (2l+1)^2βββ2lm where m is one of {0..3}, and all other boxes can be determined from this.
The function s(n) can be implemented as retrieval from a simple Vector Int or Map Int Int; the function d(n) is a bit tricker. First, given a way to find the difference between the current layer and the previous layer, we can write:
d(n) = n - difference
Along each edge of the layer, the difference between two layers is constant; as you turn the corner, you add 2 to the difference. Assigning each edge a value from 0 to 3 and going anticlockwise, we have:
d(n) = n - (initialDifference + 2 * edge)
The initial difference can be found using two successive odd squares, plus a constant.
βββββββββββββββββββββββ
β 17 16 15 14 13 β
β βββββββββββββ β
β 18 β 5 4 3 β 12 β
β β βββββ β β
β 19 β 6 β 1 β 2 β 11 β 11 - 2 = 9
β β βββββ β β
β 20 β 7 8 9 β 10 β
β βββββββββββββ β
β 21 22 23 24 25 β
βββββββββββββββββββββββ
We will use the above example as a guide. Given a layer l, the lower-bound odd square is given by (2l-1)^2, and the first post-post-corner is given by (2l-1)^2 + 2; in the example, this is 9 and 11, respectively. The odd square before that is (2l-3)^2, and the first post-corner of that layer is (2l-3)^2 + 1, here being 1 and 2. The difference is then
initialDifference = (2l-1)^2 - (21-3)^2 + 1
= 4l^2 - 4l + 1 - 4l^2 + 12l - 9 + 1
= 8l - 7
The length of an edge is given by 2l + 1, and the circumference is given by (2l + 1) * 4 - 4 = 8l. The edge number is then given by how far along the circumference n is (or the βarclengthβ) integer-divided by one-fourth of the circumference, or
edge = arclength `div` 2l
= (n - (2l-1)^2) `div` 2l
Putting it all together, we have:
d(n) = n - 8l + 7 - 2 * ((n - (2l-1)^2) `div` 2l)
where
l = ceiling((sqrt(n) - 1)/2)
Then starting with the initial nine boxes, we can calculate successive boxesβ values from box 10 onwards until the value is greater than 368078, yielding the answer 369601 at box 65.
Star 2: An Alternate Method
In the above solution, I unwrapped the spiral as a one-dimensional sequence with its index being the only indication of how it relates to other elements. Instead of coming up with these complex mathematical relationships between a box and its neighbours, I could have used a two-dimensional grid with Vector (Vector Int) or more likely Map (Int, Int) Int and starting at (0, 0). Then obtaining the neighbouring boxes becomes easy, but travelling along the spiral becomes hard, as you have to keep track of how far along youβve been and when to turn.