Subterranean Sustainability

Advent of Code 2018 Day 12

Try the simulator using your puzzle input!

Task: Solve for X where...

Part 1

X = the sum of the numbers of all pots which contain a plant after N generations, where N = 20

Part 2

X = the sum of the numbers of all pots which contain a plant after N generations, where N = 50000000000

Example input snippet

initial state: #..#.#..##......###...###

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

It represents:

• The initial state of a row of small pots
• Only the pots immediately to my right
• . are empty pots
• # are filled with plants
• Notes about how these plants spread to nearby pots

Part 1

1. A single-axis infinite grid puzzle
2. Parsing the input into a string and a dictionary
3. Trying to generate the full list of notes for the example input
4. My pot-padding algorithm
5. My pot-checking algorithm
6. Calculating the score and noticing a huge detail I overlooked

A single-axis infinite grid puzzle

• I've become familiar with infinite grid puzzles
• The ones where the puzzle input is a small subset of a boundless area of pre-filled values
• However, all prior puzzles have used two or three of the following dimensions: length/width, height, depth
• This seems like the first one that only uses one dimension: length

To illustrate, for a puzzle input like this:

#..##....

Zooming out reveals a larger area for growth:

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

• The .s continue forever in both directions
• It is foolish to check each ., since there are infinite numbers
• But it is also foolish to only ever check the pots featured in my puzzle input, since pots nearby might match one of the notes about how plants spread

Parsing the input into a string and a dictionary

Split the input at the double-newline character into two arrays: init and notes
Update init to become the result of splitting itself at the pair of characters ': ', then keeping the second element of the two-element array
Update notes to become the result of the following operations:
  Split the string at each newline character into an array of strings
  For each string, accumulate an object with an increasing amount of key-value pairs
    Split the string at the group of characters ' => ' into a two-element array
      Create a key in the accumulating object using the first element string, and set as its value the second element's string

Trying to generate the full list of notes for the example input

The provided example input's notes are truncated to only include the notes that produce plants:

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

Thankfully, the instructions also include the first 20 generations for that example input.

From that, I feel like I can deduce the notes that kill plants.

Let's try!

Initial state, zoomed out a bit:

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

After one generation, with asterisks marking killed plants:

...#...#....#.....#..#..#..#...........
      * *  *       **    **
      1 2  3       45    45

Each note follows this pattern:

LLCRR => N

That means these notes must exist...right?

..#.# => . 1
#.#.. => . 2
..##. => . 3
..### => . 4
.###. => . 5

Solidifying my knowledge:

• I can't go left-to-right an update each character when it matches a note
• I must queue up each flagged changing pot so that I don't modify the state within one generation

Comparing generation one to two:

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

No plants were killed, only produced.

Comparing generation two to three:

...##..##...##....#..#..#..##..........
..#.#...#..#.#....#..#..#...#..........
   *   *    *              *
   1   1    1              1

That means these notes must exist...right?

..##. => . 1

Yup! That was #3 earlier!

Comparing generation three to four:

..#.#...#..#.#....#..#..#...#..........
...#.#..#...#.#...#..#..##..##.........
  * *      * *            
  1 2      1 2

That means these notes must exist...right?

..#.# => . 1
#.#.. => . 2

Yup! Those were #1 and #2 earlier!

Still only 5 identified plant killing notes.

Comparing generation four to five:

...#.#..#...#.#...#..#..##..##.........
....#...##...#.#..#..#...#...#.........
   * *      * *         *   *
   1 2      1 2         3   3

These are numbered according to the original five notes.

Comparing generation five to six:

....#...##...#.#..#..#...#...#.........
....##.#.#....#...#..##..##..##........
        *    * *          
        3    1 2

Comparing generation six to seven:

....##.#.#....#...#..##..##..##........
...#..###.#...##..#...#...#...#........
    **   *           *   *   *
    36   2           3   3   3

A new note:

.##.# => . 6

Here's the list thus far:

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

• No new notes 7-8
• No new notes 8-9

Comparing generation nine to ten:

...##..#..#####....#...#...#...#.......
..#.#..#...#.##....##..##..##..##......
            ?

A new note:

##### => . 7

Here's the list thus far:

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

Comparing generation 10 to 11:

..#.#..#...#.##....##..##..##..##......
...#...##...#.#...#.#...#...#...#......
             ?

A new note:

#.##. => . 8

Here's the list thus far:

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

