summaryrefslogtreecommitdiff
path: root/2021/src/bin/day_24.rs
diff options
context:
space:
mode:
Diffstat (limited to '2021/src/bin/day_24.rs')
-rw-r--r--2021/src/bin/day_24.rs588
1 files changed, 588 insertions, 0 deletions
diff --git a/2021/src/bin/day_24.rs b/2021/src/bin/day_24.rs
new file mode 100644
index 0000000..2916f57
--- /dev/null
+++ b/2021/src/bin/day_24.rs
@@ -0,0 +1,588 @@
+use nom::{
+ branch::alt,
+ bytes::complete::{is_not, tag},
+ character::complete::{line_ending, space1},
+ combinator::map,
+ multi::separated_list1,
+ sequence::{pair, preceded, separated_pair},
+ IResult,
+};
+use proptest::prelude::*;
+use std::fs;
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+ let input = fs::read_to_string("inputs/day_24.txt")?;
+ let program = parse_program(&input).unwrap().1;
+ program.print_oracle();
+
+ // input[2] - 8 == input[3]
+ // input[4] + 8 == input[5]
+ // input[7] + 6 == input[8]
+ // input[9] + 5 == input[10]
+ // input[6] - 3 == input[11]
+ // input[1] - 1 == input[12]
+ // input[0] - 5 == input[13]
+
+ dbg!(refactored([9, 9, 9, 1, 1, 9, 9, 3, 9, 4, 9, 6, 8, 4]).unwrap());
+ dbg!(refactored([6, 2, 9, 1, 1, 9, 4, 1, 7, 1, 6, 1, 1, 1]).unwrap());
+ Ok(())
+}
+
+fn subroutine_1(
+ next_input: i64,
+ running_total: i64,
+ mod_conditional: i64,
+ result_additive: i64,
+) -> i64 {
+ if next_input != (running_total % 26) + mod_conditional {
+ running_total * 26 + next_input + result_additive
+ } else {
+ running_total
+ }
+}
+
+fn subroutine_2(
+ next_input: i64,
+ running_total: i64,
+ mod_conditional: i64,
+ result_additive: i64,
+) -> i64 {
+ if next_input != running_total % 26 + mod_conditional {
+ running_total / 26 * 26 + next_input + result_additive
+ } else {
+ running_total / 26
+ }
+}
+
+fn refactored_one_to_nine_assumption(input: [i64; 14]) -> Result<i64, String> {
+ let mut z = input[0] + 6;
+ // z-stack 1
+ z = z * 26 + input[1] + 6;
+ // z-stack 2
+ z = z * 26 + input[2] + 3;
+ // z-stack 3
+ z = if input[2] - 8 == input[3] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[3] + 11
+ };
+ // z-stack 2
+ z = z * 26 + input[4] + 9;
+ // z-stack 3
+ z = if input[4] + 8 == input[5] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[5] + 3
+ };
+ // z-stack 2
+ z = z * 26 + input[6] + 13;
+ // z-stack 3
+ z = z * 26 + input[7] + 6;
+ // z-stack 4
+ z = if input[7] + 6 == input[8] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[8] + 14
+ };
+ // z-stack 3
+ z = z * 26 + input[9] + 10;
+ // z-stack 4
+ z = if input[9] + 5 == input[10] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[10] + 12
+ };
+ // z-stack 3
+ z = if input[9] + 5 == input[10] {
+ if input[7] + 6 == input[8] {
+ if input[6] + 13 - 16 == input[11] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[11] + 10
+ }
+ } else {
+ if input[8] + 14 - 16 == input[11] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[11] + 10
+ }
+ }
+ } else {
+ if input[10] + 12 - 16 == input[11] {
+ z / 26
+ } else {
+ z / 26 * 26 + input[11] + 10
+ }
+ };
+ // z-stack 2
+ z = subroutine_2(input[12], z, -7, 11);
+ // z-stack 1
+ z = subroutine_2(input[13], z, -11, 15);
+ // z-stack 0
+
+ Ok(z)
+}
+
+fn refactored(input: [i64; 14]) -> Result<i64, String> {
+ let mut z: i64 = 0;
+
+ z = subroutine_1(input[0], z, 12, 6);
+ z = subroutine_1(input[1], z, 10, 6);
+ z = subroutine_1(input[2], z, 13, 3);
+ z = subroutine_2(input[3], z, -11, 11);
+ z = subroutine_1(input[4], z, 13, 9);
+ z = subroutine_2(input[5], z, -1, 3);
+ z = subroutine_1(input[6], z, 10, 13);
+ z = subroutine_1(input[7], z, 11, 6);
+ z = subroutine_2(input[8], z, 0, 14);
+ z = subroutine_1(input[9], z, 10, 10);
+ z = subroutine_2(input[10], z, -5, 12);
+ z = subroutine_2(input[11], z, -16, 10);
+ z = subroutine_2(input[12], z, -7, 11);
+ z = subroutine_2(input[13], z, -11, 15);
+
+ Ok(z)
+}
+
+#[derive(Debug)]
+struct Program(Vec<Instruction>);
+impl Program {
+ fn print_oracle(&self) {
+ println!("fn oracle(input: [i64; 14]) -> Result<i64, String> {{");
+ println!("let mut w: i64 = 0;");
+ println!("let mut x: i64 = 0;");
+ println!("let mut y: i64 = 0;");
+ println!("let mut z: i64 = 0;");
+
+ let mut input_index = 0;
+ for instruction in &self.0 {
+ match instruction {
+ Instruction::Inp(a) => {
+ println!("{} = input[{}];", a, input_index);
+ input_index += 1;
+ }
+ Instruction::Add(a, b) => {
+ println!("{0} = {0} + {1};", a, b);
+ }
+ Instruction::Mul(a, b) => {
+ println!("{0} = {0} * {1};", a, b);
+ }
+ Instruction::Div(a, b) => {
+ println!("if {0} == 0 {{ return Err(\"Div by 0\".into()); }}", b);
+ println!("{0} = {0} / {1};", a, b);
+ }
+ Instruction::Mod(a, b) => {
+ println!("if {0} == 0 {{ return Err(\"Mod by 0\".into()); }}", b);
+ println!("{0} = {0} % {1};", a, b);
+ }
+ Instruction::Eql(a, b) => {
+ println!("{0} = if {0} == {1} {{ 1 }} else {{ 0 }};", a, b);
+ }
+ }
+ }
+ println!("Ok(z)");
+ println!("}}");
+ }
+}
+
+#[derive(Debug)]
+enum Instruction {
+ Inp(String),
+ Add(String, String),
+ Mul(String, String),
+ Div(String, String),
+ Mod(String, String),
+ Eql(String, String),
+}
+
+fn parse_program(input: &str) -> IResult<&str, Program> {
+ map(separated_list1(line_ending, parse_instruction), Program)(input)
+}
+
+fn parse_instruction(input: &str) -> IResult<&str, Instruction> {
+ alt((
+ map(preceded(pair(tag("inp"), space1), word), |a| {
+ Instruction::Inp(a)
+ }),
+ map(
+ preceded(pair(tag("add"), space1), separated_pair(word, space1, word)),
+ |(a, b)| Instruction::Add(a, b),
+ ),
+ map(
+ preceded(pair(tag("mul"), space1), separated_pair(word, space1, word)),
+ |(a, b)| Instruction::Mul(a, b),
+ ),
+ map(
+ preceded(pair(tag("div"), space1), separated_pair(word, space1, word)),
+ |(a, b)| Instruction::Div(a, b),
+ ),
+ map(
+ preceded(pair(tag("mod"), space1), separated_pair(word, space1, word)),
+ |(a, b)| Instruction::Mod(a, b),
+ ),
+ map(
+ preceded(pair(tag("eql"), space1), separated_pair(word, space1, word)),
+ |(a, b)| Instruction::Eql(a, b),
+ ),
+ ))(input)
+}
+
+fn word(input: &str) -> IResult<&str, String> {
+ map(is_not(" \t\r\n"), |s: &str| s.to_string())(input)
+}
+
+#[allow(unused_assignments)]
+fn oracle(input: [i64; 14]) -> Result<i64, String> {
+ let mut w: i64 = 0;
+ let mut x: i64 = 0;
+ let mut y: i64 = 0;
+ let mut z: i64 = 0;
+ w = input[0];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 12;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 6;
+ y = y * x;
+ z = z + y;
+ w = input[1];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 10;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 6;
+ y = y * x;
+ z = z + y;
+ w = input[2];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 13;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 3;
+ y = y * x;
+ z = z + y;
+ w = input[3];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -11;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 11;
+ y = y * x;
+ z = z + y;
+ w = input[4];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 13;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 9;
+ y = y * x;
+ z = z + y;
+ w = input[5];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -1;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 3;
+ y = y * x;
+ z = z + y;
+ w = input[6];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 10;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 13;
+ y = y * x;
+ z = z + y;
+ w = input[7];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 11;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 6;
+ y = y * x;
+ z = z + y;
+ w = input[8];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + 0;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 14;
+ y = y * x;
+ z = z + y;
+ w = input[9];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 1 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 1;
+ x = x + 10;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 10;
+ y = y * x;
+ z = z + y;
+ w = input[10];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -5;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 12;
+ y = y * x;
+ z = z + y;
+ w = input[11];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -16;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 10;
+ y = y * x;
+ z = z + y;
+ w = input[12];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -7;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 11;
+ y = y * x;
+ z = z + y;
+ w = input[13];
+ x = x * 0;
+ x = x + z;
+ if 26 == 0 {
+ return Err("Mod by 0".into());
+ }
+ x = x % 26;
+ if 26 == 0 {
+ return Err("Div by 0".into());
+ }
+ z = z / 26;
+ x = x + -11;
+ x = if x == w { 1 } else { 0 };
+ x = if x == 0 { 1 } else { 0 };
+ y = y * 0;
+ y = y + 25;
+ y = y * x;
+ y = y + 1;
+ z = z * y;
+ y = y * 0;
+ y = y + w;
+ y = y + 15;
+ y = y * x;
+ z = z + y;
+ Ok(z)
+}
+
+proptest! {
+ #[test]
+ fn oracle_matches_refactored(input in proptest::array::uniform14(1i64..10)) {
+ let oracle_result = oracle(input.clone());
+ let refactored_result = refactored(input.clone());
+ let refactored_one_to_nine_assumption_result = refactored_one_to_nine_assumption(input);
+ assert_eq!(oracle_result, refactored_result);
+ assert_eq!(oracle_result, refactored_one_to_nine_assumption_result);
+ }
+}