Kotlin

Part 1 had me assuming, like a lot of other folks, that Part 2 would be a simple weighted graph. So I coded Part 1 as a non-weighted graph and it was great.

Part 2 looked simple enough, but different. Part 1 was breadth first, I assumed depth first would work for Part 2. When it worked great on the test input, but took 12 seconds, I knew I was in trouble. So I added caching. And it was super quick on the test input.

Real input was a whole 'nother story. I watched my system resources balloon. At last count it was using 8GB of RAM before I killed it. And that was before solving even the first line.

So I went online to find what I’m missing to see people saying it’s a linear algebra problem, and that it’s best to use some kind of library for it.

I will admit that I leaned pretty heavily on asking Gemini questions to figure out how to use the Google OR-Tools library.

So here’s my Part 2 code:

import com.google.ortools.Loader
import com.google.ortools.linearsolver.MPSolver
import com.google.ortools.linearsolver.MPVariable
import utils.*

fun main() {
    val input = getInput(10)
    val machines = parseInput1(input)
    Loader.loadNativeLibraries()
    var total = 0
    for (machine in machines) {
        val buttons = machine.buttons
        val joltages = machine.joltages
        val solver = MPSolver.createSolver("SCIP") ?: throw Exception("Could not create solver")
        val x = arrayOfNulls<MPVariable>(machine.buttons.size)
        for (i in buttons.indices) {
            x[i] = solver.makeIntVar(0.0, Double.POSITIVE_INFINITY, "x$i")
        }
        val target = joltages.map { it.toDouble() }
        val aMatrix = joltages.indices.map { joltageToArray(it, buttons) }.toTypedArray()
        for (j in joltages.indices) {
            val ct = solver.makeConstraint(target[j], target[j], "joltage_constraint_$j")
            for (i in buttons.indices) {
                ct.setCoefficient(x[i], aMatrix[j][i])
            }
        }
        val objective = solver.objective()
        for (i in buttons.indices) {
            objective.setCoefficient(x[i], 1.0)
        }
        objective.setMinimization()
        val resultStatus = solver.solve()
        if (resultStatus == MPSolver.ResultStatus.OPTIMAL) {
            val result = objective.value().toInt()
            total += result
        } else {
            println("Problem could not be solved.")
        }
    }
    println(total)
}

data class Machine(val configuration: List<Boolean>, val buttons: List<List<Int>>, val joltages: List<Int>)

fun parseInput1(input: String): List<Machine> {
    return input.lines()
        .filter { it.isNotBlank() }
        .map {
            val split = it.split(" ")
            val configuration = split.first().toCharArray()
                .slice(1..<split.first().length - 1)
                .map { char ->
                    when (char) {
                        '#' -> true
                        else -> false
                    }
                }
            val buttons = split.slice(1..<split.size - 1)
                .map { str ->
                    str.slice(1..<str.length - 1)
                        .split(",")
                        .map { number -> number.toInt() }
                }
            val joltages = split.last()
                .slice(1..<split.last().length - 1)
                .split(",")
                .map { number -> number.toInt() }
            Machine(configuration, buttons, joltages)
        }
}

fun joltageToArray(joltageIndex: Int, buttons: List<List<Int>>): Array<Double> {
    val array = DoubleArray(buttons.size) { 0.0 }.toTypedArray()
    for (i in buttons.indices) {
        if (joltageIndex in buttons[i]) {
            array[i] = 1.0
        }
    }
    return array
}