Hung-Yi's LogoHung-Yi’s Journal

Advent of Code 2022: Day 14

A TypeScript solution for the Advent of Code 2022, Day 14 puzzle: constructing walls and simulating falling sand physics.

Today’s puzzle asks us to simulate grains of sand and some simple physics rules that govern how they settle into piles, given a landscape filled with generated walls and platforms.

The example input looks like this.

498,4 -> 498,6 -> 496,6
503,4 -> 502,4 -> 502,9 -> 494,9

The comma-separated numbers represent coordinates, and the arrows represent connections to other coordinates. Together, they form lines that represent the walls and platforms that interrupt and block the flow of sand.

We start by defining some types that represent the data that we’re working with.

type Cell = "#" | "o";
type Coord = [number, number];
type Wall = Coord[];
type Cave = Map<string, Cell>;
  • A Cell represents the value at a position, either # (a wall block) or o (a grain of sand)
  • Coord is a tuple of two numbers that represent a position [x, y]
  • A Wall is defined by multiple Coord points that are connected together
  • And the Cave represent the whole 2D space by mapping stringified coordinate keys to Cell values at each position

Now we can parse the puzzle input into an array of walls.

const WALLS: Wall[] = puzzleInput
  .split("\n")
  .map(
    (line) =>
      line
        .split(" -> ")
        .map((coord) => coord.split(","))
        .map(([x, y]) => [Number(x), Number(y)]),
  );

And to make our simulation easier later, we can calculate the max depth (highest y value) that the walls go to. This also happens to be our world boundary for part 1.

const WALL_MAX_DEPTH = Math.max(
  ...WALLS.flatMap((w) => w).map(([, y]) => y),
);

Recall that a Wall is defined by a series of sparse coordinates that are connected by lines, so we still need to interpolate all the individual points that lie in between those wall coordinates. To do this, we implement a function called expand() that takes a Wall and outputs an array of coordinates that represent every point in that wall.

// Expands a wall definition into a full list of coordinates
const expand = (wall: Wall) => {
  return wall.slice(1).reduce(
    (coords, [x2, y2], ii) => {
      const [x1, y1] = wall[ii];
      return coords.concat(
        x1 === x2
          ? Array(Math.abs(y1 - y2) + 1)
            .fill(Math.min(y1, y2))
            .map((y, i) => [x1, y + i])
          : Array(Math.abs(x1 - x2) + 1)
            .fill(Math.min(x1, x2))
            .map((x, i) => [x + i, y1]),
      );
    },
    [] as Coord[],
  );
};

Now we should consider the Cave structure and how it can be used to solve the puzzle.

To store the Cell values in the Cave positions, we somehow need to convert coordinates [x,y] into a string type that can be uniquely keyed in a Map<string,Cell>. This is simply achieved by concatenating the x and y coordinates with a comma separator.

// Encodes an [x,y] coordinate to a string for use in hash map
const encodeCoord = (x: number, y: number) => `${x},${y}`;

Next, we need some functions to manipulate the cell values at any given cave position.

// Get the cell contents of a cave at [x,y]
const check = (cave: Cave, x: number, y: number, floor?: number) =>
  y === floor ? "#" : cave.get(encodeCoord(x, y));

// Settle a grain of sand at [x,y]
const settle = (cave: Cave, x: number, y: number) =>
  cave.set(encodeCoord(x, y), "o");

And finally, we can write our simulate() function.

// Simulate falling sand with or without a floor
function simulate(hasFloor: boolean) {
  const floor = hasFloor ? WALL_MAX_DEPTH + 2 : undefined;
  const abyss = floor ?? WALL_MAX_DEPTH;

  const cave: Cave = new Map<string, Cell>(
    WALLS
      .flatMap(expand)
      .map(([x, y]) => [encodeCoord(x, y), "#"]),
  );

  let sand = 0;
  while (true) {
    let [x, y] = [500, 0];
    while (y < abyss) {
      if (!check(cave, x, y + 1, floor)) {
        y++; // fall down
      } else if (!check(cave, x - 1, y + 1, floor)) {
        y++;
        x--; // fall left
      } else if (!check(cave, x + 1, y + 1, floor)) {
        y++;
        x++; // fall right
      } else {
        settle(cave, x, y);
        break;
      }
    }

    // stop counting if sand starts leaking
    if (y >= abyss) break;
    sand++;

    // stop if last grain of sand blocks source
    if (x === 500 && y === 0) break;
  }

  return sand;
}

