Robert Mion

Posted on

# Step Counter

## 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;
if (steps % 2 == 0) {
}
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()
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) {
}
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!