bendns' repos / aoc
heh
Diffstat (limited to 'src/main.rs')
-rw-r--r--src/main.rs93
1 files changed, 92 insertions, 1 deletions
diff --git a/src/main.rs b/src/main.rs
index fabbd10..fd0049a 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -140,9 +140,100 @@ pub fn p1(x: &str) -> impl Display {
z
}
+#[no_mangle]
+pub fn p2(x: &str) -> impl Display {
+ let mut gates = Vec::with_capacity(128);
+ let x = &x.as_bytes()[7 * 45 * 2 + 1..];
+ fn gate(x: &[u8]) -> [u8; 3] {
+ x.try_into().unwrap()
+ }
+ const XOR: u8 = 0;
+ const AND: u8 = 1;
+ const OR: u8 = 2;
+ for connection in x.行() {
+ let mut i = connection.split(|x| *x == b' ');
+ let [i1, op, i2, _, out] = std::array::from_fn(|_| i.Δ());
+ let [i1, i2, out] = [i1, i2, out].map(gate);
+ let op = match op {
+ b"XOR" => XOR,
+ b"AND" => AND,
+ b"OR" => OR,
+ _ => shucks!(),
+ };
+ gates.push((i1, i2, out, op));
+ }
+ let find = |i1, op: u8, i2| {
+ gates
+ .iter()
+ .find(|x| {
+ (x.0 == i1 && x.1 == i2 && x.3 == op) || (x.1 == i1 && x.0 == i2 && x.3 == op)
+ })
+ .map(|x| x.2)
+ };
+ let find_using = |op: u8, i2| {
+ gates.iter().find_map(|x| {
+ (x.1 == i2 && x.3 == op)
+ .then_some((x.0, x.2))
+ .or((x.0 == i2 && x.3 == op).then_some((x.1, x.2)))
+ })
+ };
+ // search for full adders (this is a ripple carry adder)
+ // x ^ y -> t0
+ // x & y -> t1
+ // c0 & t0 -> t2
+ // c0 ^ t0 -> z
+ // t1 | t2 -> c1
+ let mut swaps = vec![];
+ for [x, y, should_z] in const {
+ let input: [[[u8; 3]; 3]; 44] = car::from_fn!(|i| {
+ let i = i + 1;
+ let x = [b'x', (i as u8 / 10) + b'0', (i as u8 % 10) + b'0'];
+ let y = [b'y', (i as u8 / 10) + b'0', (i as u8 % 10) + b'0'];
+ let z = [b'z', (i as u8 / 10) + b'0', (i as u8 % 10) + b'0'];
+ [x, y, z]
+ });
+ input
+ } {
+ let t0 = find(x, XOR, y).unwrap(); // x ^ y -> t0
+
+ // println!("{} ^ {} -> {} (t0)", x.p(), y.p(), t0.p());
+
+ let t1 = find(x, AND, y).unwrap(); // x & y -> t1
+
+ // println!("{} & {} -> {} (t1)", x.p(), y.p(), t1.p());
+
+ // c0 & t0 -> t2
+ let Some((_c0, _t2)) = find_using(AND, t0) else {
+ swaps.push(t0);
+ swaps.push(t1);
+ // println!("swap {} with {}", t0.p(), t1.p());
+ continue;
+ };
+ // println!("(c0) {} & {} (t0) -> {} (t2)", c0.p(), t0.p(), t2.p());
+ let (_, z) = find_using(XOR, t0).unwrap(); // c0 ^ t0 -> z
+
+ // println!("(c0) {} ^ {} (t0) -> {} (z)", c0.p(), t0.p(), z.p());
+ if z != should_z {
+ swaps.push(z);
+ swaps.push(should_z);
+ // println!("swap {} with {}", z.p(), format!("z{i:02}"));
+ continue;
+ }
+ // t1 | t2 -> c1
+ // let c1 = find(t1, b"OR", t2).unwrap();
+ }
+ swaps.sort_unstable();
+ let mut out = String::with_capacity(40);
+ for swap in swaps {
+ use std::fmt::Write;
+ _ = write!(out, "{},", swap.p());
+ }
+ out
+}
+
fn main() {
let s = include_str!("inp.txt");
- println!("{}", unsafe { p1(s) });
+ println!("{}", unsafe { p2(s) });
// dbg!(exec(&program, regi));
}