Jurassic Jigsaw
Tags: adventofcode, programming, algorithms, computerscience
Published: 2022-03-11 16:00:21

## [Advent of Code 2020 Day 20](https://adventofcode.com/2020/day/20)

## [Try the simulator!](https://aocjurassicjigsaw.rmion.repl.co/)
![Simulator of Parts 1 and 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jb1s583293b6avmmaxe9.gif)

## Task: Solve for X where...
Part 1
```
X = the product of the four ID numbers of the four identified corner tiles
```
Part 2
```
X = the number of # characters that are not part of a sea monster pattern
```

### Example input
```
Tile 1234:
..##.#..#.
##..#.....
#...##..#.
####.#...#
##.##.###.
##...#.###
.#.#.#..##
..#....#..
###...#.#.
..###..###

...more tiles
```

It represents:
- Several small square image tiles that combine to form a larger square image

## Part 1: Finding the corner tiles
1. Describing how I would do that manually
2. Writing a working algorithm
3. Building a simulator

### Describing how I would do that manually
- There are four corner tiles
- Each corner tile will only have 2/4 matched sides
- Each tile may require rotating or flipping to properly align with its adjacent tiles

Parsing each tiles' four sides
```
Tile 1234:

    Side 1
  ..##.#..#.
  ##..#.....
S #...##..#. S
i ####.#...# i
d ##.##.###. d
e ##...#.### e
  .#.#.#..##
4 ..#....#.. 2
  ###...#.#.
  ..###..###
    Side 3

Due to the rotation and flipping caveat...

Side 1's match could be:
..##.#..#. or .#..#.##..

Side 2's match could be:
...#.##..# or #..##.#...

Side 3's match could be:
..###..### or ###..###..

Side 4's match could be:
.#####..#. or .#..#####.
```

Finding a match for any given side assuming there is only one  side from one other tile that will be a match. (This process gets more complicated if more than one side of more than one tile are a match.)
```
Compare the current side's string - both directions - with each of the four sides of each of the other input tiles
  If we find a match
    Record the tile name and side
    Break
  Else - there is no match
    Record the lack of match
```

Analyze the tiles for the four corner pieces
```
If a tile has 0 unmatched sides, it is an inner piece
If a tile has 1 unmatched side, it is an edge piece
If a tile has 2 unmatched sides, it is a corner piece
```

Multiply the IDs of the four corner tiles to determine the correct answer to Part 1.

### Writing a working algorithm
- Yuck: It feels brute-force-y
- Gross: It has tons of loops
- Cool: It continually mutates the same array
- Sweet!: It generates the correct answer for the example input and my input!

```
Split the input at each pair of new line characters to create an array of tile strings

Split each tile string at the new line character to change the string into an array of strings

Change each array of strings into an array with two elements:
  1. A string that stores the tile's 4-digit ID
  2. An array that stores four strings: each string representing the ordered set of . or # characters for a tile's four sides

Change each two-item array into an array with two elements:
  1. A string that stores the tile's 4-digit ID
  2. An array that stores the existence of - or lack thereof - a matching side from another tile...for each side of each tile

Change the array to only contain a subset of its items
  Where the second element - the array of four values - has, after filtering it for non-existent matches, only two items

Return the product of each of the remaining four values' number-coerced ID
```

Here's a visualization of how my algorithm works
![Algorithm visualization for Part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lnhbnpzy1lzvu8r2upa3.gif)

### Building a simulator
- The setup is similar to Giant Squid Bingo
- I opted to perform every side check in each iteration, instead of performing one side per iteration
- It's fun to watch each tile's sides update, and four of the tiles change to green when two sides are not a match

It helped me spot an error in my script:
- I was reminded of how JavaScript's `map` array method works: it operates on each item in the initial, unchanged array...and only at the end returns the changed array

