summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorDaniel Silverstone <dsilvers@digital-scurf.org>2021-12-24 07:52:18 +0000
committerDaniel Silverstone <dsilvers@digital-scurf.org>2021-12-24 07:52:18 +0000
commit93ed0fb8404dd82d9eea2a30362be47be2e4bed1 (patch)
treeae82142c89d81abebedff6009dad968c15dc89d1
parente376f97cde3e6030bbacb86141d5866c82ac9688 (diff)
downloadaoc-93ed0fb8404dd82d9eea2a30362be47be2e4bed1.tar.bz2
2021: Day 24, hand-analysed solution, blech
Signed-off-by: Daniel Silverstone <dsilvers@digital-scurf.org>
-rw-r--r--2021/src/bin/2021day24.rs223
1 files changed, 206 insertions, 17 deletions
diff --git a/2021/src/bin/2021day24.rs b/2021/src/bin/2021day24.rs
index d553fb8..887e180 100644
--- a/2021/src/bin/2021day24.rs
+++ b/2021/src/bin/2021day24.rs
@@ -83,7 +83,8 @@ fn run_program<I: Iterator<Item = i64>>(prog: &[Instruction], input: I) -> [i64;
regs
}
-fn part1(input: &[Instruction]) -> String {
+#[allow(unused)]
+fn naive_part1(input: &[Instruction]) -> String {
let digit = (1i64..=9).rev();
let model = std::iter::repeat(digit).take(14);
let model = model.multi_cartesian_product();
@@ -104,32 +105,220 @@ fn part1(input: &[Instruction]) -> String {
unreachable!()
}
-fn part2(input: &[Instruction]) -> usize {
- todo!()
+/*
+Analysis
+
+The program appears to be blocks of instructions, repeating, with different parameters
+inp w
+mul x 0
+add x z
+mod x 26
+div z {param 1}
+add x {param 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 {param 3}
+mul y x
+add z y
+
+
+If we simplify this, we get:
+
+w = input_digit
+x = (z % 26)
+z //= {param 1}
+x += {param 2}
+x = x == w
+x = x == 0
+z *= (x*25) + 1
+z += (w + {param 3}) * x
+
+Input parameters in my input start:
+
+(1, 11, 16)
+(1, 12, 11)
+(1, 13, 12)
+(26, -5, 12)
+(26, -3, 12)
+
+Seven times, param 1 is a 1, the other seven it's 26
+
+Simplifying the step block some more gets:
+
+w = input_digit
+x = ((z % 26) + {param 2}) != w
+z //= {param 1}
+z *= (x*25)+1
+z += (w+{param 3})*x
+
+In cases where param 1 is 1, the //= step can be ignored.
+Also in those steps, param 2 is always > 10, so it can never equal a digit
+thus the != step is always true (making x == 1)
+
+So in the case that param 1 is 1, the only parameter which matters is param 3, giving:
+
+w = input_digit
+x = 1
+z *= 26
+z += w + {param 3}
+
+This is, to all intents and purposes, "pushing" digit+param 3 onto a stack in z (mod 26)
+
+In the case where param 1 is 26, instead we get a situation where we "pop" the previous
+computed w+{param 3} we add {param 2} and we compare with the input digit
+seting x to 1 if they differ and 0 if they match
+
+w = input_digit
+if (pop_z + {param 2}) != w {
+ push_z w + {param 3}
+}
+
+To succeed, this virtual stack needs to be empty, essentially any time we're popping, we want
+to ensure we do not push again. Since our input starts with a push instruction and ends with
+a pop instruction, all we need to do is match things up cleanly, so that we can be sure we can
+resolve a value which will work.
+
+In pushes, the important value is param 3, since that is added to the digit
+In pops, the important value is param 2, since that's added to the popped value before comparing with the digit
+*/
+
+#[derive(Debug)]
+enum Simplified {
+ Push(i64),
+ Pop(i64),
+}
+
+fn simplify_prog(input: &[Instruction]) -> Vec<Simplified> {
+ assert_eq!(input.len(), 14 * 18);
+ let mut ret = Vec::new();
+ for i in 0..14 {
+ let base = i * 18;
+ assert!(matches!(input[base], Instruction::Input(Reg::W)));
+ let i1 = input[base + 4];
+ let i2 = input[base + 5];
+ let i3 = input[base + 15];
+ //println!("Instruction {}", i);
+ //println!("i1 = {:?}", i1);
+ //println!("i2 = {:?}", i2);
+ //println!("i3 = {:?}", i3);
+ let input1 = if let Instruction::Div(Reg::Z, BVal::Num(l)) = i1 {
+ l
+ } else {
+ panic!("i1 is not div z {{num}}")
+ };
+ let input2 = if let Instruction::Add(Reg::X, BVal::Num(l)) = i2 {
+ l
+ } else {
+ panic!("i2 is not add x {{num}}")
+ };
+ let input3 = if let Instruction::Add(Reg::Y, BVal::Num(l)) = i3 {
+ l
+ } else {
+ panic!("i3 is not add y {{num}}")
+ };
+ let instr = if input1 == 1 {
+ Simplified::Push(input3)
+ } else {
+ Simplified::Pop(input2)
+ };
+ ret.push(instr);
+ }
+ ret
+}
+
+/*
+
+With a simplified program we can do digit pairing, this is done by managing the stack
+and looking basically for constraints which will be of the form "digit X must equal digit Y + some value"
+there will be seven such constraints which will give us what will effectively be our goal constraints
+
+*/
+
+#[derive(Debug, Clone, Copy)]
+struct Constraint {
+ x: usize,
+ y: usize,
+ val: i8,
}
-#[cfg(test)]
-mod test {
- use super::*;
+impl fmt::Display for Constraint {
+ fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+ write!(
+ f,
+ "digits[{}] must equal digits[{}] + {}",
+ self.y, self.x, self.val
+ )
+ }
+}
- static TEST_INPUT: &str = r#""#;
+fn gen_constraints(input: &[Simplified]) -> Vec<Constraint> {
+ let mut ret = Vec::new();
+ let mut stack = Vec::new();
+ for (digit, op) in input.iter().enumerate() {
+ match op {
+ Simplified::Push(val) => {
+ stack.push((digit, (*val as i8)));
+ }
+ Simplified::Pop(val) => {
+ let (digit1, partial) = stack.pop().unwrap();
+ ret.push(Constraint {
+ x: digit1,
+ y: digit,
+ val: (*val as i8) + partial,
+ });
+ }
+ }
+ }
+ ret
+}
- #[test]
- fn testcase1() {
- let input: Vec<Instruction> = input_as_vec(TEST_INPUT).unwrap();
- assert_eq!(part1(&input), "7");
+fn part1(input: &[Constraint]) -> String {
+ let mut digits = [0i8; 14];
+ for Constraint { x, y, val } in input.iter().copied() {
+ if val < 0 {
+ digits[x] = 9;
+ digits[y] = 9 + val;
+ } else {
+ digits[y] = 9;
+ digits[x] = 9 - val;
+ }
}
- #[test]
- fn testcase2() {
- let input: Vec<Instruction> = input_as_vec(TEST_INPUT).unwrap();
- assert_eq!(part2(&input), 5);
+ digits
+ .into_iter()
+ .map(|v| ((v as u8) + b'0') as char)
+ .collect()
+}
+fn part2(input: &[Constraint]) -> String {
+ let mut digits = [0i8; 14];
+ for Constraint { x, y, val } in input.iter().copied() {
+ if val < 0 {
+ digits[x] = -val + 1;
+ digits[y] = 1;
+ } else {
+ digits[y] = val + 1;
+ digits[x] = 1;
+ }
}
+
+ digits
+ .into_iter()
+ .map(|v| ((v as u8) + b'0') as char)
+ .collect()
}
fn main() -> Result<()> {
let input: Vec<Instruction> = read_input_as_vec(24)?;
- println!("Part 1: {}", part1(&input));
- println!("Part 2: {}", part2(&input));
+ let simplified = simplify_prog(&input);
+ let constraints = gen_constraints(&simplified);
+ println!("Part 1: {}", part1(&constraints));
+ println!("Part 2: {}", part2(&constraints));
Ok(())
}