🌟 Advent of Code (AoC) 2024 🌟

kh-tc
qp-kh
de-cg
ka-co
...

In this example, there are 12 such sets of three inter-connected computers:

aq,cg,yn
aq,vc,wq
co,de,ka
co,de,ta
co,ka,ta
de,ka,ta
kh,qp,ub
qp,td,wh
tb,vc,wq
tc,td,wh
td,wh,yn
ub,vc,wq

use ahash::{AHashMap, AHashSet};
use itertools::Itertools;
use std::{collections::VecDeque, fs::read_to_string};

pub const INPUT_FILE: &str = "input.txt";

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum Op {
    And,
    Or,
    Xor,
}

pub fn read_gates(
    path: &str,
) -> (
    Vec<(usize, bool)>,
    Vec<(usize, usize, Op, usize)>,
    AHashMap<String, usize>,
) {
    let content = read_to_string(path).expect("Failed to read the file");
    let sections = content.split_once("\n\n").unwrap();
    let mut value_indexes = AHashMap::new();
    let mut add_value_index = |name: &str| {
        if !value_indexes.contains_key(name) {
            value_indexes.insert(name.to_string(), value_indexes.len());
        }
    };
    let gates = sections
        .1
        .lines()
        .map(|line| {
            let parts = line.split_ascii_whitespace().collect::<Vec<_>>();
            let (i0, i1, out) = (parts[0], parts[2], parts[4]);
            add_value_index(i0);
            add_value_index(i1);
            add_value_index(out);
            (
                i0.to_string(),
                i1.to_string(),
                match parts[1] {
                    "AND" => Op::And,
                    "OR" => Op::Or,
                    "XOR" => Op::Xor,
                    _ => panic!("Invalid operation"),
                },
                out.to_string(),
            )
        })
        .collect::<Vec<_>>();
    let initial_values = sections
        .0
        .lines()
        .map(|line| {
            let (name, value) = line.split_once(": ").unwrap();
            (*value_indexes.get(name).unwrap(), value == "1")
        })
        .collect();
    let gates_with_index = gates
        .iter()
        .map(|(i0, i1, op, out)| {
            (
                *value_indexes.get(i0).unwrap(),
                *value_indexes.get(i1).unwrap(),
                *op,
                *value_indexes.get(out).unwrap(),
            )
        })
        .collect();
    (initial_values, gates_with_index, value_indexes)
}

pub fn part1(
    initial_values: &[(usize, bool)],
    gate_configs: &[(usize, usize, Op, usize)],
    value_name_to_index: &AHashMap<String, usize>,
) -> u64 {
    let mut values = vec![None; value_name_to_index.len()];
    for &(index, value) in initial_values {
        values[index] = Some(value);
    }
    run_gates(&mut values, gate_configs, value_name_to_index).unwrap()
}

pub fn part2(
    initial_values: &[(usize, bool)],
    gate_configs: &[(usize, usize, Op, usize)],
    value_name_to_index: &AHashMap<String, usize>,
) -> String {
    let mut value_index_to_name = vec![""; value_name_to_index.len()];
    let mut out_index_to_bit = AHashMap::new();
    let mut z_bits = 0;
    for (name, &index) in value_name_to_index {
        value_index_to_name[index] = name.as_str();
        if name.starts_with("z") {
            z_bits += 1;
            let bit = name[1..].parse::<usize>().unwrap();
            out_index_to_bit.insert(index, bit);
        }
    }

    let mut gates = Vec::new();
    let mut must_swap_zs = Vec::new();
    let mut may_swap_index = AHashSet::new();
    let mut xor_inputs = vec![0usize; z_bits - 1];
    // For an full adder, operation leading to output must be XOR, so any output to Zxx with another operation must be swapped
    for (index, &(i0, i1, op, out)) in gate_configs.iter().enumerate() {
        gates.push((i0, i1, op, out));
        let in_name = value_index_to_name[i1];
        let out_name = value_index_to_name[out];
        if out_name.starts_with("z") {
            let bit = out_name[1..].parse::<usize>().unwrap();
            if bit < z_bits - 1 && op != Op::Xor {
                must_swap_zs.push((bit, index));
            }
        } else {
            if op == Op::Xor && (in_name.starts_with("x") || in_name.starts_with("y")) {
                let bit = in_name[1..].parse::<usize>().unwrap();
                xor_inputs[bit] = index;
            }
            may_swap_index.insert(index);
        }
    }
    // Operation from input Xn + Yn always has a path Xn XOR Yn -> midA XOR midB -> Zn
    // So there outputs found above must be moved with whatever now is midA or modB
    let mut swapped_outputs = Vec::new();
    for (bit, z_gate_index) in must_swap_zs {
        let mid_value = gates[xor_inputs[bit]].3;
        let swap_gate_index = gates
            .iter()
            .enumerate()
            .find(|(_, gate)| gate.2 == Op::Xor && (gate.0 == mid_value || gate.1 == mid_value))
            .unwrap()
            .0;
        (gates[z_gate_index].3, gates[swap_gate_index].3) =
            (gates[swap_gate_index].3, gates[z_gate_index].3);
        swapped_outputs.push(value_index_to_name[gates[z_gate_index].3]);
        swapped_outputs.push(value_index_to_name[gates[swap_gate_index].3]);
        may_swap_index.remove(&swap_gate_index);
    }

    let mut values = vec![None; value_name_to_index.len()];
    for &(index, value) in initial_values {
        values[index] = Some(value);
    }
    let x = register_value("x", &values, value_name_to_index);
    let y = register_value("y", &values, value_name_to_index);
    let z = x + y;

    for swap in may_swap_index.iter().combinations(2) {
        let (i, j) = (*swap[0], *swap[1]);
        (gates[i].3, gates[j].3) = (gates[j].3, gates[i].3);

        if let Some(computed_z) = run_gates(&mut values, &gates, value_name_to_index) {
            if z == computed_z {
                swapped_outputs.push(value_index_to_name[gates[i].3]);
                swapped_outputs.push(value_index_to_name[gates[j].3]);
                swapped_outputs.sort();
                return swapped_outputs.join(",");
            }
        }

        (gates[i].3, gates[j].3) = (gates[j].3, gates[i].3);
        values.fill(None);
        for &(index, value) in initial_values {
            values[index] = Some(value);
        }
    }

    panic!("No solution found");
}