Glancing through the remaining generations for the example, I think I've identified all kill notes...at least to re-create 20 generations with an algorithm using the example input.

Here is what I think was the full example puzzle input:

initial state: #..#.#..##......###...###

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

My pot-padding algorithm

My puzzle input features this note:

...#. => #

The example input and my input have an initial state where the first pot has a plant:

#...

I'll have to extend my puzzle input's initial state in order to address pot -1:

...#...
  *

So, I could extend the input by 3 unplanted pots on each end.

But that wouldn't cover these notes:

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

So, I should extend the input by 4 unplanted pots on each end.

But...every time?

Well, the above notes would turn this:

....#
  *

Into this:

..#.#

So, to account for the note again, I just need to extend by 2:

....#.#
  *

Perhaps to avoid over-extending my input unnecessarily, I could check whether the first location of a plant is at or after location 3 (index 2), and the last location of a plant is at or before the third to last location.

I'm anxious to see how this logic pans out.

My pot-checking algorithm

For each pot, starting at the pot three in from the left-most end and stopping at the pot three in from the right-most end
  Create an empty list to queue up the pots that must change
  If the dictionary of notes contains a key that matches the five characters in the substring of pots with the current pot as the center
    Add to the list of pots that must change an array with two elements: 1) the location of this pot; 2) the type of pot it should become (the value associated with the matched key)
Split the pots string at each character into an array of characters
For each queued up pot requiring a change
  Update the character in the saved location of the temporary array of pots so that it matches the saved pot type
Update pots to reflect the re-joined string of updated characters from the temporary array
If there is a plant in the pot three in from any side, add two empty pots to that side

Calculating the score and noticing a huge detail I overlooked

• I thought the score was the number of plants among the pots after 20 generations
• I was wrong
• I then thought the score was the accumulated number of plants from each generation
• I was wrong again
• Finally, I realized the score is the sum of all numbered positions for each of the plants among the pots after 20 generations

Yikes! That means I have to keep track of where pot 0 is in my array of characters that grows from both ends!

In my algorithm, my puzzle input initial state resembles this:

0
#.........

I insert four empty pots to the left of pot 0:

-4   0
 ....#.....

Whenever the pot three in from the left gets a plant, like this:

-4-2 0
 ..#.#.....

I add two more empty pots to the left-most edge:

-6     0
 ....#.#.....

• As long as I set some variable to -4 before processing generation 0...
• and decrement that variable by 2 any time I insert two more empty pots to the left-most edge
• then I should have the number of the pot at the left-most edge by the time the 20th generation arrives

And if I have the number of the left-most pot, then I can calculate the sum like this:

For each character in an array created from splitting the pots string at each character
  Accumulate a sum - starting at 0
    If the character is a # - indicating a plant
      Increment the sum by the sum of the index of the current character and the pot number of the left-most pot

The results:

• It generated the correct answer for the example input
• It generated the correct answer for my input, too!

Building a simulator in preparation for Part 2

• I saw what I needed to in my console
• But I figured it would be no trouble to simulate the first 20 generations
• And it might be helpful if Part 2 requires simulating more generations and finding a pattern

Try the simulator using your puzzle input!

Part 2

1. Just as I thought: a test of repeatability to predict a far off generation
2. Which generation is that? Ok, now count!
3. Some light arithmetic to generate the correct answer

Just as I thought: a test of repeatability to predict a far off generation

• The 50-billionth generation? Woah!
• Much like with the lumberyard puzzle, it seems I have to find some cycle in the plant spreading that I can carry out toward 50 billion
• I could start by letting my simulator run for a while

Which generation is that? Ok, now count!

• I see that the plants eventually stop spreading
• But my simulator doesn't count the generations or display the sum for each step
• I need to know which generation to stop my algorithm at, and see the sum

After updating my simulator, I get my answers:

• The sum is still increasing...why?
• Oh, because the pots with plants shifts one to the right each generation
• So, the sum will increase at a static integer amount each generation because the number of each planted pot grows by 1

What's that static integer?

201 generation:  16188
200 generation: -16113
                ------
                    75

Some light arithmetic

• Each generation, the sum grows by 75
• After generation 200, the sum is 16113

I need to solve for X:

X = 16113 + (75 * (50000000000 - 200))

According to my calculator:

X = 3750000001113

• Copy
• Paste
• Submit
• Two gold stars!

I did it!!

• I solved both parts!
• I made a simulator that revealed the pattern for Part 2!

What a fun infinite-expanding-area-themed puzzle!