DEV Community

Cover image for Planet of Discord
Robert Mion
Robert Mion

Posted on

Planet of Discord

#adventofcode #algorithms #computerscience #programming

Advent of Code 2019 Day 24

Try the simulator of Part 1 using your puzzle input!

Simulator for Part 1

Task: Solve for X where...

Part 1 

X = the biodiversity rating for the first layout that appears twice
Enter fullscreen mode Exit fullscreen mode

Part 2 

X = the number of bugs present after 200 minutes
Enter fullscreen mode Exit fullscreen mode

Example input 

....# #..#. #..## ..#.. #....
Enter fullscreen mode Exit fullscreen mode

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, ...
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

The first if is wrong. It should be:

 The current cell contains a bug, and the sum is NOT 1
Enter fullscreen mode Exit fullscreen mode

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!
Simulator for Part 1

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!

Top comments (0)