Step Counter
Tags: adventofcode, algorithms, javascript, programming
Published: 2024-03-06 17:54:53

## [Advent of Code 2023 Day 21](https://adventofcode.com/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:
```js
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`

```js
let start = [(grid.length - 1) / 2, (grid.length - 1) / 2]
```

Prepare grid:
```js
grid[start[0]][start[1]] = '.'
```

#### That same list of adjacent tiles
Remember this?
```js
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:
```js
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:
```js
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!