commit 05438ad725ffc0c53dd69740d92c153d8cb3ca6b
parent 015bcfd95477751ec565a63a38dfd30071660a4f
Author: Louis Burda <quent.burda@gmail.com>
Date: Thu, 20 Apr 2023 00:54:06 +0200
Add day 24 solution
Diffstat:
| A | src/24/disasm | | | 276 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/24/src/main.rs | | | 365 | ++++++++++++++++++++++++------------------------------------------------------- |
| M | src/24/test1 | | | 77 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---- |
3 files changed, 460 insertions(+), 258 deletions(-)
diff --git a/src/24/disasm b/src/24/disasm
@@ -0,0 +1,276 @@
+; 14 subprograms, each with two parameters a, b
+; two types of subprograms, z is either divided by 26 or 1
+; when z / 26, x is < 0, else x >= 10
+
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 12 ; x = 12 + z % 26
+eql x w
+eql x 0 ; x = w != (12 + z % 26)
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y ; z *= x * 25 + 1
+mul y 0
+add y w
+add y 4
+mul y x
+add z y ; z += x * (w + 4)
+
+; z = (w + 4)
+
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 15 ; x = 15 + z % 26
+eql x w
+eql x 0 ; x = w != (15 + z % 26)
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y ; z *= (25 * x + 1)
+mul y 0
+add y w
+add y 11
+mul y x
+add z y ; z += x * (w + 11)
+
+; z = (w != 15 + z % 26) * (w + 11)
+
+inp w
+mul x 0
+add x z
+mod x 26
+div z 1
+add x 11 ; x = 11 + z % 26
+eql x w
+eql x 0 ; x = w != 11 + z % 26
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y ; z *= x * 25 + 1
+mul y 0
+add y w
+add y 7
+mul y x
+add z y ; z += z * (w + 7)
+
+; z = (w != 11 + z % 26) * (w + 7)
+
+inp w
+mul x 0
+add x z
+mod x 26
+div z 26 ; z = z / 26
+add x -14 ; x = z % 26 - 14
+eql x w ; w + 14 == z % 26 (sum!)
+eql x 0 ; w + 14 != z % 66
+mul y 0
+add y 25
+mul y x
+add y 1
+mul z y ; z *= 25 * x + 1
+mul y 0
+add y w
+add y 2
+mul y x
+add z y ; z += x * (w + 2)
+
+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/src/main.rs b/src/24/src/main.rs
@@ -1,20 +1,5 @@
-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,
@@ -25,7 +10,7 @@ enum Command {
Equal
}
-#[derive(Clone)]
+#[derive(PartialEq,Clone)]
enum Operand {
Register(usize),
Immediate(isize)
@@ -35,25 +20,7 @@ enum Operand {
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],
+ op: Option<Operand>
}
impl Reg {
@@ -74,6 +41,13 @@ impl Reg {
}
impl Operand {
+ fn imm(&self) -> isize {
+ match self {
+ Operand::Immediate(imm) => *imm,
+ _ => unreachable!()
+ }
+ }
+
pub fn parse(part: &str) -> Operand {
let res = part.parse();
if res.is_ok() {
@@ -84,202 +58,6 @@ impl Operand {
}
}
-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();
@@ -291,35 +69,36 @@ fn parse_input(input: &str) -> Vec<Instruction> {
"inp" => Instruction {
cmd: Command::Input,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::Immediate(0)
+ op: None
},
"add" => Instruction {
cmd: Command::Addition,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::parse(parts.next().unwrap())
+ op: Some(Operand::parse(parts.next().unwrap()))
},
"mul" => Instruction {
cmd: Command::Multiply,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::parse(parts.next().unwrap())
+ op: Some(Operand::parse(parts.next().unwrap()))
},
"div" => Instruction {
cmd: Command::Divide,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::parse(parts.next().unwrap())
+ op: Some(Operand::parse(parts.next().unwrap()))
},
"mod" => Instruction {
cmd: Command::Modulo,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::parse(parts.next().unwrap())
+ op: Some(Operand::parse(parts.next().unwrap()))
},
"eql" => Instruction {
cmd: Command::Equal,
dst: Reg::parse(parts.next().unwrap()),
- op: Operand::parse(parts.next().unwrap())
+ op: Some(Operand::parse(parts.next().unwrap()))
},
_ => unreachable!()
};
+ _ = inst.dst;
instructions.push(inst);
}
@@ -327,30 +106,108 @@ fn parse_input(input: &str) -> Vec<Instruction> {
return instructions;
}
+/* MONAD consists of 14 subprograms, each evaluating a single digit
+ *
+ * each subprogram compares the input digit w to z % 26 + a
+ * and sets z to 26 * z + w + b if w is equal and to z + w + b
+ * when it isnt.
+ *
+ * many subprograms have a >= 10, which prevents the existence
+ * of w to satisfy w == z % 26 + a. in these cases z is guaranteed to be
+ * multiplied by 26, creating a base-26 representation of (w + b)
+ * for subsequent rounds that have a >= 10 (b is never such that w + b >= 26)
+ *
+ * all subprograms that have a < 10 have a <= 0. in these cases
+ * w may be chosen as w' + b' + a to satisfy the condition w == z % 26 + a
+ * with w' and b' being parameters from the corresponding previous subprogram.
+ * each of these subprograms divides z by 26 initially, but still multiplies by
+ * 26 when w does not satisfy the condition w == z % 26 + a;
+ *
+ * in this way, rounds with a >= 10, signify a push() onto the stack,
+ * shifting the value and setting the next base-26 digit, while rounds
+ * with a <= 10 signify a pop() from the stack, by dividing by 26. as long
+ * as w satifies the condition w == z % 26 + a for subprograms with a < 0,
+ * there will be as many pop()s as push()s to the stack and the final
+ * value will be 0. since parameter b is never 0, every push needs to be
+ * reversed to result in z == 0.
+ * */
+
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))
- ]
- };
+ /* for part 1 we must satisfy w == w' + b' + a with maximal w and w'.
+ * when b' + a is negative, w' must be larger than w: w' = 9, w = 9 + b' + a
+ * when b' + a is positive, w must be larger than w': w = 9, w' = 9 - b' - a
+ */
+
+ let mut idx = 0usize;
+ let mut digits = [0isize; 14];
+ let mut stack: Vec<(usize,isize,isize)> = Vec::new();
+ for (i,inst) in instructions.iter().enumerate() {
+ let is_input = match inst.cmd { Command::Input => true, _ => false };
+ if is_input {
+ let div = instructions[i+4].op.as_ref().unwrap().imm();
+ let a = instructions[i+5].op.as_ref().unwrap().imm();
+ let b = instructions[i+15].op.as_ref().unwrap().imm();
+ if div == 26 {
+ let prev = stack.pop().unwrap();
+ if a + prev.2 < 0 {
+ digits[prev.0] = 9;
+ digits[idx] = digits[prev.0] + prev.2 + a;
+ } else {
+ digits[idx] = 9;
+ digits[prev.0] = digits[idx] - prev.2 - a;
+ }
+ } else {
+ stack.push((idx, a, b));
+ }
+ idx += 1;
+ }
+ }
- aoc::debugln!("PARSE");
- alu.eval(&instructions);
- aoc::debugln!("EVALED");
+ let answer = digits.iter().map(|d| format!("{}", d))
+ .collect::<Vec<String>>().join("");
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("92928914999991");
+}
- alu.regs[Reg::Z].borrow().print();
- aoc::debugln!("");
+fn part2(aoc: &mut aoc::Info) {
+ let instructions = parse_input(&aoc.input);
- aoc::debugln!("DEPTH {}", alu.regs[Reg::Z].borrow().depth());
-}
+ /* for part 2 we must satisfy w == w' + b' + a with minimal w and w'.
+ * when b' + a is negative, w' must be larger than w: w = 1, w' = 9 - b' - a
+ * when b' + a is positive, w must be larger than w': w' = 1, w = 9 + b' + a
+ */
+
+ let mut idx = 0usize;
+ let mut digits = [0isize; 14];
+ let mut stack: Vec<(usize,isize,isize)> = Vec::new();
+ for (i,inst) in instructions.iter().enumerate() {
+ let is_input = match inst.cmd { Command::Input => true, _ => false };
+ if is_input {
+ let div = instructions[i+4].op.as_ref().unwrap().imm();
+ let a = instructions[i+5].op.as_ref().unwrap().imm();
+ let b = instructions[i+15].op.as_ref().unwrap().imm();
+ if div == 26 {
+ let prev = stack.pop().unwrap();
+ if a + prev.2 < 0 {
+ digits[idx] = 1;
+ digits[prev.0] = digits[idx] - prev.2 - a;
+ } else {
+ digits[prev.0] = 1;
+ digits[idx] = digits[prev.0] + prev.2 + a;
+ }
+ } else {
+ stack.push((idx, a, b));
+ }
+ idx += 1;
+ }
+ }
-fn part2(_aoc: &mut aoc::Info) {
-
+ let answer = digits.iter().map(|d| format!("{}", d))
+ .collect::<Vec<String>>().join("");
+ aoc.answer = Some(format!("{}", answer));
+ aoc.solution = Some("91811211611981");
}
fn main() {
diff --git a/src/24/test1 b/src/24/test1
@@ -1,4 +1,73 @@
-add x 1
-add x 2
-eql x y
-add z x
+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
+
