Advent of Code 2017 Day 11
Part 1
- Infinite hexagonal grid: The prequel!
- 90 degree rotation
- Summing each move
- Calculating the minimum possible steps
Infinite hexagonal grid: The prequel!
- My prior - and first - encounter with a hexagonal grid was 2020 Day 24: Lobby Layout
- I solved both parts of that puzzle, so my confidence is strong today...especially since this is Day 11, so perhaps a bit easier to solve than Day 24
90 degree rotation
The diagram provided in this puzzle is:
\ n /
nw +--+ ne
/ \
-+ +-
\ /
sw +--+ se
/ s \
That orientation poses a problem if I want to represent each tile using an array...like I did to solve Lobby Layout.
In that puzzle, the neighboring tiles were in these six directions:
east, southeast, southwest, west, northwest, and northeast
That might be depicted as:
nw | ne
----/ \----
e | * | w
----\ /----
sw | se
That orientation works great!
I can use a 2D array as a data structure and represent each relative coordinate like this:
[-1,-1] | [-1, 1]
----/ \----
[ 0,-2] | * | [ 0, 2]
----\ /----
[ 1,-1] | [ 1, 1]
Thankfully, this puzzle only cares about the number of steps from an origin to a destination.
Therefore, I can easily rotate the diagram 90 degrees clockwise:
sw | nw
----/ \----
s | * | n
----\ /----
se | ne
...and use this dictionary as the relative coordinates:
'sw': [-1,-1]
'se': [ 1,-1]
'nw': [-1, 1]
'ne': [ 1, 1]
'n': [ 0, 2]
's': [ 0,-2]
Now, I'm ready to process each move!
Summing each move
Split the input at each comma character into and array of strings
For each string, accumulate a 2-element array, starting with both elements as 0
Update the first element to be the sum of itself and the first number in the 2-element array associated with the string that matches in the dictionary of relative coordinates
Update the second element to be the sum of itself and the second number in the 2-element array associated with the string that matches in the dictionary of relative coordinates
My algorithm accumulates the following arrays for the respective inputs:
ne,ne,ne = [3,3]
ne,ne,sw,sw = [0,0]
ne,ne,s,s = [2,-2]
se,sw,se,sw,sw = [-1,-5]
Calculating the minimum possible steps
Somehow, I need to arrive at the following step counts from the respective 2-element arrays:
[3,3] = 3
[0,0] = 0
[2,-2] = 2
[-1,-5] = 3
Doing it manually:
[ 3 , 3 ]
-3 -3 = 3 steps (ne)
[ 0 , 0 ] = done!
[ 0 , 0 ] = done!
[ 2 ,-2 ]
-2 +2 = 2 steps (se)
[ 0 , 0 ] = done!
[-1 ,-5 ]
+1 +1 = 1 step (sw)
[ 0 ,-4 ]
+2 = 1 step (s)
[ 0 ,-2 ]
+2 = 1 step (s)
[ 0 , 0 ] = done!
Is there a formula here?
Yes, I believe so.
It can be found in the last example:
[-1 ,-5 ]
My formula:
- The absolute value of the first number
- Plus half of the absolute value of the second number after bringing it closer to zero by an amount equal to the absolute value of the first number
Does it work?
[-1 ,-5 ]
1
+2 (5 - 1 / 2)
--
3
How about for this?
[ 2 ,-2 ]
2
+0 (2 - 2 / 2)
--
2
Testing on my puzzle input:
[ -267, -1353 ]
267
+543 (1353 - 267 / 2)
----
810 CORRECT ANSWER!
This animation shows my whole algorithm working on another simple example:
Part 2
- Twist: find the max
- Troubleshooting, testing, terrific!
Twist: find the max
This should only require a few modifications to my Part 1 algorithm:
Split the input at each comma character into and array of strings
For each string, accumulate three items:
1. A 2-element array, starting with both elements as 0
2. Another 2-element array, starting with both elements as 0
3. A number, starting as 0
Update the first element in the first item to be the sum of itself and the first number in the 2-element array associated with the string that matches in the dictionary of relative coordinates
Update the second element in the first item to be the sum of itself and the second number in the 2-element array associated with the string that matches in the dictionary of relative coordinates
If the sum of the absolute values of both updated elements is greater than the third item
Store a copy of the first item in the second item
Update the third item to equal the greater sum
Troubleshooting, testing, terrific!
- I originally wasn't tracking the third item as an accumulating value
- Instead, I was comparing the new sum to the sum of the most recent values in the first item
- This resulted in the second item almost always storing the values from the previous turn: not what I wanted
After adding the third item and updating it appropriately, my algorithm output this array as the second item:
[ -927, -2207 ]
927
+640 (2207 - 927 / 2)
----
1567 CORRECT ANSWER!
I did it!!
- I solved both parts!
- In under 20 lines of code!
- With a single
reduce()! - First, manually by using arithmetic on the two numbers...then, by finding and programming the formula!
- I made a short GIF that animates my algorithm and formula!
Top comments (0)