# Advent of Code 2021 - Day 6, in Kotlin - Lanternfish

Kotlin solutions to parts 1 and 2 of Advent of Code 2021, Day 6: 'Lanternfish'

Posted on

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:

:)

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!