Advent of Code 2021 - Day 6, in Kotlin - Lanternfish • Todd Ginsberg

There’s something fishy about this puzzle! If we have these exponentially spawning fishies, how come we haven’t solved world hunger with them? How come they haven’t fully taken over the ocean? How come their numbers haven’t crashed because there are too many of them competing for food? What do all the other fishies think of these lanternfish moving into their underwater neighborhoods and taking up all the good spots?

By the way, this line from the puzzle kills me:

Although you know nothing about this specific species of lanternfish, you make some guesses about their attributes.

If you’d rather just view code, the GitHub Repository is here .

Strategy

Sure, we could go do what the puzzle text tells us to do and simulate every individual fish. This will actually work for part one (I tried!) but won’t work for part two unless you have a lot of memory and a lot of patience. Therefore, we’ll need a more clever solution. If you think about it, we don’t really need to simulate every fish, do we? For example, all of the fishies that will give birth two days from now are identical. They create a specfic number of identical offspring fishies. So we know we can possibly keep the count of how many fishies there are per offspring-cycle-day. And since there are only nine days at most in the entire cycle, we don’t have to keep track of much. We just have to keep track of how many fishies we have on each offspring-day. If we rotate through this array of fishies and add offspring where appropriate, we should be able to solve this without a lot of memory or time being spent.

I’ll explain more below in part one.

Problem Input

Our input is a single String with comma separated values. Let’s do something different and parse them each into a LongArray.

class Day06(input: String) {

    private val fishiesPerDay: LongArray = parseInput(input)

    private fun parseInput(input: String): LongArray =
        LongArray(9).apply {
            input.split(",").map { it.toInt() }.forEach { this[it] += 1L }
        }
}

Our LongArray is constructed in such a way that the index into the array represents time, and the value represent the number of fishies that create offspring on that day.

For example, the input from the sample puzzle for part one is 3,4,3,1,2. That means we have 1 fish on day 1, 1 fish on day 2, 2 fish on day 3, and 1 fish on day 4. After parsing that would look like: [0, 1, 1, 2, 1, 0, 0, 0, 0].

⭐ Day 6, Part 1

The puzzle text can be found here.

In order to implement our logic, we’re going to need to rotate our LongArray. Meaning - take the first element and make it the last element, and move all of the other elements down by 1. So if we have [1, 2, 3] and we rotate that array left, we’d end up with [2, 3, 1]. We’ll add an extension function on LongArray to handle this.

// In Day06

private fun LongArray.rotateLeftInPlace() {
    val leftMost = first()
    this.copyInto(this, startIndex = 1)
    this[this.lastIndex] = leftMost
}

Because the first element in the array is going to be overwritten, we need to set it aside in leftMost. Then we have the LongArray copy over itself with copyInto starting with the element in slot 1, by specifying startIndex. Finally to complete the rotation we add leftMost back into the array a the lastIndex (such a handy thing!).

Now that we can rotate our time-based fishy array, we can use that to simulate an entire day lanternfish life:

// In Day06

private fun simulateDays(days: Int): Long {
    repeat(days) {
        fishiesPerDay.rotateLeftInPlace()
        fishiesPerDay[6] += fishiesPerDay[8]
    }
    return fishiesPerDay.sum()
}

We’ll use the repeat function to run our logic for a given number of days. For each day, we’ll rotateLeftInPlace our fishy array, having the effect of advancing time by one day. This has the effect of moving the day-0 fish to become day-8 fish (because array spot 0 rotates around to spot 8). But where do the offspring come from? Since these lanternfish are fungible (No, not you little lanternfish who might be reading this, you are unique, the rest of them are fungible), we don’t really care which fishes are in the day-8 slot and which are in the day-6 slot, so we are going to add all of the day-8 fishies to the day-6 fishes, representing the new generation.

To help visualize, here’s what our array looks like during a simulated day in which we create a single offspring:


// Before - 1 fish about to have 1 offspring
fishiesPerDay = [1,0,0,0,0,0,2,0,3]  

// Rotate - 1 fish in the final slot = new offspring, they have 8-day cycles initially
fishiesPerDay = [0,0,0,0,0,2,0,3,1] 

// Add back parents - 1 fish added to slot 6 for the parents, they have 6-day cycles
fishiesPerDay = [0,0,0,0,0,2,1,3,1] 
                             ^   ^
                             |   +--------- offspring
                             |
                             +------------- parents

Now we can solve part one of our puzzle:

// In Day07

fun solvePart1(): Long =
    simulateDays(80)

Star earned! Onward!

⭐ Day 6, Part 2

The puzzle text can be found here.

Since we wrote everything we needed in part one for part two, there’s not much excitement to be found here:

// In Day06

fun solvePart2(): Long = 
    simulateDays(256)

I did get curious and figured out that with my input, anything more than 433 days of simulation would roll a Long back over to negative numbers. The maximum value for a Long in Kotlin is 9,223,372,036,854,775,807. That’s a lot of lanternfish! At that point, we’d have to reimplement our algorithm to use an Array<BigInteger> rather than a LongArray.

One more note on this, you could probably just as easily implement this with a List or an ArrayDeque. I had originally done the work using a Map and then realized I was over-complicating it. But a Map totally works if you are willing to shuffle the indexes around.

Star earned!

⭐ Day 6, Part 1

⭐ Day 6, Part 2

Further Reading