[Try the simulator!](https://aocjurassicjigsaw.rmion.repl.co/)
![Simulator of Part 1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/eizwmlb6f851focs6oyn.gif)

## Part 2: Failing to piece it all together
1. Rotating and flipping arrays
2. Trying to arrange the pieces correctly
3. Admitting defeat while celebrating accomplishments

### Flipping and rotating arrays of strings
```
Flip vertically:
Reverse the array

Flip horizontally:
Split each string into an array
  Reverse the array
    Concatenate each element into a string

Rotate counter-clockwise:
For each string in the array
  Return a new string that is the concatenation of each character at the location in each string matching the index of the current string

Rotate clockwise:
For each string in the array
  Return a new string that is the concatenation of each character at the location in each string - of a reversed array - matching the index of the current string
```

### Trying to arrange the pieces correctly
- My algorithm got 'out-of-hand' rather quickly

```
Store an ordered list of each parsed tile
Store an ordered list of each pairing of tile ID and it's matching sides as calculated from Part 1
Store the size of the image by calculating the square root of the length of the list of tiles
Create two arrays of matching dimensions:
  1. To eventually hold each properly oriented tile array
  2. To eventually hold each tile id in its proper slot

Pick any of the four corner tiles to place in the top-left slot of the both grid arrays
  While it's top and left sides are not both marked as 'No match'
    Rotate it clockwise
    Shift the side instructions array such that the last item is moved to the front

For each row in the grid
  For each column in the row
    If in the top row:
      If proceeding to the right in the same row:
        Look-up the id of the tile to the left
        Store its matching tile from the list of tiles
        While its top side is not marked as 'No match'
          Rotate the tile clockwise
          Shift the side instructions array such that the last item is moved to the front
        If the characters along the right edge of the tile to the left don't match up with the characters along the left edge of the current tile
          Flip the current tile vertically
        Add the current tile and its id to the respective grid arrays
    If in the left-most column and not in the top row:
      Look-up the id of the tile above
      Store its matching tile from the list of tiles
      While its left and bottom sides are not marked as 'No match'
        Rotate the tile clockwise
        Shift the side instructions array such that the last item is moved to the front
      If the characters along the bottom edge of the tile above don't match up with the characters along the top edge of the current tile
        Flip the current tile horizontally
      Add the current tile and its id to the respective grid arrays
```

That's as far as I got.
- Using the example input as test, I couldn't get past correctly orienting the tile in the bottom-left corner such that the tile upcoming to the right would be correct
- I was about to go down if...else hell

## Admitting defeat while celebrating accomplishments
- 1/2 parts solved
- 1 working simulator built for Part 1
- Practice writing array rotation and flipping algorithms
- Having enough persistence to nearly fill in the image grid programmatically
- Troubleshooting my sloppy code enough to recognize the importance of elegant code

I'll find you one day, sea monsters!

## UPDATED: Part 2 Retry: Success!
1. Picking up where I left off
2. Jigsaw formed, now to find the sea monsters
3. Found them!...but not enough of them. Huh?
4. Building the simulator a.k.a. Part 3

### Picking up where I left off
- I couldn't stop thinking about this puzzle
- I created small paper tiles to simulate the example input
- Doing this helped me see that my algorithm must not have been far off
- I needed to carefully analyze my code and re-write where necessary

Here's what I needed my tile orientation and placing algorithm to do:
```
Setup algorithm:
Create an array to store the parsed tile strings
Complete Part 1 again to attain an array mapping each tile's side to between two and four other tiles' sides
Determine the full image's width/height by calculating the square root of either array
Create two more arrays:
  1. To store correctly placed and oriented tile strings in a multi-dimensional array
  2. To store the IDs of each correctly placed tile in a multi-dimensional array
Pick one of the four corner pieces - it doesn't matter which -  from the array mapping tile sides
Shift the elements in its side mapping array until the elements marking 'No match' are in locations 1 and 4 - the slots representing its top and left sides
Add an element to both of the new arrays:
  1. The tile string to the first array in the first nested array
  2. The ID to the first string in the first nested array
Create two legends:
  1. When attempting to align the next right-adjacent tile's known matching side with the recently placed tile, refer to an array mapping the side to the number of necessary clockwise moves to perform
  1. When attempting to align the next bottom-adjacent tile's known matching side with the recently placed tile, refer to an array mapping the side to the number of necessary clockwise moves to perform

Image-building algorithm:
Do as many times as the image is tall
  Do as many times as the image is wide
    As long as the current cell is not in the left-most location:
      Look-up the id of the tile in the cell to the left
      Look-up that tile's newly-shifted right-matching side
      Look-up the corresponding tile string
      Rotate the tile string clockwise - and shift its matching sides array - according to the legend until its identified matching side is in location 4 - representing left - of it's matching sides array
      If the strings of this tile's left side and the left adjacent tile's right side are reversed:
        Flip the tile's string vertically
        Swap the matching side array elements at locations 1 and 3 - top and bottom
      Add an element to both multi-dimensional arrays:
        1. The tile string of this tile
        2. The ID of this tile
    As long as the current cell is in the left-most location, and not in the top row:
      Look-up the id of the tile in the cell to above
      Look-up that tile's newly-shifted bottom-matching side
      Look-up the corresponding tile string
      Rotate the tile string clockwise - and shift its matching sides array - according to the legend until its identified matching side is in location 1 - representing top - of it's matching sides array
      If the strings of this tile's top side and the top adjacent tile's bottom side are reversed:
        Flip the tile's string horizontally
        Swap the matching side array elements at locations 2 and 4 - right and left
      Add an element to both multi-dimensional arrays:
        1. The tile string of this tile
        2. The ID of this tile
```
And here's a visualization of the setup and image-building algorithm:
![Visualization of larger tile formation algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qga2ilfct5pawmenkwc6.gif)

Lastly, I needed to combine and crop each element in the newly-populated tile string array.

Here's that single, highly-method-chained operation in JavaScript
```js
image.map(row => row.map(tile => {
        return tile.slice(1, 9).map(line => line.slice(1,9))
      })).map(row => row.reduce((accumulator, current) => {
        current.forEach((line, index) => {
          accumulator[index] += line
        })
        return accumulator
      }, Array(8).fill(null).map(el => '')).flat(1)).flat(1)
```

### Jigsaw formed, now to find the sea monsters
Per the instructions, I needed to search a string-concatenated copy of my newly-crafted image for each instance of the following pattern:
```
                  # 
#    ##    ##    ###
 #  #  #  #  #  #   
```

This, to me, meant dabbling in my most uncomfortable computer science topic: Regular Expressions.

Thankfully, tools like [RegExr](https://regexr.com) make this process fun, insightful, and educational.

Here is the RegEx I created and used to solve this puzzle:
```
/.*(?<head>.{18}#.).*\n.*(?<body>#.{4}##.{4}##.{4}###).*\n.*(?<feet>.#.{2}#.{2}#.{2}#.{2}#.{2}#.{3}).*/g
```

I spent a long time researching ways to use `replaceAll`s optional function argument to help me complete my task.

Sadly, I couldn't find a way to update each of the three captured groups from my RegEx individually using that method and its function.

Instead, I had to do it manually. Very manually.

For example, let's say my RegEx finds a sea monster in this sub-string, from the example input
```
Searched this:
.#.#...#.###...#.##.##..
#.#.##.###.#.##.##.#####
..##.###.####..#.####.##

Matched this:
                    #   
  #    ##    ##    ###  
   #  #  #  #  #  #     
```

My objective was to programmatically find the locations of each sea monster hash within those three lines and replace each one with some other non-period character.

To do that, I had to:
```
Calculate the indexed location of the hash in the second line of the pattern, since it represents the left-most character in the pattern - and is therefore a reliable left edge
Use that number to create reference points for the first and third lines of the pattern from which to start
Additionally, store all three indexed first locations of the strings within which all three lines of the pattern reside - to know how far from which to indent
Furthermore, store the width of each line - since it now includes a new line character

Replace the joined string representing the image using a series of substring concatenations which craft a new string by joining each fragment of the most recent string with Os replacing each of the 18 characters in the matched sea monster pattern
```

### Found them!...but not enough of them. Huh?
Good news and unexpectedly bad news:

#### Good news:
- Running this algorithm on the example input produces the correct answer: 273

#### Bad news:
- Running this algorithm on my input produces an incorrect answer which is 'too high'

Per the instructions:
`you might need to rotate or flip your image before it's oriented correctly to find sea monsters`

This led me to assume that for all but one orientation of the image, there would be 0 matched sea monster patterns.

Wrong.

As I soon found out, some orientations may include a few sea monster patterns.

One orientation, however, will have substantially more.

#### Even worse unexpected news:
- My RegEx wasn't finding every match
- If there was any overlap among two patterns - meaning somewhere among the three lines of one match is one or more lines of another match elsewhere horizontally in the string - it would only match one

My terrible solution, given my lack of experience with RegEx?
- Run the RegEx a few times on the image string in hopes of finding all matches

So, I wrapped my RegEx algorithm in a loop that arbitrarily runs three times.

And Viola! Correct answer generated...as long as I pre-, manually-oriented my image string correctly.

### Building the simulator a.k.a. Part 3
My expectations for this simulator:
1. Run Parts 1 and 2 automatically in sequence from one button click
2. Include the slider to adjust the simulator's processing speed
3. For Part 2, offer buttons for the user to re-orient the image string
4. Each time one of those buttons is pressed, simulate the progressive rendering of each line of the processed image
5. Don't show the original image, but rather show only the sea monsters
6. Track the smallest identified number of hash characters found among each of the re-oriented and processed image strings - the answer to Part 2

I got all but #2.

That's ok, though.

Because I discovered a memory leak in my tactic for offering users a speed slider.

Sadly, I was unable to fix the leak:
- I couldn't successfully use `clearInterval` to stop and destroy the interval that continually runs once started

Instead - and for this simulator only thus far:
- I removed the slider
- I hard-coded an interval delay that's not too fast and not too slow
- I added a button to 'Jump to the end' - it runs a loop for the remaining necessary iterations, clears and destroys the interval, and sets the stage for Part 2

## It's time to move on. This time standing proud!
- My algorithms for both parts is ~230 lines long
- My JavaScript for the simulator is ~500 lines long

I spent half a week on this puzzle
- Part 1 took 1 day to solve and simulate
- Part 2 took 1 day to solve and simulate
- Showing my work took 2 days to write

Thankfully, it was an exciting ride, the most challenging puzzle thus far, and the coolest simulator I've build thus far.

## [Try the simulator!](https://aocjurassicjigsaw.rmion.repl.co/)
![Simulator of Parts 1 and 2](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jb1s583293b6avmmaxe9.gif)