Advent of Code 2023 Day 21
Part 1
I hope it's as easy as I think
- 64 steps
- Even number steps
- Any tile that can be reached in 64 or fewer steps
- And an amount of steps that is even
- Is a valid tile
I plan to write a recursive function that:
- Continually walks away from the starting point
- Catalogues each tile visited
- Adds tiles visited on every other step to a list of valid tiles
- Avoids proceeding if a tile has been visited
This has worked for similar challenges.
I expect it to work here.
But I've been surprised before!
Here I go!
Make grid; Find start; Prepare grid;
Make grid:
input.split('\n').map(line => line.split(''))
Find start:
- Luckily, the start is dead-center of a grid with equal and odd length dimensions
- So, the start is at X and Y of
(length - 1) / 2
let start = [(grid.length - 1) / 2, (grid.length - 1) / 2]
Prepare grid:
grid[start[0]][start[1]] = '.'
That same list of adjacent tiles
Remember this?
const adjacents = [[-1,0],[0,1],[1,0],[0,-1]]
I'll use that in my recursive function to check all four possible next moves at the current tile.
Writing my recursive function
Here it is:
function stepper(current, steps) {
if (steps > 64) return false;
visited.add(current.join(','))
if (steps % 2 == 0) {
valid.add(current.join(','))
}
adjacents.forEach(coord => {
let [row, col] = [current[0] + coord[0], current[1] + coord[1]]
if (row < 0 || row == grid.length || col < 0 || col == grid[0].length) {
return false;
} else {
switch (grid[row][col]) {
case '#':
visited.add(row + ',' + col)
return;
case '.':
return stepper([row,col], steps + 1)
}
}
})
}
It runs. But it doesn't finish when run on my example input.
For the same reason as a few days ago: too many rabbit holes to dig and climb out of.
So, I need to write a non-recursive function.
One that visits all the tiles within a 64 step radius.
And just accumulates tiles to proceed from along it's journey.
Writing my non-recursive function
"This will be straightforward", I thought.
"I did this recently, so it's just recall", I thought.
"Should only take a few minutes to code up", I thought.
Fast-forward an hour.
"Why is my list of cells to visit getting higher than the amount of cells in my grid?", I thought.
"Why are there multiple occurrences of the same cell with the same step count?", I thought.
"Why isn't this working?", I thought.
Fast-forward a half hour.
I figured out my error.
It was simple:
In my case
for the next cell being a .
, I first check whether that cell has been visited. If it hasn't, I add it to my list of cells to visit.
What I was missing was adding it to the list of visited cells, since I know I'm eventually going to visit it.
Here's my entire program in JavaScript:
let grid = input.split('\n').map(line => line.split(''))
let start = [(grid.length - 1) / 2, (grid.length - 1) / 2]
grid[start[0]][start[1]] = '.'
const adjacents = [[-1,0],[0,1],[1,0],[0,-1]]
let visited = new Set()
visited.add(start.join(','))
let valid = new Set()
let todo = [[start, 0]]
while (todo.length > 0) {
let [xy, steps] = todo.shift()
let [row, col] = xy
if (steps % 2 == 0 && steps <= 64) {
valid.add(xy.join(','))
}
adjacents.forEach(coord => {
let [r, c] = [row + coord[0], col + coord[1]]
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
return false;
} else {
switch (grid[r][c]) {
case '#':
visited.add(r + ',' + c)
break;
case '.':
if (!visited.has([r,c].join(','))) {
visited.add(r + ',' + c)
todo.push([[r,c], steps + 1])
}
break;
}
}
})
}
Running my program with fingers crossed
It generates 42
on the example input.
There are 80 .
s in the example input, not including the S
.
And since the even step rule is in effect, that feels like the correct answer: half the total .
s.
Running it on my puzzle input only took a few seconds to complete.
It generated a number just under 4k.
It is the correct answer!
Woohoo!!!
That wasn't as easy as I'd hoped. Mostly due to my ignorance.
But I got there.
Part 2
To infinity, and...no thanks.
I love the twist:
- Infinite repeating grid
- A step count in the tens of millions
I know for sure I couldn't solve this by simulating single-cell movements.
I have a hunch there's a neat formula that correlates the area of the circle surrounding the starting point with the number of possible valid steps.
Except, in my input I see instances of this pattern:
.#.
#.#
.#.
That middle cell is unreachable, and should never be counted in such a formula.
So, now I'm really at a loss for how I'd solve this.
Sadly, I know I won't be earning another gold star today.
I'll gladly take my one gold star with me to the next challenge.
And hope that I can solve at least two more Part 1's before this year is over.
I have four more chances!
Top comments (0)