Skip to Content

Advent of Code 2017 - Day 22, in Kotlin

Kotlin solutions to parts 1 and 2 of Advent of Code 2017, Day 22: 'Sporifica Virus'

Posted on

On Day 22 we a nasty infection in the form of another grid problem. If you’d rather jump straight to the code, it’s right here.

I’ve challenged myself to post each day’s solution to Github and blog about it. Like last year, I’m going to be solving these problems in Kotlin. I might go back and revise solutions, but I’ll be sure to annotate that fact in these posts.

Problem Input

We are given a set of input for this problem. I’ve loaded this into a List<String> called input, which we will do some further parsing on later.

Day 22, Part 1

Diagnostics indicate that the local grid computing cluster has been contaminated with the Sporifica Virus. The grid computing cluster is a seemingly-infinite two-dimensional grid of compute nodes. Each node is either clean or infected by the virus.

To prevent overloading the nodes (which would render them useless to the virus) or detection by system administrators, exactly one virus carrier moves through the network, infecting or cleaning nodes as it moves. The virus carrier is always located on a single node in the network (the current node) and keeps track of the direction it is facing.

To avoid detection, the virus carrier works in bursts; in each burst, it wakes up, does some work, and goes back to sleep. The following steps are all executed in order one time each burst:

If the current node is infected, it turns to its right. Otherwise, it turns to its left. (Turning is done in-place; the current node does not change.) If the current node is clean, it becomes infected. Otherwise, it becomes cleaned. (This is done after the node is considered for the purposes of changing direction.) The virus carrier moves forward one node in the direction it is facing. Diagnostics have also provided a map of the node infection status (your puzzle input). Clean nodes are shown as .; infected nodes are shown as #. This map only shows the center of the grid; there are many more nodes beyond those shown, but none of them are currently infected.

The virus carrier begins in the middle of the map facing up.

For example, suppose you are given a map like this:

..#
#..
...

Then, the middle of the infinite grid looks like this, with the virus carrier’s position marked with [ ]:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . # . . .
. . . #[.]. . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

The virus carrier is on a clean node, so it turns left, infects the node, and moves left:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . # . . .
. . .[#]# . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

The virus carrier is on an infected node, so it turns right, cleans the node, and moves up:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . .[.]. # . . .
. . . . # . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Four times in a row, the virus carrier finds a clean, infects it, turns left, and moves forward, ending in the same place and still facing up:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . #[#]. # . . .
. . # # # . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Now on the same node as before, it sees an infection, which causes it to turn right, clean the node, and move forward:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . # .[.]# . . .
. . # # # . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

After the above actions, a total of 7 bursts of activity had taken place. Of them, 5 bursts of activity caused an infection.

After a total of 70, the grid looks like this, with the virus carrier facing up:

. . . . . # # . .
. . . . # . . # .
. . . # . . . . #
. . # . #[.]. . #
. . # . # . . # .
. . . . . # # . .
. . . . . . . . .
. . . . . . . . .

By this time, 41 bursts of activity caused an infection (though most of those nodes have since been cleaned).

After a total of 10000 bursts of activity, 5587 bursts will have caused an infection.

Given your actual map, after 10000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.)

Another grid problem! This time it is unbounded, so we have to weigh our options. Approaches we could take:

  1. Create a massive grid that we couldn’t possibly overrun.
  2. Implement the grid as a List<List<Char>> and move all of the columns and rows if we run over the edges.
  3. Create a Node and create the neighbors when we need them.
  4. Store coordinates in a data class as a key to a map, and the value of the node as the value in the map.

I’m going to go with option 4, a map of coordinates. I feel 1 would work but uses a ton of memory for no real purpose (also, it will become impractical when we get to part two). Number 2 is impractical, expanding the grid on demand is too much work for too little gain. And number 3 is more difficult than it looks - if I need a new neighbor to the North, we have to make sure it links up with any of its existing neighbors.

So a map it is! Let’s define the key, an x/y Point. Sure, we could use Pair<Int,Int>, but this seems easier to read.

data class Point(val x: Int, val y: Int) {
    operator fun plus(that: Point): Point =
        Point(x + that.x, y + that.y)
}

The operator + will allow us to alter our location by means of an offset Point. I’m also going to define an enumeration for our node state. Originally I had just used true/false, but the question changes in part two and we’ll need this later:

enum class NodeState {
    Clean,
    Infected
}

We have enough to parse our input and set our starting point.

private val grid = parseInput(input)
private var current = Point(input.size / 2, input.first().length / 2)

private fun parseInput(input: List<String>): MutableMap<Point, NodeState> {
    val destination = mutableMapOf<Point, NodeState>()
    input.forEachIndexed { y, row ->
        row.forEachIndexed { x, char ->
            destination[Point(x, y)] = if (char == '.') NodeState.Clean else NodeState.Infected
        }
    }
    return destination
}

