Sporifica Virus
Tags: adventofcode, algorithms, computerscience, programming
Published: 2022-07-21 12:32:42

## [Advent of Code 2017 Day 22](https://adventofcode.com/2017/day/22)

## [Try the simulator using your puzzle input!](https://aocsporificavirus.rmion.repl.co/)
![Simulator running on my puzzle input](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4srft7dnvytpeyr5cxhl.gif)

## 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:
![Correctly displaying the initial state of the map](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4b1752n3umzo812rol2z.png)

#### Directions and rotation
List of relative coordinates based on direction of current node:
![Generating relative coordinates](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zujsz9oklptylu77dytm.gif)

Adjusting the list of directions so the first element reflects the orientation of the recently rotated current node:
![Performing the rotation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j7fhey43r8tq47kktu2p.gif)

#### 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:
![Grid expansion algorithm](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/32ieklznkc2m7lim71bk.gif)

### 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:
![Example puzzle input processed](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/32sy77t57okqj6m3xpsk.png)

What I saw after running it on my puzzle input:
![My puzzle input processed](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vle8rfhl2qqcydijci3o.png)

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:
![10 million bursts later](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/t5pdbcxmgp02ndahfdmw.png)

What I saw after 10M iterations for my puzzle input:
![10 million bursts later](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sxo9q59zob5hylwvz1rt.png)

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](https://aocsporificavirus.rmion.repl.co/) for both parts!

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

Just good, clean algorithmic fun!