DEV Community

Cover image for Hex Ed
Robert Mion
Robert Mion

Posted on

Hex Ed

Advent of Code 2017 Day 11

Part 1

  1. Infinite hexagonal grid: The prequel!
  2. 90 degree rotation
  3. Summing each move
  4. 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  \
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

That might be depicted as:

  nw   |   ne
 ----/   \----
 e  |  *  |  w
 ----\   /----
  sw   |   se
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

...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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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!
Enter fullscreen mode Exit fullscreen mode

Is there a formula here?

Yes, I believe so.

It can be found in the last example:

[-1 ,-5 ]
Enter fullscreen mode Exit fullscreen mode

My formula:

  1. The absolute value of the first number
  2. 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
Enter fullscreen mode Exit fullscreen mode

How about for this?

[ 2 ,-2 ]

 2
+0 (2 - 2 / 2)
--
 2
Enter fullscreen mode Exit fullscreen mode

Testing on my puzzle input:

[ -267, -1353 ]

 267
+543 (1353 - 267 / 2)
----
 810 CORRECT ANSWER!
Enter fullscreen mode Exit fullscreen mode

This animation shows my whole algorithm working on another simple example:
Algorithm for Part 1

Part 2

  1. Twist: find the max
  2. 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
Enter fullscreen mode Exit fullscreen mode

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!
Enter fullscreen mode Exit fullscreen mode

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)