Trench Map

Advent of Code 2021 Day 20

Visualize the solution in your browser

Use this interactive visualization tool I made to see how this challenge's example input image is enhanced up to 10 times:

Solve for X where...

X == number of pixels lit after N number of image enhancements

Parts 1 and 2

1. N = 2
2. N = 50

That's the output. What's the input?

• A multi-line string
• Containing the characters # and .

What does the input represent?

Two things:

1. An algorithm for determining the lightness or darkness of the output 'pixel'
2. An original input image comprised of individual 'pixels'

How is the input image processed?

For each pixel in the input image
  Concatenate the values of all nine pixels that form a grid with the current pixel at its center - moving horizontally in order from top-left to bottom-right
  Coerce each value to its boolean equivalent: `0` for `.` and `1` for `#`
  Parse that 9-digit integer as a binary number to generate a base-10 integer between 0 and 512
  Look-up the character at the base-10 integer's index in the provided algorithm
  Re-assign the input pixel's value to the searched-for value

What's the catch?

Infinity!

• The full input image isn't relegated to what is provided in the challenge's input
• The solver needs to simulate a seemingly endless frame around the input image...starting with all . values
• Upon each enhancement, each of the frame's values must be updated, too, as if they're part of the image ### Simultaneously!
• When iterating through the input image's pixels, each subsequent check should refer to the image's state prior to any new output pixel changes
• The solver therefore must find a way to compare each 3x3 grid's values with those from a clone of the input image

Solving this puzzle one piece at a time

Piece 1: Duplicating an array and severing all links to the original array

How - in JavaScript at least - do you clone a 2D array...while ensuring that any changes to the original array or cloned array don't affect the other?

let arr1 = [[0,1,0],[1,0,1],[0,1,0]];
let arr2 = arr1; // Nope. Just a reference.
let arr2 = arr1.slice(); // Not quite. Too shallow.
let arr2 = Array.from(arr1); // Same as previous. Too shallow.
let arr2 = arr1.map(nestedArray => nestedArray.slice()); // Yup!

Piece 2: The 3x3 grid of values per pixel

This became a fun research project to find eloquent solutions for a common problem:

• Traverse each adjacent index in a 2D array
• Account for indices at the edges and corners

In essence, treat each index as (0,0) and get the values at:

(-1,-1)(-1, 0)(-1, 1)
( 0,-1)( 0, 0)( 0, 1)
( 1,-1)( 1, 0)( 1, 1)

I opted to use this algorithm:

Once, at the start of the program
  Store all nine coordinates in a list
At the start of each enhancement
  Pad the input image area by an extra row and column on each side
Loop through each index, starting from the 2nd row and column and ending at the 2nd to last row and column
  Update each pixel's value to the one resulting from this calculation:
    Loop through each position-relative coordinate in the stored reference list
      Look-up the value from the cloned image in the position corresponding to the row whose index equals the sum of: the pixel's row index and the value in the first position of the current iteration's coordinate from the stored reference list...and the column who index equals a similar sum, but using the value in the second position
    Concatenate those nine values into one string
    Parse that string as a binary number to generate a base-10 integer between 0 and 512
    Look-up and return the character at the base-10 integer's index in the provided algorithm

It seems like a lot. But it's only about four - albeit long - lines of JavaScript.

The most eloquent solution I found for this algorithm is in this paste by JavaScript solver Topaz

Piece 3: Blink and you'll miss it!

The 512-character string algorithm used to enhance each pixel has a hidden secret:

• Foregoing all but the first and last characters, it looks like this: #....

Why is that significant?

Because given that the image should technically 'extend for infinity' - with all dark pixels . at first - then the frame around the center of the image is filled with this pattern:

...    ...    ###
... -> .#. -> ###
...    ...    ###

• That becomes 000000000 in binary and 0 in base-10.
• Which means the . in the center will become #, the character at index 0 in the algorithm.
• Which means that every pixel framing the center of the input image will switch between . and # after each enhancement

Here's a visualization of that blinking in effect after each image enhancement:

How do we account for this in our algorithm?

Store the number of times we want to enhance the image
  Increment that number by one, for reasons described below
Store the number of enhancements complete, starting at 0

Sub-routine:
Prepare the image for enhancement by applying an appropriately-sized frame of dark pixels
  Re-assign to the input image a mutated copy where:
    X new rows - where x is the current number of times remaining - of equal columns are added before all current rows and after
      Each new row is filled with items whose value is:
        The value stored in the variable storing the number of completed enhancements, subtracted from 1: starts at 0, then `1 - 0 = 1`, then `1 - 1 = 0`, etc.
        If it is 0, use `.`
        Else - it is 1 - use `#`
    X new columns - where x is the current number of times remaining - are added to each row - including originals and new ones
      Same as above: each new column is assigned the appropriate value `.` or `#`

Core loop:
While the image still needs to enhance (times > 1):
  Clone the input image
  Enhance the input image by referencing each pixel in the cloned image
  Update the enhancements completed tracker to equal 1 minus the current value, in essence toggling between `0` and `1`
  Slice off the no-longer-relevant framing pixel rows and columns
    Remove rows and columns from the enhanced image:
      Starting from the row or column equal to `times` - 1`
      Ending at the row of column equal to `its length - (times - 1)`
  Generate new framing rows and pixels
  Decrement times by 1

I hope this diagram offers more clarity of the padding process:

For those who read everything, or skipped straight here

• This puzzle was a beast

• I struggled several times, across a few days: traversing adjacent indices in a 2D array, duplicating a 2D array correctly, discovering and accounting for the blinking pattern, building a tool to configure the number of enhancements and run the algorithm manually

• I persevered.

• I correctly solved both parts.

• I built a fun tool to visualize what I accomplished.

• I wrote this article to reflect on the entire experience.

I think it's time for a brief break from AoC to give my brain a rest.

See you in the next one!