The function does the following:

  1. Depending on whether we have a floor or not, define the depth of the floor and the out-of-bounds depth, which we call abyss.
  2. Construct the cave by populating it with wall blocks for all the WALLS, which we parsed out earlier.
  3. With two while loops, generate grains of sand and make them fall, respectively. The if/else if/else if/else block controls which direction the grain falls in, and whether it is forced to settle in a position in the Cave.
  4. If the sand falls past the abyss depth, stop counting grains of sand, break out of the loop, and return the answer.
  5. If the current grain of sand has settled at the source [500,0] then the Cave is full, so stop the simulation and return the answer.

For part 1, the simulation has no floor, and for part 2, the simulation has a floor which is 2 units deeper than the maximum depth of the walls.

const part1 = simulate(false);
const part2 = simulate(true);

Final Solution

type Cell = "#" | "o";
type Coord = [number, number];
type Wall = Coord[];
type Cave = Map<string, Cell>;

const WALLS: Wall[] = puzzleInput
  .split("\n")
  .map(
    (line) =>
      line
        .split(" -> ")
        .map((coord) => coord.split(","))
        .map(([x, y]) => [Number(x), Number(y)]),
  );


const WALL_MAX_DEPTH = Math.max(
  ...WALLS.flatMap((w) => w).map(([, y]) => y),
);

// Expands a wall definition into a full list of coordinates
const expand = (wall: Wall) => {
  return wall.slice(1).reduce(
    (coords, [x2, y2], ii) => {
      const [x1, y1] = wall[ii];
      return coords.concat(
        x1 === x2
          ? Array(Math.abs(y1 - y2) + 1)
            .fill(Math.min(y1, y2))
            .map((y, i) => [x1, y + i])
          : Array(Math.abs(x1 - x2) + 1)
            .fill(Math.min(x1, x2))
            .map((x, i) => [x + i, y1]),
      );
    },
    [] as Coord[],
  );
};

// Encodes an [x,y] coordinate to a string for use in hash map
const encodeCoord = (x: number, y: number) => `${x},${y}`;

// Get the cell contents of a cave at [x,y]
const check = (cave: Cave, x: number, y: number, floor?: number) =>
  y === floor ? "#" : cave.get(encodeCoord(x, y));

// Settle a grain of sand at [x,y]
const settle = (cave: Cave, x: number, y: number) =>
  cave.set(encodeCoord(x, y), "o");

// Simulate falling sand with or without a floor
function simulate(hasFloor: boolean) {
  const floor = hasFloor ? WALL_MAX_DEPTH + 2 : undefined;
  const abyss = floor ?? WALL_MAX_DEPTH;

  const cave: Cave = new Map<string, Cell>(
    WALLS
      .flatMap(expand)
      .map(([x, y]) => [encodeCoord(x, y), "#"]),
  );

  let sand = 0;
  while (true) {
    let [x, y] = [500, 0];
    while (y < abyss) {
      if (!check(cave, x, y + 1, floor)) {
        y++; // fall down
      } else if (!check(cave, x - 1, y + 1, floor)) {
        y++;
        x--; // fall left
      } else if (!check(cave, x + 1, y + 1, floor)) {
        y++;
        x++; // fall right
      } else {
        settle(cave, x, y);
        break;
      }
    }

    // stop counting if sand starts leaking
    if (y >= abyss) break;
    sand++;

    // stop if last grain of sand blocks source
    if (x === 500 && y === 0) break;
  }

  return sand;
}

const part1 = simulate(false);
const part2 = simulate(true);

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