looks like we got that ||dynamic programming|| problem
#Day 10
true knot
dense dock
nothing like 70 lines of gleam just to parse the input :P
potent mesa
i am so lost
true knot
well, I've got part 1, but part 2 looks like a LP minimization problem and I really don't want to try to implement that in gleam right now
potent mesa
@exotic trout did you solve pt 2 in gleam?
solid hearth
One eternity later
P1 is done
BFS + daying of waiting for it to compute
Can’t go // because of ruby lol
potent mesa
i ended up using list_combination_with_repetitions from gleam_community_maths for part 1
fn min_presses_pt_1(
light_diagram: Set(Int),
buttons: List(Set(Int)),
presses: Int,
) -> Int {
case
maths.list_combination_with_repetitions(buttons, presses)
|> result.unwrap(yielder.empty())
|> yielder.any(fn(buttons) {
list.fold(buttons, set.new(), set.symmetric_difference) == light_diagram
})
{
True -> presses
False -> min_presses_pt_1(light_diagram, buttons, presses + 1)
}
}
pub fn pt_1(machines: List(Machine)) {
list.map(machines, fn(m) { min_presses_pt_1(m.light_diagram, m.buttons, 1) })
|> int.sum
}
being able to use set.symmetric_difference was cool too
though weirdly just using list.combinations also worked on my input (which ran a lot faster). i guess it didnt require any buttons to be pressed more than once?
solid hearth
I can use bitmaps also
potent mesa
my naive part 2 (that doesnt finish in time on my input, only on the example) is pretty similar, but just converts the buttons to dicts that get combined
fn min_presses_pt_2(
joltage_requirements: Dict(Int, Int),
buttons: List(Dict(Int, Int)),
presses: Int,
) -> Int {
case
maths.list_combination_with_repetitions(buttons, presses)
|> result.unwrap(yielder.empty())
|> yielder.any(fn(buttons) {
list.fold(buttons, dict.new(), fn(acc, b) {
dict.combine(acc, b, int.add)
})
== joltage_requirements
})
{
True -> presses
False -> min_presses_pt_2(joltage_requirements, buttons, presses + 1)
}
}
pub fn pt_2(machines: List(Machine)) {
list.map(machines, fn(m) {
min_presses_pt_2(
m.joltage_requirements,
list.map(m.buttons, fn(b) {
set.to_list(b)
|> list.map(fn(i) { #(i, 1) })
|> dict.from_list
}),
1,
)
})
|> int.sum
}
Probably some z3 shit would work
potent mesa
yep
thats what most people used
but no erlang bindings for it unfortunately
when people are resorting to stuff like this you know it's cooked
https://github.com/apprenticewiz/adventofcode/blob/main/haskell/2025/day10b/src/Main.hs#L41-L42
tiny tangle
happy about my part 1, struggling for part 2
pub fn pt_1(input: String) {
input
|> parse_pt_1
|> list.map(fn(machine) {
let Machine(indicators:, buttons:, joltages: _) = machine
list.range(1, list.length(buttons))
|> list.find(fn(n) {
buttons
|> list.combinations(n)
|> list.find(fn(combination) {
list.fold(combination, 0, int.bitwise_exclusive_or) == indicators
})
|> result.is_ok
})
|> result.unwrap(0)
})
|> int.sum
}
Can’t stand the word joltage anymore 
gilded sigil
Yeah I don’t think I’ll implement a linear solver today
Might pipe into Z3 just to get the result out but I hate having to do that
Maybe there’s a different approach with branch and bound and some heuristics
potent mesa
yeah
const filename = "formula.z3"
pub fn pt_2(machines: List(Machine)) {
list.map(machines, fn(m) {
let contents =
[
"(set-logic LIA)",
"(set-option :produce-models true)",
list.index_map(m.buttons, fn(_, i) {
"(declare-const x"
<> int.to_string(i)
<> " Int)\n"
<> "(assert (>= x"
<> int.to_string(i)
<> " 0))"
})
|> string.join("\n"),
list.map(dict.to_list(m.joltage_requirements), fn(p) {
let #(i, v) = p
"(assert (= "
<> case
list.index_map(m.buttons, fn(b, i) { #(i, b) })
|> list.filter(fn(p) { set.contains(p.1, i) })
|> list.map(pair.first)
{
[] -> "0"
[i] -> "x" <> int.to_string(i)
is ->
"(+ "
<> list.map(is, fn(i) { "x" <> int.to_string(i) })
|> string.join(" ")
<> ")"
}
<> " "
<> int.to_string(v)
<> "))"
})
|> string.join("\n"),
"(minimize (+ "
<> list.index_map(m.buttons, fn(_, i) { "x" <> int.to_string(i) })
|> string.join(" ")
<> "))",
"(check-sat)",
"(get-objectives)",
"(exit)",
]
|> string.join("\n")
let assert Ok(_) = simplifile.write(to: filename, contents:)
let assert Ok(output) =
shellout.command("z3", with: [filename], in: ".", opt: [])
let assert [_, " " <> n, ..] = string.split(output, ")")
let assert Ok(n) = int.parse(n)
n
})
|> utils.tap(fn(_) { simplifile.delete(filename) })
|> int.sum
}
unfortunately shellout doesnt have a way of directly passing in stdin, otherwise I would have done z3 -in instead of writing a file each time
the let assert [_, " " <> n, ..] = string.split(output, ")") to parse the output is so cursed lol
cause it outputs something like
sat
(objectives
((+ x0 x1 x2 x3 x4 x5 x6) 75)
)
ok it can work with stdin if I do this
shellout.command(
"sh",
with: ["-euc", "echo '" <> contents <> "' | z3 -in"],
in: ".",
opt: [],
)
but then it's no longer portable to other operating systems and only works on linux
its also not really any faster
Ran 2025 day 10:
Part 1: ✅ (in 330.314 ms)
Part 2: ✅ (in 1.772 s)
Woah finally did it
potent mesa
Omg your p1 is so fast
it's even faster if I take the list.combinations shortcut:
Ran 2025 day 10:
Part 1: ✅ (in 28.437 ms)
Part 2: ✅ (in 1.749 s)
still not sure why that works tho
gilded sigil
I did mine with a bfs and a priority queue it's pretty fast
Part 1 | 61.804ms
Part 2 | 1237.453ms
Ok so mine was taking ages because I used strings lol
Converting it to bit shift/ bit mask and now it’s instant
gilded sigil
```rust
const filename = "formula.z3"
pub fn pt_2(machines: List(Machine)) {
...
If you wanted you could use the temporary package for the input file to z3, it would take care of cleanup even if something failed. I did it like this
use file <- temporary.create(temporary.file())
let assert Ok(_) = simplifile.write(program, to: file)
let assert Ok(output) = shellout.command("z3", with: [file], in: ".", opt: [])
let assert [_, " " <> n, ..] = string.split(output, ")")
int_extra.expect(n)
thats a good idea
gilded sigil
Thanks for the help with z3! It would have taken me ages to figure out the exact incantation it needed
potent mesa
when people are resorting to stuff like this you know it's cooked
<https://githu...
oh I mainly just ripped the z3 program from here ^ lol
i wasnt in the mood to figure out the incantation either
decided to convert my part 1 to using bitwise logic and it's so much faster
fn min_presses_pt_1(light_diagram: Int, buttons: List(Int), presses: Int) -> Int {
case
list.combinations(buttons, presses)
|> list.any(fn(buttons) {
list.reduce(buttons, int.bitwise_exclusive_or) == Ok(light_diagram)
})
{
True -> presses
False -> min_presses_pt_1(light_diagram, buttons, presses + 1)
}
}
pub fn pt_1(machines: List(Machine)) {
list.map(machines, fn(m) {
min_presses_pt_1(
list.fold(set.to_list(m.light_diagram), 0, fn(acc, i) {
int.bitwise_shift_left(1, i) |> int.bitwise_or(acc)
}),
list.map(m.buttons, fn(button) {
list.fold(set.to_list(button), 0, fn(acc, i) {
int.bitwise_shift_left(1, i) |> int.bitwise_or(acc)
})
}),
1,
)
})
|> int.sum
}
Ran 2025 day 10:
Part 1: ✅ (in 5.495 ms)
Part 2: ✅ (in 1.755 s)
solar kelp
i used bitwise ops too! felt very smart briefly. I am tapping out for part 2 and going to rip off some z3 stuff from other people because I am wayyyyyyyyyy too mathematically illiterate to do this LOL
might circle back on it some time in teh future
exotic trout
<@1126184667188572201> did you solve pt 2 in gleam?
nope
potent mesa
If you wanted you could use the `temporary` package for the input file to z3, it...
I decided to do this so I didnt have to handle the Result from temporary.create:
let assert Ok(res) =
temporary.create(temporary.file(), fn(file_path) {
let assert Ok(_) = simplifile.write(formula, to: file_path)
shellout.command("z3", with: [file_path], in: ".", opt: [])
})
as "Failed to create temporary file"
Looks good to me!
potent mesa
somehow using temp files actually slightly improved the performance, even over the sh -euc echo '<program>' | z3 -in version
gilded sigil
I went with z3 😬
tiny tangle
oh
gilded sigil
It's a sad day
tiny tangle
i read bfs and priority queue, tought you were doing some shenanigans
potent mesa
thats part 1
gilded sigil
No that's my solution to part 1
tiny tangle
ah
gilded sigil
I tried coming up with a branch and bound version of part 2 that could use some heuristic to prune the search space but couldn't find anything smart
potent mesa
i spent like 2 hours trying to translate this solution to gleam
https://github.com/Nathan-Fenner/adventofcode/blob/main/day10.ts
i got close to it working i think, but not good enough
so maybe youll have better luck if you want to try it
gilded sigil
i spent like 2 hours trying to translate this solution to gleam
https://github.c...
Oh that's so incrdibly short for a solution
potent mesa
fn min_presses_pt_2(
required_joltage: Dict(Int, Int),
buttons: List(Dict(Int, Int)),
presses: Int,
) -> Result(Int, Nil) {
let joltage_values = dict.to_list(required_joltage)
case
list.all(joltage_values, fn(p) { p.1 == 0 }),
list.any(joltage_values, fn(p) { p.1 < 0 })
{
_, True -> Error(Nil)
True, _ -> Ok(presses)
False, _ ->
case
list.combination_pairs(joltage_values)
|> list.find_map(fn(p) {
case p {
#(#(i, v), #(j, w)) if v > w ->
case
list.filter(buttons, fn(button) {
dict.has_key(button, i) && !dict.has_key(button, j)
})
{
[button] -> Ok(button)
_ -> Error(Nil)
}
#(#(i, v), #(j, w)) if v < w ->
case
list.filter(buttons, fn(button) {
dict.has_key(button, j) && !dict.has_key(button, i)
})
{
[button] -> Ok(button)
_ -> Error(Nil)
}
_ -> Error(Nil)
}
})
{
Ok(button) -> {
min_presses_pt_2(
dict.combine(required_joltage, button, int.add),
buttons,
presses + 1,
)
}
Error(Nil) -> {
list.map(buttons, fn(button) {
dict.combine(required_joltage, button, int.add)
|> min_presses_pt_2(buttons, presses + 1)
})
|> result.values
|> list.max(order.reverse(int.compare))
}
}
}
}
pub fn pt_2(machines: List(Machine)) {
list.map(machines, fn(m) {
min_presses_pt_2(
m.joltage_requirements,
list.map(m.buttons, fn(b) {
set.to_list(b)
|> list.map(fn(i) { #(i, -1) })
|> dict.from_list
}),
0,
)
})
|> result.values
|> int.sum
}
this is where I got to
gilded sigil
I want to try translating it
tiny tangle
i keep reading about gauss jordan elimination or something
might try and go with that
potent mesa
yeah, I think if you can eliminate enough recursive calls it eventually works
the main logic to the above solution is two things:
- you start from the final desired joltage and work towards all zeros, rather than starting at all zeros
- if there's a differential between two joltages, and only one button has the index of the higher of the two while not having the index of the lower of the two, then you can safely pick that button as you're guaranteed to have to click it at some point
potent mesa
```rust
fn min_presses_pt_2(
required_joltage: Dict(Int, Int),
buttons: List...
this code actually does work and returns the right answer on the example, it just doesnt do enough pruning i think, cause it never finishes on my input
gilded sigil
Did you check the ts solution works on your input?
potent mesa
i didnt check that
gilded sigil
Or does that hang forever as well?
potent mesa
the gleam version hangs on the third line of my input, but it makes it through the first two pretty quickly
so it might just be something dumb
condensed the z3 formula generation down a fair bit to this:
"(set-logic LIA) (set-option :produce-models true)"
<> list.index_fold(m.buttons, "", fn(acc, _, i) {
let v = var(i)
acc <> " (declare-const" <> v <> " Int) (assert (>=" <> v <> " 0))"
})
<> dict.fold(m.joltage_requirements, "", fn(acc, i, v) {
let vs =
list.index_fold(m.buttons, "", fn(acc, b, j) {
case set.contains(b, i) {
True -> acc <> var(j)
False -> acc
}
})
acc <> " (assert (= (+" <> vs <> ") " <> int.to_string(v) <> "))"
})
<> " (minimize (+"
<> list.index_fold(m.buttons, "", fn(acc, _, i) { acc <> var(i) })
<> ")) (check-sat) (get-objectives) (exit)"
var is this helper fn
fn var(i: Int) -> String {
" x" <> int.to_string(i)
}
you're a legend, lily
potent mesa
final solutions for today. gonna go to bed now
https://whitespace.moe/lily/gleam_aoc/src/branch/main/src/aoc_2025/day_10.gleam
gilded sigil
i spent like 2 hours trying to translate this solution to gleam
https://github.c...
My translation runs in half a second on the three machine input 
gilded sigil
Yeah no idea how to further speed it up
Unless there's a smart way to prune each state even further by looking at the buttons
potent mesa
Did you manage to check how long the original TS took?
gilded sigil
Nope
sinful inlet
ok yeah im not smart enough to pull this one off
potent mesa
Feel free to steal the Z3 script above lol
sinful inlet
Part 1: _ (in 271.488 ms)
for part 1 there's no reason to push a button more than once because pushing it twice is equivalent to not pushing it
sinful inlet
that's sth at least
potent mesa
for part 1 there's no reason to push a button more than once because pushing it ...
Ooh, that makes so much sense
true knot
at worst you'll need to push all the buttons once
so my part 1 was just "can you do it in 1 button? can you do it in 2 buttons? ..." incrementing the size of the combination I took until I found a size that worked, and with like 7-8 buttons total per row that's a pretty tiny set of possibilities to brute-force over
potent mesa
Yeah thats exactly the same as my solution
Runs in about 4-5ms using xor, or ~25ms using sets+symmetric_difference
sinful inlet
woops, did a bit too much for pt 1, I went with a bfs that just pushes all the buttons (with the previously pressed ones) to the queue on each iteration
solid hearth
decided to convert my part 1 to using bitwise logic and it's so much faster
For me also the perf gain was insane
sinful inlet
ah dang my parsed machine is fairly different yours lily, let's see
hold the phone, just gotta hold off on already converting everything to a bitwise int in the parser and do it later
tysm @potent mesa , I'd never even heard of Z3
Part 1: _ (in 375.047 ms)
Part 2: _ (in 1.993 s)
ashen flax
I wonder if I could use a differential evolution algorithm to solve part 2. Definitely wouldn’t be the most efficient way, but might be fun to implement.
hollow ermine
Holy hell that was difficult
I also used the z3 route lol. Did learn some nice things about string_tree and using subprocesses so there's that at least 
true knot
yeah, decided to do the z3 route and as penance I refactored it to make it look aesthetically appealing
fn solve_with_z3(machine: Machine) -> Int {
let sat =
set_options
<> declare_variables(machine)
<> assert_linear_equations(machine)
<> minimize_sum_of_variables(machine)
<> check_satisfiability
let assert Ok(Ok(res)) = send_file_to_z3(sat)
let assert [_, " " <> n, ..] = string.split(res, ")")
to.int(n)
}
I like how everyone decided to use my output parsing trick haha
true knot
I've done some previous aoc problems in a different SAT optimization library (Rosette for Racket) but figuring out how to do it by calling out from Gleam was interesting
potent mesa
I think I'm gonna try calling out to clp or scip tomorrow since those are more focussed on these kind of problems
hollow ermine
I have to say that ILP solvers (and problems) of all types are oretty cool. I'd love to do more with them, but outside of some very specific fields they're just not that needed 🙁
true knot
solving it in Rosette
(define (minimize-presses machine)
(clear-vc!)
(match-define (Machine _ buttons joltages) machine)
(define-symbolic* n integer? #:length (length buttons))
(define sol
(optimize #:minimize (list (foldl + 0 n))
#:guarantee (begin
(for ([v (in-list n)])
(assert (>= v 0)))
(for ([total (in-list joltages)]
[index (in-naturals)])
(define valid-n
(for/list ([b (in-list buttons)]
[var (in-list n)]
#:when (set-member? b index))
var))
(assert (= total (foldl + 0 valid-n)))))))
(evaluate (foldl + 0 n) sol))
I should learn racket
true knot
it's fun
true knot
this is a pretty good post about how someone solved it without an SAT solver, using linear algebra to reduce the solution space to just a couple of free variables in each set https://forums.somethingawful.com/showthread.php?threadid=4101136&pagenumber=4#post549873748
lavish cape
I'm too dumb for part 2
lean leaf
What I'm most fascinated by is how widespread Z3 is
I've done linear programming before, hell even integer branch & bound before, but never have I heard of Z3
& now today it's like
Everyone is just bringing it up
solar kelp
I have the maths knowledge of an 8 year old so it's been completely shocking to me LOL
lean leaf
Won't get it done by today or tomorrow but I think I'll try implementing simplex in gleam some day
plush herald
thx @potent mesa for your incredible solution to use Z3
potent mesa
the z3 program itself isnt really mine, i just took it from someone who called z3 from haskell and converted it to gleam
plush herald
Yes, but sharing it here is already a lot for beginners like me in the Gleam ecosystem.
potent mesa
the format scip uses is definitely nicer to read than z3
oh you dont even need the general section, even better
hollow ermine
Wow that is a lot nicer than the smt format for z3 😐
potent mesa
yeah
the labels are optional too, so it can be as short as just
Minimize
x0 + x1 + x2 + x3 + x4
Bounds
x0 >= 0
x1 >= 0
x2 >= 0
x3 >= 0
x4 >= 0
Subject To
x0 + x2 + x3 = 7
x3 + x4 = 5
x0 + x1 + x3 + x4 = 12
x0 + x1 + x4 = 7
x0 + x2 + x4 = 2
End
seems like the
Generals
x0 x1 x2 x3 x4
section is actually needed, otherwise it returns float results sometimes
cool, part 2 converted to scip complete
pub fn pt_2(machines: List(Machine)) {
list.map(machines, fn(m) {
let vars =
list.range(0, list.length(m.buttons) - 1)
|> list.map(fn(i) { "x" <> int.to_string(i) })
let formula =
"Minimize "
<> string.join(vars, " + ")
<> " Bounds "
<> list.map(vars, string.append(_, " >= 0")) |> string.join(" ")
<> " Subject To "
<> dict.fold(m.joltage_requirements, "", fn(acc, i, v) {
let sum =
list.index_fold(m.buttons, [], fn(acc, b, j) {
case set.contains(b, i) {
True -> ["x" <> int.to_string(j), ..acc]
False -> acc
}
})
|> string.join(" + ")
acc <> sum <> " = " <> int.to_string(v) <> " "
})
<> "Generals "
<> string.join(vars, " ")
<> " End"
let assert Ok(res) =
temporary.create(
temporary.file() |> temporary.with_suffix(".lp"),
fn(file_path) {
let assert Ok(_) = simplifile.write(formula, to: file_path)
shellout.command("scip", with: ["-f", file_path], in: ".", opt: [])
},
)
as "Failed to create temporary file"
let output = case res {
Ok(output) -> output
Error(#(i, output)) ->
panic as {
"SCIP command failed with exit status "
<> int.to_string(i)
<> " and output: "
<> output
}
}
let assert Ok(n) =
string.split(output, "\n")
|> list.find_map(fn(line) {
case line {
"objective value:" <> rest ->
Ok(string.trim(rest) |> utils.unsafe_int_parse)
_ -> Error(Nil)
}
})
as { "Unexpected SCIP output: " <> output }
n
})
|> int.sum
}
now i want to try making an scip script that can solve all the machines in one go
potent mesa
so it works fine if you just merge all the variables into the same script and make one big sum to minimize. this is all three of the machines in the example for instance
hollow ermine
Is that faster than doing them all separately? Starting up N processes instead of 1 should have some overhead of course, but making the problem much bigger might get longer faster than just doing the problems 1 by 1 (in parallel if needed)
I used the parallel_map package to do all the problems concurrently
solar kelp
so it works fine if you just merge all the variables into the same script and ma...
big fan of these guys as little emoticons
potent mesa
Is that faster than doing them all separately? Starting up N processes instead o...
i dont think it's any slower
but ugh it looks like it has some kind of limit to the number of variables it can solve for at once, cause it works on 152 lines of my input, but not the full 166
and it runs super fast on those first 152 lines too
Part 2: - (in 241.295 ms)
i guess ill have to do it in chunks of 100
potent mesa
Ran 2025 day 10:
Part 1: ✅ (in 5.909 ms)
Part 2: ✅ (in 263.164 ms)
that was easy, just wrapped it in
list.sized_chunk(machines, 100)
|> list.map(fn(machines) {
...
}) |> int.sum
weirdly though SCIP decides the problem is infeasible for some chunk sizes but not others
ah, i just needed to reverse the order of the variable declarations in the script
cause i was prepending them, and apparently the order it evaluates them in matters
gilded sigil
WHAA 🤯
potent mesa
Ran 2025 day 10:
Part 1: ✅ (in 5.013 ms)
Part 2: ✅ (in 420.653 ms)
I want to ~copy~ see it
gilded sigil
```rust
Ran 2025 day 10:
Part 1: ✅ (in 5.013 ms)
Part 2: ✅ (in 420.653 ms)
`...
That’s so much faster than I expected
solar kelp
WHATTT that's amazing
potent mesa
just committed it
potent mesa
there were a few python implementations in that thread that i referenced
just simplified it a bit further to use Bool instead of ints that are only 0 or 1
could probably remove the inf if I made the function return Result(Int, Nil) instead
potent mesa
which of these do you all prefer?
const inf = 999_999_999_999_999
pub fn min_presses_pt_2(
joltages: List(Int),
button_map: Dict(List(Bool), List(Int)),
parity_map: Dict(List(Int), List(List(Bool))),
) -> Int {
use <- bool.guard(list.all(joltages, fn(x) { x == 0 }), return: 0)
use <- bool.guard(list.any(joltages, fn(x) { x < 0 }), return: inf)
list.map(joltages, fn(x) { x % 2 })
|> dict.get(parity_map, _)
|> result.unwrap([])
|> list.fold(inf, fn(min, buttons_to_press) {
let assert Ok(joltage_drops) = dict.get(button_map, buttons_to_press)
as "Invalid button combination"
let next_joltages =
list.zip(joltages, joltage_drops) |> list.map(fn(p) { { p.0 - p.1 } / 2 })
int.min(
min,
list.count(buttons_to_press, function.identity)
+ 2
* min_presses_pt_2(next_joltages, button_map, parity_map),
)
})
}
pub fn min_presses_pt_2(
joltages: List(Int),
button_map: Dict(List(Bool), List(Int)),
parity_map: Dict(List(Int), List(List(Bool))),
) -> Result(Int, Nil) {
use <- bool.guard(list.all(joltages, fn(x) { x == 0 }), return: Ok(0))
use <- bool.guard(list.any(joltages, fn(x) { x < 0 }), return: Error(Nil))
list.map(joltages, fn(x) { x % 2 })
|> dict.get(parity_map, _)
|> result.unwrap([])
|> list.fold(Error(Nil), fn(min, buttons_to_press) {
let assert Ok(joltage_drops) = dict.get(button_map, buttons_to_press)
as "Invalid button combination"
case
list.zip(joltages, joltage_drops)
|> list.map(fn(p) { { p.0 - p.1 } / 2 })
|> min_presses_pt_2(button_map, parity_map)
{
Ok(new_min) -> {
let new_min =
list.count(buttons_to_press, function.identity) + 2 * new_min
case min {
Ok(cur_min) if cur_min < new_min -> min
_ -> Ok(new_min)
}
}
Error(Nil) -> min
}
})
}
the second is longer but means you dont end up with some random big number if there's no solution
sinful inlet
||what the fuck I put in a troll answer to part 1 because you never know||
(slight day 12 spoiler above, my bad)
potent mesa
for day 12?
sinful inlet
yeah
potent mesa
this is day 10 lol
gilded sigil
I think I like the result returning one better
potent mesa
yeah same
getting a panic from the let assert in the main part 2 body is nicer than getting some huge number as a result when the input isnt solvable
gilded sigil
I want to try and implement this
potent mesa
did some more bitwise logic so the dicts didnt have to deal with as many lists:
https://whitespace.moe/lily/gleam_aoc/src/branch/main/src/aoc_2025/day_10.gleam#L77-L147
it now encodes the combination of buttons to be pressed as a single integer rather than a list of bools, which still works as a unique index to the dict, and still allows counting of how many buttons were pressed by counting the number of ones in the binary representation of the int
solar kelp
did some more bitwise logic so the dicts didnt have to deal with as many lists:
...
I just had a crack at porting this to OCaml and it's so cool that it works
thank you for doing the hard bit so I could copy you outright
lol
time dune exec day10
Executed in 660.14 millis fish external
usr time 584.98 millis 1.59 millis 583.38 millis
sys time 60.74 millis 0.00 millis 60.74 millis
remarkable
potent mesa
yeah its pretty cool
i still dont fully understand the algorithm
but i get most of it
solar kelp
it still seems like complete magic to me
ashen flax
Yay, I did part 2. Thank you @potent mesa for posting that reddit message about bifurcation. After struggling with an off by one error for half the afternoon I finally completed Advent of Code.
Part 1 (20 ms): _
Part 2 (1260 ms): _
Ok so I've managed to implement gaussian elimination in pure gleam and make it reaaally fast
I'm still not sure I haven't made any mistake in the implementation but the tests I have are quite encouraging
So to reduce a 100x100 matrix it takes 0.39ms
For reference doing the same thing in numpy takes 0.22ms
I'm impressed it's even in the same ballpark as numpy honestly
tiny tangle
How are you going to proceed after gaussian elimination? It helps to reduce the amount of free variables, but I think you still need bruteforce at the end?
gilded sigil
Well bruteforcing is still pretty slow, but doable!
Brute forcing all the remaining combinations takes about 10s without any other smart trick
wanton eagle
Brute forcing all the remaining combinations takes about 10s without any other s...
wait, what? My brute force is taking like, hours
You're just brute forcing all the possible free variables, right?
gilded sigil
Yeah
wanton eagle
do you do anything clever to like, stop the search at some point?
since you're looking for a minimum
gilded sigil
Yeah I have an upper bound for each button
wanton eagle
how large is your upper bound?
For like, 500, my 3 variable solution is not finishing after 20+ minutes
each iteration of the loop takes ~1us too so it's uh, rough
gilded sigil
Mhm it's smaller than 500, what I do is I look at the joltages {1, 20, 30, 12, 4} and for each button I take the minimum of all the joltages it affects
So it's usually quite small
gilded sigil
Yeah! I've read there's other smart things one could do looking at the reduced matrix but I can't figure out how to implement it
That's the best I could come up with
wanton eagle
I have some errands to do but let me see if just doing that quickly works for me 👀 very possible I have some other bug
gilded sigil
I think I'll take the pure gleam 10s solution for now
I'm pretty happy with how gaussian elimination performs, that's no longer the bottleneck by a mile
wanton eagle
thanks - hopefully I can figure it out. I might poke you to see if you see anything obvious if I can't, if that's ok 😅
gilded sigil
Sure thing!
wanton eagle
floating point math is my op frfr
your answer is too low
perhaps I am simply better at button pushing than you, mr. code
hell yeah, frick floating points
to figure out what's so slow about my solution...
currently my single threaded solution runs in almost four minutes
I suspect it's my very slow brute force
gilded sigil
Have you timed how long it takes to reduce a matrix?
My very slow brute force takes 10 seconds at most
wanton eagle
Have you timed how long it takes to reduce a matrix?
I haven't timed it but it's definitely not my bottleneck
looks like about 500us per matrix
gilded sigil
Mmh should be plenty enough yeah
You could try and see how may free variables each machine ends up with
Most of the machines in my input only have 3/4 free variables but maybe your input could be unlucky and many with a lot of free variables
wanton eagle
So I think my big problem is that I'm brute forcing too high. I took your approach of taking the minimum value of joltages but that wasn't enough. There are some equations like
a = -90 + i
so if i doesn't even pass 90 it's not going to work
originally I did by the maximum joltage but I shaved two minutes off by doing max(abs(constant)) + min(joltage)
I threw a flame graph at it, I think part of it might be that my "button simulation" is a bit slow (it relies on dicts which is fast enough individually but might be too slow when done on n^3 elements when n is order of hundreds lol
wanton eagle
Managed to get it under a minute!
wanton eagle
@gilded sigil I'm very curious how we differ on our brute forcing of free variables. I'm sure there's some obvious trick to do better than I'm doing...
I need to think about how I'd do what you mentioned about setting an upper bound per button. Given the way I structure the brute force that could be tricky
gilded sigil
What I do is
- reduce the matrix to echelon form
- figure out which buttons are free
- set an upper bound for each with the minimum of the joltages the button affects
- get all possible combinations for each free variable
- solve the system using those, and get the one with the smallest result (filtering out negative and fractional ones as soon as I can)
wanton eagle
What I do is
- reduce the matrix to echelon form
- figure out which buttons are ...
I think I see it - your brute force is a lot smarter than mine in that you give a range for each variable individually, while I use the same upper bound for all variables (naively)
The approach I took therefore requires the bound to be the max joltage overall, which is obviously wasteful
Will have to give this a whirl
wanton eagle
@gilded sigil
________________________________________________________
Executed in 5.21 secs fish external
usr time 5.85 secs 717.00 micros 5.85 secs
sys time 0.98 secs 785.00 micros 0.97 secs
thank you for the idea!
wanton eagle
I'll push the code up shortly, but the only change I made from what I shared before was that I bounded the brute force for each variable to the min joltage it could produce (like you suggested), rather than to my other proxy for the maximum possible free variable bound
before it was effectively a nested loop of [0..n] and [0..n], now the bound is dynamic by the variable
I want to clean up some of the error handling a bit but that's the bulk of it!
potent mesa
Nice work!
wanton eagle
Shaved a second off by simply jamming every matrix into a process
Executed in 3.21 secs fish external
usr time 8.95 secs 575.00 micros 8.95 secs
sys time 0.73 secs 452.00 micros 0.73 secs