DEV Community

loading...

[Advent of Code 2020] Day 17 Solution (TypeScript)

kais_blog profile image Kai Originally published at kais.blog ・4 min read

This post was originally published at kais.blog. It is part of a series of step-by-step tutorials about the Advent of Code 2020 event.

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

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 = [
  "#..#..#.",
  ".#..#..#",
  ".#..#...",
  
];
Enter fullscreen mode Exit fullscreen mode

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

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;
Enter fullscreen mode Exit fullscreen mode
type Point3D = [x: number, y: number, z: number];
Enter fullscreen mode Exit fullscreen mode
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);
  }
}
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

Part 2

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;
Enter fullscreen mode Exit fullscreen mode
type Point4D = [x: number, y: number, z: number, w: number];
Enter fullscreen mode Exit fullscreen mode
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);
  }
}
Enter fullscreen mode Exit fullscreen mode
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;
}
Enter fullscreen mode Exit fullscreen mode

If you like my content and you want to see more, please follow me on Twitter!

Questions, feedback or just wanna chat? Come and join my Discord!

This post was originally published at kais.blog.

Discussion (0)

Forem Open with the Forem app