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;
  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!