Super weak. Do better.

Endowments drive me insane. They don’t get used to do anything. Just giant dragon hoards.

My alma mater could probably give half a million people free tuition by using its endowment, and they have the gall to beg me for donations and I’m still paying off my loans.

Oh, so the Green party got a constitutional amendment?

Has it done anything?

Kotlin

Looking at the puzzle, I knew that I had no clue how to solve it. So I came here to see if I was missing something or if there were any hints.

And the hint I saw was to do the simplest check possible, so I gave it a shot.

And that got the test input wrong, but I ran it against the real input anyway just to see if it was right. And it was.

I think if I had gone on my instincts and just tried to solve this, I could have gone around in circles for hours or days trying to get it right.

fun main() {
    val input = getInput(12)
    val (gifts, regions) = parseInput1(input)
    var total = 0
    for (i in regions.indices) {
        val totalAreaOfGifts = regions[i].gifts.mapIndexed { index, count -> count * gifts[index].area }.sum()
        if (totalAreaOfGifts <= regions[i].area) {
            total++
        }
    }
    println(total)
}

data class Gift(val shape: List<List<Char>>, val area: Int)

data class Region(val width: Int, val height: Int, val area: Int, val gifts: List<Int>)

fun parseInput1(input: String): Pair<List<Gift>, List<Region>> {
    val gifts: MutableList<Gift> = mutableListOf()
    val regions: MutableList<Region> = mutableListOf()
    val lines = input.lines()
    lines.forEachIndexed { index, line ->
        if (line.contains(":")) {
            if (line.contains("x")) {
                val split = line.split(" ")
                val shape = split.first().replace(":", "").split("x")
                val width = shape.first().toInt()
                val height = shape.last().toInt()
                regions.add(
                    Region(
                        width,
                        height,
                        width * height,
                        split.slice(1..<split.size).map { str -> str.toInt() })
                )
            } else {
                var nextBlankLineIndex = 0
                for (i in index + 1..<lines.size) {
                    if (lines[i].isBlank()) {
                        nextBlankLineIndex = i
                        break
                    }
                }
                val shape = lines.slice(index + 1..<nextBlankLineIndex).map { it.toCharArray().toList() }
                val area = shape.flatten().filter { it == '#' }.size
                gifts.add(Gift(shape, area))
            }
        }
    }
    return gifts to regions
}

The results speak for themselves.

I won’t be commenting further as this is an obvious waste of time.

That’s rich from a party running a decades long proven losing strategy.

I have criticisms of the Republican party, too. But since I’m not willing to roll up my sleeves, join them, and change them from the inside, those criticisms are null and void in your eyes.

For The Green Party, no, I’m not a fan. For the reasons I’ve outlined.

Yes, Jill Stein has no chance with the current system, exactly my point.

But in smaller, more local races, The Green Party could gain seats all over the country. Just like the DSA does.

The Green Party doesn’t interest me.

Yeah, you did pull it out of thin air.

Not naming it Furball Space Agency feels like a missed opportunity.

She’s worse than that. She wastes her party’s limited resources on fruitless (counter productive even) presidential campaigns for personal clout.

If she was serious, and not a complete fraud, she’d be putting her effort into smaller campaigns all over the country to build the party up.

I think I got pretty lucky that the Java library I used was pretty straightforward and had good docs.

This was definitely an unfulfilling way to solve a puzzle. I did take linear algebra in college, but I really struggled in that class and retained none of it.

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
}

Kotlin

This was substantially easier than yesterday’s problem. Especially considering I still haven’t done Part 2 from yesterday.

Anyway, here is my Part 2 solution for today. Given how quickly Part 1 ran without a cache, I didn’t think Part 2 would be much different, until my computer fans spun up and stayed there for over a minute. So I added a cache and re-ran it and it ran in 31ms.

const val end = "out"
var map: Map<String, List<String>>? = null
val problemVertices = "dac" to "fft"
val cache: MutableMap<Pair<String, Pair<Boolean, Boolean>>, Long> = mutableMapOf()

fun main() {
    val input = getInput(11)
    map = parseInput1(input)
    val total = countPaths2("svr", false to false).first
    println(total)
}

fun countPaths2(vertex: String, problemVerticesEncountered: Pair<Boolean, Boolean>): Pair<Long, Pair<Boolean, Boolean>> {
    val otherVertices = map!![vertex]!!
    var total = 0L
    val nextProblemVerticesEncountered =
        (problemVerticesEncountered.first || vertex == problemVertices.first) to (problemVerticesEncountered.second || vertex == problemVertices.second)
    for (otherVertex in otherVertices) {
        val key = otherVertex to nextProblemVerticesEncountered
        if (cache.contains(key)) {
            total += cache[key]!!
        } else if (otherVertex == end) {
            if (nextProblemVerticesEncountered.first && nextProblemVerticesEncountered.second) {
                total++
            }
        } else {
            total += countPaths2(otherVertex, nextProblemVerticesEncountered).first
        }
    }
    cache[vertex to nextProblemVerticesEncountered] = total
    return total to nextProblemVerticesEncountered
}


fun parseInput1(input: String): Map<String, List<String>> = input.lines()
    .filter { it.isNotBlank() }
    .associate {
        val split = it.split(": ")
        split[0] to split[1].split(" ").toList()
    }

