https://kotlinlang.org logo
Join Slack
Powered by
<Advent of Code 2024 day 13> (spoilers) :thread:
# advent-of-code
a
k
My best day so far: Solution
b
i solved the math problem easy, but for some reason it was giving me the wrong number until i moved some terms around, not sure if it was rounding errors or what
p
I totally went for like 50 minutes down the 
You estimate that each button would need to be pressed no more than 100 times to win a prize. How else would someone be expected to play?
trap and went Djikstra, only to realize it is simple set of linear equations with easy analitical solution 😄
b
yea i saw the 2 sets of linear equations with 2 unknowns and was like.... it can't be that simple
i even checked them all to make sure they were weren't multiples so a unique solution had to exist
Untitled.kt
Untitled.kt
the top line worked and the bottom line didnt:
mathematically they should be the same
p
I would suspect the fact, that division tends to bring bigger error than multiplication when using floats in combination with the fact, that double.toLong() rounds always down to zero, so 0.999... becomes zero, but guessing
a
Todays tasks are complete mathematical. My solution for the both tasks is the same
j
Interesting... I came up with the same works perfectly on part 1, op part 2 it also correctly says that on the sample machines 2 and 4 are solvable, however, on real input I'm getting "too high" 😞
Copy code
data class ClawMachine(val a: Pair<Long, Long>, val b: Pair<Long, Long>, val prize: Pair<Long, Long>) {
    fun tokensToWin(): Long {
        val xxx = a.first * prize.second - a.second * prize.first
        val yyy = a.first * b.second - b.first * a.second
        if (xxx.mod(yyy) != 0L) return 0
        val bPresses = xxx / yyy
        val aPresses = (prize.first - b.first * bPresses) / a.first
        return 3 * aPresses + bPresses
    }
}
b
rounding error?
n
I ended up with a pretty simple approach:
Copy code
class Machine(val ax: Int, val ay: Int, val bx: Int, val by: Int, val px: Int, val py: Int) {
    fun tokens(d: Long): Long {
        val pxd = px + d
        val pyd = py + d
        val na = (pyd * bx - pxd * by) / (ay * bx - ax * by)
        val nb = (pxd - ax * na) / bx
        return if (na * ax + nb * bx == pxd && na * ay + nb * by == pyd) na * 3 + nb else 0
    }
}
j
ah... right. I was assuming the 
mod
check protects me from it since I'm working with Longs but I missed the 
... / a.first
part 🤦
m
I don't want to talk about today. I was solving Diophantine equations and going down a rabbithole I should NOT have gone hahaha.
same 2
Also, I shot myself in my foot by using my POINT class today. I use y/x points
Copy code
typealias Point = Pair<Int, Int>
val Point.y get() = first
val Point.x get() = second
but the input are x/y points. So I paired them up using 
x to y
and then doing 
pair.y
but 
pair.y
returns 
x
That was a LOONNGGG debugging session for me today
🙃 1
m
ha today went smoothly for me except in part 2 because it gave the wrong answer. It feels like cheating but all I did to fix it was add a test to make sure my answers did satisfy the original equations and then threw out the ones that didn't. I don't quite understand what the calculation issue is yet
d
augh, it was a system of linear equations the whole time
single solution
j
Did not find the trick for part 2 and took out the smt solver solution from last year. Only I had to switch to int solving. https://github.com/bulldog98/advent-of-code/blob/main/advent2024/src/main/kotlin/year2024/Day13.kt
d
e
Its kinda tricky. The text would suggest that simple equation solving won’t be enough because there could be multiple solutions with different costs (so should have go with proper linear programming and optimization problem). At least for my input, pure solving with some filtering was fine.
d
It suggests that but it’s not true
All machines are of the form: a * ax + b * bx = px a * ay + b * by = py where ax, ay, bx, by, px, and py are constants pure system of linear equations, one solutions or infinite
👍 1
I computed an lcm factor but I guess that wasn’t really necessary, made the math easier to reason about when i was deriving the solution
Copy code
fun Machine.bestPlay(): Play? {
    val zx = lcm(a.x, a.y) / a.x
    val zy = lcm(a.x, a.y) / a.y

    val bm = (zx * prize.x - zy * prize.y) / (zx * b.x - zy * b.y)
    val am = (prize.x - b.x * bm) / a.x

    if ((a * am) + (b * bm) != prize) return null
    return Play(am, bm, am * 3 + bm)
}
vs
Copy code
fun Machine.bestPlay(): Play? {
    val bm = (a.x * prize.y - a.y * prize.x) / (a.x * b.y - a.y * b.x)
    val am = (prize.y - b.y * bm) / a.y

    if ((a * am) + (b * bm) != prize) return null
    return Play(am, bm, am * 3 + bm)
}
m
Day 13 Michael.cpp
Day 13 Michael.cpp
d
I didn't remember the general form y = (a1c2 - a2c1) / (a1b2 - a2b1), derived by hand
For a1x + b1y = c1, etc
And here I was ready to complain about needing to know obscure theorems 🤣
Still got it
Copy code
a1x+b1y = c1
a2x+b2y = c2
x = (c1 - b1y) / a1
a2 (c1 - b1y) / a1 + b2y = c2
a2 (c1 - b1y) + a1b2y = a1c2
a2c1 - a2b1y + a1b2y = a1c2
a1b2y - a2b1y  = a1c2 - a2c1
(a1b2 - a2b1)y = a1c2 - a2c1
y = (a1c2 - a2c1) / (a1b2 - a2b1)
🧠 1
Surprisingly hard to just Google
Cleaned it up more
a
if anyone needs the example answer for Part 2, with the 4 machines: the 2nd and 4th machines have solutions (rather than 1st and 3rd in part 1)
Copy code
part Two:
0 Pt(94, 34) Pt(22, 67) P(x=10000000008400, y=10000000005400) 0 0
1 Pt(26, 66) Pt(67, 21) P(x=10000000012748, y=10000000012176) 118679050709 103199174542
2 Pt(17, 86) Pt(84, 37) P(x=10000000007870, y=10000000006450) 0 0
3 Pt(69, 23) Pt(27, 71) P(x=10000000018641, y=10000000010279) 102851800151 107526881786
test input: 875318608908
m
Was too lazy to solve the linear equations by hand and used apache commons-math, which has a terrible api but does the job
👍 1
l
I spent my entire afternoon (here in Vietnam) trying to fix my DP solution. Just to realize like 10 min ago that it is in fact a liner equation. Then all is done in 10 min using Cramer's rule https://github.com/CongLuanTran/Advent-of-Code-2024/blob/main/src/Day13.kt
Day13.kt
But for some reason the code for my part 1 run longer than part 2, may be because there are more hits and so more division calculated, which lead to increase in run time?
m
isn't that just JVM warmup
l
Ah ok, that makes sense. I tried to switch their place and then the runtime change. Do you have any idea how to measure time correctly?
m
Copy code
generateSequence { Day13() }.map { 
        measureTime { it.part1() } to measureTime { it.part2() }
    }.take(10000).last()
