commit 015bcfd95477751ec565a63a38dfd30071660a4f
parent 7aa125464ece55d450f01b7b2655bc75cdad6d66
Author: Louis Burda <quent.burda@gmail.com>
Date: Wed, 19 Apr 2023 21:30:57 +0200
[Day 24] Try functional lazy eval approach
Diffstat:
5 files changed, 720 insertions(+), 0 deletions(-)
diff --git a/src/24/Cargo.toml b/src/24/Cargo.toml
@@ -0,0 +1,7 @@
+[package]
+name = "day24"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
+aoc = { path = "../common/aoc" }
diff --git a/src/24/input b/src/24/input
@@ -0,0 +1,253 @@
+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 4
+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 11
+mul y x
+add z y
+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 7
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -14
+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 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 11
+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 13
+mul y x
+add z y
+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 9
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 13
+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 -7
+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 6
+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 2
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -2
+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 11
+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 12
+mul y x
+add z y
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26
+add x -4
+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 -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 13
+mul y x
+add z y
+
diff --git a/src/24/part1 b/src/24/part1
@@ -0,0 +1,97 @@
+--- Day 24: Arithmetic Logic Unit ---
+
+Magic smoke starts leaking from the submarine's arithmetic logic unit (ALU). Without the ability to
+perform basic arithmetic and logic functions, the submarine can't produce cool patterns with its
+Christmas lights!
+
+It also can't navigate. Or run the oxygen system.
+
+Don't worry, though - you [1m[97mprobably[0m have enough oxygen left to give you enough time to build a new
+ALU.
+
+The ALU is a four-dimensional processing unit: it has integer variables w, x, y, and z. These
+variables all start with the value 0. The ALU also supports [1m[97msix instructions[0m:
+
+
+ - inp a - Read an input value and write it to variable a.
+
+ - add a b - Add the value of a to the value of b, then store the result in variable a.
+
+ - mul a b - Multiply the value of a by the value of b, then store the result in variable a.
+
+ - div a b - Divide the value of a by the value of b, truncate the result to an integer, then store
+the result in variable a. (Here, "truncate" means to round the value toward zero.)
+
+ - mod a b - Divide the value of a by the value of b, then store the [1m[97mremainder[0m in variable a. (This
+is also called the modulo operation.)
+
+ - eql a b - If the value of a and b are equal, then store the value 1 in variable a. Otherwise,
+store the value 0 in variable a.
+
+
+In all of these instructions, a and b are placeholders; a will always be the variable where the
+result of the operation is stored (one of w, x, y, or z), while b can be either a variable or a
+number. Numbers can be positive or negative, but will always be integers.
+
+The ALU has no [1m[97mjump[0m instructions; in an ALU program, every instruction is run exactly once in order
+from top to bottom. The program halts after the last instruction has finished executing.
+
+(Program authors should be especially cautious; attempting to execute div with b=0 or attempting to
+execute mod with a<0 or b<=0 will cause the program to crash and might even damage the ALU. These
+operations are never intended in any serious ALU program.)
+
+For example, here is an ALU program which takes an input number, negates it, and stores it in x:
+
+inp x
+mul x -1
+
+Here is an ALU program which takes two input numbers, then sets z to 1 if the second input number is
+three times larger than the first input number, or sets z to 0 otherwise:
+
+inp z
+inp x
+mul z 3
+eql z x
+
+Here is an ALU program which takes a non-negative integer as input, converts it into binary, and
+stores the lowest (1's) bit in z, the second-lowest (2's) bit in y, the third-lowest (4's) bit in x,
+and the fourth-lowest (8's) bit in w:
+
+inp w
+add z w
+mod z 2
+div w 2
+add y w
+mod y 2
+div w 2
+add x w
+mod x 2
+div w 2
+mod w 2
+
+Once you have built a replacement ALU, you can install it in the submarine, which will immediately
+resume what it was doing when the ALU failed: validating the submarine's [1m[97mmodel number[0m. To do this,
+the ALU will run the MOdel Number Automatic Detector program (MONAD, your puzzle input).
+
+Submarine model numbers are always [1m[97mfourteen-digit numbers[0m consisting only of digits 1 through 9. The
+digit 0 [1m[97mcannot[0m appear in a model number.
+
+When MONAD checks a hypothetical fourteen-digit model number, it uses fourteen separate inp
+instructions, each expecting a [1m[97msingle digit[0m of the model number in order of most to least
+significant. (So, to check the model number 13579246899999, you would give 1 to the first inp
+instruction, 3 to the second inp instruction, 5 to the third inp instruction, and so on.) This means
+that when operating MONAD, each input instruction should only ever be given an integer value of at
+least 1 and at most 9.
+
+Then, after MONAD has finished running all of its instructions, it will indicate that the model
+number was [1m[97mvalid[0m by leaving a 0 in variable z. However, if the model number was
+[1m[97minvalid[0m, it will leave some other non-zero value in z.
+
+MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of
+the MONAD documentation was eaten by a tanuki. You'll need to [1m[97mfigure out what MONAD does[0m some other
+way.
+
+To enable as many submarine features as possible, find the largest valid fourteen-digit model number
+that contains no 0 digits. [1m[97mWhat is the largest model number accepted by MONAD?[0m
+
+
diff --git a/src/24/src/main.rs b/src/24/src/main.rs
@@ -0,0 +1,359 @@
+use std::rc::Rc;
+use std::cell::RefCell;
+
+struct Reg;
+
+macro_rules! new {
+ ( $x:expr ) => {
+ Rc::new(RefCell::new($x))
+ };
+}
+
+macro_rules! clone {
+ ( $x:expr ) => {
+ Rc::clone($x)
+ };
+}
+
+#[derive(Copy,Clone)]
+enum Command {
+ Input,
+ Addition,
+ Multiply,
+ Divide,
+ Modulo,
+ Equal
+}
+
+#[derive(Clone)]
+enum Operand {
+ Register(usize),
+ Immediate(isize)
+}
+
+#[derive(Clone)]
+struct Instruction {
+ cmd: Command,
+ dst: usize,
+ op: Operand
+}
+
+#[derive(Clone)]
+struct Operation {
+ cmd: Command,
+ a: Rc<RefCell<Monad>>,
+ b: Option<Rc<RefCell<Monad>>>
+}
+
+#[derive(Clone)]
+enum Monad {
+ Operation(Operation),
+ Immediate(isize),
+ Digit(usize)
+}
+
+struct ALU {
+ regs: [Rc<RefCell<Monad>>; 4],
+}
+
+impl Reg {
+ pub const X: usize = 0;
+ pub const Y: usize = 1;
+ pub const Z: usize = 2;
+ pub const W: usize = 3;
+
+ pub fn parse(part: &str) -> usize {
+ match part {
+ "x" => Reg::X,
+ "y" => Reg::Y,
+ "z" => Reg::Z,
+ "w" => Reg::W,
+ _ => unreachable!()
+ }
+ }
+}
+
+impl Operand {
+ pub fn parse(part: &str) -> Operand {
+ let res = part.parse();
+ if res.is_ok() {
+ return Operand::Immediate(res.unwrap());
+ } else {
+ return Operand::Register(Reg::parse(part));
+ }
+ }
+}
+
+impl ALU {
+ fn op(&self, op: Operand) -> Rc<RefCell<Monad>> {
+ match op {
+ Operand::Register(r) => clone!(&self.regs[r]),
+ Operand::Immediate(imm) => new!(Monad::Immediate(imm))
+ }
+ }
+
+ fn eval(&mut self, instructions: &Vec<Instruction>) {
+ let mut digit = 0;
+ for instruction in instructions {
+ match instruction.cmd {
+ Command::Input => {
+ self.regs[instruction.dst] = new!(Monad::Digit(digit));
+ digit += 1;
+ },
+ _ => {
+ let monad = new!(
+ Monad::Operation(Operation {
+ cmd: instruction.cmd.clone(),
+ a: clone!(&self.regs[instruction.dst]),
+ b: Some(self.op(instruction.op.clone()))
+ })
+ );
+ match instruction.cmd {
+ Command::Modulo => {
+ monad.borrow_mut().transform_mod();
+ },
+ Command::Equal => {
+ monad.borrow_mut().transform_eql();
+ },
+ _ => {}
+ }
+ self.regs[instruction.dst] = Monad::simplify(&monad);
+ },
+ }
+ }
+ }
+}
+
+impl Monad {
+ fn is_zero(&self) -> bool {
+ match self {
+ Monad::Immediate(0) => true,
+ _ => false
+ }
+ }
+
+ pub fn simplify(monad: &Rc<RefCell<Self>>) -> Rc<RefCell<Self>> {
+ let borrow: &Self = &monad.borrow();
+ match borrow {
+ Monad::Operation(op) => {
+ match op.cmd {
+ Command::Divide => {
+ if op.a.borrow().is_zero() {
+ return new!(Monad::Immediate(0));
+ }
+ },
+ Command::Multiply => {
+ if op.a.borrow().is_zero() {
+ return new!(Monad::Immediate(0));
+ } else if op.b.as_ref().unwrap().borrow().is_zero() {
+ return new!(Monad::Immediate(0));
+ }
+ },
+ Command::Addition => {
+ if op.a.borrow().is_zero() {
+ return clone!(&op.b.as_ref().unwrap());
+ } else if op.b.as_ref().unwrap().borrow().is_zero() {
+ return clone!(&op.a);
+ }
+ },
+ _ => {}
+ }
+ },
+ _ => { }
+ }
+ return clone!(monad);
+ }
+
+ fn print(&self) {
+ if aoc::get_debug() == 0 { return; }
+ match self {
+ Monad::Operation(op) => {
+ aoc::debug!("(");
+ aoc::debug!("{}", match op.cmd {
+ Command::Addition => "+",
+ Command::Multiply => "*",
+ Command::Divide => "/",
+ Command::Modulo => "%",
+ Command::Input => "I",
+ Command::Equal => "=",
+ });
+ aoc::debug!(" ");
+ op.a.borrow().print();
+ if op.b.is_some() {
+ aoc::debug!(" ");
+ op.b.as_ref().unwrap().borrow().print();
+ }
+ aoc::debug!(")");
+ },
+ Monad::Immediate(imm) => {
+ aoc::debug!("{}", imm);
+ },
+ Monad::Digit(idx) => {
+ aoc::debug!("!{}", idx);
+ }
+ }
+ }
+
+ fn depth(&self) -> usize {
+ match self {
+ Monad::Operation(op) => {
+ if op.b.is_some() {
+ 1 + usize::max(op.a.borrow().depth(),
+ op.b.as_ref().unwrap().borrow().depth())
+ } else {
+ 1 + op.a.borrow().depth()
+ }
+ },
+ _ => 1,
+ }
+ }
+
+ fn transform_mod(&mut self) {
+ match self {
+ Monad::Operation(op) => {
+ match op.cmd {
+ Command::Modulo => {
+ /* a % b => a + (a / b) * b * -1 */
+ aoc::debugln!("MOD");
+ let op1 = Monad::Operation(Operation {
+ cmd: Command::Divide,
+ a: clone!(&op.a),
+ b: Some(clone!(op.b.as_ref().unwrap()))
+ });
+ let op2 = Monad::Operation(Operation {
+ cmd: Command::Multiply,
+ a: Monad::simplify(&new!(op1)),
+ b: Some(clone!(op.b.as_ref().unwrap()))
+ });
+ let op3 = Monad::Operation(Operation {
+ cmd: Command::Multiply,
+ a: Monad::simplify(&new!(op2)),
+ b: Some(new!(Monad::Immediate(-1)))
+ });
+ op.cmd = Command::Addition;
+ op.b = Some(Monad::simplify(&new!(op3)));
+ },
+ _ => unreachable!()
+ }
+ },
+ _ => unreachable!()
+ }
+ }
+
+ fn transform_eql(&mut self) {
+ match self {
+ Monad::Operation(op) => {
+ match op.cmd {
+ Command::Equal => {
+ /* a == b => (a + (a % b) * -1) / b */
+ aoc::debugln!("EQL");
+ let mut op1 = Monad::Operation(Operation {
+ cmd: Command::Modulo,
+ a: clone!(&op.a),
+ b: Some(clone!(op.b.as_ref().unwrap()))
+ });
+ op1.transform_mod();
+ let op2 = Monad::Operation(Operation {
+ cmd: Command::Multiply,
+ a: new!(op1),
+ b: Some(new!(Monad::Immediate(-1)))
+ });
+ let op3 = Monad::Operation(Operation {
+ cmd: Command::Addition,
+ a: Monad::simplify(&new!(op2)),
+ b: Some(clone!(&op.a))
+ });
+ op.cmd = Command::Divide;
+ op.a = Monad::simplify(&new!(op3));
+ },
+ _ => unreachable!()
+ }
+ },
+ _ => unreachable!()
+ }
+ }
+
+ //fn solve_for_zero(&self) -> Vec<Option<usize>> {
+ // let digits = Vec::new();
+
+ // return digits;
+ //}
+}
+
+fn parse_input(input: &str) -> Vec<Instruction> {
+ let mut instructions = Vec::new();
+
+ for line in input.lines() {
+ if line.is_empty() { continue; }
+
+ let mut parts = line.split(" ");
+ let inst = match parts.next().unwrap() {
+ "inp" => Instruction {
+ cmd: Command::Input,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::Immediate(0)
+ },
+ "add" => Instruction {
+ cmd: Command::Addition,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::parse(parts.next().unwrap())
+ },
+ "mul" => Instruction {
+ cmd: Command::Multiply,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::parse(parts.next().unwrap())
+ },
+ "div" => Instruction {
+ cmd: Command::Divide,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::parse(parts.next().unwrap())
+ },
+ "mod" => Instruction {
+ cmd: Command::Modulo,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::parse(parts.next().unwrap())
+ },
+ "eql" => Instruction {
+ cmd: Command::Equal,
+ dst: Reg::parse(parts.next().unwrap()),
+ op: Operand::parse(parts.next().unwrap())
+ },
+ _ => unreachable!()
+ };
+
+ instructions.push(inst);
+ }
+
+ return instructions;
+}
+
+fn part1(aoc: &mut aoc::Info) {
+ let instructions = parse_input(&aoc.input);
+
+ let mut alu = ALU {
+ regs: [
+ new!(Monad::Immediate(0)),
+ new!(Monad::Immediate(0)),
+ new!(Monad::Immediate(0)),
+ new!(Monad::Immediate(0))
+ ]
+ };
+
+ aoc::debugln!("PARSE");
+ alu.eval(&instructions);
+ aoc::debugln!("EVALED");
+
+ alu.regs[Reg::Z].borrow().print();
+ aoc::debugln!("");
+
+ aoc::debugln!("DEPTH {}", alu.regs[Reg::Z].borrow().depth());
+}
+
+fn part2(_aoc: &mut aoc::Info) {
+
+}
+
+fn main() {
+ aoc::run(part1, part2);
+}
+
diff --git a/src/24/test1 b/src/24/test1
@@ -0,0 +1,4 @@
+add x 1
+add x 2
+eql x y
+add z x
