Chronal Charge

Advent of Code 2018 Day 11

Task: Solve for X where...

Part 1

X = the X,Y coordinate of the top-left fuel cell of the 3x3 square with the largest total power

Part 2

X = the X,Y,size identifier of the top-left fuel cell of the 
 square with the largest total power

Example input

18

It represents:

• A grid serial number
• Used as part of a formula to determine a fuel cell's power level

Part 1

1. Codifying the equation for finding the power level of a fuel cell
2. Generating the 300x300 grid and populating each power level
3. Finding the largest total power

Codifying the equation for finding the power level of a fuel cell

For cell at X,Y in a 0-indexed multi-dimensional array with some grid serial number as serial:

// Find the fuel cell's rack ID
// which is its X coordinate plus 10
rackID = X(+1) + 10

// Begin with a power level of 
// the rack ID times the Y coordinate
power = rackID * Y(+1)

// Increase the power level by 
// the value of the grid serial number
power += serial

// Set the power level to 
// itself multiplied by the rack ID
power *= rackID

// Keep only the hundreds digit of the power level
power = String(power).padStart(3,'0').slice(-3)[0]

// Subtract 5 from the power level
power -= 5

Generating the 300x300 grid and populating each power level

Create an array of length 300
  Where each item is an array of length 300
    Where each item is correct power level integer

Finding the largest total power

Set largest to -Infinity
For each row, starting from the third
  For each column, starting from the third
    Calculate the sum of all cells in the 3x3 grid where the current cell is the bottom-right corner
    If the sum is greater than largest, set largest as a 2-element array:
      1. The sum
      2. The X,Y coordinate of this cell
Return the second item in largest: the X,Y coordinate

The results:

• It generated the correct answer for the first example grid serial number!
• And for the second!
• And for my puzzle input!

Part 2

1. I should have seen this coming
2. My algorithm for generating the set of relative coordinates
3. Fixing my mistake: right code in the wrong place
4. Seeing the results and realizing it may never finish
5. Fingers crossed this is the correct answer, like in the examples

I should have seen this coming

• When Part 1 defines some area and asks the solver to find a small subset
• Part 2 usually increases the size of one of the two: the larger area, or the size of the subset (to include up to the full area)
• Thankfully, this puzzle features a relatively small area, and keeps the puzzle solution constrained to that area
• I may be able to solve this part, too!

My algorithm for generating the set of relative coordinates

• In Part 1, I pre-defined the list of relative coordinates to use in my nested for loop to calculate the sum of each 3x3 square
• In Part 2, I'll have to dynamically generate that list based on the current iteration's square size: 1-300
• I need to critically analyze aspects of my algorithm in order to discover an equation for writing a more flexible one

These are the Y,X coordinates for my 3x3 square - relative to the bottom-right corner:

[
 [[-2,-2],[-2,-1],[-2,0]],
 [[-1,-2],[-1,-1],[-1,0]],
 [[ 0,-2],[ 0,-1],[ 0,0]],
]

• An array of length 3
• Each nested array is of length 3
• Each Y coordinate starts at -2 and increments by one up to 0
• The X coordinate is the same in each column, starts at -2 and increments by one up to 0 from left-to-right

These are the indices of nested array values:

[
 [[ 0, 0],[ 0, 1],[ 0,2]],
 [[ 1, 0],[ 1, 1],[ 1,2]],
 [[ 2, 0],[ 2, 1],[ 2,2]],
]

• Every value is the difference of the index and 2
• 2 is the length of the arrays, minus 1

Thus, my winning equation is to set each pair of values like this:

[row - (array.length - 1), col - (array.length - 1)]

• Where array.length is 1-300 depending on the size of the square
• row is the index of the first-level array
• col is the index of the nested array

Testing it on squares of size 1-4:

1
[ [ 0, 0 ] ]

2
[ [ -1, -1 ], [ -1, 0 ], [ 0, -1 ], [ 0, 0 ] ]

3
[
  [ -2, -2 ], [ -2, -1 ],
  [ -2, 0 ],  [ -1, -2 ],
  [ -1, -1 ], [ -1, 0 ],
  [ 0, -2 ],  [ 0, -1 ],
  [ 0, 0 ]
]

4
[
  [ -3, -3 ], [ -3, -2 ],
  [ -3, -1 ], [ -3, 0 ],
  [ -2, -3 ], [ -2, -2 ],
  [ -2, -1 ], [ -2, 0 ],
  [ -1, -3 ], [ -1, -2 ],
  [ -1, -1 ], [ -1, 0 ],
  [ 0, -3 ],  [ 0, -2 ],
  [ 0, -1 ],  [ 0, 0 ]
]

It seems like it works as expected!

Now it's time to duplicate Part 1's algorithm and insert this code where appropriate.

Fixing my mistake: right code in the wrong place

• Duplicate Part 1's algorithm: check
• Add a third, outermost for loop that goes from 0 to 299
• Insert this new relative-coordinate-generating algorithm inside the innermost for loop
• Run....
• .......
• .......
• Stop
• Add a print statement to see the 0-299 count up
• Run....
• See it go increasingly slowly from 0-9
• Stop

What's happening?

For each number 0 thru 299
  For each row, 0 thru 299
    For each column, 0 thru 299
      Generate the list of relative coordinates
      Calculate the sum
      Update the largest total power tracker
Return the X,Y,size value from the tracker

Yikes!

I'm generating the list of relative coordinates at every check of the next bottom-right fuel cell!

The algorithm needs to work like this, instead:

For each number 0 thru 299
  Generate the list of relative coordinates
  For each row, 0 thru 299
    For each column, 0 thru 299
      Calculate the sum
      Update the largest total power tracker
Return the X,Y,size value from the tracker

Seeing the results and realizing it may never finish

This animation shows my logged statements for grid serial number 18:

• That would take hours to reach the square size 300
• Luckily, it doesn't have to run long
• Because the correct answer is the square of size 16

The correct answer is using an even smaller square for grid serial number 42: 12x12

Maybe mine will be similar? Let's run it and see!

I let it run a bit longer.

The largest total power never changed.

Fingers crossed this is the correct answer, like in the examples

• Copy
• Paste
• Submit

Second gold star!!

I did it!!!

• I solved both parts!
• I wrote an algorithm that dynamically generates a flattened list of relative coordinates to any given cell in a 2D array!

My Part 2 algorithm may never finish.

But I just needed the correct answer from it.

And that's exactly what I got.