commit 1745ab68d95f754c07ffffcb6e6d2a0b71b89390
parent 87e5fe549f53d56d70763009fd4551dc697925ac
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Fri, 24 Dec 2021 05:29:38 -0600
Add 2021 day 24
Diffstat:
| A | 2021/day24/input.txt | | | 252 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | 2021/day24/main.rs | | | 218 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
2 files changed, 470 insertions(+), 0 deletions(-)
diff --git a/2021/day24/input.txt b/2021/day24/input.txt
@@ -0,0 +1,252 @@
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 11
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 8
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 12
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 8
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 10
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 12
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -8
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 10
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 15
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 2
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 15
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 8
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -11
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 4
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 10
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 9
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -3
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 10
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 15
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 3
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -3
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 7
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -1
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 7
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -10
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 2
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -16
+eql x w
+eql x 0
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y
+mul y 0
+add y w
+add y 2
+mul y x
+add z y
diff --git a/2021/day24/main.rs b/2021/day24/main.rs
@@ -0,0 +1,218 @@
+use std::collections::{HashMap, VecDeque};
+
+#[derive(Debug, Copy, Clone, Hash, Eq, PartialEq)]
+enum Reg {
+ W,
+ X,
+ Y,
+ Z,
+}
+
+impl Reg {
+ fn new(s: &str) -> Self {
+ match s {
+ "w" => Self::W,
+ "x" => Self::X,
+ "y" => Self::Y,
+ "z" => Self::Z,
+ _ => unreachable!(),
+ }
+ }
+
+ fn get_val(&self, regs: &HashMap<Reg, i64>) -> i64 {
+ *regs.get(self).unwrap_or(&0)
+ }
+}
+
+#[derive(Debug, Copy, Clone)]
+enum Arg {
+ Register(Reg),
+ Value(i64),
+}
+
+impl Arg {
+ fn new(s: &str) -> Self {
+ match s.parse::<i64>() {
+ Ok(val) => Self::Value(val),
+ Err(_) => Self::Register(Reg::new(s)),
+ }
+ }
+
+ fn get_val(&self, regs: &HashMap<Reg, i64>) -> i64 {
+ match self {
+ Self::Register(r) => *regs.get(r).unwrap_or(&0),
+ Self::Value(v) => *v,
+ }
+ }
+}
+
+#[derive(Debug, Copy, Clone)]
+enum Op {
+ Inp(Reg),
+ Add(Reg, Arg),
+ Mul(Reg, Arg),
+ Div(Reg, Arg),
+ Mod(Reg, Arg),
+ Eql(Reg, Arg),
+}
+
+impl Op {
+ fn new(s: &str) -> Self {
+ let mut it = s.split(' ');
+ match (it.next(), it.next(), it.next()) {
+ (Some("inp"), Some(a), None) => Self::Inp(Reg::new(a)),
+ (Some("add"), Some(a), Some(b)) => Self::Add(Reg::new(a), Arg::new(b)),
+ (Some("mul"), Some(a), Some(b)) => Self::Mul(Reg::new(a), Arg::new(b)),
+ (Some("div"), Some(a), Some(b)) => Self::Div(Reg::new(a), Arg::new(b)),
+ (Some("mod"), Some(a), Some(b)) => Self::Mod(Reg::new(a), Arg::new(b)),
+ (Some("eql"), Some(a), Some(b)) => Self::Eql(Reg::new(a), Arg::new(b)),
+ _ => unreachable!(),
+ }
+ }
+
+ fn eval(&self, regs: &mut HashMap<Reg, i64>, input: &mut VecDeque<i64>) {
+ match self {
+ Self::Inp(a) => {
+ regs.insert(*a, input.pop_front().unwrap());
+ }
+ Self::Add(a, b) => {
+ regs.insert(*a, a.get_val(regs) + b.get_val(regs));
+ }
+ Self::Mul(a, b) => {
+ regs.insert(*a, a.get_val(regs) * b.get_val(regs));
+ }
+ Self::Div(a, b) => {
+ regs.insert(*a, a.get_val(regs) / b.get_val(regs));
+ }
+ Self::Mod(a, b) => {
+ regs.insert(*a, a.get_val(regs) % b.get_val(regs));
+ }
+ Self::Eql(a, b) => {
+ regs.insert(*a, (a.get_val(regs) == b.get_val(regs)) as i64);
+ }
+ }
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<String>>();
+ let program = input.iter().map(|s| Op::new(&s)).collect::<Vec<Op>>();
+ let alt_program = (0..input.len())
+ .filter(|i| match i % (input.len() / 14) {
+ 4 | 5 | 15 => true,
+ _ => false,
+ })
+ .map(|i| {
+ input[i]
+ .split(' ')
+ .skip(2)
+ .next()
+ .unwrap()
+ .parse::<i64>()
+ .unwrap()
+ })
+ .collect::<Vec<_>>()
+ .chunks_exact(3)
+ .map(|c| (c[0], c[1], c[2]))
+ .collect::<Vec<(i64, i64, i64)>>();
+ println!("Part 1: {}", part_1(&program, &alt_program));
+ println!("Part 2: {}", part_2(&program, &alt_program));
+}
+
+fn run(program: &Vec<Op>, input: &VecDeque<i64>) -> i64 {
+ let mut input = input.clone();
+ let mut regs = HashMap::new();
+ for &op in program.iter() {
+ op.eval(&mut regs, &mut input);
+ }
+ *regs.get(&Reg::Z).unwrap()
+}
+
+fn alt_run(alt_input: &Vec<(i64, i64, i64)>, input: &VecDeque<i64>) -> i64 {
+ let mut input = input.clone();
+ let mut z = 0;
+ for &(v1, v2, v3) in alt_input {
+ let w = input.pop_front().unwrap();
+ // let x = ((z % 26 + v2) != w) as i64;
+ // z = (z / v1) * (x * 25 + 1) + (w + v3) * x;
+ if z % 26 != w - v2 {
+ z = z / v1 * 26 + w + v3;
+ } else {
+ z = z / v1;
+ }
+ // we always have v1 = 1 when v2 > 9 (upper path)
+ // these steps essentially enqueues (w + v3) into a stack (*= 26)
+ // conversely we always have v1 = 26 when v2 < 0
+ // we can deque (/= 26) if the last enqueued number is equal to (w - v2)
+ // there are 7 fixed enqueues, and goals is to follow the deque branch
+ // in other 7
+ }
+ z
+}
+
+fn part_1(program: &Vec<Op>, alt_program: &Vec<(i64, i64, i64)>) -> i64 {
+ let mut digits = [0; 14].iter().map(|&x| x).collect::<VecDeque<_>>();
+ let mut queue = VecDeque::<(usize, i64)>::new();
+ for (i, &(v1, v2, v3)) in alt_program.iter().enumerate() {
+ match v1 {
+ 1 => {
+ queue.push_back((i, v3));
+ }
+ 26 => {
+ let (prev_i, prev_v3) = queue.pop_back().unwrap();
+ // find largest prev_w and w such that prev_w + prev_v3 == w - v2
+ // v2 is always negative
+ // diff = w - prev_w
+ let diff = prev_v3 + v2;
+ if diff > 0 {
+ digits[i] = 9;
+ digits[prev_i] = 9 - diff;
+ } else {
+ digits[i] = 9 + diff;
+ digits[prev_i] = 9;
+ }
+ }
+ _ => unreachable!(),
+ }
+ }
+ let model_number = digits.iter().fold(0, |acc, x| acc * 10 + x);
+ assert!(alt_run(alt_program, &mut digits.clone()) == 0);
+ assert!(run(program, &mut digits.clone()) == 0);
+ model_number
+}
+
+fn part_2(program: &Vec<Op>, alt_program: &Vec<(i64, i64, i64)>) -> i64 {
+ let mut digits = [0; 14].iter().map(|&x| x).collect::<VecDeque<_>>();
+ let mut queue = VecDeque::<(usize, i64)>::new();
+ for (i, &(v1, v2, v3)) in alt_program.iter().enumerate() {
+ match v1 {
+ 1 => {
+ queue.push_back((i, v3));
+ }
+ 26 => {
+ let (prev_i, prev_v3) = queue.pop_back().unwrap();
+ // find largest prev_w and w such that prev_w + prev_v3 == w - v2
+ // v2 is always negative
+ // diff = w - prev_w
+ let diff = prev_v3 + v2;
+ if diff > 0 {
+ digits[i] = 1 + diff;
+ digits[prev_i] = 1;
+ } else {
+ digits[i] = 1;
+ digits[prev_i] = 1 - diff;
+ }
+ }
+ _ => unreachable!(),
+ }
+ }
+ let model_number = digits.iter().fold(0, |acc, x| acc * 10 + x);
+ assert!(alt_run(alt_program, &mut digits.clone()) == 0);
+ assert!(run(program, &mut digits.clone()) == 0);
+ model_number
+}