Planet of Discord

Advent of Code 2019 Day 24

Try the simulator of Part 1 using your puzzle input!

Task: Solve for X where...

Part 1

X = the biodiversity rating for the first layout that appears twice

Part 2

X = the number of bugs present after 200 minutes

Example input

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

It represents:

• A scan of the area of Eris
• # are bugs
• . are empty spaces

Part 1

1. Another one of these puzzles, eh?
2. Generating the array of increasing powers of two
3. Checking adjacent cells and queuing the cells to switch
4. Tracking each step's state
5. Setup, main loop and output
6. Troubleshooting because I misread the instructions
7. Building the bugs' life simulator

Another one of these puzzles, eh?

You know the type:

• Area of tiles
• Each with two or more possible states
• Each one queued up to change based on adjacent tiles
• Then change the queued tiles
• Identify the first state that repeats

What's novel about this one:

• The method of scoring takes into account an equation based on the location of certain tiles
• That should only require a look-up after the first duplicate state is identified

Generating the array of increasing powers of two

Create an array of length 25 (5x5)
  Fill it with values equal to the two to the power of the current index: 2^0, 2^1, 2^2, ...

Checking adjacent cells and queuing the cells to switch

I'll use a list of relative coordinates, as in other puzzles:

* = originating cell
A: (-1, 0)
B: ( 0, 1)
C: ( 1, 0)
D: ( 0,-1)

Visual:
.A.
D*B
.C.

A written description of the algorithm:

Using the current cell's coordinates:
  For each relative coordinate
    As long as the coordinate relative to the current cell is a valid location in the grid (not outside its bounds)
      Return true if the value in that cell is a bug
      Return false if the value in that cell is empty
  Calculate the sum of true values
  Queue the cell up as one to switch if:
    The current cell contains a bug, and the sum is 1
    The current cell is empty, and the sum is 1 or 2

Tracking each step's state

• By now, I've learned that comparing arrays - even with all equal values - will always return 'false', at least in JavaScript
• In lieu of that, I will store a binary number derived from a concatenation of 0s and 1s coerced from #s and .s from the most recent state of the switched area

For example:

Initial state:
....#
#..#.
#..##
..#..
#....

As a string:
....##..#.#..##..#..#....

As 0s and 1s:
0000110010100110010010000

As binary:
1658000

Setup, main loop and output

Setup:
Replace #s with 1s and .s with 0s in the input
Split the input at each newline character into an array of strings
  Split each string into an array of characters
    Coerce each character into a number: 0 or 1
Create ratings, an array of 25 powers of 2, starting at 1
Create the array of 4 relative coordinates
Create an array, states, and add to it the binary number representing the initial state of my puzzle input

Main loop:
Repeat until manually escaped via a condition:
  Create an empty queue
  For each row in the parsed grid of tiles
    For each column in the row
      Set bugs to the result of the following operations:
        For each of the four relative coordinates
          If there is no cell there, return false
          Else, if there is a cell there
            Return true if the cell has a bug
            Return false if the cell is empty
        Filter the updated list of four booleans to only include true values
        Return the number of true values
      Add the current cell's coordinates to the queue if it matches the criteria for switching a cell's value as described earlier
  For each queued coordinate
    Update the value of the appropriate cell to its opposite state: bug or empty
  Generate a binary number from the new state of the grid as described earlier
  If the tracked list of states includes this binary number
    Add the new binary number as the last item in states
    Escape the main loop
  Else, if this binary number is not in the tracked list of states
    Add the new binary number as the last item in states

Output:
Using the last binary number in states
  Convert it to a stringified decimal
  Pad the beginning with 0s until the string has 25 characters
  Split the string into an array of characters
  For each character
    Accumulate a sum - starting at 0 - according to the following operations
      If the current character is 1
        Increment the sum by the number in ratings at the same location as the current character's location in its array

Return the sum

Troubleshooting because I misread the instructions

Earlier, I referenced this criteria:

  Queue the cell up as one to switch if:
    The current cell contains a bug, and the sum is 1
    The current cell is empty, and the sum is 1 or 2

The first if is wrong. It should be:

    The current cell contains a bug, and the sum is NOT 1

That took a bit longer to find and fix than I liked.

But I found it. And I fixed it.

And I generated the correct answer!

Building the bugs' life simulator

• I felt like it had been ages since I built a simulator, but it had only been a few days
• I sensed this would be a simple one to build
• I wanted to render the bugs, the applicable ratings, and the sum of applicable ratings for each minute

Try the simulator of Part 1 using your puzzle input!

Part 2

Great: a drastically more difficult puzzle

• That is usually the case when - for me, at least - Part 1 seems relatively easy
• Enter: Callback to Part 2 of Day 20
• Enter: Recursion
• Enter: Infinity
• In other words: intimidation += 10000
• In other words: no thanks

Celebrating my accomplishments

• I solved Part 1!
• I built a simulator for Part 1!
• I practiced converting strings to binary and back again
• I was reminded of how important it is to carefully read instructions

Bummer:

• I gave up immediately on Part 2 out of intimidation of the presumed algorithmic complexity

Intcode finale, here I come!