Sporifica Virus

Advent of Code 2017 Day 22

Try the simulator using your puzzle input!

Part 1

1. Another infinite-2D-grid puzzle!
2. Describing the ingredients of a hopefully working algorithm
3. Step-by-step
4. Testing on the example input
5. A small, but important, forgotten condition
6. Before revealing the answer, I want to simulate it!

Another infinite-2D-grid puzzle!

As per usual:

• Each tile changes based on some condition
• Orientation matters
• I'll need to track a specific type of tile change

Describing the ingredients of a hopefully working algorithm

• An infection burst counter
• A 2D array generated from the input
• A virus carrier location (a.k.a. current node) tracker
• An direction tracker
• Designation of a clean vs. infected node (a.k.a. . vs. #)
• A way to expand a particular side of the array by one tile if the current node is near or at an edge
• A way to correct the location of the current node when expanding the 2D array from the top or left edges
• A way to determine the nodes to the left and right, no matter the current node's facing direction
• A way to determine if the burst happened on an infected node
• A way to determine if the burst caused a clean node to become infected

It feels intimidating, but I've done a lot of this in similar puzzles.

Although, this feels like a complicated combination of lots of techniques.

Let's see if I can do it!

Step-by-step

Generate the grid

Split the input at each newline character
  Split each string at each character

Set the initial location of the current node

Create a 2-element array where:
  1. Half of the length of the grid, rounded down
  2. Half of the length of any array in the grid, rounded down

For a grid of length 3: [1,1]
For a grid of length 25: [12,12]

Display the grid with the location of the current node highlighted as per the illustrations in the instructions

For each row in the grid
  For each cell in the row
    Unless the cell is the current node
      Pad the cell with a space character on each side
    Otherwise
      Pad the cell with square brackets on each side
  Concatenate the modified cell values into one string
Join each line into one string, separated by newline characters

Success for the example input:

 .  .  # 
 # [.] . 
 .  .  . 

And success for my puzzle input:

Directions and rotation

List of relative coordinates based on direction of current node:

Adjusting the list of directions so the first element reflects the orientation of the recently rotated current node:

A summary of my subroutines thus far

• Rotate the list of directions so the current node's direction is at the first location
• Change the direction of the current node based on its state
• Change the contents of the current node based on its state, incrementing the infection burst count if the state changes from clean to infected
• Move the current node forward one toward its direction
• Render the grid, calling attention to the current node

Expand the grid whenever the current node as at an edge

If the current node is in any location marked *:

***
*.*
***

Expand the grid to resemble this:

.....
.***.
.*.*.
.***.
.....

My algorithm works like this...

1. The existing grid rows are expanded
2. A new grid is created with a new row at each end with the same number of cells as the existing grid rows

A visual depiction, for clarity:

Testing on the example input

Now that I've written a function to handle each step, it's time to test on larger and larger burst amounts using the example input, hoping to get the same numbers as referenced in the instructions!

Test results:

• After 7 bursts: success!
• After 70 bursts: success!
• After 10000 bursts: ERROR!
• After 1000 bursts: ERROR!

Uh-oh, what was happening?

A small, but important, forgotten condition

Several minutes of head-scratching later, I found my bug:

• When expanding the grid, I only checked whether the current node's row or column was the first
• I also needed to include the row or column being the last

Testing again:

• After 1000 bursts: no error!
• After 10000 bursts: success!

Before revealing the answer, I want to simulate it!

• I really want to see the answer appear after watching the example input and my puzzle input run in a simulator
• So, now I have to build one

...

Simulator: built!

What I saw after running it on the example input:

What I saw after running it on my puzzle input:

And, as expected, I generated the correct number of infection bursts!

Part 2

1. New rules and a performance test?!
2. Step-by-step...again
3. Testing on the example input

New rules and a performance test?!

• Four states instead of two!
• A reorientation rule for each state!
• Simulating 10M bursts (1000 times more than Part 1)

Based on the played out simulations from Part 1, the virus should eventually enter into a repeating cycle.

The trick will be to determine the burst number and cycle length so that I can extract it out to 10M.

But first, can I successfully re-factor my algorithm to run correctly under these new rules?

Step-by-step...again

Reorienting the current node

The new rules are:

[.] => Turn left
[W] => No change
[#] => Turn right
[F] => Turn left or right twice

Thankfully, that is a straightforward switch statement with four cases.

Toggling the current node's state

The rules and their single-letter symbols are now:

Clean nodes become weakened    [.] => [W]
Weakened nodes become infected [W] => [#]
Infected nodes become flagged  [#] => [F]
Flagged nodes become clean     [F] => [.]

Thankfully, that, too, is a straightforward switch statement with four cases.

Lastly, I updated my condition for incrementing the amount of infection bursts to account for a weakened node preceding an infection node.

Testing on the example input

Running my new algorithm for 100 bursts on the example input successfully generates 26 infection bursts!

Next, I need to update my simulator so I can see if the virus enters into a similar cycle.

Updating my simulator

• Since Part 2 requires 1000k times more iterations, I opted not to simulate each run, but to render the grid and infection bursts once all iterations have completed
• I expected the simulator to hang indefinitely given 10M iterations
• Much to my surprise, it finished within a second for both the example input and my puzzle input!

What I saw after 10M iterations for the example input:

What I saw after 10M iterations for my puzzle input:

Alas, it was the correct answer!

I did it!!

• I solved both parts!
• I made several GIFs to describe a few of my subroutines
• I built a simulator for both parts!

I'm grateful for this visual puzzle that wasn't the performance test I anticipated.

Just good, clean algorithmic fun!