Guard Gallivant-JS Tutorial-php.cn

Guard Gallivant

DDD

Release： 2024-12-16 04:40:11

Original

134 people have browsed it

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(''))

Copy after login

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] = ".";
    }
  }
}

Copy after login

Creating an object to track guard's current rotation:

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

Copy after login

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()

Copy after login

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

Copy after login

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

Copy after login

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] = ".";
    }
  }
}

Copy after login

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)

Copy after login

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.