Today’s puzzle asks us to search for the shortest path through an elevation map, where we are only able to ascend one unit at a time. We’re supposed to search from a given starting point S to a given ending point E, but the trick to part 2 is actually to search in reverse!

The example input looks like this.

Sabqponm
abcryxxl
accszExk
acctuvwj
abdefghi

Note the S and the E for the “start” and “end” points, and the lowercase letters represent heights (in alphabetical order).

We start by defining a Point type that holds information related to our search.

type Point = {
  x: number;
  y: number;
  letter: string;
  height: string;
  cost: number;
  visited: boolean;
};

Then we define a makeHeightmap() function that parses the puzzle input into a Point[][] data structure, using some ternary expressions to determine the height and starting cost for each point.

const makeHeightmap = () =>
  puzzleInput
    .split('\n')
    .map((line, x) => line
    .split('')
    .map((letter, y) => ({
      x, y, letter,
      height: letter === 'S' ? 'a'
        : letter === 'E' ? 'z'
        : letter,
      cost: letter === 'E' ? 0 : Infinity,
      visited: false
    } as Point)));

We implement a quick utility function that allows us to compare lowercase letters as numerical heights. This is trivial if we take advantage of the fact that the ASCII character codes of the lowercase letters are already in the numerical order that we need.

const compareHeight = (p: Point, q: Point) =>
  q.height.charCodeAt(0) - p.height.charCodeAt(0);

Now, our eventual Dijkstra’s search will require a way to find all the neighbors from a given point. We implement getNeighbors() by literally constructing an array for each direction (up, down, left, right) and filtering out the invalid positions, as well as any points that have been visited and any that aren’t one step down from the current point (remembering that we’re searching in reverse).

const getNeighbors = (p: Point, heightmap: Point[][]) =>
  [
    heightmap[p.x - 1]?.[p.y],
    heightmap[p.x + 1]?.[p.y],
    heightmap[p.x]?.[p.y - 1],
    heightmap[p.x]?.[p.y + 1]
  ].filter(q => !!q && !q.visited && compareHeight(q, p) <= 1);

Dijkstra’s algorithm will perform a little faster with a priority queue to ensure we are searching optimally, so we implement a basic one by defining insertByMinCost() which puts a point into the queue in the right position, so that the points in the queue are all in ascending cost order.

const insertByMinCost = (ps: Point[], p: Point) => {
  const queue = ps.filter(x => x !== p);
  const pos = ps.findIndex(x => x.cost > p.cost);
  queue.splice(pos === -1 ? queue.length : pos, 0, p);
  return queue;
}

Finally we implement the search algorithm, which takes a variable lambda function, letting us customize when the search will end. Once the search ends, we inspect the final point that we landed on and return the cost that it took us to reach it.

const dijkstra = (goal: (p: Point) => boolean) => {
  const heightmap = makeHeightmap();
  let queue = heightmap.flatMap(x => x).filter(p => p.letter === 'E');
  let p: Point = null;
  do {
    p = queue.shift();
    for (const neighbor of getNeighbors(p, heightmap)) {
      neighbor.cost = p.cost + 1;
      queue = insertByMinCost(queue, neighbor);
    }
    p.visited = true;
  } while (!goal(p))

  return p?.cost;
}

Now the only difference between part 1 and part 2 is that we end on exactly the S point for part 1, whereas part 2 lets us end on any point with a height of a, including S.

const part1 = dijkstra(p => p.letter === 'S');
const part2 = dijkstra(p => p.height === 'a');

type Point = {
  x: number;
  y: number;
  letter: string;
  height: string;
  cost: number;
  visited: boolean;
};

const makeHeightmap = () =>
  puzzleInput
    .split('\n')
    .map((line, x) => line
    .split('')
    .map((letter, y) => ({
      x, y, letter,
      height: letter === 'S' ? 'a'
        : letter === 'E' ? 'z'
        : letter,
      cost: letter === 'E' ? 0 : Infinity,
      visited: false
    } as Point)));

const compareHeight = (p: Point, q: Point) =>
  q.height.charCodeAt(0) - p.height.charCodeAt(0);

const getNeighbors = (p: Point, heightmap: Point[][]) =>
  [
    heightmap[p.x - 1]?.[p.y],
    heightmap[p.x + 1]?.[p.y],
    heightmap[p.x]?.[p.y - 1],
    heightmap[p.x]?.[p.y + 1]
  ].filter(q => !!q && !q.visited && compareHeight(q, p) <= 1);

const insertByMinCost = (ps: Point[], p: Point) => {
  const queue = ps.filter(x => x !== p);
  const pos = ps.findIndex(x => x.cost > p.cost);
  queue.splice(pos === -1 ? queue.length : pos, 0, p);
  return queue;
}

const dijkstra = (goal: (p: Point) => boolean) => {
  const heightmap = makeHeightmap();
  let queue = heightmap.flatMap(x => x).filter(p => p.letter === 'E');
  let p: Point = null;
  do {
    p = queue.shift();
    for (const neighbor of getNeighbors(p, heightmap)) {
      neighbor.cost = p.cost + 1;
      queue = insertByMinCost(queue, neighbor);
    }
    p.visited = true;
  } while (!goal(p))

  return p?.cost;
}

const part1 = dijkstra(p => p.letter === 'S');
const part2 = dijkstra(p => p.height === 'a');

console.log("Part 1:", part1);
console.log("Part 2:", part2);

Part 1: 383
Part 2: 377