Transparent Origami

Advent of Code 2021 Day 13

Try the simulator

Solve for X where:

X = an eight-letter code

Input is:

• A multi-line string

It represents

• A list of x,y coordinates that each represent dots on a sheet of paper
• An ordered list of folding instructions

Folding instructions?

• Each instruction 'folds' an imaginary piece of paper in half along either the x or y axes
• After each fold, the coordinate area is halved
• Once the final fold is done, the overlapping dots will be arranged in a pattern that spells out eight uppercase letters

...#..#..#.   #.##.|#..#.   #####   O
....#......   #...#|.....   #...#
...........   .....|#...#   #...#
#..........   #...#|.....   #...#
...#....#.#   .#.#.|#.###   #####
...........   .....|.....   .....
........... ^ .....|.....   .....
----------- |
........... |    <<---
........... |
.#....#.##.
....#......
......#...#
#..........
#.#........

Initial algorithm challenges

• Determining the width and height of the 'paper'
• Performing each 'fold'

Width and height

1. Collect all x coordinates, determine the maximum value. Do the same for y.
2. Remember that each fold is at the midpoint, so each side's length must be the value of the first fold for each axis...doubled...plus 1: midpoint of array length 5 is 2: 2 * 2 + 1 = 5;

Performing each 'fold' with terrible time and space complexity

Setup:
  Create a 2D array
  Fill it with `.` to indicate transparent cells
  For each coordinate, update the corresponding cell's value in the array  to `#` to indicate a dot

Fold:
  If instruction is to fold vertically, bottom-over-top:
    For each row in the array (below the fold line)
      For each cell in the row
        If the value in the cell equally far from - and on the opposite side of - the fold line has a #:
          Continue
        Else if it has a . and the value in this cell has a #:
          Replace the cell's value with this one's
    Copy the array, including only the first half of rows
  If instruction is to fold horizontally, right-over-left:
    For each row in the array
      For each cell in the row (right of the fold line)
        If the value in the cell equally far from - and on the opposite side of - the fold line has a #:
          Continue
        Else if it has a . and the value in this cell has a #:
          Replace the cell's value with this one's
    Copy the array, including only the first half of cells in each row

This did not generate a correct answer for my input.

I couldn't think of any other algorithms to generate an answer even to Part 1: determine the number of dots on the page after a single fold.

The brief search for an eloquent solution

• As soon as I saw JavaScript solver Pandicon's solution, I smacked my head in shame for not seeing it earlier!

Forget about width and height

We don't need to know the width and height of the paper to solve this!

Forget about tracking 2D arrays

We can just perform in-place updates of the correct coordinate in each of our pairs based on the instruction axis!

• Each fold is the same N operations, no matter what the width or length of the imaginary sheet of paper is
• After the final fold, the paper size will be small enough to include eight capital letters formed from a series of dots, so it will 'cost' nothing at all to render

Performing a fold the smart way

If the fold is along the x axis (right over left):
  If the x coordinate is greater than the midpoint's value:
    Update the x coordinate's value to the difference of:
      The midpoint's value and
      The absolute value of the result from subtracting:
        The x coordinate's value from the midpoint's value

If the fold is along the y axis (bottom over top):
  If the y coordinate is greater than the midpoint's value:
    Update the y coordinate's value to the difference of:
      The midpoint's value and
      The absolute value of the result from subtracting:
        The y coordinate's value from the midpoint's value

It seems complex, but is simply expressed like this:

target_xy = (this_xy > coord) ? coord - Math.abs(coord - this_xy) : target_xy

Watching paper fold in real-time

• After solving Part 2 of the puzzle, I discovered that the code spans 6 rows and 40 columns
• I wanted to build a web app that could accept any puzzler's input and perform the necessary folds one step at a time
• It would display only the top-left 6 rows and 40 cells within those rows
• With each fold, more and more # would appear as a result of dots appearing from a fold
• By the final fold, the code would reveal itself to the user

Try the simulator

Lessons learned

• Stop attempting to solve puzzles so literally. Instead think critically about the least necessary information needed in each step
• Look for clues in the instructions for game area sizes. Then think twice about whether that even matters!
• A handy formula for finding a cell that is equidistant from the current one relative to a midpoint