DEV Community

Robert Mion
Robert Mion

Posted on

RAM Run

#adventofcode #algorithms #javascript #programming

Advent of Code 2024 Day 18

Part 1

Another variation of smallest possible answer

A few of the last several puzzles required finding the smallest valid answer.

One recent puzzle felt nearly identical to this one in that I had to explore every path within a maze from start to finish in order to identify the shortest path.

I don't love these puzzle types because I haven't learned how to re-create a proper shortest-path algorithm, commonly referred to as Djikstra's algorithm or an A* algorithm, I believe.

Instead, when I attempt them, I leverage the skills I have: recursion, novice memoization, and brute force

Sadly, most of these puzzle variations show up after Day 12, where Part 2 is usually a test of identifying some pattern in the data to jump straight to the answer, or of building an algorithm that can quickly eliminate billions or trillions of incorrect paths.

I say all of that only to admit once again:

  • I'll be proud to come away with one gold star today
  • And I won't be mad if I come away with zero

Process part of the input and create the grid

The input is a list of X,Y coordinates in a 70x70 grid.

Except the example grid is 6x6.

Making the grid is simple:

function makeGrid(width, height) {
  return new Array(height + 1)
    .fill(0)
    .map(
      el => new Array(width + 1).fill('.')
    )
}
Enter fullscreen mode Exit fullscreen mode

Calling my function looks like:

let grid = makeGrid(6,6)
Enter fullscreen mode Exit fullscreen mode

And seeing it as a grid looks like:

console.log(grid.map(line => line.join('')).join('\n'))
Enter fullscreen mode Exit fullscreen mode

Viola!

.......
.......
.......
.......
.......
.......
.......
Enter fullscreen mode Exit fullscreen mode

Now to generate the list of coordinates from the input:

let coords = input.split('\n').map(coord => coord.split(',').map(Number))
Enter fullscreen mode Exit fullscreen mode

An explanation:

  • Split the text at each new line
  • Split each coordinate string at the comma
  • Convert each string to a number

Lastly, changing only up to a certain amount of cells to corrupted:

function updateGrid(amt) {
  coords.slice(0, amt).forEach(coord => {
    grid[coord[1]][coord[0]] = '#'
  })
}
Enter fullscreen mode Exit fullscreen mode

When I call it with 12:

updateGrid(12)
Enter fullscreen mode Exit fullscreen mode

I correctly see this:

...#...
..#..#.
....#..
...#..#
..#..#.
.#..#..
#.#....
Enter fullscreen mode Exit fullscreen mode

Well, that was fun and easy!

Next, I'll employ my usual strategy of adding a border around the grid to prevent the need for overly-complex conditions in my main loop.

Pad the grid with a 1-cell-wide border

I need to add a cell around each bordering cell in the grid.

The way I've done this in past challenges is with the following function:

function addGridBorder() {
  grid = grid.map(row => ['#', ...row, '#'])
  grid = [
    new Array(size + 2).fill('#'),
    ...grid,
    new Array(size + 2).fill('#'),
  ]
}
Enter fullscreen mode Exit fullscreen mode

What it does:

  • Adds a cell to each existing row, at the beginning and end
  • Adds two rows to the grid, at the beginning and end, containing the new amount of cells

And with that, my example grid now looks like this:

#########
#...#...#
#..#..#.#
#....#..#
#...#..##
#..#..#.#
#.#..#..#
##.#....#
#########
Enter fullscreen mode Exit fullscreen mode

The only change I have to pay attention to is my new start and end coordinates, since they will now be one off for both X and Y coordinates:

let start = [1, 1]
let end = [size, size]
Enter fullscreen mode Exit fullscreen mode

...where size is the width/height of the grid when counting from 0 (e.g. size 7 equates to a grid from 0-6 like in the example)

Now for the super hard part...

A program that explores all possible paths and hopefully terminates eventually

The beginnings of a recursive function

If I'm charting a path through a grid, I'm gonna use recursion.

function walkGrid(n) {
  if () {
  } else {
    walkGrid(n - 1)
  }
}
Enter fullscreen mode Exit fullscreen mode

The conditions will be more robust than n, of course.

What will I need to keep track of?

  • The current cell in the grid
  • The cells previously visited (doubling as the number of steps taken)

And what should the base cases be?

  • Adjacent cells are dead ends or already visited
  • Number of steps taken is greater than the current winner for least number of steps

I'll build each of these parts of the algorithm in the next few sections.

Which cells came before?

Throughout the recursive function, I need to keep track of which cells have been visited.

Only by doing this can I arrive at a base case where all four of the next cells are one of either:

  • A dead end
  • A backstep

So, I need a list that can store a unique set of points:

let visited = new Set()
Enter fullscreen mode Exit fullscreen mode

And I won't add the list of X,Y coordinates to it. First, I'll convert to a string so it is seen as unique in JavaScript's brain:

visited.add([X,Y].join(','))
Enter fullscreen mode Exit fullscreen mode
Which cells could come next?

First, the usual list of four nearby cell relative coordinates:

let nearby = [
  [0,1],
  [1,0],
  [0,-1],
  [-1,0]
]
Enter fullscreen mode Exit fullscreen mode

Those represent each possible next move ($) for any given originating cell (*):

.$.
$*$
.$.
Enter fullscreen mode Exit fullscreen mode
What will the function invocation look like?

The first time I call walkGrid(), what might the call look like?