fn run_gates(
    values: &mut Vec<Option<bool>>,
    gate_configs: &[(usize, usize, Op, usize)],
    value_name_to_index: &AHashMap<String, usize>,
) -> Option<u64> {
    let mut gates = VecDeque::new();
    for &gate in gate_configs {
        gates.push_front(gate);
    }
    let mut progress = gates.len();
    while let Some(gate) = gates.pop_back() {
        let (i0_index, i1_index, op, out_index) = gate;
        if let (Some(i0), Some(i1)) = (values[i0_index], values[i1_index]) {
            progress = gates.len();
            let out = match op {
                Op::And => i0 & i1,
                Op::Or => i0 | i1,
                Op::Xor => i0 ^ i1,
            };
            values[out_index] = Some(out);
        } else {
            gates.push_front(gate);
            progress -= 1;
            if progress == 0 {
                return None;
            }
        }
    }
    Some(register_value("z", &values, value_name_to_index))
}

fn register_value(
    reg_name: &str,
    values: &Vec<Option<bool>>,
    value_name_to_index: &AHashMap<String, usize>,
) -> u64 {
    value_name_to_index
        .iter()
        .fold(0, |number, (name, &index)| {
            if name.starts_with(reg_name) && values[index].unwrap() {
                let bit = name[1..].parse::<usize>().unwrap();
                number | (1 << bit)
            } else {
                number
            }
        })
}

fn main() {
    let (initial_values, gates, value_indexes) = read_gates(INPUT_FILE);
    println!("part 1: {}", part1(&initial_values, &gates, &value_indexes));
    println!("part 2: {}", part2(&initial_values, &gates, &value_indexes));
}

use std::fs::read_to_string;

pub const INPUT_FILE: &str = "input.txt";

pub type Schematics = [u32; 5];

pub fn read_locks_and_keys(path: &str) -> (Vec<Schematics>, Vec<Schematics>) {
    let content = read_to_string(path).expect("Failed to read file");
    let blocks = content.split("\n\n").collect::<Vec<_>>();
    let mut locks = Vec::new();
    let mut keys = Vec::new();

    for block in blocks {
        let lines = block.lines().collect::<Vec<_>>();
        let mut schematic = [0; 5];
        for line in &lines[1..(lines.len() - 1)] {
            for (i, ch) in line.chars().enumerate() {
                if ch == '#' {
                    schematic[i] += 1;
                }
            }
        }
        if lines[0] == "#####" {
            locks.push(schematic);
        } else {
            keys.push(schematic);
        }
    }

    (locks, keys)
}

pub fn part1(locks: &[Schematics], keys: &[Schematics]) -> usize {
    let mut fitting_pairs = 0;
    for lock in locks {
        for key in keys {
            if lock.iter().zip(key.iter()).all(|(l, k)| l + k <= 5) {
                fitting_pairs += 1;
            }
        }
    }
    fitting_pairs
}

fn main() {
    let (locks, keys) = read_locks_and_keys(INPUT_FILE);
    println!("part 1: {}", part1(&locks, &keys));
}