To pick nits, cloud computing isn’t over hyped. It is really, actually cool and useful.

Now saying that you have to use AWS, Azure, or whatever other cloud provider is dumb. But the tech used in cloud computing really is the future.

My desktop OS is built with the same tech and it’s amazing.

Edit: and I do a bunch of self hosting with cloud tech.

And now I want to play Dwarf Fortress again.

95%+ of you would be leaving massive, massive performance on the table by using Linux

Pulling numbers out of thin air.

Also, I’m not seeing the “massive” here. But I’m not someone who sweats about framerates as long as they’re stable and above 60fps. I have always been a mid-spec player.

Those Nvidia numbers aren’t great, but in general, fuck Nvidia. They are getting better about their drivers, and the performance on Linux will continue to get better.

But me, I’m happy gaming on Linux, and so are lots of folks.

Kotlin

My solution can’t be very good because it took over a minute to run part 2. I used a ray casting algorithm to determine if a point was in the main polygon. I did that for the 2 corners of each rectangle that weren’t given as input. If both of those corners were in the polygon, then I checked each point of each edge of that rectangle.

My first stab at this didn’t consider the edge points of the rectangle, and after looking at some visualizations of the polygon, I could see where I was going wrong. I wouldn’t have considered a rectangle with all 4 corners in the polygon could have an edge that goes outside the polygon without looking at a visualization.

Part 2 code:

fun main() {
    val input = getInput(9)
    val polygon = parseInput1(input)
    val rectangles: MutableList<Rectangle> = mutableListOf()
    for (i in polygon.indices) {
        for (j in i + 1..<polygon.size) {
            rectangles.add(Rectangle(polygon[i], polygon[j]))
        }
    }
    rectangles.sortByDescending { it.area }
    var answer: Rectangle? = null
    for (rectangle in rectangles) {
        if (isInsidePolygon(rectangle.corner3, polygon)
            && isInsidePolygon(rectangle.corner4, polygon)
        ) {
            val edgePoints: MutableList<Pair<Long, Long>> = mutableListOf()
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner1, rectangle.corner4))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner3))
            edgePoints.addAll(getAllPointsBetween(rectangle.corner2, rectangle.corner4))
            var isInside = true
            for (edgePoint in edgePoints) {
                if (!isInsidePolygon(edgePoint, polygon)) {
                    isInside = false
                    break
                }
            }
            if (isInside) {
                answer = rectangle
                break
            }
        }
    }
    println(answer?.area ?: "Whoops")
}

fun parseInput1(input: String): List<Pair<Long, Long>> = input.lines()
    .filter { it.isNotBlank() }
    .map {
        val split = it.split(",")
        split[0].toLong() to split[1].toLong()
    }

data class Rectangle(val corner1: Pair<Long, Long>, val corner2: Pair<Long, Long>) {
    val corner3: Pair<Long, Long> = corner1.first to corner2.second
    val corner4: Pair<Long, Long> = corner2.first to corner1.second
    val area: Long = (1 + abs(corner1.first - corner2.first)) * (1 + abs(corner1.second - corner2.second))
}

fun isInsidePolygon(point: Pair<Long, Long>, polygon: List<Pair<Long, Long>>): Boolean {
    val x = point.first
    val y = point.second
    var intersectionCount = 0L
    for (i in polygon.indices) {
        val p1 = polygon[i]
        val p2 = polygon[(i + 1) % polygon.size]
        if (point == p1 || point == p2 || isOnEdge(point, p1, p2)) {
            return true
        }
        val y1 = p1.second
        val y2 = p2.second
        val crossesRay = (y in y1..<y2) || (y in y2..<y1)
        if (crossesRay) {
            val x1 = p1.first
            val x2 = p2.first
            val xIntersect = (x2 - x1) * (y - y1).toDouble() / (y2 - y1) + x1
            if (x < xIntersect) {
                intersectionCount++
            }
        }
    }
    return intersectionCount % 2L != 0L
}

fun isOnEdge(p: Pair<Long, Long>, p1: Pair<Long, Long>, p2: Pair<Long, Long>): Boolean {
    val crossProduct = (p.second - p1.second) * (p2.first - p1.first) -
            (p.first - p1.first) * (p2.second - p1.second)
    if (crossProduct != 0L) {
        return false
    }
    val isBetweenX = p.first in minOf(p1.first, p2.first)..maxOf(p1.first, p2.first)
    val isBetweenY = p.second in minOf(p1.second, p2.second)..maxOf(p1.second, p2.second)
    return isBetweenX && isBetweenY
}

fun getAllPointsBetween(left: Pair<Long, Long>, right: Pair<Long, Long>): List<Pair<Long, Long>> {
    if (right.first == left.first) {
        val max = maxOf(left.second, right.second)
        val min = minOf(left.second, right.second)
        return (min + 1..<max).toList().map { right.first to it }
    } else if (right.second == left.second) {
        val max = maxOf(left.first, right.first)
        val min = minOf(left.first, right.first)
        return (min + 1..<max).toList().map { it to right.second }
    } else {
        throw Exception("Whoops")
    }
}