Module aoc::year2017::day21

Fractal Art

The image size starts at 3x3, growing exponentially to 18x18 after 5 generations and 2187x2187 after 18 generations. The first insight to solving efficiently is realizing that we don’t need to compute the entire image, instead only the count of each pattern is needed. Multiplying the count of each pattern by the number of set bits in each pattern gives the result.

The second insight is that after 3 generations, the 9x9 image can be split into nine 3x3 images that are independent of each other and the enhancement cycle can start over. Interestingly most of the 3x3 patterns in the input are not needed, only the starting 3x3 pattern and the six 2x2 to 3x3 patterns.

Adding a few extra made up rules:

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

then using the example:

    .#.    #..#    ##.##.    ###|.#.|##.
    ..# => .... => #..#.. => #.#|###|#..
    ###    ....    ......    ###|.#.|...
           #..#    ##.##.    ---+---+---
                   #..#..    .#.|##.|##.
                   ......    ###|#..|#..
                             .#.|...|...
                             ---+---+---
                             ##.|##.|#.#
                             #..|#..|.#.
                             ...|...|#.#

Splitting the 9x9 grid results in:

    1 x ###    2 x .#.    5 x ##.    1 x #.#
        # #        ###        #..        .#.
        ###        .#.        ...        #.#

The enhancement cycle can start again with each 3x3 image. This means that we only need to calculate 2 generations for the starting image and each 2x2 to 3x3 rule.

Structs

• Pattern 🔒

Functions

• parse
• part1
• part2
• three_by_three_permutations 🔒
  Generate an array of the 8 possible transformations possible from rotating and flipping the 3x3 input.
• to_index 🔒
  Convert a pattern slice of ones and zeroes to a binary number.
• two_by_two_permutations 🔒
  Generate an array of the 8 possible transformations possible from rotating and flipping the 2x2 input.