As with previous days, we have options when it comes to direction. I’m going to keep today nice and simple and just define the direction as an integer, and the offsets for turning/movement as a list of Point objects. I will also provide handy methods for turning left and right. I could have put these on Point, but I wanted to keep movement separated from location.

private val directions = listOf(Point(0, -1), Point(1, 0), Point(0, 1), Point(-1, 0))
private var pointing = 0

private fun left(): Int =
    if (pointing == 0) 3 else pointing - 1

private fun right(): Int =
    pointing.inc() % 4

The left and right functions just provide a new index into our directions list, taking care to not over or underflow.

Now we have everything we need to walk around on our grid and implement the core requirements:

fun solvePart1(iterations: Int = 10_000): Int {
    var infectionsCaused = 0
    repeat(iterations) {
        if (grid.getOrDefault(current, NodeState.Clean) == NodeState.Clean) {
            infectionsCaused += 1
            grid[current] = NodeState.Infected
            pointing = left()
        } else {
            // Infected
            grid[current] = NodeState.Clean
            pointing = right()
        }
        current += directions[pointing]
    }
    return infectionsCaused
}

For every iteration, we either are causing or cleaning up an infection, as well as moving. Movement is done by changing pointing to the offset we care about (left or right from the past one). We keep a counter of infectionsCaused and move after every turn.

Running this for 10,000 iterations takes about 15ms and earns us a star!

Day 22, Part 2

As you go to remove the virus from the infected nodes, it evolves to resist your attempt.

Now, before it infects a clean node, it will weaken it to disable your defenses. If it encounters an infected node, it will instead flag the node to be cleaned in the future. So:

  • Clean nodes become weakened.
  • Weakened nodes become infected.
  • Infected nodes become flagged.
  • Flagged nodes become clean.
  • Every node is always in exactly one of the above states.

The virus carrier still functions in a similar way, but now uses the following logic during its bursts of action:

Decide which way to turn based on the current node:

  • If it is clean, it turns left.
  • If it is weakened, it does not turn, and will continue moving in the same direction.
  • If it is infected, it turns right.
  • If it is flagged, it reverses direction, and will go back the way it came.
  • Modify the state of the current node, as described above.
  • The virus carrier moves forward one node in the direction it is facing.

Start with the same map (still using . for clean and # for infected) and still with the virus carrier starting in the middle and facing up.

Using the same initial state as the previous example, and drawing weakened as W and flagged as F, the middle of the infinite grid looks like this, with the virus carrier’s position again marked with [ ]:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . # . . .
. . . #[.]. . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

This is the same as before, since no initial nodes are weakened or flagged. The virus carrier is on a clean node, so it still turns left, instead weakens the node, and moves left:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . # . . .
. . .[#]W . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

The virus carrier is on an infected node, so it still turns right, instead flags the node, and moves up:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . .[.]. # . . .
. . . F W . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

This process repeats three more times, ending on the previously-flagged node and facing right:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . W W . # . . .
. . W[F]W . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Finding a flagged node, it reverses direction and cleans the node:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . W W . # . . .
. .[W]. W . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

The weakened node becomes infected, and it continues in the same direction:

. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . W W . # . . .
.[.]# . W . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

Of the first 100 bursts, 26 will result in infection. Unfortunately, another feature of this evolved virus is speed; of the first 10000000 bursts, 2511944 will result in infection.

Given your actual map, after 10,000,000 bursts of activity, how many bursts cause a node to become infected? (Do not count nodes that begin infected.)

See? I told you we’d need that enum. Let’s redefine it:

enum class NodeState {
    Clean,
    Infected,
    Weakened,
    Flagged
}

And while we’re at it, let’s provide a reverse() function to go along with left() and right():

private fun reverse(): Int =
    (pointing + 2) % 4

And now we can solve part two, which looks a lot like part one, but with more states:

fun solvePart2(iterations: Int = 10_000_000): Int {
    var infectionsCaused = 0
    repeat(iterations) {
        when (grid.getOrDefault(current, NodeState.Clean)) {
            NodeState.Clean -> {
                pointing = left()
                grid[current] = NodeState.Weakened
            }
            NodeState.Weakened -> {
                infectionsCaused += 1
                grid[current] = NodeState.Infected
            }
            NodeState.Infected -> {
                pointing = right()
                grid[current] = NodeState.Flagged
            }
            NodeState.Flagged -> {
                pointing = reverse()
                grid[current] = NodeState.Clean
            }
        }
        current += directions[pointing]
    }
    return infectionsCaused
}

This runs in only about 1.6 seconds for me, even with 10,000,000 iterations! That’s one more star for us.

I hope you had fun.

That makes 22 days and 44 stars with only 6 left to go! Only 3 days remaining!

Further Reading

  1. Index of All Solutions - All solutions for 2017, in Kotlin.
  2. My Github repo - Solutions and tests for each day.
  3. Solution - Full code for day 22.
  4. Advent of Code - Come join in and do these challenges yourself!
  5. Music to Code By - Tainted Love, by Soft Cell.