Discussion on: AoC Day 2: Inventory Management System

[Jon Bristow]

I lost about 10 minutes to my son stalling getting into bed.

Kotlin Solution

Answer 1

Once again a fairly straightforward opener. Just run through, do some simple frequency checking and spit back the results. I think this is technically O(n²⁾ but it moved fast enough for me. (And in a more lazy language, it ends up being closer to O(n) anyway)

fun String.frequencies(): Map<Char, Int> =
        groupBy { it }.mapValues { (_, v) -> v.count() }

fun answer1(input: List<String>) =
    input.map {
        val freqs = it.frequencies()
        freqs.anyValue(2::equals) to freqs.anyValue(3::equals)
    }
        .unzip().toList()
        .map { bs -> bs.count { it } }
        .fold(1, Int::times)

Answer 2

As Ryan said, this is just Hamming distance with the added wrinkle that you need to throw away the differences while counting them. Lots of optimization room here, but once again, we shave off just under half the possibilities by only doing unique combinations and going from a raw n^2 to (n*(n+1))/2.

At around 10 ms (calculated by shuffling my input 1000 times), I don't think there's an easy way to make this noticeably faster at this point without a more esoteric method.

fun <A, B> List<A>.cartesian(transform: (A, A) -> B): Sequence<B> {
    return init.asSequence().mapIndexed { i, a ->
        drop(i + 1).asSequence().map { b ->
            transform(a, b)
        }
    }.flatten()
}

fun <A> Pair<A, A>.same() = first == second
fun <A> Pair<A, A>.different() = first != second

fun answer2(input: List<String>) =
    input.cartesian { s1, s2 ->
        s1.zip(s2)
    }.find { // find short circuits on Sequence
        it.count(Pair<Char, Char>::different) == 1
    }?.filter {
        it.same()
    }?.joinToString("") { it.first.toString() }