let start = [1,1]
let visited = new Set()
walkGrid(start, visited)
Enter fullscreen mode Exit fullscreen mode
Is that enough arguments? Only one way to find out!

Time for some pseudocode!

function walkGrid(start, visited) {
  if ( /* arrived at bottom-right corner of grid */ ) {
    // how many cells were visited?
       // compare to current winner and update if appropriate
  } else {
    // check all adjacent cells
    if ( /* no adjacent cells can come next */ ) {
      // exit this iteration
    } else {
      // call function again for each possible next move
      nearby.forEach(walkGrid(next, visited))
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

That only took a few minutes to think through.

It feels like it accounts for the main things, but I may very well have missed something.

I'm ready to flesh it out into actual code.

A first attempt at putting the pieces together

After filling in the first base case, my function now looks like this:

function walkGrid(current, visited) {
  visited.add(current.join(','))
  if ( current.join(',') == end.join(',') ) {
    fewestSteps = Math.min(visited.size, fewestSteps);
    return false;
  } else {}
}
Enter fullscreen mode Exit fullscreen mode

I added a variable to track the winning number of steps:

let fewestSteps = Infinity
Enter fullscreen mode Exit fullscreen mode

After another few minutes, I added code to the else clause:

function walkGrid(current, visited) {
  visited.add(current.join(','))
  if ( current.join(',') == end.join(',') ) {
    fewestSteps = Math.min(visited.size, fewestSteps);
    return false;
  } else {
    let next = nearby.map(
      coord => grid[coord[0] + current[0]][coord[1] + current[1]] == '#' ? false : true
    )
    if ( next.every(el => el == false) ) {
      return false;
    } else {
      next.forEach((el, index) => {
        el ? walkGrid([current[0] + nearby[index][0], current[1] + nearby[index][1]], visited) : null
      })
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

It may not be eloquent, but it should make sense after you can decipher the array accessing syntax and math.

The big question is: does it even work?

Before I run it, I'll add some logging statements.

Well, just one for now:

if ( current.join(',') == end.join(',') ) {
  console.log(current, visited.size)
  fewestSteps = Math.min(visited.size, fewestSteps);
  return false;
}
Enter fullscreen mode Exit fullscreen mode

I'll know it works if it can reach this base case and at some point print out the correct answer, 22.

Time to press run and see what kind of errors I see!

So. Many. Bugs.
  • Max call stack exceeded
  • Can't access some variable before it's defined
  • Visited coordinate list isn't growing beyond three items

Turns out, I had syntax errors and logic gaps.

Thankfully, it's kind of fun to debug.

After fixing those issues, I saw longer lists of visited coordinates print.

But the coordinates included dead ends.

Why is that?

Oh, right, because every time I enter the function, I add the current coordinate to the visited list.

So, even if the shortest path doesn't include that point, since it was visited as part of an earlier iteration, it gets added.

How might I prevent this from happening?

Thankfully, I can delete an item from a Set():

visited.delete(current.join(',))
Enter fullscreen mode Exit fullscreen mode

I do that in the condition checking for all adjacent cells being dead ends or already visited:

if ( next.every(el => el == false) ) {
  visited.delete(current.join(','))
  return false;
}
Enter fullscreen mode Exit fullscreen mode

Running again with fewer logging statements:

  • I see whenever it hits a dead end
  • I see a number printed when it hits the target end point

But I'm seeing a number one greater than the expected answer.

Why? Because I include the starting location in my visited list.

The answer asks for the number of steps taken.

That's one less than an amount that includes the starting location.

Accounting for that, my algorithm spits out the correct answer!

But something seems odd still:

  • Why doesn't it print any of the possible higher numbers associated with paths that initially lead down?

To test this, I adjust the order of my adjacent cells...to go down first.

Running again, I get a different answer - a larger one.

Why is my function seemingly only exploring one path?

Hmmmm.

My hunch is I'm doing two things wrong:

  1. I need to use a unique set of visited points each time I further recurse into the function
  2. I need to clean up my condition for recursing

After both are complete, my larger last condition looks like this:

if ( next.every(el => el == false) ) {
  visited.delete(current.join(','))
  return false;
} else {
  next.forEach((el, index) => {
    if (el) {
      walkGrid(
        [
         current[0] + nearby[index][0], 
         current[1] + nearby[index][1]
        ], new Set(visited))
    } else {
      return false
    }
  })
}
Enter fullscreen mode Exit fullscreen mode

Oh, and I forgot to add my performance-boosting condition that breaks early if a path is longer than the current shortest:

if (visited.size - 1 > fewestSteps) {
  return false
}
Enter fullscreen mode Exit fullscreen mode

And with that, I press run again...

and see the correct answer!

In fact, regardless of the order of adjacent cell coordinates, I see the correct answer!

Woohoo!

Now for the real test: my puzzle input.

Will my algorithm ever finish?

Will it generate the correct answer?

I wonder...

Processing my puzzle input

I see numbers.

They are decreasing gradually.

No errors yet.

Still waiting.

This may take a while.

As long as the program doesn't abruptly stop, I can wait.

...

I let my program run for several hours.

The number it printed last was only a dozen less than the number it printed several hours prior.

I'm 100% positive it is not the correct answer.

And I was 99% positive I wouldn't get even one gold star today because of this shortest-path challenge.

It's a bummer, but expected by Day 18.

It's also time to move on.

Top comments (0)