2024 Day 6: Guard Gallivant

Advent of Code

Advent of Code
OJS
Published

December 6, 2024

Day 6!

Part 1

Today, it feels like we are designing a videogame! I usually hide the input parsing, though I thought today’s was notable in that I found a better way to map out a grid using integer and mod division to calculate the starting position:

input = {
  const map = raw.split('\n').map(d => d.split("")) // 2D array
  const [nrow, ncol] = [map.length, map[0].length] // dims
  const start_index = map.flat().indexOf("^") // guard start
  // use integer & mod div to find location
  const [curr_row, curr_col] = [Math.floor(start_index/ncol), start_index % ncol]
  const clean_map = map.slice()
  clean_map[curr_row][curr_col] = '.' // replace so it's counted as an empty spot

  const input = {
    start: [curr_row, curr_col],
    layout: clean_map,
    dir: 0, // up
    dims: [nrow, ncol]
  }
  
  return input
}

Now that that is sorted, let’s proceed to part 1…

possible_moves = [
  [-1, 0], // up
  [0, 1], // right
  [1, 0], // down
  [0, -1] // left
]

First, since we know we are navigating around a grid, let’s define movements in the four cardinal directions.

move_guard = (input, possible_moves) => {
  const pos = [] // positions
  let [[row, col], dir] = [input.start, input.dir]

  while (true) { // until guard leaves grid
    
    // add current position and heading
    pos.push([row, col, dir])

    // get next pos and direction
    const [next_row, next_col] = [row + possible_moves[dir][0], 
                                  col + possible_moves[dir][1]]
    
    // OOB check
    if (next_row < 0 || next_row >= input.dims[0] || 
          next_col < 0 || next_col >= input.dims[1]) {
      return pos
    } 

    // if blocked, turn right
    if (input.layout[next_row][next_col] === "#") {
      dir = (dir + 1) % 4
    }

    // update position so it gets pushed for next iter
    [row, col] = [row + possible_moves[dir][0], 
                  col + possible_moves[dir][1]]
    
  }
}

Now we’re getting serious – the main bulk of the problem!

This function traces the guard’s path by running through each step in a while loop. This way, we can set the condition to break on the guard leaving the bounds of our grid. Also, since we are keeping track of the direction using an integer, we can utilize it as an index with a little creative math.

Though this function looks clean, it was not my first attempt. I originally thought that this would be a great use case for a recursive function – each call would move the guard a step forward, then call itself again (assuming it stayed in bounds). However, as soon as I scaled up to the full input, I exceeded the call stack, so I went back to the drawing board.

new Set(move_guard(input, possible_moves)
      .map(d => JSON.stringify( [ d[0], d[1] ] ))).size

Once we have our function, it’s just a matter of finding the number of unique positions visited. I chose to do this with JSON.stringify(), then creating a Set from those strings and counting the length. After the fact, I saw someone’s solution for another day that used bitwise shifts and joins to calculate uniques (which I’ll use in Part 2).

Part 1 complete!

⭐

Part 2

Uh oh, more complex now… we have to check how many discrete locations we can add an extra obstacle to in the guard’s path to send him into an infinite loop. This was daunting to start with, because anything that has to deal with checking for infinite loops seems difficult to do without launching into an infinite loop yourself. For example, if you revisit a specific location, who’s to say that your next step will continue the loop?

However, after some pondering, I realized that that is not the case here. We have very specific rules about movement, so we can say with certainty that if a position is repeated, and a guard is facing the same way as before, then a loop is happening. In fact, we can abstract it away farther, and only care about checking the turn points for overlaps, since those are the ‘decision points’ where a loop could be entered.

check_loop = (input, possible_moves) => {
  const pos = new Set()
  let [[row, col], dir] = [input.start, input.dir]
  let turn = false

  while(true) {
    // if move is a turn
    if (turn) {
      // check if position and heading exists
      const current_pos = (row << 16) | (col << 8) | dir
      if (pos.has(current_pos)) {
        // exit and say yes loop exists
        return true
      }
      // otherwise add and keep going
      pos.add(current_pos)
    }

    // get next pos and direction
    const [next_row, next_col] = [row + possible_moves[dir][0], 
                                  col + possible_moves[dir][1]]

    // OOB check
    if (next_row < 0 || next_row >= input.dims[0] || 
          next_col < 0 || next_col >= input.dims[1]) {
      return false // no loop, exits grid
    }

    if (input.layout[next_row][next_col] === "#") {
      dir = (dir + 1) % 4
      turn = true
    } else {
      row = next_row
      col = next_col
      turn = false
    }
  }
}

To start, let’s modify the previous function to log all the positions as a Set, as well as tracking the heading in the position Set, as that will be critical to determining if we are in a loop.

Another change of note is we are now keeping a boolean flag turn to keep track of whether each move is a turn or not. This way, we can say that if the guard is turning, check if the position has been reached before; otherwise, continue as is onto the next step.

If you look closely, you’ll also see the bit shifting mentioned above being used to collapse row, col, and dir down to one number.

{
  // get unique route positions
  const all_route = move_guard(input, possible_moves)
    .map(d => (d[0] << 8) | d[1] )
  
  const unique_pos = Array.from(new Set(all_route))
    // multiply by masking hex codes to shorten down the bits 
    .map(d => ( [(d >> 8) & 0xFF, d & 0xFF] ))
  
  // keep track of new obstacles
  const loop_counter = new Set()

  // for each position on the route
  unique_pos.forEach(d => {
    // add obstacle
    input.layout[ d[0] ][ d[1] ] = "#"
    // see if loop exists
    if (check_loop(input, possible_moves)) {
      // add to tracker
      loop_counter.add( (d[0] << 8) | d[1] )
    }
    // reset layout for next iter
    input.layout[ d[0] ][ d[1] ] = "."
  })
  // return unique counts
  return loop_counter.size - 1 // duped the start position
}

Unfortunately, there wasn’t many better ways to find all the loops than to try each one, adding an obstacle to a different location each time. To shrink the search space some, I decided to only try adding obstacles to the locations that the guard visited in Part 1 – after all, if he never runs into it, then it won’t be a loop since we know that he exits cleanly with the default map.

Anyways, we just need to iterate through those positions, modifying the grid and running our check_loop() function on each; once we have the resultant positions, we just need the count of uniques.

⭐

Ramping up in difficulty for sure now!

-CH