day24.nim (5283B)
1 # Copyright (c) 2024, Natacha Porté 2 # 3 # Permission to use, copy, modify, and distribute this software for any 4 # purpose with or without fee is hereby granted, provided that the above 5 # copyright notice and this permission notice appear in all copies. 6 # 7 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 10 # ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 12 # ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 13 # OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 14 15 from std/algorithm import sorted 16 from std/sequtils import concat, foldl, mapIt, to_seq 17 from std/sets import `-`, contains, clear, excl, HashSet, incl, items 18 from std/strutils import join, parse_int, split 19 from std/tables import `[]`, `[]=`, has_key, keys, pairs, Table, to_table 20 21 # Read input file 22 23 proc read_input(): (Table[string, int], Table[string, seq[string]]) = 24 var first = true 25 for l in stdin.lines: 26 if l == "": 27 assert first 28 first = false 29 elif first: 30 let item = l.split(": ") 31 assert not result[0].has_key(item[0]) 32 assert len(item) == 2 33 assert item[1] == "0" or item[1] == "1" 34 result[0][item[0]] = parse_int(item[1]) 35 else: 36 let part1 = l.split(" -> ") 37 assert len(part1) == 2 38 assert not result[1].has_key(part1[1]) 39 let part2 = part1[0].split(" ") 40 assert len(part2) == 3 41 result[1][part1[1]] = part2 42 43 let (init, gates) = read_input() 44 45 # Puzzle 1 46 47 proc compute(values: var Table[string, int], gates: Table[string, seq[string]], v: string): int = 48 if values.has_key(v): 49 return values[v] 50 let 51 gate = gates[v] 52 left = compute(values, gates, gate[0]) 53 right = compute(values, gates, gate[2]) 54 case gate[1] 55 of "AND": result = left and right 56 of "OR": result = left or right 57 of "XOR": result = left xor right 58 else: assert false 59 assert result == 0 or result == 1 60 values[v] = result 61 62 func zkeys(gates: Table[string, seq[string]]): seq[string] = 63 for k in gates.keys(): 64 if k[0] == 'z': 65 result.add(k) 66 result = sorted(result) 67 68 func answer1(init: Table[string, int], gates: Table[string, seq[string]]): int = 69 var values = init 70 var factor = 1 71 result = 0 72 for k in zkeys(gates): 73 result += factor * compute(values, gates, k) 74 factor *= 2 75 76 echo "Puzzle 1: ", answer1(init, gates) 77 78 # Puzzle 2 79 80 proc extended_compute(values: var Table[string, int], gates: Table[string, seq[string]], v: string): int = 81 if values.has_key(v): 82 return values[v] 83 if not gates.has_key(v): 84 values[v] = -2 85 return -2 86 let 87 gate = gates[v] 88 left = extended_compute(values, gates, gate[0]) 89 right = extended_compute(values, gates, gate[2]) 90 if left < 0 or right < 0: 91 values[v] = -1 92 return -1 93 assert left == 0 or left == 1 94 assert right == 0 or right == 1 95 case gate[1] 96 of "AND": result = left and right 97 of "OR": result = left or right 98 of "XOR": result = left xor right 99 else: assert false 100 assert result == 0 or result == 1 101 values[v] = result 102 103 func suffix(index: int): string = 104 if index < 10: "0" & $index else: $index 105 106 func deps(gates: Table[string, seq[string]], root: string): HashSet[string] = 107 var to_visit = @[root] 108 result.incl(root) 109 while len(to_visit) > 0: 110 let head = to_visit[0] 111 to_visit = to_visit[1 .. ^1] 112 if gates.has_key(head): 113 let g = gates[head] 114 for d in @[g[0], g[2]]: 115 if d notin result: 116 result.incl(d) 117 to_visit.add(d) 118 119 proc test_adder(gates: Table[string, seq[string]], index: int): void = 120 let cur_suffix = suffix(index) 121 for x in @[0, 1]: 122 for y in @[0, 1]: 123 for cc in @[0, 1]: 124 let c = if index > 0: cc else: 0 125 var values = to_table(@[("x" & cur_suffix, x), ("y" & cur_suffix, y)]) 126 for i in 0 ..< index: 127 values["x" & suffix(i)] = if i == index-1: c else: 0 128 values["y" & suffix(i)] = if i == index-1: c else: 0 129 let res = extended_compute(values, gates, "z" & cur_suffix) 130 if res != (x + y + c) mod 2: 131 echo "Bad adder at ", index, ": ", res, " for ", x, " + ", y, " + ", c 132 let d = if index == 0: deps(gates, "z" & cur_suffix) else: deps(gates, "z" & cur_suffix) - deps(gates, "z" & suffix(index - 1)) 133 for k in d.items.to_seq.sorted: 134 if gates.has_key(k): 135 echo " ", k, ".", values[k], " = ", gates[k].join(" ") 136 else: 137 echo " ", k, ".", values[k] 138 139 func swap(gates: Table[string, seq[string]], p: seq[(string, string)]): Table[string, seq[string]] = 140 result = gates 141 for s in p: 142 result[s[0]] = gates[s[1]] 143 result[s[1]] = gates[s[0]] 144 145 # Fix list is manually generated, using test_adder output and 146 # pattern recognition inside the operator's brain. 147 let 148 fixes = @[("z06", "jmq"), ("z13", "gmh"), ("rqf", "cbd"), ("qrh", "z38")] 149 fixed_gates = swap(gates, fixes) 150 151 for k in zkeys(gates): 152 test_adder(fixed_gates, parse_int(k[1 .. ^1])) 153 154 echo "Puzzle 2: ", fixes.mapIt(@[it[0], it[1]]).foldl(concat(a, b)).sorted().join(",")