AoC 2021 D20: Trench Map

| Problem statement | Source code | Tags: Cellular automata

← Previous Back to AoC Index Next →

Perhaps the single most important observation is that algorithm[0] is # and algorithm[511] is . in the real input, which means that the infinite empty space outside the image alternates between . and # each step. Other than that, this is still a cellular automaton problem, since each pixel's next state depends only on its current 3x3 neighborhood.

This time, I decided to represent the image as an actual 2D array, because I need to quickly tell which cells are "out of bounds" and therefore alternates between . and #. Other than that, the implementation is the same as previous ones. For each pixel in the new image, find its 3x3 neighborhood in the old image, compute the corresponding index, and look up the new value from the algorithm string. If the neighbor is out of bounds, use the default pixel value for that step.

function enhanceImage(
  image: boolean[][],
  algo: string,
  defaultPixel: boolean,
): boolean[][] {
  const newImage: boolean[][] = [];
  const height = image.length;
  const width = image[0].length;

  for (let y = -1; y <= height; y++) {
    const newRow: boolean[] = [];
    for (let x = -1; x <= width; x++) {
      let index = 0;
      for (let dy = -1; dy <= 1; dy++) {
        for (let dx = -1; dx <= 1; dx++) {
          index <<= 1;
          const ny = y + dy;
          const nx = x + dx;
          index |= Number(image[ny]?.[nx] ?? defaultPixel);
        }
      }
      newRow.push(algo[index] === "#");
    }
    newImage.push(newRow);
  }

  return newImage;
}

The main loop just loops n times, each time alternating the default pixel.

let enhancedImage = image;
let defaultPixel = false;
for (let i = 0; i < n; i++) {
  enhancedImage = enhanceImage(enhancedImage, algo, defaultPixel);
  if (algo[0] === "#" && algo.at(-1) === ".") {
    defaultPixel = !defaultPixel;
  } else if (algo[0] === "#") {
    defaultPixel = true;
  }
}

← Previous Back to AoC Index Next →