Advent of Code 2020 Day 17 - Solution + Tutorial (TypeScript)

published 2020-12-20T13:31:33.000Z

All TypeScript Solutions for Advent of Code 2020

I'll try to update asap. Please bear in a mind that I'll probably lag one or multiple days behind.

Prerequisites

I assume you've put your puzzle input into an array called lines where each array item is a line of the input text file. It's up to you to either parse the text file or create an array by hand.

const lines = [
  "#..#..#.",
  ".#..#..#",
  ".#..#...",
  …
];

Solution

Preface

Starting with Day 10, I'll just publish my solution for both parts without explaining every single step. Unfortunately, I can't continue providing full step-by-step tutorials for each day. The concepts used get more difficult day by day. So, I've concluded that it's better if I wrote separate blog posts about these concepts later.

Also, it's holiday season. This makes it much more difficult creating well-thought-out tutorials. However, I'll try to annotate my code examples a little. This way, you might understand what I've done.

I will now move on to sharing useful tips for web developers regularly. These should help you become a better developer. Also, the shared tips should help with solving problems like those we encounter in Advent of Code. Here's my first post: 14 Awesome JavaScript Array Tips You Should Know About

Puzzle

Just to make sure, you know what I'm talking about, take a look at today's puzzle:

Day 17: Conway Cubes

Part 1

TODO: The code is ready, I'm working on the description.

let pocketDimension = new PocketDimension();
const initialSize = lines.length;

lines.forEach((line, y) => {
  const z = 0;
  [...line].forEach((cube, x) => {
    if (cube !== "#") return;
    pocketDimension.activate([x, y, z]);
  });
});

for (let cycle = 1; cycle <= 6; cycle++) {
  const newPocketDimension = new PocketDimension();

  // Use pad to take growing dimension into account.
  const pad = cycle;
  for (let x = -pad; x < initialSize + pad; x++) {
    for (let y = -pad; y < initialSize + pad; y++) {
      for (let z = -pad; z <= pad; z++) {
        const point = [x, y, z] as Point3D;

        const isActive = pocketDimension.isActive(point);
        const activeNeighbors = countActiveNeighbors(pocketDimension, point);

        if ((isActive && activeNeighbors === 2) || activeNeighbors === 3) {
          newPocketDimension.activate(point);
        }
      }
    }
  }

  pocketDimension = newPocketDimension;
}

return pocketDimension.activeCount;

type Point3D = [x: number, y: number, z: number];

class PocketDimension {
  protected _xMap: Map<number, Map<number, Set<number>>>;

  public constructor() {
    this._xMap = new Map<number, Map<number, Set<number>>>();
  }

  public get activeCount(): number {
    let active = 0;

    for (const yMap of this._xMap.values()) {
      for (const zMap of yMap.values()) {
        active += zMap.size;
      }
    }

    return active;
  }

  public isActive([x, y, z]: Point3D): boolean {
    return this._xMap.get(x)?.get(y)?.has(z) ?? false;
  }

  public activate([x, y, z]: Point3D): void {
    let yMap = this._xMap.get(x);

    if (!yMap) {
      yMap = new Map<number, Set<number>>();
      this._xMap.set(x, yMap);
    }

    let zMap = yMap.get(y);

    if (!zMap) {
      zMap = new Set<number>();
      yMap.set(y, zMap);
    }

    zMap.add(z);
  }
}

function countActiveNeighbors(
  pocketDimension: PocketDimension,
  [x, y, z]: Point3D,
  threshold = 4
): number {
  let activeNeighbors = 0;

  // Use delta to look for neighbors.
  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      for (let dz = -1; dz <= 1; dz++) {
        if (dx === 0 && dy === 0 && dz === 0) continue;

        const isActive = pocketDimension.isActive([x + dx, y + dy, z + dz]);

        if (isActive) {
          activeNeighbors++;

          // We don't need to count more than threshold (default: 4).
          if (activeNeighbors >= threshold) {
            return activeNeighbors;
          }
        }
      }
    }
  }

  return activeNeighbors;
}

Part 2

TODO: The code is ready, I'm working on the description.

let pocketDimension = new PocketDimension();
const initialSize = lines.length;

lines.forEach((line, y) => {
  const z = 0;
  const w = 0;
  [...line].forEach((cube, x) => {
    if (cube !== "#") return;
    pocketDimension.activate([x, y, z, w]);
  });
});

for (let cycle = 1; cycle <= 6; cycle++) {
  const newPocketDimension = new PocketDimension();

  const pad = cycle;
  for (let x = -pad; x < initialSize + pad; x++) {
    for (let y = -pad; y < initialSize + pad; y++) {
      for (let z = -pad; z <= pad; z++) {
        for (let w = -pad; w <= pad; w++) {
          const point = [x, y, z, w] as Point4D;

          const isActive = pocketDimension.isActive(point);
          const activeNeighbors = countActiveNeighbors(
            pocketDimension,
            point
          );

          if ((isActive && activeNeighbors === 2) || activeNeighbors === 3) {
            newPocketDimension.activate(point);
          }
        }
      }
    }
  }

  pocketDimension = newPocketDimension;
}

return pocketDimension.activeCount;

type Point4D = [x: number, y: number, z: number, w: number];

class PocketDimension {
  protected _xMap: Map<number, Map<number, Map<number, Set<number>>>>;

  public constructor() {
    this._xMap = new Map<number, Map<number, Map<number, Set<number>>>>();
  }

  public get activeCount(): number {
    let active = 0;

    for (const yMap of this._xMap.values()) {
      for (const zMap of yMap.values()) {
        for (const wMap of zMap.values()) {
          active += wMap.size;
        }
      }
    }

    return active;
  }

  public isActive([x, y, z, w]: Point4D): boolean {
    return this._xMap.get(x)?.get(y)?.get(z)?.has(w) ?? false;
  }

  public activate([x, y, z, w]: Point4D): void {
    let yMap = this._xMap.get(x);

    if (!yMap) {
      yMap = new Map<number, Map<number, Set<number>>>();
      this._xMap.set(x, yMap);
    }

    let zMap = yMap.get(y);

    if (!zMap) {
      zMap = new Map<number, Set<number>>();
      yMap.set(y, zMap);
    }

    let wMap = zMap.get(z);

    if (!wMap) {
      wMap = new Set<number>();
      zMap.set(z, wMap);
    }

    wMap.add(w);
  }
}

function countActiveNeighbors(
  pocketDimension: PocketDimension,
  [x, y, z, w]: Point4D,
  threshold = 4
): number {
  let activeNeighbors = 0;

  for (let dx = -1; dx <= 1; dx++) {
    for (let dy = -1; dy <= 1; dy++) {
      for (let dz = -1; dz <= 1; dz++) {
        for (let dw = -1; dw <= 1; dw++) {
          if (dx === 0 && dy === 0 && dz === 0 && dw === 0) continue;

          const isActive = pocketDimension.isActive([
            x + dx,
            y + dy,
            z + dz,
            w + dw,
          ]);

          if (isActive) {
            activeNeighbors++;

            if (activeNeighbors >= threshold) {
              return activeNeighbors;
            }
          }
        }
      }
    }
  }

  return activeNeighbors;
}