Fractal Art

Advent of Code 2017 Day 21

Try the simulator using your puzzle input!

Part 1

1. Seems familiar...
2. Algorithm sub-task: Split an array into sections
3. Algorithm sub-task: Generate all possible stringified variations
4. Algorithm sub-task: Match each section with an enhancement rule
5. Algorithm sub-task: Voltron! (a.k.a. combine all sections back into a single square)
6. Fingers crossed: putting together all the pieces

Seems familiar...

• A 2D array of .s and #s as on or off
• A need to rotate or flip arrays to match some pattern
• An end goal of revealing some image, perhaps?

Traveling backwards through Advent of Code works to my advantage here!

Because I successfully solved both parts of 2020 Day 20: Jurassic Jigsaw!

And, as part of that, I wrote four utility functions that work on a 2D array of strings:

• Flip horizontally
• Flip vertically
• Rotate clockwise
• Rotate counter-clockwise

I'm so grateful to my past self that I persevered in writing those functions.

Algorithm sub-task: Split an array into sections

In each iteration, I must break the pixels into 2x2 or 3x3 squares.

For example, break this array:

#..#
....
....
#..#

Into these arrays:

#. .#
.. ..

.. ..
#. .#

How might I do this?

• With nested for loops
• And a gradually filled 2D array
• Where each nested array is either 2- or 3-elements in length

Create an empty array
For i from 0 to the square size, incrementing i by 2 or 3
  For j from 0 to the square size, incrementing j by 2 or 3
    Add to the array a 2D array where each array is the same length as the square size
      And the characters in each cell correspond to the cell the proper number of spaces to the right and then below the current cell
Return the array

Hopefully this animation better explains how it works:

Algorithm sub-task: Generate all possible stringified variations

The puzzle input is a list of enhancement rules:

../.# => ##./#../...
.#./..#/### => #..#/..../..../#..#

In each iteration to enhance the photo, each sub-section must be matched with a rule.

To make things more complicated, the sub-section may require rotating or flipping to match a rule.

My approach to accounting for this?

• Process each enhancement rule into a dictionary
• Where the keys are the resulting larger square
• And the values are Set()s storing all possible variations of the originating, smaller square

This requires the use of two of my four array rotation and flipping functions mentioned earlier.

In particular:

• Rotate clockwise
• Flip vertically

I could have picked any one from each of the rotation and flipping functions.

In addition, I must be able to convert strings to arrays...and back!

Convert string to array:

Split the string at each slash character
  Split each string at each character

Convert array to string:

For each array in the array
  Join all characters into a single string
Join each string with a slash character

Putting it all together:

Process the puzzle input into a list containing 2-element arrays
  Element 1 is one variant of the pattern to be matched
  Element 2 is the resulting larger square pattern

For each 2-element list
  Accumulate a list with two dictionaries
    The first will store all 2x2 square patterns
    The second will store all 3x3 square patterns
  Store into the appropriate dictionary a key that is the second element's string, where the value is the result of the following operations:
     Create an empty unique set of values
     Do as many times as the area of the square
       Convert the string into an array
       Rotate the array clockwise
       Convert the array into a string
       Add the string into the unique set if not already there
       If the current iteration is divisible by 4
         Convert the string into an array
         Flip the array vertically
         Convert the array into a string
         Add the string into the unique set if not already there
     Set the value equal to the now-filled unique set of strings

For the example input, the algorithm above generates this list of dictionaries:

[
  { '##./#../...': 
      Set(4) {
      '../#.', '#./..', '.#/..', '../.#'
      } 
  },
  {
    '#..#/..../..../#..#': 
      Set(8) {
      '#../#.#/##.',
      '##./#.#/#..',
      '###/..#/.#.',
      '..#/#.#/.##',
      '.#./#../###',
      '###/#../.#.',
      '.##/#.#/..#',
      '.#./..#/###'
      }
  }
]

When running the same algorithm on my puzzle input, I noticed several Sets only included 1 or 2 strings.

That alarmed me.

However, upon closer inspection, I noticed the strings were:

../..
###/#.#/###

No matter how you flip or rotate those strings as arrays, there will only ever be one variant.

Now I feel confident I can:

• Generate a list of all variants one time for use in each iteration
• Avoid trying to match 3x3 square strings when the square I'm checking is 2x2
• Divide the art into smaller squares
• Identify the correct enhancement rule for each square

Now that I can identify the correct enhancement rule, I need to match it to each section's string.

Algorithm sub-task: Match each section with an enhancement rule

I'm referring to an algorithm that turns these:

#. .#
.. ..

.. ..
#. .#

Into these:

##.  ##.
#..  #..
...  ...

