Advent of Code 2021 - Day 7, in Kotlin - The Treachery of Whales • Todd Ginsberg

I love the premise of today’s puzzle - we’re enlisting the help of a bunch of crabs in mini submarines to fend off a giant whale. I suspect that there’s some clever math trick we can use to get right to the answer we want, but I’m not the strongest mathematician so instead we’ll take a functional programming approach.

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

Problem Input

Like yesterday, today’s input is a single String with comma separated Ints representing the horizontal positions of the crabs. Because more than one crab can exist in any given horizontal position, there will be some duplication in this data. Since the amount of fuel does not vary by crab, only by the position of the crab, let’s store this data in a Map<Int,Int> where the key is the horizontal position of the crab and the value is how many crabs are at that position.

class Day07(input: String) {

    private val crabs: Map<Int, Int> = input.split(",").map { it.toInt() }.groupingBy { it }.eachCount()

}

We’ll use groupingBy and eachCount from the Kotlin standard library to do most of the work for us.

⭐ Day 7, Part 1

The puzzle text can be found here.

For part one, our strategy will be to figure out the entire range of horizontal positions, whether a crab currently sits there or not. This means we’ll have to pick out the smallest and largest horizontal positions and make an IntRange out of it. One might think we could call crabs.keys.indices because that returns an IntRange, but we’d be wrong about that. It turns out when we call crabs.keys, we get a Set<Int>, and the indicies function only creates an IntRange from 1 to the size of the set. While this might make sense in some contexts, it’s definitely not what we need today. So let’s wrote our own asRange() extension function on Set<Int>.

// In Day7

private fun Set<Int>.asRange(): IntRange =
    this.minOf { it }..this.maxOf { it }

We could make that extension function more generic I suppose, but we’ll use this for now and see if the need for something more generic comes up in a future Advent of Code. Now that we have the full range of horizontal positions, we can write a function to find the horizontal position that is the cheapest fuel-wise to move our crabs to.

// In Day7

private fun solve(fuelCost: (Int) -> Int): Int =
    crabs.keys.asRange().minOf { target ->
        crabs.map { (crab, crabCount) ->
            fuelCost((target - crab).absoluteValue) * crabCount
        }.sum()
    }

We want to be able to use this function for part two as well (spoiler: the only thing that changes is the fuel cost), so we’ll take a function fuelCost as an argument to our solve function. The fuelCost function take an Int as an argument representing the distance to travel, and returns an Int representing the fuel cost for that distance.

We start our solve function by getting the full range of horizontal spots to evaluate. We want the smallest one, so we’ll use minOf, which allows us to calculate the total cost for each target spot and take the smallest one. For each target, we want to calculate the cost of moving all of the crabs to that spot. This is where our fuelCost function comes in. We calculate the distance from our crab to the target and take the absoluteValue and pass it to our fuelCost function. We multiply that cost by the number of crabs we need to move. Summing these values gives us the cost to move all of the crabs to the target, and again, we take the smallest one via minOf.

Now we can solve part one:

// In Day7

fun solvePart1(): Int =
    solve { it }

Our fuelCost function isn’t all that exciting. Fuel costs 1 * distance in part one, so we can simply pass in it.

Star earned, onward!

⭐ Day 7, Part 2

The puzzle text can be found here.

Since we have most of what we need from part one, all we have to do for part two is to write ourselves a new distance function. Let’s look at the explanation of the formula in the puzzle text again:

Each change of 1 step in horizontal position costs 1 more unit of fuel than the last: the first step costs 1, the second step costs 2, the third step costs 3, and so on.

Aha! This is a summation of the integers between 1 and the distance. So if we want to go 3 steps, we’ll end up with 1 + 2 + 3 = 6. This means we have a couple of options.

We could declare an IntRange and call sum() on it:

// Example

(1 .. 3).sum() // 6

And that works fine. The issue with that is the sum() implementation iteratively adds all of the individual values in the IntRange. For small numbers this is fine but for large numbers it just wastes time.

Or we could take a mathematical shortcut:

// Example

n * (n-1) / 2  // Formula

3 * (3+1) / 2  // 6

This is a very handy formula for summing 1 to n, and I’ve run into it a number of tines not just in Advent of Code, but actual every day programming. This does the same thing as IntRange.sum() (assuming we have a range with no gaps), it just does it via calculation rather than summation.

Now that we know that, we can solve part two:

// In Day07

fun solvePart2(): Int =
    solve { distance ->
        (distance * (distance + 1)) / 2
    }

Star earned!

⭐ Day 7, Part 1

⭐ Day 7, Part 2

Further Reading