+/AoC

advent of code

git clone https://git.julia.blue/+/AoC

Julia RyanCleanup8111133

master
3.2 KiB112 linesraw
1from collections import deque
2from operator import or_, and_, xor
3
4
5with open("input") as f:
6    initial, allgates = f.read().split("\n\n")
7
8values = {name: int(val) for name, val in [s.split(":") for s in initial.splitlines()]}
9gates = deque()
10for g in allgates.splitlines():
11    l, op, r, _, out = g.split()
12    gates.append((l, r, {"AND": and_, "OR": or_, "XOR": xor}[op], out))
13original = gates.copy()
14
15while len(gates) > 0:
16    if not any(g[3].startswith("z") for g in gates):
17        break
18    (l, r, op, out) = cur = gates.popleft()
19    if l in values and r in values:
20        values[out] = op(values[l], values[r])
21    else:
22        gates.append(cur)
23
24extract = lambda l: ((int(k[1:]), v) for k, v in values.items() if k.startswith(l))
25num = lambda name: sum([b * 2**i for i, b in sorted(extract(name))])
26
27print(num("z"))
28
29print(f"{num("z"):046b}")
30# x, y = num("x"), num("y")
31# print(f"{x+y:046b}")
32# print()
33# print(f"{x:046b}")
34# print(f"{y:046b}")
35
36r"""
37how to add stuff:
38
39z0 = x0 ^ y0
40c0 = x0 & y0
41
42e1 = x1 ^ y1
43z1 = e1 ^ c0
44t1 = e1 & c0
45a1 = x1 & y1
46c1 = a1 | t1
47
48e2 = x2 ^ y2
49z2 = e2 ^ c1
50t2 = e2 & c1
51a2 = x2 & y2
52c2 = a2 | t2
53
54...
55
56e(xor)  = x ^ y
57z(um)   = e ^ c⁻¹
58t(mp)   = e & c⁻¹
59a(nd)   = x & y
60c(arry) = a | t     (except on last? or last carry is z⁺¹)
61
62so gate counts for input with b bits should be:
63 OR: b
64XOR: 2b + 1
65AND: 2b + 1
66
67counts for my input:
68 OR: 44
69AND: 89
70XOR: 89
71
72that means no extra gates which makes things way easier!
73i was so worried we'd have to do disjunctive normal form and
74minimization and SAT solving 😅
75
76wait a sec... if this is really just gonna be a bunch of term renaming, how
77far can i get with vim?
78put x's on left: :%s/y\(\d\d\) \(\S*\) x../x\1 \2 y\1
79sort by operation: :sort /.*\%3v/
80
81add some newlines between the e/z xors and the a/t ands so you can see the
825 groups of gates clearly.
83
84to rename xors: 0mal"ay2l$b"byw:%s/b/ea
85'aj
86                                       ⬆
87do the same for other letters by swapping this char
88
89now lets compute t, start by flipping all the "e\d\d"'s to the left side
90similarly to how we did x's at the start: %s/\(...\) \([A-Z]*\) \(e..\)/\3 \2 \1
91
92wait a sec, one of the ANDs doesn't have an e term... hopefully that means
93this is the first swapped wire. go back through the original input file to
94find their names
95
96alright back to computing temps. because we have mismatched numbers on the
97lhs and rhs, it's easiest to add a line to use as a loop variable of sorts
98at the top of the file, then we can use marks, gg, and ` to create a macro
99that goes to the top of the file, increments and yanks it, and then goes
100back to the mark, down a line and does a replacement similar to the xor
101renaming one.
102
103... actually scratch that, a simpler way would be to handle the ORs first
104since the numbers do line up there. also i think i see more mismatched wires?
105
106i continued to bumbled through like this and found the 4 pairs. I think
107I could write code to automate the renaming process, the annoying part
108would be accounting for the kinds of swaps (a,t,z,e,c pick 2). I don't
109feel like doing that especially because this approach falls over in the
110face of any extraneous gates, and maybe doesn't handle swaps across
111different bits?
112"""