Advent of Code 2016 Day 18
Part 1
- Seems easy enough...by now
- Visualizing the rules
- Getting from relative coordinates to
trap
orsafe
- Creating the initial state of rows
- Counting the safe tiles
- Testing my algorithm
Seems easy enough...by now
- Reveal
N
number of rows in the grid - Using specific adjacent tiles
- And a set of rules
I got this!
Visualizing the rules
Given...
ABC
1
1
is a trap when:
ABC = T--
ABC = TT-
ABC = -TT
ABC = --T
1
is therefore safe when:
ABC = ---
ABC = -T-
ABC = T-T
ABC = TTT
Getting from relative coordinates to trap
or safe
This animation outlines my planned algorithm visually:
This pseudocode better describes my planned algorithm and incorporates a modified dictionary from the one hinted at in the animation above:
Create an object with eight keys
Each key is a 3-character representation of the rule to match, and the value is the resulting tile state
Set each tile as safe or trap based on the character returned from the following operations:
Create a list of three relative coordinates:
1. [-1,-1]
2. [-1, 0]
3. [-1, 1]
Update each coordinate depending on the value of the cell that distance from the current tile:
If the value is safe or the cell is outside the bounds of the grid
Use 0
Else, it's a trap
Use 1
Concatenate all three numbers together to form a 3-character string
Return the character associated with the 3-character string in the eight-key object
This JavaScript is the actual working algorithm:
rules = {
'000': '.',
'010': '.',
'101': '.',
'111': '.',
'100': '^',
'110': '^',
'011': '^',
'001': '^'
}
// For each col in each row...
tiles[row][col] = rules[
[[-1,-1],[-1,0],[-1,1]]
.map(el => {
let tile = tiles[row + el[0]][col + el[1]]
switch (typeof tile) {
case "undefined":
return 0
break;
case "string":
return tile == "." ? 0 : 1
break;
}
}
)
.join('')
]
Creating the initial state of rows
The above JavaScript references an array of arrays called tiles
.
What should that array look like before iterating through all cells but those in the first row?
For the input of ..^^.
with 3
rows:
[
['.','.','^','^','.'],
[ , , , , ]
[ , , , , ]
]
How might I construct that nested array?
let tiles = new Array(3)
.fill(null)
.map(
el => new Array(input.length).fill(null)
)
tiles[0] = input.split('')
- All but the last line create a nested array with
null
as each cell's value - The last line replaces the first array with one generated from each character in the input string
Counting the safe tiles
reduce()
to the rescue, twice!
- The inner one counts up each safe tile in a row
- The outer one tallies each row's count
tiles.reduce(
(sum1, row) => sum1 += row.reduce(
(sum2, cell) => sum2 += cell == '.' ? 1 : 0, 0)
, 0)
Testing my algorithm
I call my function like this:
part1(input, rows)
-
part1('..^^.', 3)
: 6 - `part1('.^^.^.^^^^', 10): 38
And with my puzzle input for 40 rows: 1926
That is the correct answer!
Part 2
And with my puzzle input for 400K rows:
...
...
Nearly 20M!
That is the correct answer again!
Admittedly, it took over 10 seconds to run.
I did it!!
- I solved both parts!
- At this point, I feel very confident working with simpler adjacent cell-themed puzzles like this one!
- As long as the performance test in Part 2 isn't absurd!
Top comments (0)