https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2025 day 10> (spoilers) :thread:
# advent-of-code
a
Advent of Code 2025 day 10 (spoilers) 🧵
y
Interesting if we can cook something with xors here. Upd: probably not
m
All right, here is my solution using Z3.
b
yea it definitely looks like a linear algebra problem, it's been so long since college math
j
Ok it looks like today's the day I'll spend trying to figure out the solution for P2. Neat.
e
@y9san9 my brute-force solution for the first part:
Copy code
fun main() {
    solve("Factory") {
        data class Parsed(
            val targetVector: BitSet,
            val generatorVectors: List<BitSet>,
            val increments: List<List<Int>>,
            val targetJoltages: List<Int>
        )

        val input = lines
            .map { it.split(" ") }
            .map { line ->
                val tv = line.first().drop(1).dropLast(1)
                    .let { raw ->
                        BitSet(raw.length).apply {
                            raw.forEachIndexed { i, c -> if (c == '#') set(i) }
                        }
                    }
                val (gv, gj) = line.drop(1).dropLast(1).map { rem ->
                    rem.replace("(", "")
                        .replace(")", "").split(",")
                        .let { raw ->
                            BitSet(raw.size).apply {
                                raw.forEach { set(it.toInt()) }
                            } to raw.map { it.toInt() }
                        }
                }.let { p -> p.map { it.first } to p.map { it.second } }

                val tj = line.last().drop(1).dropLast(1).split(",").map { it.toInt() }

                Parsed(tv, gv, gj, tj)
            }

        fun allCombinations(k: Int, w: Int): List<List<Int>> {
            if (w !in 0..k) return emptyList()

            val combinations = mutableListOf<List<Int>>()
            val indices = IntArray(w) { it + 1 }
            var i: Int

            while (true) {
                combinations.add(indices.toList())

                i = w - 1
                while (i >= 0 && indices[i] == k - (w - 1 - i)) i--
                if (i < 0) break

                indices[i]++
                for (j in i + 1 until w) indices[j] = indices[j - 1] + 1
            }
            return combinations.map {
                it.map { v -> v - 1 }
            }
        }

        fun combinations(k: Int): List<List<Int>> = (1..k).map { allCombinations(k, it) }.flatten()

        part1(-1) {
            input.sumOf { (t, g, _, _) ->
                val curr = BitSet()
                combinations(g.size)
                    .forEach { combination ->
                        combination.forEach {
                            curr.xor(g[it])
                            if (curr == t) {
                                return@sumOf combination.size.toLong()
                            }
                        }

                        curr.clear()
                    }
                0
            }
        }
}
e
ILP is NP-complete, so there must be something about the input that makes it tractable
I translated each line to smtlib and threw them at z3 and it worked out for the solution
d10p2.pl
needs more experimenting
d
Part 1 was easy shortest path. Banged my head against part 2 for hours, open reddit and see references to ILP and specific libraries… not fun, skip
There’s this Kotlin lib but I don’t want to figure out how to use it
brew install z3
, copy paste Perl script, thank u, next
I figured out at some point that pathing wasn’t going to do it and that this could be looked at as a sum of vectors, but I wasn’t previously familiar with ILP or the libraries for solving said problems, so I was trying to solve it the normal way, maybe with some dynamic programming
Here’s a solution that doesn’t use an external libraries in Python (via Reddit): https://github.com/ayoubzulfiqar/advent-of-code/blob/main/2025/Python/Day10/part_2.py
e
I did consider that approach but didn't pursue it since I checked and the number of buttons versus the number of counters didn't look promising
but if they happen to be structured in such a way that it works, I'll give it a shot
m
hate days like these, but I'd hope that a non-algebra version does exists
@Dan Fingal-Surma well at least I can run 'a' solution now and then solve it manually later, thanks
m
@ephemient That's some weird looking Kotlin you have there! 😄
😱 1
🤣 2
p
A memiozed arrays goes brrrr day for me 😄 I am too lazy for a proper linear equation solver for the second part
m
There are two types of people: "I am too lazy for a proper memoization solution, I just used an equation solver" and "I am too lazy for a proper equation solver, I just used memoization"
😅 2
b
what did you memoize? i tried caching and it just blew up the heap
p
I made some headway with a-star, "optimizing" by only trying the max possible presses of a button and half that. Solved ~10 of my lines in a few ms, but the rest were taking multiple minutes at a time. I gave up in the end and used z3. I'd much rather a solution that doesn't use z3 and makes sense to my brain :)
y25d10.kt
same 1
j
I refuse to use z3-like solvers until I figure out on my own how to do part2, at least until new year 🙂 .
d
Someone was able to do it with DFS
Interesting, I tried selecting "lowest value" and "largest button" which made se progress but got stuck
I will probably try this when I have time
j
I used branch and bound finally to get the answer (multithreaded!), but it takes one and half minutes, so for sure it's a wrong solution...
d
Feels like the right solution is use a ILP library 😭
p
@bj0 That was before my heap blew up on later lines in input -- basically memoization did not help in most of the inputs -- I was still waiting for it to finish when I was writing that statement 😅 (in the end I went for ai-assisted z3 solution)
🫠 1
j
Fi.....nally.
Copy code
16:19:06.105 [main] INFO Tester -- part 1 ex took 15.498708ms: 7
16:19:06.172 [main] INFO Tester -- part 1 took 66.816875ms: 498
16:19:06.221 [main] INFO Tester -- part 2 ex 2 took 48.687375ms: 99
16:19:06.221 [main] INFO Tester -- part 2 ex took 488.583us: 33
16:19:06.524 [main] INFO Tester -- part 2 took 302.857125ms: 17133
Gauss-Jordan after all. I spent too much time on that yesterday, because there were cases when it was giving not-the-shortest path. (So I switched to 3-mins long Branch-and-Bound). But today I changed my approach and instead of any pruning in gauss-jordan, I let it go and collect all possible solutions, and only after that took the .minOf() Boy I can finally rest 🙂
💯 2
b
I too finally got part2 solved! Linear algebra to reduce the buttons and requirements as much as possible then a DFS search from there. Runs surprisingly fast!
Copy code
Part 1: 481 (cold: 30ms, hot: 10ms)
Part 2: 20142 (cold: 188ms, hot: 22ms)
j
Didn’t get it done on wednesday, but finally managed it this Sunday. I used branch-and-bound where the last bound needed was that when a joltage output is affected by the exact same buttons left in the set of buttons to try, then they should have the same value. After thousands of lines and many hours of experimenting, 168 lines left. It’s not very fast, but it’s fast enough and it works
j
I've just read about https://en.wikipedia.org/wiki/Bareiss_algorithm and I'm eager to check it later this week, because my current implementation forced me to introduce 
data class Fraction
with a whole set of operations and it's suboptimal 🙂
👀 1
p
I had another poke and got some matrices to RREF without needing fractions but need to eliminate some negatives somehow. Hoping to find some time around work tasks to dip in and out.
j
What I do (with my current Gauss-Jordan approach) is to find ALL possible RREFs that meet the criteria (non-negative integers) and then select the one with minimal sum
usually there are more vectors (buttons) than the dimension (lights), so this is where the choice comes from.
105 Views
Open in Slack
PreviousNext
Powered by