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
- Codifying the equation for finding the
power level
of a fuel cell - Generating the 300x300 grid and populating each
power level
- 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
- I should have seen this coming
- My algorithm for generating the set of relative coordinates
- Fixing my mistake: right code in the wrong place
- Seeing the results and realizing it may never finish
- 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.
Top comments (0)