Or something like that maybe?
just doing it a lot of times
and then measuring:
😛
p
My mind jump straight to simultaneous equations this morning, and grabbed an envelope and pen to scramble for the formula, and regex to parse the input. Second solution parses the input char by char and and solves every time it has accumulated 6 longs.
Copy code
Warming up 2 puzzles over 5s for year 2024 day 13...
Warmup finished after 5.000116042s with 10393 iterations
year 2024 day 13 part 1
	 Scan took 17.571us 👑: 38714
	 Default took 211.683us (12.05x): 38714
year 2024 day 13 part 2
	 Scan took 17.624us 👑: 74015623345775
	 Default took 210.985us (11.97x): 74015623345775
Day13.kt
e
Day13.kt I need more sleep, I totally went down the wrong solution path (trying to reduce modulos) until the morning
a
Q: what is this check so many have in their solutions? 
if (a * ax + b * bx == x && a * ay + b * by == y)
the equations being solved for 
a
and 
b
or 
countA
and 
countB
basically guarantee that those will be equal - it's how we derive the formula/equation we're solving. mine only has the check for integer coefficients (because I use 
toDouble
in the equations). possible answer: is it to verify that 
a
& 
b
don't have rounding errors due to division with Longs?
m
sanity check for me in the rounding errors yes
✅ 1
🙏 1
a
hmm, I wonder if just doing 
m % 1 == 0.0
is risky if the floating part is close to 0 but not exactly and would end up passing that check. but I think Kotlin/Java math guarantees comparison with 0.0 being actually zero, right?
p
I think that least hidden surprises are when you never go floating point like https://github.com/glubo/adventofcode/blob/main/src/main/kotlin/cz/glubo/adventofcode/y2024/day13/Day13.kt#L54
🙌 1
Floating point are full of surprises, especially when you combine a substraction of two big numbers with division, that makes rounding errors go brrr 😄
🙏 1
a
ok, I think I'll remove that 
toDouble
and put in the rounding-check like everyone else. thank you!
m
I don't like dealing with Doubles and prefer to just work within Int/Long workspace if I can do so. But you have to indeed check on modulo on every division or just check your endresult
👍 2
p
yeah, that's the toll I am willing to pay for not dealing with floating point error transmission (if the problem space allows it)
a
the other check I had with 
a: Double
before the modulo 1 was: 
a.toLong().toDouble() == a
🤣 while feels like a GW-BASIC hack
m
better start implementing a safeDiv function that returns
Copy code
sealed interface SafeLong {
    @JvmInline value class JustValue(val value: Long) : SafeLong
    data object DivByZero : SafeLong
    data class WithModulo(val value: Long, val module: Long) : SafeLong
}
😂
😅 1
p
Copy code
private infix fun Long.safeDiv(other: Long) = if (rem(other) == 0L) div(other) else null
    private fun solve(ax: Long, ay: Long, bx: Long, by: Long, x: Long, y: Long): Long  {
        val b = ((x * ay - y * ax) safeDiv (bx * ay - by * ax)) ?: return 0
        val a = ((x - b * bx) safeDiv ax) ?: return 0
        return 3 * a + b
    }