##.  ##.
#..  #..
...  ...

How my algorithm works:

For each section
  Generate a stringified version of the array
  Determine which of the two dictionaries to reference: 2x2 or 3x3 patterns
  Initialize a match as empty
  For each key in the proper dictionary
    If any of the strings in the set of values associated with that key match the stringified section array
      Update match to reflect the key associated with the matching string
  Overwrite the section with the array-itized string

Hopefully this animation better explains how it works:

I think the last task prior to writing a main loop is to re-combine all enhanced squares into one.

Algorithm sub-task: Voltron! (a.k.a. combine all sections back into a single square)

I'm referring to an algorithm that turns these:

##.  ##.
#..  #..
...  ...

##.  ##.
#..  #..
...  ...

Into this:

##.##.
#..#..
......
##.##.
#..#..
......

This took some serious critical thinking from me.

Surprisingly - though, not in hindsight - the two algorithms I made are very similar to the two slicing algorithms above.

• With nested for loops
• And a gradually filled 2D array
• Where each nested array is N-elements in length, where N equals the length of the fuller list (a multiple of 2 or 3)

Create an empty array
For i from 0 to the square size, incrementing i by the square root of the square's size
  For j from 0 to the square size, incrementing j by the square root of the square's size
    Add to the array a concatenation of the following strings
      If a multiple of 2:
        Current row and column merged with next row, same column
      If a multiple of 3:
        Current row and column merged with next row, same column, merged with next row, same column
Return each string joined with a slash character

It all feels simultaneously eloquent and spaghetti-like.

But, at least with a few tests, it appears to work!

The big question is:

• Will it get me through at least 5 rounds of enhancement?

Fingers crossed: putting together all the pieces

In a nutshell, my algorithm must:

Do 5 times
  1. Divide the array into 2x2 or 3x3 squares
  2. Match each square to an enhancement rule
  3. Merge each larger, enhanced square
  4. Convert the merged string into an array in preparation for the next iteration

I had to add a condition to account for the very first iteration, as it's the only one that must avoid step 3.

Otherwise, steps 1, 2 and 4 went smoothly.

Step 3 didn't seem to work correctly on iteration 5 only.

To be clear:

• 3x3 to 4x4 - success (after adding the condition)
• 4x4 to 6x6 - success
• 6x6 to 9x9 - success
• 9x9 to 12x12 - success
• 12x12 to 18x18 - successful...enough...for now

To generate the correct answer for Part 1, I just needed the number of pixels left on after 5 iterations.

Luckily, my algorithm could successfully generate that number.

Although my algorithm failed to generate the correct enhanced image from 12x12 to 18x18, the contents of the enhanced image were correct:

• I could safely tally the amount of # in the incorrectly proportioned image to generate the correct answer

After writing a nested reduce() algorithm, I had the count.

Viola! Part 1 solved!

Part 2

1. I've got to get this to work, dammit!
2. Building the simulator

I've got to get this to work, dammit!

• As expected, I must identify why my algorithm fails to properly enhance the 12x12 square
• Because, by golly!, I must complete 18 enhancements!

Fast forward to hours later where I finally figured it out!

My merging algorithms naively hard-coded the number of smaller squares to concatenate together.

This sufficed up to - but not including - the 12x12 image:

• 4x4 generates 4 2x2 squares that become 2 columns of 3x3 squares
• 6x6 generates 6 2x2 squares that become 3 columns of 3x3 squares
• 9x9 generates 9 3x3 squares that become 3 columns of 4x4 squares
• 12x12 generates 36 2x2 squares that become 6 columns of 3x3 squares

I needed to ensure that my merging algorithms always accounted for the proper number of columns, so that they correctly stitched together each row of the smaller squares into the correctly-sized row of the larger square.

I got it to work!!

I eventually discovered a working equation.

Even better, it allowed me to re-factor my two malfunctioning merging algorithms into one flexible merging algorithm!

Building the simulator

• To celebrate all the above effort, I knew I had to build one
• Thankfully, it didn't take long
• The result isn't as visually stimulating as I hoped
• But knowing it generates the correct answers is incredibly fulfilling

Try the simulator using your puzzle input!

I did it!!

• I solved both parts!
• I wrote so many algorithms!
• I persisted, and eventually discovered and fixed my errors!
• I made a few GIFs that visually depicted how my smaller algorithms work!
• I built a simulator that displays each enhanced image!
• I can't believe I finally did it!

It took hours to realize where I was miscalculating a few important counters.

But, eventually, I figured it out.

This puzzle and it's counterpart - 2020 Day 20 - will forever hold special, infamous places in my brain and heart...for being devilishly satisfying algorithmic puzzles that I......eventually......solved!