# 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
```