if you don't mind some boxing
or avoiding boxing
Copy code
private inline fun Long.safeDiv(other: Long, onFail: () -> Nothing) =
        if (rem(other) == 0L) div(other) else onFail()

    private fun solve(ax: Long, ay: Long, bx: Long, by: Long, x: Long, y: Long): Long {
        val b = (x * ay - y * ax).safeDiv(bx * ay - by * ax) { return 0 }
        val a = (x - b * bx).safeDiv(ax) { return 0 }
        return 3 * a + b
    }
d
Yeah I am not using floating point, so I need to check that the equation actually has integer solutions
e
dealing with the rounding I've did this:
Copy code
fun Double.isInt() = floor(this) == ceil(this)
d
That's what 10000000000000L is intended to defeat
j
Things I tried today: Iteration - obviously. Iteration but limited to LCM steps - of course. Iteration but backwards - yes Iteration but first pressing B then A (because B is cheaper, so that must be important, right?) CRT - considered, but didn't implemented. stopping coding for a while and drawing several lines with a pen... uhhh. really.. COULD IT BE SO EASY? Keep in mind I had 
prize = posA * timesA + posB * timesB
from the very beginning, I just hadn't realized that it's a system of two equations with only two unknowns. Obligatory visualization attached 😆
😆 2
p
Here comes my solution 🤯
p
I have a similar solution...
p
You also don’t have proper math paper. 😁 I borrowed some drawing paper from my daughter for this (if you watch closely there are some clues)
p
There's no better maths paper for advent of code than the literal back of an envelope
j
Folks, you don’t need doubles or anything non-integer. Just calculate equation in ints (well, longs), then check if the result calculated back (sum of products) is equal to position of price.
☝️ 2
p
d
I don’t trust floating point math 😆
same 1
e
just check % before /
☝️ 1
j
There’s only one thing in modern computing I trust less than floats: LLMs 😁
👍 1
d
Check at the end was less code
bc I defined + and * on Point
Copy code
val db = (a.x * prize.y - a.y * prize.x) / (a.x * b.y - a.y * b.x)
val da = (prize.y - b.y * db) / a.y
return if (a * da + b * db == prize) da * 3 + db else 0
n
I always feel smugly superior to people who spend a lot of time parsing these wordy inputs when with a number getter you can just do input.getLongs.chunked(6). But that smugness gets knocked down right quick when I start having to do basic math. Still, that was a lot of fun.
e
did a regex match for a whole stanza at once in kotlin though. no particular reason for it one way or another
d
I simplified to
Copy code
Regex("""(\d+).*?(\d+).*?(\d+).*?(\d+).*?(\d+).*?(\d+)""")
val (ax, ay, bx, by, px, py) = pattern.find(lines.joinToString())!!.destructured
e
you could have
Copy code
List(6) { """(\d+)""" }.joinToString(".*?").toRegex()
🧠 1
d
Saves 5 characters
🙂
Copy code
val pattern = Regex(List(6) { "(\\d+)" }.joinToString(".*?"))
Now we’re cooking, -11
🏌️ 1
c
Not a fan of that one. The puzzle text felt intentionally misleading. How are you to know your machines all have exactly 1 solution when the text suggests the problem is to find the optimal cost which heavily implies there are multiple.
☝️ 2
The cheapest way to win the prize The only way to win the prize is by pushing the 
A
button 
80
times and the 
B
button 
40
times. This would line up the claw along the 
X
axis (because 
80*94 + 40*22 = 8400
) and along the 
Y
axis (because 
80*34 + 40*67 = 5400
). Doing this would cost 
80*3
tokens for the 
A
presses and 
40*1
for the 
B
presses, a total of 
280
tokens.
🙃 1
A bit naughty
I'd nearly got some wacky solution of backwards counting a cache of remainders working before the wife pointed out it was just simultaneous equations
l
Yeah that "cheapest" word led me down the path of Unbound Knapsack and wasted 2 hours yesterday on it.
n
This is at least the second one that was misleading, so expect more.
d
I was reading about the general integer form solution to Diophantine equations and then I was like wait there are 2 of these
e
they're often misleading
c
The blinking stones for instance going on about order all the time but actually being irrelevant felt like fair misleading because working that out was part of the puzzle. In this case though it's heavily implied it's a cost minimisation exercise and the only reason it isn't is that your input is crafted to ensure only a single solution exists. There could easily have been inputs with multiple solutions but there weren't. That feels a bit more unfair.
e
that's part of the point
c
It's often pointed out you can make certain assumptions, or that your input excludes certain cases so your solution can be more focused/not have to cover every scenario. This felt like the opposite.
d
Yeah the only way for multiple solutions is 2 vectors with the same slope but then you'd get divide by zero
So you'd know if that case were hit
c
Meh, anyway, bed time, then onto the next one 🙂
n
I'm not good at remembering things, but I don't recall this kind of misdirection in previous years. I half-suspect it'll fit thematically, but even if it doesn't, it's a new thing to keep us on our toes. Or I just forgot all the other times...very possible.
d
But yeah I patterned matched search problem
v
My solution solves the system of two linear equations by finding the intersection of two lines via vector operations. After some debugging, 
Math.ulp
is used for fuzzy equality checks with relative epsilon. I was stuck for a while realizing that if A, B and Prize directions are all collinear it would require writing a separate sub-solution of weighted Diophantine equations using the extended Euclidean algorithm, but luckily there were no such cases in my input. 😅 https://github.com/vkopichenko/Contests/blob/main/adventofcode/src/2024/y24day13.kt
Copy code
data class Line(val point: Vector, val direction: Vector)
    infix fun Line.intersection(that: Line): Vector? =
        // TODO: using Cramer's rule might be more efficient
        (that.point - this.point)
            .projectOnto(that.direction.perpendicular())
            .unprojectOnto(this.direction)
            ?.plus(this.point)
j
I had some spare time last weekend and decided to completely over engineer day 13:
Copy code
data class Puzzle13(val aX: Long, val aY: Long, val bX: Long, val bY: Long, val pX: Long, val pY: Long) {
    private val solution = solve {
        variable("a") * aX + variable("b") * bX eq pX
        variable("a") * aY + variable("b") * bY eq pY
    }

    val minCost: Long?
        get() {
            val a = solution["a"].asLong() ?: return null
            val b = solution["b"].asLong() ?: return null
            return if (a >= 0 && b >= 0) 3 * a + b else null
        }

    fun part2() = copy(pX = pX + 10000000000000L, pY = pY + 10000000000000L)
}
44 Views
Open in Slack
PreviousNext
Powered by