## 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

- Collect all x coordinates, determine the maximum value. Do the same for y.
- 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

## Top comments (0)