- commit
- 6d197c44c53a0baecd11260fdbfa802264aa3acf
- parent
- 579058de161dc8383f62df63e3193bc5c815ef26
- Author
- Tobias Bengfort <tobias.bengfort@posteo.de>
- Date
- 2024-12-26 00:21
2024-12-24
Diffstat
| A | 2024/24/input.txt | 313 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/24/solution.rs | 193 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/24/test1.txt | 10 | ++++++++++ |
| A | 2024/24/test2.txt | 47 | +++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2024/24/test3.txt | 19 | +++++++++++++++++++ |
5 files changed, 582 insertions, 0 deletions
diff --git a/2024/24/input.txt b/2024/24/input.txt
@@ -0,0 +1,313 @@ -1 1 x00: 1 -1 2 x01: 1 -1 3 x02: 0 -1 4 x03: 0 -1 5 x04: 0 -1 6 x05: 1 -1 7 x06: 0 -1 8 x07: 1 -1 9 x08: 1 -1 10 x09: 0 -1 11 x10: 1 -1 12 x11: 0 -1 13 x12: 0 -1 14 x13: 1 -1 15 x14: 0 -1 16 x15: 1 -1 17 x16: 0 -1 18 x17: 0 -1 19 x18: 0 -1 20 x19: 1 -1 21 x20: 0 -1 22 x21: 0 -1 23 x22: 1 -1 24 x23: 1 -1 25 x24: 0 -1 26 x25: 1 -1 27 x26: 0 -1 28 x27: 1 -1 29 x28: 0 -1 30 x29: 0 -1 31 x30: 1 -1 32 x31: 0 -1 33 x32: 1 -1 34 x33: 0 -1 35 x34: 0 -1 36 x35: 0 -1 37 x36: 0 -1 38 x37: 1 -1 39 x38: 0 -1 40 x39: 0 -1 41 x40: 0 -1 42 x41: 1 -1 43 x42: 1 -1 44 x43: 1 -1 45 x44: 1 -1 46 y00: 1 -1 47 y01: 0 -1 48 y02: 1 -1 49 y03: 1 -1 50 y04: 0 -1 51 y05: 0 -1 52 y06: 1 -1 53 y07: 1 -1 54 y08: 0 -1 55 y09: 1 -1 56 y10: 1 -1 57 y11: 1 -1 58 y12: 1 -1 59 y13: 1 -1 60 y14: 0 -1 61 y15: 1 -1 62 y16: 1 -1 63 y17: 1 -1 64 y18: 1 -1 65 y19: 0 -1 66 y20: 0 -1 67 y21: 0 -1 68 y22: 1 -1 69 y23: 1 -1 70 y24: 0 -1 71 y25: 0 -1 72 y26: 0 -1 73 y27: 0 -1 74 y28: 1 -1 75 y29: 1 -1 76 y30: 0 -1 77 y31: 1 -1 78 y32: 0 -1 79 y33: 1 -1 80 y34: 1 -1 81 y35: 0 -1 82 y36: 0 -1 83 y37: 1 -1 84 y38: 0 -1 85 y39: 0 -1 86 y40: 0 -1 87 y41: 1 -1 88 y42: 0 -1 89 y43: 1 -1 90 y44: 1 -1 91 -1 92 y13 AND x13 -> pfp -1 93 y08 XOR x08 -> wkm -1 94 y01 XOR x01 -> hqt -1 95 bhs AND vcd -> rwn -1 96 y23 XOR x23 -> srm -1 97 hrf AND swk -> hph -1 98 mnk XOR ttp -> z29 -1 99 y02 AND x02 -> dpq -1 100 y30 AND x30 -> bbw -1 101 thd OR hqc -> jhn -1 102 hsj XOR rkn -> z19 -1 103 vvv OR vhb -> php -1 104 fvk OR dpq -> rmb -1 105 dcg AND mjn -> nrm -1 106 dsr AND rqq -> hdf -1 107 jpm XOR pvd -> z43 -1 108 dht XOR vww -> z21 -1 109 csg OR wnn -> z45 -1 110 wsd XOR jbn -> z42 -1 111 mrw XOR jsb -> z22 -1 112 vww AND dht -> bcg -1 113 gqs OR gdq -> vss -1 114 y05 AND x05 -> qks -1 115 y29 XOR x29 -> mnk -1 116 rqt XOR qdd -> z37 -1 117 y11 AND x11 -> pbw -1 118 nbm XOR vpk -> z06 -1 119 vqc AND pcs -> nnj -1 120 jbn AND wsd -> vdm -1 121 wtv OR nnj -> sfv -1 122 x20 XOR y20 -> wks -1 123 kcj OR rwn -> pst -1 124 bnq OR rfv -> hst -1 125 y40 XOR x40 -> qwr -1 126 pwg OR ghj -> dht -1 127 pst AND pks -> rpj -1 128 pst XOR pks -> z27 -1 129 dcd OR bdg -> msm -1 130 y23 AND x23 -> vjv -1 131 x12 XOR y12 -> kfs -1 132 x32 XOR y32 -> qcs -1 133 bhs XOR vcd -> z26 -1 134 y38 XOR x38 -> cdb -1 135 y21 AND x21 -> mth -1 136 nsk OR kjg -> wbn -1 137 y12 AND x12 -> fvr -1 138 y33 XOR x33 -> vqc -1 139 y41 AND x41 -> cdr -1 140 btr AND tmt -> jwt -1 141 wks XOR wgs -> z20 -1 142 y25 AND x25 -> cgg -1 143 npp XOR kfs -> z12 -1 144 jwt OR mdh -> rqt -1 145 y13 XOR x13 -> cbp -1 146 x01 AND y01 -> qng -1 147 wks AND wgs -> ghj -1 148 x14 AND y14 -> wkg -1 149 hfm XOR hqt -> z01 -1 150 mht XOR gwt -> z10 -1 151 php XOR qpd -> z41 -1 152 mnk AND ttp -> gqs -1 153 y24 XOR x24 -> mqq -1 154 fcp OR jnv -> nmq -1 155 fgm AND cbp -> jsn -1 156 bgw OR hdf -> mmq -1 157 dcg XOR mjn -> z14 -1 158 y08 AND x08 -> bdg -1 159 y05 XOR x05 -> vmd -1 160 x03 XOR y03 -> wmn -1 161 tgg XOR fsb -> z35 -1 162 srm AND rsf -> gtj -1 163 njw OR rpj -> hrf -1 164 fsb AND tgg -> fkq -1 165 y07 XOR x07 -> krv -1 166 bfr AND dmw -> fvk -1 167 hqt AND hfm -> hkm -1 168 x35 AND y35 -> drp -1 169 x34 XOR y34 -> jrw -1 170 rft OR nrt -> wnb -1 171 rkn AND hsj -> vmf -1 172 x11 XOR y11 -> dbm -1 173 x06 AND y06 -> dsw -1 174 krt XOR dbm -> z11 -1 175 nmp AND mqq -> rgc -1 176 fgm XOR cbp -> z13 -1 177 mmq XOR dhp -> z16 -1 178 jcm OR bbw -> hdn -1 179 y30 XOR x30 -> tmc -1 180 ndk OR fvr -> fgm -1 181 jgd AND msm -> rcs -1 182 dmw XOR bfr -> z02 -1 183 jsb AND mrw -> kwp -1 184 x44 AND y44 -> wnn -1 185 wmn AND rmb -> jnw -1 186 qks OR jgc -> nbm -1 187 y34 AND x34 -> jrt -1 188 srn OR fqc -> pcs -1 189 vpk AND nbm -> gdb -1 190 wmn XOR rmb -> z03 -1 191 mht AND gwt -> vwp -1 192 y02 XOR x02 -> bfr -1 193 pbw OR jfr -> npp -1 194 x17 XOR y17 -> pcp -1 195 x24 AND y24 -> z24 -1 196 x39 XOR y39 -> fmv -1 197 y28 XOR x28 -> swk -1 198 y17 AND x17 -> fgt -1 199 rsf XOR srm -> z23 -1 200 x19 AND y19 -> dpm -1 201 x41 XOR y41 -> qpd -1 202 vwp OR ttt -> krt -1 203 jgp OR kkw -> rkn -1 204 y06 XOR x06 -> vpk -1 205 wkg OR nrm -> rqq -1 206 fkq OR drp -> tmt -1 207 hbs AND fcg -> kkw -1 208 nmp XOR mqq -> fpq -1 209 x09 XOR y09 -> jgd -1 210 hst AND qwr -> vhb -1 211 x18 AND y18 -> jgp -1 212 fsh XOR jhn -> z44 -1 213 fgt AND nmq -> vtv -1 214 x15 AND y15 -> bgw -1 215 nqk XOR wkm -> z08 -1 216 vjv OR gtj -> nmp -1 217 fth AND qcs -> z32 -1 218 nqk AND wkm -> dcd -1 219 vmd AND wbn -> jgc -1 220 pgc OR jrt -> tgg -1 221 jrw XOR sfv -> z34 -1 222 hbs XOR fcg -> z18 -1 223 jrw AND sfv -> pgc -1 224 fth XOR qcs -> srn -1 225 x18 XOR y18 -> hbs -1 226 x26 XOR y26 -> vcd -1 227 fmv AND wnb -> bnq -1 228 tqj OR hph -> ttp -1 229 gdb OR dsw -> btq -1 230 vqc XOR pcs -> z33 -1 231 rgc OR fpq -> tgs -1 232 vmf OR dpm -> wgs -1 233 y28 AND x28 -> tqj -1 234 y00 XOR x00 -> z00 -1 235 btq AND krv -> stq -1 236 x32 AND y32 -> fqc -1 237 cdb XOR crc -> z38 -1 238 qhk AND fcw -> nsk -1 239 php AND qpd -> rdj -1 240 qtc OR ghf -> crc -1 241 qhk XOR fcw -> z04 -1 242 kpw AND tgs -> kth -1 243 x42 AND y42 -> gsr -1 244 npp AND kfs -> ndk -1 245 y14 XOR x14 -> dcg -1 246 pjh OR sdp -> fth -1 247 x37 XOR y37 -> qdd -1 248 y37 AND x37 -> ghf -1 249 stq OR jss -> z07 -1 250 y00 AND x00 -> hfm -1 251 y16 AND x16 -> fcp -1 252 y43 AND x43 -> hqc -1 253 wnb XOR fmv -> z39 -1 254 jnw OR rjn -> fcw -1 255 tgs XOR kpw -> z25 -1 256 pvd AND jpm -> thd -1 257 x42 XOR y42 -> wsd -1 258 y03 AND x03 -> rjn -1 259 y22 AND x22 -> scr -1 260 y19 XOR x19 -> hsj -1 261 x33 AND y33 -> wtv -1 262 scr OR kwp -> rsf -1 263 x07 AND y07 -> jss -1 264 x15 XOR y15 -> dsr -1 265 x43 XOR y43 -> jpm -1 266 rdj OR cdr -> jbn -1 267 dsr XOR rqq -> z15 -1 268 hdn XOR qdb -> z31 -1 269 x29 AND y29 -> gdq -1 270 y04 AND x04 -> kjg -1 271 mth OR bcg -> jsb -1 272 dbm AND krt -> jfr -1 273 y40 AND x40 -> vvv -1 274 msm XOR jgd -> z09 -1 275 vmd XOR wbn -> z05 -1 276 y38 AND x38 -> rft -1 277 qng OR hkm -> dmw -1 278 nmq XOR fgt -> z17 -1 279 y04 XOR x04 -> qhk -1 280 swk XOR hrf -> z28 -1 281 y10 XOR x10 -> gwt -1 282 krv XOR btq -> nqk -1 283 y10 AND x10 -> ttt -1 284 vss XOR tmc -> z30 -1 285 x26 AND y26 -> kcj -1 286 y36 AND x36 -> mdh -1 287 hst XOR qwr -> z40 -1 288 x27 XOR y27 -> pks -1 289 y16 XOR x16 -> dhp -1 290 y20 AND x20 -> pwg -1 291 tmt XOR btr -> z36 -1 292 gsr OR vdm -> pvd -1 293 y35 XOR x35 -> fsb -1 294 x22 XOR y22 -> mrw -1 295 kth OR cgg -> bhs -1 296 jsn OR pfp -> mjn -1 297 y09 AND x09 -> gdd -1 298 dhp AND mmq -> jnv -1 299 x31 AND y31 -> sdp -1 300 tmc AND vss -> jcm -1 301 jhn AND fsh -> csg -1 302 rqt AND qdd -> qtc -1 303 x27 AND y27 -> njw -1 304 x21 XOR y21 -> vww -1 305 y44 XOR x44 -> fsh -1 306 qdb AND hdn -> pjh -1 307 vtv OR pcp -> fcg -1 308 x39 AND y39 -> rfv -1 309 rcs OR gdd -> mht -1 310 x31 XOR y31 -> qdb -1 311 cdb AND crc -> nrt -1 312 y25 XOR x25 -> kpw -1 313 x36 XOR y36 -> btr
diff --git a/2024/24/solution.rs b/2024/24/solution.rs
@@ -0,0 +1,193 @@
-1 1 use std::collections::HashMap;
-1 2
-1 3 #[path = "../lib.rs"]
-1 4 mod lib;
-1 5
-1 6 enum Operator {
-1 7 And,
-1 8 Or,
-1 9 Xor,
-1 10 }
-1 11
-1 12 #[derive(PartialEq, Eq, PartialOrd, Ord)]
-1 13 enum NodeType {
-1 14 X,
-1 15 Y,
-1 16 Z,
-1 17 XandY,
-1 18 XandY0,
-1 19 XxorY,
-1 20 CarryAndXY,
-1 21 Carry,
-1 22 }
-1 23
-1 24 fn parse_input() -> (usize, usize, HashMap<String, (String, Operator, String)>) {
-1 25 let mut rules = HashMap::new();
-1 26 let mut x = 0;
-1 27 let mut y = 0;
-1 28 let mut init = true;
-1 29
-1 30 for line in lib::iter_input() {
-1 31 if line == "" {
-1 32 init = false;
-1 33 } else if init {
-1 34 let (key, s) = line.split_once(": ").unwrap();
-1 35 if s == "1" {
-1 36 let k = key[1..].parse::<usize>().unwrap();
-1 37 if key.starts_with('x') {
-1 38 x |= 1 << k;
-1 39 } else {
-1 40 y |= 1 << k;
-1 41 }
-1 42 }
-1 43 } else {
-1 44 let (tmp1, key) = line.split_once(" -> ").unwrap();
-1 45 let (lhs, tmp2) = tmp1.split_once(' ').unwrap();
-1 46 let (sop, rhs) = tmp2.split_once(' ').unwrap();
-1 47 let op = match sop {
-1 48 "AND" => Operator::And,
-1 49 "OR" => Operator::Or,
-1 50 "XOR" => Operator::Xor,
-1 51 _ => unreachable!(),
-1 52 };
-1 53 rules.insert(key.to_string(), (lhs.to_string(), op, rhs.to_string()));
-1 54 }
-1 55 }
-1 56
-1 57 return (x, y, rules);
-1 58 }
-1 59
-1 60 fn get_value(
-1 61 key: &str,
-1 62 x: usize,
-1 63 y: usize,
-1 64 values: &mut HashMap<String, bool>,
-1 65 rules: &HashMap<String, (String, Operator, String)>,
-1 66 ) -> bool {
-1 67 if let Some(r) = values.get(key) {
-1 68 return *r;
-1 69 } else if key.starts_with('x') {
-1 70 let k = key[1..].parse::<usize>().unwrap();
-1 71 return (x >> k) & 1 == 1;
-1 72 } else if key.starts_with('y') {
-1 73 let k = key[1..].parse::<usize>().unwrap();
-1 74 return (y >> k) & 1 == 1;
-1 75 }
-1 76 let (lhs, op, rhs) = rules.get(key).unwrap();
-1 77 let l = get_value(lhs, x, y, values, rules);
-1 78 let r = get_value(rhs, x, y, values, rules);
-1 79 return match op {
-1 80 Operator::And => l && r,
-1 81 Operator::Or => l || r,
-1 82 Operator::Xor => l ^ r,
-1 83 };
-1 84 }
-1 85
-1 86 fn calc(x: usize, y: usize, rules: &HashMap<String, (String, Operator, String)>) -> usize {
-1 87 let mut values = HashMap::new();
-1 88 let mut z = 0;
-1 89 for key in rules.keys() {
-1 90 if key.starts_with('z') && get_value(key, x, y, &mut values, &rules) {
-1 91 z |= 1 << key[1..].parse::<usize>().unwrap();
-1 92 }
-1 93 }
-1 94 return z;
-1 95 }
-1 96
-1 97 fn rules2dot(rules: &HashMap<String, (String, Operator, String)>) {
-1 98 println!("digraph d {{");
-1 99 for (key, (lhs, op, rhs)) in rules.iter() {
-1 100 let color = match op {
-1 101 Operator::And => "red",
-1 102 Operator::Or => "green",
-1 103 Operator::Xor => "yellow",
-1 104 };
-1 105 println!(" {lhs} -> {key};");
-1 106 println!(" {rhs} -> {key};");
-1 107 println!(" {key} [fillcolor={color},style=filled];");
-1 108 }
-1 109 println!("}}");
-1 110 }
-1 111
-1 112 fn get_type(key: &str, rules: &HashMap<String, (String, Operator, String)>) -> NodeType {
-1 113 if key.starts_with('x') {
-1 114 return NodeType::X;
-1 115 } else if key.starts_with('y') {
-1 116 return NodeType::Y;
-1 117 }
-1 118
-1 119 let (lhs, op, rhs) = rules.get(key).unwrap();
-1 120 // println!("{key}: {lhs} {op:?} {rhs}");
-1 121 if lhs.starts_with('x') || rhs.starts_with('x') {
-1 122 return match op {
-1 123 Operator::And => if &lhs[1..] == "00" {
-1 124 NodeType::XandY0
-1 125 } else {
-1 126 NodeType::XandY
-1 127 },
-1 128 Operator::Or => unreachable!(),
-1 129 Operator::Xor => NodeType::XxorY,
-1 130 };
-1 131 }
-1 132 return match op {
-1 133 Operator::And => NodeType::CarryAndXY,
-1 134 Operator::Or => NodeType::Carry,
-1 135 Operator::Xor => NodeType::Z,
-1 136 };
-1 137 }
-1 138
-1 139 fn get_errors(rules: &HashMap<String, (String, Operator, String)>) -> String {
-1 140 // addition with logic gates works like this:
-1 141 //
-1 142 // z(i) = x(i) ^ y(i) ^ carry(i)
-1 143 // carry(i + 1) = (x(i) && y(i)) || (carry(i) && (x(i) ^ y(i)))
-1 144 //
-1 145 // Each node can be identified by looking at the inputs and operator only.
-1 146 // The first and last bits are special. The first bit has no carry;
-1 147 // the last bit has only carry.
-1 148
-1 149 let mut errors = vec![];
-1 150
-1 151 let mut outputs = HashMap::new();
-1 152 for (key, (lhs, _, rhs)) in rules.iter() {
-1 153 outputs.entry(key).or_insert(vec![]);
-1 154 outputs.entry(lhs).or_insert(vec![]).push(key);
-1 155 outputs.entry(rhs).or_insert(vec![]).push(key);
-1 156 }
-1 157
-1 158 for (key, out) in outputs.iter() {
-1 159 let mut out_types = vec![];
-1 160 for k in out.iter() {
-1 161 out_types.push(get_type(k, &rules));
-1 162 }
-1 163 out_types.sort();
-1 164
-1 165 if !match (get_type(key, &rules), &out_types[..]) {
-1 166 (NodeType::X, [NodeType::XandY, NodeType::XxorY]) => true,
-1 167 (NodeType::Y, [NodeType::XandY, NodeType::XxorY]) => true,
-1 168 (NodeType::X, [NodeType::XandY0, NodeType::XxorY]) => true,
-1 169 (NodeType::Y, [NodeType::XandY0, NodeType::XxorY]) => true,
-1 170 (NodeType::Z, []) => true,
-1 171 (NodeType::XandY, [NodeType::Carry]) => true,
-1 172 (NodeType::XandY0, [NodeType::Z, NodeType::CarryAndXY]) => true,
-1 173 (NodeType::XxorY, [NodeType::Z, NodeType::CarryAndXY]) => true,
-1 174 (NodeType::XxorY, []) if *key == "z00" => true,
-1 175 (NodeType::CarryAndXY, [NodeType::Carry]) => true,
-1 176 (NodeType::Carry, [NodeType::Z, NodeType::CarryAndXY]) => true,
-1 177 (NodeType::Carry, []) if *key == "z45" => true,
-1 178 _ => false,
-1 179 } {
-1 180 errors.push(key.to_string());
-1 181 }
-1 182 }
-1 183
-1 184 errors.sort();
-1 185 return errors.join(",");
-1 186 }
-1 187
-1 188 fn main() {
-1 189 let (x, y, rules) = parse_input();
-1 190
-1 191 println!("part1: {}", calc(x, y, &rules));
-1 192 println!("part2: {}", get_errors(&rules));
-1 193 }
diff --git a/2024/24/test1.txt b/2024/24/test1.txt
@@ -0,0 +1,10 @@ -1 1 x00: 1 -1 2 x01: 1 -1 3 x02: 1 -1 4 y00: 0 -1 5 y01: 1 -1 6 y02: 0 -1 7 -1 8 x00 AND y00 -> z00 -1 9 x01 XOR y01 -> z01 -1 10 x02 OR y02 -> z02
diff --git a/2024/24/test2.txt b/2024/24/test2.txt
@@ -0,0 +1,47 @@ -1 1 x00: 1 -1 2 x01: 0 -1 3 x02: 1 -1 4 x03: 1 -1 5 x04: 0 -1 6 y00: 1 -1 7 y01: 1 -1 8 y02: 1 -1 9 y03: 1 -1 10 y04: 1 -1 11 -1 12 ntg XOR fgs -> mjb -1 13 y02 OR x01 -> tnw -1 14 kwq OR kpj -> z05 -1 15 x00 OR x03 -> fst -1 16 tgd XOR rvg -> z01 -1 17 vdt OR tnw -> bfw -1 18 bfw AND frj -> z10 -1 19 ffh OR nrd -> bqk -1 20 y00 AND y03 -> djm -1 21 y03 OR y00 -> psh -1 22 bqk OR frj -> z08 -1 23 tnw OR fst -> frj -1 24 gnj AND tgd -> z11 -1 25 bfw XOR mjb -> z00 -1 26 x03 OR x00 -> vdt -1 27 gnj AND wpb -> z02 -1 28 x04 AND y00 -> kjc -1 29 djm OR pbm -> qhw -1 30 nrd AND vdt -> hwm -1 31 kjc AND fst -> rvg -1 32 y04 OR y02 -> fgs -1 33 y01 AND x02 -> pbm -1 34 ntg OR kjc -> kwq -1 35 psh XOR fgs -> tgd -1 36 qhw XOR tgd -> z09 -1 37 pbm OR djm -> kpj -1 38 x03 XOR y03 -> ffh -1 39 x00 XOR y04 -> ntg -1 40 bfw OR bqk -> z06 -1 41 nrd XOR fgs -> wpb -1 42 frj XOR qhw -> z04 -1 43 bqk OR frj -> z07 -1 44 y03 OR x01 -> nrd -1 45 hwm AND bqk -> z03 -1 46 tgd XOR rvg -> z12 -1 47 tnw OR pbm -> gnj
diff --git a/2024/24/test3.txt b/2024/24/test3.txt
@@ -0,0 +1,19 @@ -1 1 x00: 0 -1 2 x01: 1 -1 3 x02: 0 -1 4 x03: 1 -1 5 x04: 0 -1 6 x05: 1 -1 7 y00: 0 -1 8 y01: 0 -1 9 y02: 1 -1 10 y03: 1 -1 11 y04: 0 -1 12 y05: 1 -1 13 -1 14 x00 AND y00 -> z05 -1 15 x01 AND y01 -> z02 -1 16 x02 AND y02 -> z01 -1 17 x03 AND y03 -> z03 -1 18 x04 AND y04 -> z04 -1 19 x05 AND y05 -> z00