202412060000 Advent of Code 2024 Day 06

Guard Gallivant

Today we visit the suit manufacturing plant from 2018 day 5 and need to avoid creating time paradoxes by hiding from the guard.

The Puzzle

Today we visit the suit manufacturing plant from 2018 day 5 and need to avoid creating time paradoxes by hiding from the guard.

The guard walks around the plant — our input grid — in a deterministic way. It will walk forward until it encounters an obstacle, then turn 90° to the right.

For the first part, we need to find all the spaces that the guard will visit before leaving the grid entirely. For the second part, we need to find all the possible places that we can place an additional obstruction that will result in the guard looping her path forever.

Solution

For some reason decided that dealing with deltas would be annoying — see my reticence for grid index handling in the day 4 write-up — so I decided to to rotate the whole grid instead of turning the guard.

That ended up being what's classically termed "a really dumb idea". It was extremely slow, to the point where it didn't work for part 2. Well, technically it might have been working but I thought it was stuck in a loop since it had taken more than a few minutes running in the background.

So I debugged things and found some simple optimizations. Once I was pretty sure I had a good solution, I let it run again. It did return this time, but took 138s.

For some context here, my computer has an M2 Max Apple Silicon chip. Reports vary, and Apple doesn't publish the data, but it probably runs at about 3.5 GHz. 138 seconds of compute is close to approximately 483 billion cycles. If one cycle took a second, my solution would take 15,316 years to finish. This is what is classically termed "way too slow" and "a tragic waste of the modern miracle of cpu clock speeds". Needless to say, I wanted to make it better.

In a vain effort to avoid rewriting the code to turn the guard instead of rotate the grid, I looked for other options. The biggest win I found was to only search the path that the guard takes when there are no obstacles. There's no way to add 1 obstacle and have it result in a cycle if the guard wouldn't hit it anyway. This took the time from 138 seconds to ~35 seconds. By far the biggest absolute win of the whole optimization process.

Next, I bit the bullet and refactored to move the guard and not rotate the grid. This brought the time down from ~35 seconds to 5 seconds.

Last, I found a few smaller wins.

• Change the method for tracking things to not require a clone of the grid. Instead I mutated the one grid and made sure to be able to reset it back to the start state. This got us to 4.5 seconds.
• Not re-computing the start position each time we check a potential obstruction location. We saved about a quarter of a second here, bringing us down to ~4.2 seconds.
• Moving the allocation of the [dx, dy] outside the hot loop and mutating it on each loop got us to ~3.8 seconds. This one makes me suspect that getting the string allocations for the set hashes out of that loop would be a nice win. The only way I can see now to reduce those would be to implement the jump table idea (see below).

const OBSTACLE = '#';
const FREE = '.';

const findStart = (grid) => {
  for (let y = 0; y < grid.length; y++) {
    for (let x = 0; x < grid[y].length; x++) {
      if (grid[y][x] === '^') return [x, y];
    }
  }
};

const walk = (grid, x, y) => {
  let dir = 0;
  let seen = new Set();
  let path = new Set();
  let [dx, dy] = MH_DELTAS[dir];

  while (true) {
    const hash = `${x},${y},${dir}`;
    if (oob(grid, x, y)) return [path, 0];
    if (seen.has(hash)) return [path, 1];
    path.add(`${x},${y}`);
    seen.add(hash);

    while (grid[y + dy]?.[x + dx] === OBSTACLE) {
      dir = (dir + 1) % 4;
      [dx, dy] = MH_DELTAS[dir];
    }

    x = x + dx;
    y = y + dy;
  }
};

export const solutionOne = (input) => {
  const grid = input.map(chars);
  const [x, y] = findStart(grid);
  return walk(input.map(chars), x, y)[0].size;
};

export const solutionTwo = (input) => {
  let grid = input.map(chars);
  const [sx, sy] = findStart(grid);
  const path = walk(grid, sx, sy)[0];

  let cycles = 0;
  for (let y = 0; y < grid.length; y++) {
    for (let x = 0; x < grid[y].length; x++) {
      if (grid[y][x] !== '^' && path.has(`${x},${y}`)) {
        grid[y][x] = OBSTACLE;
        cycles += walk(grid, sx, sy)[1];
        grid[y][x] = FREE;
      }
    }
  }
  return cycles;
};

I do have some other ideas, but I'm not going to bother with them now. For completeness sake, here they are even though I don't know if they'd help or not.

• Pre-compute a jump table. From one point where the guard turns, we could know that his location and direction will walk him all the way down to the next turn point. You could maybe implement this a bit differently by just walking the guard all the way to the the next obstacle before doing the main walk loop.
• Do some interesting bit-masking type collision detection. You can usually get some speed wins by doing bitwise operations where possible. I'm not sure how this would really
• Use imaginary numbers. On almost all these grid coordinate type problems, you can reframe the system into imaginaries and then do simple math on them. Not sure how much more speed there is in this approach though. It does simplify the coordination logic for moving the guard though.
• I wonder if you could cache some
• Parallelize. But this is something I don't typically do for AoC since I prefer finding the best single threaded solution.

While the problem wasn't too difficult, I spent a good bit of time today optimizing my solution so that it wouldn't be a drag on the total execution time for all puzzles this year. I'm not a huge fan of the puzzles that require a lot of small fine tuning to a mostly inefficient solution algorithm. I much prefer when there's an analytical solution or "better" algorithm than the naïve, brute-force way.

You can find the full solutions to today's AoC puzzles in my AoC GitHub repo.