202412020000 Advent of Code 2024 Day 02

Red-Nosed Report

We've made it to our first location in our search for the chief elf historian, the reindeer reactor from 2015 day 19. The reindeer need some help finding out which series of readings from their reactor are safe.

The Puzzle

We've made it to our first location in our search for the chief elf historian, the reindeer reactor from 2015 day 19. The reindeer need some help finding out which series of readings from their reactor are safe.

A safe reading is a row of our input that is strictly monotonically increasing or decreasing as well as having deltas between readings within a certain range.

Solution

I started out by doing a simple, inefficient test for whether the array was sorted by just comparing it to copies that were sorted. We then need to check that the absolute value between the measurements satisfy $x\in \mathbb{N}|0<x<4$.

const safe = (l) =>
  (l.eq([...l].asc()) || l.eq([...l].desc())) &&
  diffs(l)
    .map(Math.abs)
    .every((d) => 0 < d && d < 4);

export const solutionOne = (input) => input.map(parse).filter(safe).length;

The second part expands our definition of safe to include readings that would be safe if we removed one value from the set. I'm pretty sure there's an $O\left(n\right)$ solution to this, but I just checked each possibility.

export const solutionTwo = (input) =>
  input.map(parse).filter((level) => {
    if (safe(level)) return true;
    for (let i = 0; i < level.length; i++) {
      if (safe(level.cut(i))) return true;
    }
  }).length;

Once I had the answers, I went back and cleaned things up a little bit.

First of all, I removed a line in the second solution.

input.map(parse).filter((level) => {
- if (safe(level)) return true;
  for (let i = 0; i < level.length; i++) {
    if (safe(level.cut(i))) return true;
  }
}).length;

If the whole level is safe then cutting the first (or last) would also be safe. This optimization works nicely to eliminate a branching operation and results in a very slight speed increase.

Next, I changed my monotonicity check to avoid creating two copies of the array and sorting them. Instead I just used the differences (that we needed to compute anyway for the step size check) to do it. This also resulted in a slight (but larger) speed increase.

const safe = (level) => {
  const ds = diffs(level);
  return (
    (ds.every((d) => d > 0) || ds.every((d) => d < 0)) &&
    ds.map(Math.abs).every((d) => 0 < d && d <= 3)
  );
};

Lastly, I realized that I've had to do this kind of thing before a few times for AoC and decided to add a monotonic function to my library of helpers. I included a flag for whether it should care about strictly monotonic (i.e. $\mathrm{\Delta }>0$ instead of $\mathrm{\Delta }\ge 0$)

Array.prototype.monotonic = function (strict = false) {
  const deltas = this.diffs();
  const cmpInc = strict ? (d) => d > 0 : (d) => d >= 0;
  const cmpDec = strict ? (d) => d < 0 : (d) => d <= 0;
  return deltas.every(cmpInc) || deltas.every(cmpDec);
};

Which in turn makes the final solution functional, high-level, and abstract, just like the Haskell gods intended.

const safe = (level) =>
  level.monotonic(true) &&
  diffs(level)
    .map(Math.abs)
    .every((d) => 0 < d && d <= 3);

Slow again. Ultimately refactored into a pretty nice looking solution. I can feel the rust coming off though. Hopefully, I'm a little quicker tomorrow.

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