13
๐ค - 2024 DAY 24 SOLUTIONS - ๐ค
(programming.dev)
An unofficial home for the advent of code community on programming.dev!
Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.
Solution Threads
M | T | W | T | F | S | S |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 |
Icon base by Lorc under CC BY 3.0 with modifications to add a gradient
console.log('Hello World')
Haskell part 2, much better solution
Okay, here's the outline again - this one ran instantly.
Rather than probing with example values, I took a different approach, debugging the structure. I only really care about inputs and outputs, so I wrote something that turns the "wiring diagram" into a map of label -> Expr, where
(the
Eq
instance is stable in symmatric expressions, eg(==) (EAnd a b) (Eand c d) = a == c && b == d || a == d && b == c
)The expressions are grounded in "inputs" ("x00".."x44", "y00".."y44") - that is, they just expand out all of the intermediary labelled things.
Then I constructed a circuit that I was after by building a non-swapped 44/45-bit full adder, and produced the same set of expressions for those.
Then: for each output, z00..z45, check the "spec" expression against the actual one. If they're identical, move on.
Otherwise, find some candidate pairs to swap. For these, I considered all possible labelled outputs except "stable" ones - that is, those that were input depdendencies of z_(i-1) - ie, don't swap any outputs involved in the computation that's validated thus far.
Taking the new layout with swapped outputs and its corresponding set of expressions, carry on searching as before.
A linear scan over the output bits was all that was required - a unique answer poped out without any backtracking.
Anyway, happy Christmas all.
PS. My other version worked (eventually) - it was following this approach that led me to realise that my "spec" full adder was broken too :-D Never skip the unit tests.
(@[email protected] you were asking about alternatives to graphviz-style approaches I recall)
Yes, I was, and this is very impressive. This should be a generic solution right? I'll have to work out how to run it and test on my input.
Generic-ish. It'll fit any of the input problems I think. You could fool it by using a non-canonical circuit, because it knows nothing about the equivalence of boolean expressions; and it also relies on one swap sufficing to fix an output, so I didn't go particularly far into turning it into a generic search. Either of those problem extensions would take much more effort from a solver, so my expectation is that they were deliberately avoided.