Guard Gallivant

Advent of Code 2024 Day 6

Part 1

A very familiar kind of puzzle

• 2D grid
• Obstacles throughout
• Track a path
• Count the unique tiles visited

Let's get to it!

One step at a time

Parsing the grid:

let grid = input.split('\n').map(el => el.split(''))

Identifying the guard's starting location and replacing it with an empty tile:

let guard = null;
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Creating an object to track guard's current rotation:

let facing = [
  [-1,0],
  [0,1],
  [1,0],
  [0,-1]
]

• Guard starts facing north, so subsequent moves require visiting rows of lesser indices
• Upon each obstacle, the guard must turn right
• That would make her face east, so subsequent moves require visiting columns of greater indices
• Each time the next cell is an obstacle, my algorithm will pull the first item from the list and move it to the back

Tracking visited cells:

let visited = new Set()

Upon each move, I'll attempt to add the stringified coordinates to this Set().

Moving the guard:

while (true) {
  visited.add(guard.join(","));
  let next = [guard[0] + facing[0][0], guard[1] + facing[0][1]];
  if (
    next[0] >= 0 &&
    next[0] < grid.length &&
    next[1] >= 0 &&
    next[1] < grid[0].length
  ) {
    if (grid[next[0]][next[1]] == ".") {
      guard = next;
      console.log(guard);
    } else if (grid[next[0]][next[1]] == "#") {
      let oldDirection = facing.shift();
      facing.push(oldDirection);
    }
  } else {
    break;
  }
}

An explanation:

Keep going until manually broken out of
  Add the current coordinate to the tracked list
  Record the next location to visit
  If it is within the grid
    If it is empty cell
      Move the guard
    Else If it is an obstacle
      Rotate the guard
  Else
    Break out of the loop

This algorithm successfully generates a visited cell list of 41 for the example input!

Will it generate the correct answer for my puzzle input?

Yes!!!

Awesome.

On to Part 2!

Part 2

I kinda saw this coming, and was dreading it

The ol', check every possible option for a valid one puzzle.

My big question when reading is:

• How will I identify when the guard enters a loop?

But I think I know:

• I'll track the facing direction as well as the coordinate
• If the list includes a copy of the next one being added, then a loop is about to begin

Time to make things a lot more complicated!

Looping through each cell to find all the loops

First, I want to generate a list of all cells with a ., excluding the guard's starting cell:

let empties = [];
for (let r = 0; r < grid.length; r++) {
  for (let c = 0; c < grid[0].length; c++) {
    if (grid[r][c] == ".") {
      empties.push([r, c]);
    }
    if (grid[r][c] == "^") {
      guard = [r, c];
      grid[r][c] = ".";
    }
  }
}

Then, using a reduce to iterate through each . in the grid, copying the grid and original guard position, moving lots of the original code inside the reduce, expanding the while loop to include a condition for the tracked coordinate and rotation list having an instance of the current state:

let part2 = empties.reduce((count, coord) => {
    let guardCopy = guard.slice()
    let gridCopy = grid.map(row => row.slice())
    gridCopy[coord[0]][coord[1]] = "#"
    let facing = [
        [-1,0],
        [0,1],
        [1,0],
        [0,-1]
      ]
    let visited = new Set()
    while (true) {
        let stamp = guardCopy.join(',') + facing[0].join(',')
        if (visited.has(stamp)) {
            count++
            break;
        } else {
            visited.add(stamp);
            let next = [guardCopy[0] + facing[0][0], guardCopy[1] + facing[0][1]]
            if (
              next[0] >= 0 &&
              next[0] < gridCopy.length &&
              next[1] >= 0 &&
              next[1] < gridCopy[0].length
            ) {
              if (gridCopy[next[0]][next[1]] == ".") {
                guardCopy = next;
              } else if (gridCopy[next[0]][next[1]] == "#") {
                let oldDirection = facing.shift();
                facing.push(oldDirection);
              }
            } else {
              break;
            }
        }
    }
    return count
}, 0)

It's a lot.

But it works! At least on the example input.

Will it work on mine, though???

Well...it took 30 seconds to run.

But...it generated an answer!

And it is the...

CORRECT ANSWER!!!

Woohoo!!!

Part 1 was a cinch. And Part 2 was a tough but welcome ramp up in scale.

Two more gold stars in the bag!

On to Day 7.