Day 24: Crossed Wires
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Haskell bits and pieces
The nice thing about Haskell’s laziness (assuming you use Data.Map rather than Data.Map.Strict) is that the laziness can do a ton of the work for you - you might’ve spotted a few Haskell solutions in earlier days’ threads that use this kind of trick (eg for tabling/memoisation). Here’s my evaluation function:
eval l =
let
v = l & Map.map (\case
Const x -> x
And a b -> v Map.! a && v Map.! b
Or a b -> v Map.! a || v Map.! b
Xor a b -> v Map.! a /= v Map.! b)
in v
For part 2, we know what the graph should look like (it’s just a binary adder); I think this is a maximal common subgraph problem, but I’m still reading around that at the mo. I’d love to know if there’s a trick to this.
Thank you for showing this trick, I knew Haskell was lazy but this one blew my mind again.
Dart
Not very happy with this, as for part 2 the code just told me which four pairs of bits of the output needed investigation and I then tediously worked through how they differed from the correct adder implementation in the debugger.
Spoilered as it is overly long and not very interesting.
spoiler
import 'package:collection/collection.dart';
import 'package:more/more.dart';
var nodes = <String, Node>{};
class Node {
String name = '';
bool? state;
var outputGates = <String>[];
}
class Wire implements Node {
@override
String name;
@override
bool? state;
@override
var outputGates = <String>[];
Wire(this.name, this.state);
set() {
for (var g in outputGates) {
(nodes[g]! as Gate).set();
}
}
}
class Gate implements Node {
String input1, input2, type;
@override
String name;
@override
bool? state;
@override
var outputGates = <String>[];
Gate(this.name, this.input1, this.input2, this.type);
set() {
var a = nodes[input1]!.state;
var b = nodes[input2]!.state;
if (a == null || b == null) return;
state = switch (type) { 'AND' => a && b, 'OR' => a || b, _ => a ^ b };
for (var g in outputGates) {
(nodes[g]! as Gate).set();
}
}
}
void setup(List<String> lines) {
var parts = lines.splitAfter((e) => e.isEmpty);
Map<String, Node> wires = Map.fromEntries(parts.first.skipLast(1).map((e) {
var p = e.split(': ');
return MapEntry(p[0], Wire(p[0], p[1] == '1'));
}));
nodes = Map.fromEntries(parts.last.map((e) {
var p = e.split(' ');
return MapEntry(p.last, Gate(p.last, p[0], p[2], p[1]));
}));
nodes.addAll(wires);
for (var g in nodes.values) {
if (g is! Gate) continue;
nodes[g.input1]!.outputGates.add(g.name);
nodes[g.input2]!.outputGates.add(g.name);
}
}
String line(String s) => nodes.keys
.where((e) => e.startsWith(s))
.sorted()
.reversed
.map((e) => nodes[e]!.state! ? '1' : '0')
.join('');
part1(List<String> lines) {
setup(lines);
nodes.values.whereType<Wire>().forEach((e) => e.set());
return int.parse(line('z'), radix: 2);
}
part2(List<String> lines) {
setup(lines);
var bits = nodes.keys.count((e) => e.startsWith('x'));
for (var b in 0.to(bits)) {
nodes.values.whereType<Gate>().forEach((e) => e.state = null);
nodes.values.whereType<Wire>().forEach(((e) => e.state = false));
nodes['y${b.toString().padLeft(2, "0")}']!.state = true;
nodes.values.whereType<Wire>().forEach((e) => e.set());
print('${line("x")}\t${line("y")}\t${line("z")}\t$b');
var output = line('z');
for (var i in 0.to(bits)) {
if (output[bits - i] != ((i == b) ? "1" : "0")) print(i);
}
}
tree('z05');
tree('z06');
// Add break point here and inspect and solve manually using `tree`.
print('break here');
}
tree(String s, {indent = ''}) {
var here = nodes[s]!;
if (here is Wire) {
print('$indent${here.name} (wire)');
return;
}
here as Gate;
print('$indent${here.name} ${here.type}');
tree(here.input1, indent: indent + '| ');
tree(here.input2, indent: indent + '| ');
}
Haskell
Part 1 was trivial, just apply the operations and delay certain ones until you have all the inputs you need.
Code
import Control.Arrow
import Data.Bits
import Numeric
import qualified Data.Char as Char
import qualified Data.List as List
import qualified Data.Map as Map
parse s = (Map.fromList inputs, equations)
where
ls = lines s
inputs = map (take 3 &&& (== "1") . drop 5) . takeWhile (/= "") $ ls
equations = map words . filter (/= "") . tail . dropWhile (/= "") $ ls
operations = Map.fromList
[ ("AND", (&&))
, ("XOR", xor)
, ("OR", (||))
]
solveEquations is [] = is
solveEquations is (e:es)
| is Map.!? input1 == Nothing = solveEquations is (es ++ [e])
| is Map.!? input2 == Nothing = solveEquations is (es ++ [e])
| otherwise = solveEquations (Map.insert output (opfunc value1 value2) is) es
where
value1 = is Map.! input1
value2 = is Map.! input2
opfunc = operations Map.! operation
(input1:operation:input2:_:output:[]) = e
wireNumber prefix = List.filter ((prefix `List.isPrefixOf`) . fst)
>>> flip zip [0..]
>>> List.filter (snd . fst)
>>> List.map ((2 ^ ). snd)
>>> sum
part1 = uncurry solveEquations
>>> Map.toList
>>> wireNumber "z"
part2 (is, es) = List.intercalate "," . List.sort . words $ "z08 ffj dwp kfm z22 gjh jdr z31"
main = getContents
>>= print
. (part1 &&& part2)
. parse
For part 2 I tried symbolic solving to detect discrepancies but I wouldn’t achieve anything with it.
SymbolicEquation
data SymbolicEquation = Single { eqName :: String }
| Combine
{ eqName :: String
, eqOperation :: String
, eqLeft :: SymbolicEquation
, eqRight :: SymbolicEquation
}
deriving (Eq)
instance Show SymbolicEquation where
show (Single name) = name
show (Combine name op l r) = "(" ++ name ++ "= " ++ show l ++ " " ++ op ++ " " ++ show r ++ ")"
symbolicSolve is [] = is
symbolicSolve is (e:es)
| is Map.!? input1 == Nothing = symbolicSolve is (es ++ [e])
| is Map.!? input2 == Nothing = symbolicSolve is (es ++ [e])
| otherwise = symbolicSolve (Map.insert output (Combine output operation value1 value2) is) es
where
value1 = is Map.! input1
value2 = is Map.! input2
(input1:operation:input2:_:output:[]) = e
My solution was to use the dotEngine-function to translate the operations into a digraph in graphviz-style which I simply plotted and searched through using a python script.
dotEngine
dotEngine (input1:operation:input2:_:output:[]) = [
input1 ++ " -> " ++ output ++ " [ label=" ++ operation ++ "];"
, input2 ++ " -> " ++ output ++ " [ label=" ++ operation ++ "];"
]
I took a loook at the initial graph which was a vertical line with a few exception which I figured would be the misordered wires.
I did try some hardware-simulations in the far past to build bit-adders which helped me recognize patterns like carry calculation.
First I replaced all occurences of x__ XOR y__ -> w with x__ XOR y__ -> xor__ to recognize them more easily. The same with AND of xs and ys.
Using the following script I would then use some Regex to search for the rules that corresponded to carry calculations or structures I knew. The script would break exactly four times and I would then figure out what to switch by hand through looking at the updated graphViz.
Please excuse the bad coding style in the script, I had written it on the ipython-REPL.
python script
r = open("input").read()
for i in range(2, 45):
prevI = str(i - 1).zfill(2)
I = str(i).zfill(2)
forward = f"xor{I} AND carry{prevI} -> (\\w+)"
backward = f"carry{prevI} AND xor{I} -> (\\w+)"
m1 = re.search(forward, r)
m2 = re.search(backward, r)
if m1 is None and m2 is None:
print(forward, backward)
break
m = m1 or m2
r = r.replace(m.group(1), f"combinedCarry{I}")
forward = f"and{I} OR combinedCarry{I} -> (\\w+)"
backward = f"combinedCarry{I} OR and{I} -> (\\w+)"
m1 = re.search(forward, r)
m2 = re.search(backward, r)
if m1 is None and m2 is None:
print(forward, backward)
break
m = m1 or m2
r = r.replace(m.group(1), f"carry{I}")
open("input", "w").write()
When solving such a swapped wire problem I would then use my haskell function to plot it out again and stare at it for a few minutes until I understood wich parts belonged where.
The last one looked like this
In this one I needed to switch jdr and carry31 to make it work.
Haskell
For part2 I compared the bits in the solution of part1 with the sum of x and y. With that, I could check the bits that did not match in a graphviz diagram and work from there.
code
import Control.Arrow
import Control.Monad.RWS
import Data.Bits (shiftL)
import Data.Char (digitToInt)
import Data.Functor
import Data.List
import Data.Map qualified as M
import Data.Tuple
import Text.ParserCombinators.ReadP hiding (get)
import Text.ParserCombinators.ReadP qualified as ReadP
type Cable = String
data Connection = And Cable Cable | Or Cable Cable | Xor Cable Cable deriving (Show)
cable = count 3 ReadP.get
eol = char '\n'
initial :: ReadP (M.Map Cable Bool)
initial = M.fromList <$> endBy ((,) <$> cable <*> (string ": " *> (toEnum . digitToInt <$> ReadP.get))) eol
wires = M.fromList <$> endBy wire eol
wire = do
a <- cable <* char ' '
op <- choice [string "AND" $> And, string "OR" $> Or, string "XOR" $> Xor]
b <- char ' ' *> cable
c <- string " -> " *> cable
return (c, op a b)
parse = fst . last . readP_to_S ((,) <$> initial <*> (eol *> wires <* eof))
type Problem = RWS (M.Map Cable Connection) () (M.Map Cable Bool)
getConnection :: Connection -> Problem Bool
getConnection (And a b) = (&&) <$> getWire a <*> getWire b
getConnection (Or a b) = (||) <$> getWire a <*> getWire b
getConnection (Xor a b) = xor <$> getWire a <*> getWire b
xor True False = True
xor False True = True
xor _ _ = False
getWire :: Cable -> Problem Bool
getWire cable = do
let computed = do
a <- asks (M.! cable) >>= getConnection
modify (M.insert cable a)
return a
gets (M.!? cable) >>= maybe computed return
fromBin :: [Bool] -> Int
fromBin = sum . fmap fst . filter snd . zip (iterate (`shiftL` 1) 1)
toBin :: Int -> [Bool]
toBin = unfoldr (\v -> if v == 0 then Nothing else Just (first (== 1) (swap (divMod v 2))))
part1 initial wiring = fst $ evalRWS (mapM getWire zs) wiring initial
where
zs = filter ((== 'z') . head) . sort $ M.keys wiring
part2 initial wiring = fmap fst . filter snd $ zip [0..] (zipWith (/=) p1 expect)
where
xs = fromBin . fmap (initial M.!) . filter ((== 'x') . head) $ sort $ M.keys initial
ys = fromBin . fmap (initial M.!) . filter ((== 'y') . head) $ sort $ M.keys initial
zs = filter ((== 'z') . head) . sort $ M.keys wiring
p1 = part1 initial wiring
expect = toBin $ xs + ys
main = getContents >>= print . (fromBin . uncurry part1 &&& uncurry part2) . parse
Haskell, programmatic solution
I spent an entire day on this because I didn’t write a unit test to check my “swap outputs” function, which effectively did nothing.
In any case: the approach (which may be more interesting than the code, I know people were interested) involved probing the addition circuit with some example additions - that is, I wrote something that’d let me give alternative inputs from x & y and compute the result using the circuit. I then gave it some simple pairs of values that’d exercise the add and carry bits (ie, pairs chosen from {i << n, n <- {1..43}, i <- {1, 3}}). That gave me some breaking trials.
Because the errors were relatively sparse, I then scanned over pairs of outputs, swapping those that didn’t introduce a data dependency and checking (a) that no new errors were introduced over the trial sets, (b) for any reduction in the number of errors found. I got a bunch fo outputs like this:
swap of ("ccp","mnh") improves matters
bad trial count reduced from 346 to 344
which found the pairs for me. The search could be improved by more carefully tying the probe inputs to the outputs’ dependencies (ie, if the first error comes from the (xi, yi) input bits, then look for swaps of the dependencies introduced by zi) - but in any case, it finds the answer. Phew.
