diff options
| -rw-r--r-- | 24/Cargo.toml | 11 | ||||
| -rw-r--r-- | 24/input | 252 | ||||
| -rw-r--r-- | 24/input-commented | 278 | ||||
| -rw-r--r-- | 24/small | 136 | ||||
| -rw-r--r-- | 24/src/main.rs | 420 | ||||
| -rw-r--r-- | 24/src/main.rs.bak | 379 | ||||
| -rw-r--r-- | 24/tests/main.rs | 17 | ||||
| -rw-r--r-- | Cargo.lock | 8 | ||||
| -rw-r--r-- | Cargo.toml | 1 |
9 files changed, 1502 insertions, 0 deletions
diff --git a/24/Cargo.toml b/24/Cargo.toml new file mode 100644 index 0000000..e9e1108 --- /dev/null +++ b/24/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_24" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/24/input b/24/input new file mode 100644 index 0000000..ea46334 --- /dev/null +++ b/24/input @@ -0,0 +1,252 @@ +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 10 +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 5 +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 12 +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 12 +mul y x +add z y +inp w +mul x 0 +add x z +mod x 26 +div z 1 +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 6 +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 4 +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 15 +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 3 +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 7 +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 11 +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 2 +mul y x +add z y +inp w +mul x 0 +add x z +mod x 26 +div z 26 +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 -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 26 +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 11 +mul y x +add z y diff --git a/24/input-commented b/24/input-commented new file mode 100644 index 0000000..1ea20b8 --- /dev/null +++ b/24/input-commented @@ -0,0 +1,278 @@ +; 0 0 0 0 +inp w ; w = digit[0] +mul x 0 ; nop +add x z ; nop +mod x 26 ; nop +div z 1 ; nop **NOTE** parameter M[0] = 1 +add x 10 ; x = 10 **NOTE** parameter N[0] = 10 +eql x w ; x = (digit[0] == 10), which is 0 for valid input +eql x 0 ; x = (digit[0] != 10), which is 1 for valid input +mul y 0 ; nop +add y 25 ; y = 25 +mul y x ; y = 25 if valid digit, 0 otherwise +add y 1 ; y = 26 if valid digit, 1 otherwise +mul z y ; nop +mul y 0 ; y = 0 +add y w ; y = digit[0] +add y 10 ; y = digit[0] + 10 **NOTE** parameter O[0] = 10 +mul y x ; y = digit[0] + 10 if valid digit, 0 otherwise +add z y ; z = digit[0] + 10 if valid digit, 0 otherwise + +let m = vec![1, 1, 1, 26, 1, 26, 1, 26, 1, 1, 26, 26, 26, 26]; +let n = vec![10, 13, 15, -12, 14, -2, 13, -12, 15, 11, -3, -13, -12, -13]; +let o = vec![10, 5, 12, 12, 6, 4, 15, 3, 7, 11, 2, 12, 4, 11]; +for i in 0 .. 14 { + w = input.pop(); + x = if ((z % 26) / m[i] + n[i]) != w { 1 } else { 0 }; + z = z * (25 * x + 1) + (w + o[i]) * x; +} + +; _ _ a a where a = digit[0] + 10 if valid digit, 0 otherwise +inp w ; w = digit[1] +mul x 0 ; x = 0 +add x z ; x = a +mod x 26 ; x = a % 26 +div z 1 ; nop **NOTE** parameter M[0] = 1 +add x 13 ; x = a % 26 + 13 **NOTE** parameter N[1] = 13 +eql x w ; x = (a % 26 + 13) == digit[1] +eql x 0 ; x = (a % 26 + 13) != digit[1], 1 for valid-so-far +mul y 0 ; y = 0 +add y 25 ; y = 25 +mul y x ; y = 25 if valid-so-far, 0 otherwise +add y 1 ; y = 26 if valid-so-far, 1 otherwise +mul z y ; z = a * 26 if valid-so-far, a otherwise +mul y 0 ; y = 0 +add y w ; y = digit[1] +add y 5 ; y = digit[1] + 5 **NOTE** parameter O[1] = 5 +mul y x ; y = digit[1] + 5 if valid digit, 0 otherwise +add z y ; z += y, thus fail if y is nonzero +; fail if z is nonzero + +inp w +mul x 0 +add x z +mod x 26 +div z 1 ; note +add x 15 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -12 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 1 ; note +add x 14 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -2 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 1 ; note +add x 13 ; note +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 15 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -12 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 1 ; note +add x 15 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 1 ; note +add x 11 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -3 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -13 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -12 ; note +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 ; note +mul y x +add z y + +inp w +mul x 0 +add x z +mod x 26 +div z 26 ; note +add x -13 ; note +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 ; note +mul y x +add z y + diff --git a/24/small b/24/small new file mode 100644 index 0000000..4e496e9 --- /dev/null +++ b/24/small @@ -0,0 +1,136 @@ +--- scanner 0 --- +404,-588,-901 +528,-643,409 +-838,591,734 +390,-675,-793 +-537,-823,-458 +-485,-357,347 +-345,-311,381 +-661,-816,-575 +-876,649,763 +-618,-824,-621 +553,345,-567 +474,580,667 +-447,-329,318 +-584,868,-557 +544,-627,-890 +564,392,-477 +455,729,728 +-892,524,684 +-689,845,-530 +423,-701,434 +7,-33,-71 +630,319,-379 +443,580,662 +-789,900,-551 +459,-707,401 + +--- scanner 1 --- +686,422,578 +605,423,415 +515,917,-361 +-336,658,858 +95,138,22 +-476,619,847 +-340,-569,-846 +567,-361,727 +-460,603,-452 +669,-402,600 +729,430,532 +-500,-761,534 +-322,571,750 +-466,-666,-811 +-429,-592,574 +-355,545,-477 +703,-491,-529 +-328,-685,520 +413,935,-424 +-391,539,-444 +586,-435,557 +-364,-763,-893 +807,-499,-711 +755,-354,-619 +553,889,-390 + +--- scanner 2 --- +649,640,665 +682,-795,504 +-784,533,-524 +-644,584,-595 +-588,-843,648 +-30,6,44 +-674,560,763 +500,723,-460 +609,671,-379 +-555,-800,653 +-675,-892,-343 +697,-426,-610 +578,704,681 +493,664,-388 +-671,-858,530 +-667,343,800 +571,-461,-707 +-138,-166,112 +-889,563,-600 +646,-828,498 +640,759,510 +-630,509,768 +-681,-892,-333 +673,-379,-804 +-742,-814,-386 +577,-820,562 + +--- scanner 3 --- +-589,542,597 +605,-692,669 +-500,565,-823 +-660,373,557 +-458,-679,-417 +-488,449,543 +-626,468,-788 +338,-750,-386 +528,-832,-391 +562,-778,733 +-938,-730,414 +543,643,-506 +-524,371,-870 +407,773,750 +-104,29,83 +378,-903,-323 +-778,-728,485 +426,699,580 +-438,-605,-362 +-469,-447,-387 +509,732,623 +647,635,-688 +-868,-804,481 +614,-800,639 +595,780,-596 + +--- scanner 4 --- +727,592,562 +-293,-554,779 +441,611,-461 +-714,465,-776 +-743,427,-804 +-660,-479,-426 +832,-632,460 +927,-485,-438 +408,393,-506 +466,436,-512 +110,16,151 +-258,-428,682 +-393,719,612 +-211,-452,876 +808,-476,-593 +-575,615,604 +-485,667,467 +-680,325,-822 +-627,-443,-432 +872,-547,-609 +833,512,582 +807,604,487 +839,-516,451 +891,-625,532 +-652,-548,-490 +30,-46,-14 diff --git a/24/src/main.rs b/24/src/main.rs new file mode 100644 index 0000000..1500019 --- /dev/null +++ b/24/src/main.rs @@ -0,0 +1,420 @@ +use advent_lib::prelude::*; + +use std::collections::HashMap; +use std::io::Write; + +#[derive(Debug,Clone,Eq,PartialEq)] +enum Instruction { + Inp(Variable), + Add(Variable, Expression), + Mul(Variable, Expression), + Div(Variable, Expression), + Mod(Variable, Expression), + Eql(Variable, Expression), +} + +#[derive(Debug,Clone,Eq,PartialEq)] +enum Expression { + Variable(Variable), + Literal(i64), +} + +#[derive(Debug,Clone,Copy,Eq,PartialEq)] +enum Variable { + W, + X, + Y, + Z, +} + +#[derive(Debug,Clone,Eq,PartialEq)] +struct State { + w: i64, + x: i64, + y: i64, + z: i64, + program_counter: usize, + input: Vec<i64>, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut program = Vec::new(); + for line in &input { + let words: Vec<&str> = line.split_whitespace().collect(); + match words[0] { + "inp" => { + let a = parse_variable(words[1]); + program.push(Instruction::Inp(a)); + }, + "add" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Add(a, b)); + }, + "mul" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Mul(a, b)); + }, + "div" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Div(a, b)); + }, + "mod" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Mod(a, b)); + }, + "eql" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Eql(a, b)); + }, + _ => panic!("not an instruction"), + } + } + + let initial_state = State { + w: 0, + x: 0, + y: 0, + z: 0, + input: Vec::new(), + program_counter: 0, + }; + + /* + run_nondeterminsitically(&initial_state, &program, false); + run_nondeterminsitically(&initial_state, &program, true); + */ + let mut state = initial_state.clone(); + //for n in vec![9, 9, 9, 9, 5, 9, 6, 9, 9, 1, 9, 3, 2, 6].iter().rev() { + //for n in vec![4, 8, 1, 1, 1, 5, 1, 4, 7, 1, 9, 1, 1, 1].iter().rev() { + for n in vec![7, 4, 8, 3, 2, 1, 9, 8, 6, 4, 5, 7, 3, 3].iter().rev() { + state.input.push(*n); + } + for stop in [18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, 234, + 252].iter() + { + run_until(&mut state, &program, *stop); + debug_state(&state); + } + + Ok(()) +} + + +fn parse_expression(word: &str) -> Expression { + match word { + "w" => Expression::Variable(Variable::W), + "x" => Expression::Variable(Variable::X), + "y" => Expression::Variable(Variable::Y), + "z" => Expression::Variable(Variable::Z), + _ => Expression::Literal(word.parse::<i64>().unwrap()), + } +} + + +fn parse_variable(word: &str) -> Variable { + match word { + "w" => Variable::W, + "x" => Variable::X, + "y" => Variable::Y, + "z" => Variable::Z, + _ => panic!("not a variable name"), + } +} + + +#[allow(dead_code)] +fn run(state: &mut State, program: &Vec<Instruction>) { + loop { + if is_done(state, program) { + break; + } + iterate(state, program); + } +} + + +#[allow(dead_code)] +fn run_until(state: &mut State, program: &Vec<Instruction>, end: usize) { + loop { + if state.program_counter == end { + break; + } + iterate(state, program); + } +} + + +fn iterate(state: &mut State, program: &Vec<Instruction>) { + match &program[state.program_counter] { + Instruction::Inp(a) => { + //debug_state(state); + + let result = state.input.pop().unwrap(); + set_variable(state, &a, result); + }, + Instruction::Add(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value + b_value; + set_variable(state, &a, result); + }, + Instruction::Mul(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value * b_value; + set_variable(state, &a, result); + }, + Instruction::Div(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value / b_value; + set_variable(state, &a, result); + }, + Instruction::Mod(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value % b_value; + set_variable(state, &a, result); + }, + Instruction::Eql(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = if a_value == b_value { 1 } else { 0 }; + set_variable(state, &a, result); + }, + } + + state.program_counter += 1; +} + + +fn evaluate_expression(state: &State, expression: &Expression) -> i64 { + match expression { + Expression::Variable(Variable::W) => state.w, + Expression::Variable(Variable::X) => state.x, + Expression::Variable(Variable::Y) => state.y, + Expression::Variable(Variable::Z) => state.z, + Expression::Literal(n) => *n, + } +} + + +fn evaluate_variable(state: &State, variable: &Variable) -> i64 { + match variable { + Variable::W => state.w, + Variable::X => state.x, + Variable::Y => state.y, + Variable::Z => state.z, + } +} + + +fn set_variable(state: &mut State, variable: &Variable, value: i64) { + match variable { + Variable::W => { state.w = value; }, + Variable::X => { state.x = value; }, + Variable::Y => { state.y = value; }, + Variable::Z => { state.z = value; }, + } +} + + +fn is_done(state: &State, program: &Vec<Instruction>) -> bool { + if state.program_counter >= program.len() { + return true; + } + + false +} + + +#[allow(dead_code)] +fn debug_input(input: &Vec<i64>) { + for digit in input.iter().rev() { + print!("{}", digit); + } + println!(""); +} + + +#[allow(dead_code)] +fn debug_state(state: &State) { + println!("line {}: {} {} {} {}", state.program_counter, state.w, + state.x, state.y, state.z); +} + + +#[allow(dead_code)] +fn run_fake(state: &mut State) { + // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 + let m = vec![1, 1, 1, 26, 1, 26, 1, 26, 1, 1, 26, 26, 26, 26]; + let n = vec![10, 13, 15, -12, 14, -2, 13, -12, 15, 11, -3, -13, -12, -13]; + let o = vec![10, 5, 12, 12, 6, 4, 15, 3, 7, 11, 2, 12, 4, 11]; + for i in 0 .. 14 { + state.w = state.input.pop().unwrap(); + state.x = state.z % 26; + state.z /= m[i]; + state.x = if state.x + n[i] != state.w { 1 } else { 0 }; + state.z = state.z * (25 * state.x + 1) + (state.w + o[i]) * state.x; + } + + + /* The largest input allowed by this matrix is: 99995969919326 + * The smallest is: 48111514719111 + * + * Below is a trace of the state at the start of each iteration, when + * invoked with the largest allowed input. Note that z (the final column) + * is the only state actually passed between iterations, but for the purpose + * of reverse-engineering, the below trace shows all four registers. + * + * line 18: 9 1 19 19 + * line 36: 9 1 14 508 + * line 54: 9 1 21 13229 + * line 72: 9 0 0 508 + * line 90: 5 1 11 13219 + * line 108: 9 0 0 508 + * line 126: 6 1 21 13229 + * line 144: 9 0 0 508 + * line 162: 9 1 16 13224 + * line 180: 1 1 12 343836 + * line 198: 9 0 0 13224 + * line 216: 3 0 0 508 + * line 234: 2 0 0 19 + * line 252: 6 0 0 0 + * + * Below is a similar trace invoked with the smallest allowed input. + * + * line 18: 4 1 14 14 + * line 36: 8 1 13 377 + * line 54: 1 1 13 9815 + * line 72: 1 0 0 377 + * line 90: 1 1 7 9809 + * line 108: 5 0 0 377 + * line 126: 1 1 16 9818 + * line 144: 4 0 0 377 + * line 162: 7 1 14 9816 + * line 180: 1 1 12 255228 + * line 198: 9 0 0 9816 + * line 216: 1 0 0 377 + * line 234: 1 0 0 14 + * line 252: 1 0 0 0 + * + * Here is a trace of a disallowed input. + * + * line 18: 7 1 17 17 + * line 36: 4 1 9 451 + * line 54: 8 1 20 11746 + * line 72: 3 1 15 11741 + * line 90: 2 1 8 305274 + * line 108: 1 1 5 305271 + * line 126: 9 1 24 7937070 + * line 144: 8 1 11 7937057 + * line 162: 6 1 13 206363495 + * line 180: 4 1 15 5365450885 + * line 198: 5 1 7 5365450877 + * line 216: 7 1 19 5365450889 + * line 234: 3 1 7 5365450877 + * line 252: 3 1 14 5365450884 + * + */ +} + + +#[allow(dead_code)] +fn cmp_histories(a: &Vec<i64>, b: &Vec<i64>) -> std::cmp::Ordering { + for i in 0 .. a.len() { + if a[i] > b[i] { + return std::cmp::Ordering::Greater; + } else if b[i] > a[i] { + return std::cmp::Ordering::Less; + } + } + + std::cmp::Ordering::Equal +} + + +#[allow(dead_code)] +fn run_nondeterminsitically(initial_state: &State, program: &Vec<Instruction>, + seek_min: bool) +{ + let mut all_states: HashMap<i64, Vec<i64>> = HashMap::new(); + all_states.insert(0, Vec::new()); + let mut last_program_counter = 0; + for stop in [18, 36, 54, 72, 90, 108, 126, 144, 162, 180, 198, 216, 234, + 252].iter() + { + println!("going until {} with {} states in", stop, all_states.len()); + let mut new_all_states: HashMap<i64, Vec<i64>> = HashMap::new(); + + let mut odometer = 0; + for (z_in, history) in all_states.iter() { + odometer += 1; + if odometer % 100000 == 0 { + print!(" {}", odometer); + let _ = std::io::stdout().flush(); + } + + for w in 1 .. 10 { + let mut state = initial_state.clone(); + state.z = *z_in; + state.input.push(w); + state.program_counter = last_program_counter; + + run_until(&mut state, &program, *stop); + + let z_out = state.z; + + let mut new_history = history.clone(); + new_history.push(w); + + match new_all_states.get(&z_out) { + None => { + new_all_states.insert(z_out, new_history); + } + Some(matching_history) => { + let mut ordering = cmp_histories(&new_history, matching_history); + if seek_min { + ordering = ordering.reverse(); + } + match ordering { + std::cmp::Ordering::Less => { + let matching_history = matching_history.clone(); + new_all_states.insert(z_out, matching_history); + } + _ => { + new_all_states.insert(z_out, new_history); + } + } + } + } + } + } + println!(""); + + all_states = new_all_states; + last_program_counter = *stop; + } + + let winning_history = all_states.get(&0).unwrap(); + for n in winning_history { + print!("{}", n); + } + println!(""); +} + diff --git a/24/src/main.rs.bak b/24/src/main.rs.bak new file mode 100644 index 0000000..37bfd78 --- /dev/null +++ b/24/src/main.rs.bak @@ -0,0 +1,379 @@ +use advent_lib::prelude::*; + +#[derive(Debug,Clone,Eq,PartialEq)] +enum Instruction { + Inp(Variable), + Add(Variable, Expression), + Mul(Variable, Expression), + Div(Variable, Expression), + Mod(Variable, Expression), + Eql(Variable, Expression), +} + +#[derive(Debug,Clone,Eq,PartialEq)] +enum Expression { + Variable(Variable), + Literal(i64), +} + +#[derive(Debug,Clone,Copy,Eq,PartialEq)] +enum Variable { + W, + X, + Y, + Z, +} + +#[derive(Debug,Clone,Eq,PartialEq)] +struct State { + w: i64, + x: i64, + y: i64, + z: i64, + program_counter: usize, + input: Vec<i64>, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut program = Vec::new(); + for line in &input { + let words: Vec<&str> = line.split_whitespace().collect(); + match words[0] { + "inp" => { + let a = parse_variable(words[1]); + program.push(Instruction::Inp(a)); + }, + "add" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Add(a, b)); + }, + "mul" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Mul(a, b)); + }, + "div" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Div(a, b)); + }, + "mod" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Mod(a, b)); + }, + "eql" => { + let a = parse_variable(words[1]); + let b = parse_expression(words[2]); + program.push(Instruction::Eql(a, b)); + }, + _ => panic!("not an instruction"), + } + } + + let initial_state = State { + w: 0, + x: 0, + y: 0, + z: 0, + input: Vec::new(), + program_counter: 0, + }; + + /* + for w in 1 .. 10 { + for z in 254176 .. 394784 { + //for z in 9776 .. 15185 { + let mut ws = vec![w]; + + let mut state = initial_state.clone(); + state.input = ws.clone(); + state.z = z; + //state.program_counter = 0; // start of iteration 0 + //state.program_counter = 18; // start of iteration 1 + //state.program_counter = 36; // start of iteration 2 + //state.program_counter = 54; // start of iteration 3 + //state.program_counter = 72; // start of iteration 4 + //state.program_counter = 90; // start of iteration 5 + //state.program_counter = 108; // start of iteration 6 + //state.program_counter = 126; // start of iteration 7 + //state.program_counter = 144; // start of iteration 8 + //state.program_counter = 162; // start of iteration 9 + state.program_counter = 180; // start of iteration 10 + + run_until(&mut state, &program, 198); // start of iteration 11 + if state.x == 0 + //if state.z >= 9776 && state.z <= 15184 + //&& state.z / 26 - 3 >= 1 && state.z / 26 - 3 <= 9 + { + println!("yay {} {}", state.z / 26, state.x); + let new_w = state.z / 26 - 3; + ws.push(new_w); + state.input.push(new_w); + } else { + continue; + } + + run_until(&mut state, &program, 216); // start of iteration 12 + if state.z >= 376 && state.z <= 584 + && (state.z - 350) / 26 >= 1 && (state.z - 350) / 26 <= 9 + { + let new_w = state.z / 26 - 12; + ws.push(new_w); + state.input.push(new_w); + } else { + continue; + } + + run_until(&mut state, &program, 234); // start of iteration 13 + if state.z >= 14 && state.z <= 22 { + let new_w = state.z - 13; + ws.push(new_w); + state.input.push(new_w); + } else { + continue; + } + + run(&mut state, &program); + if state.z == 0 { + println!("success! w = {:?}, z = {}", ws, z); + } + } + } + */ + + /* + let mut input = Vec::new(); + for _ in 0 .. 14 { + input.push(9); + } + input[13] = 9; + + let mut odometer = 0; + loop { + if input[0] == 3 { + let mut state = initial_state.clone(); + //state.input = input.clone(); + + run(&mut state, &program); + //run_fake(&mut state); + if state.z == 0 { + break; + } + + odometer += 1; + if odometer % 1 == 0 { + print!("iteration {} ", odometer); + debug_input(&input); + debug_state(&state); + } + } + + for i in 0 .. 14 { + input[i] -= 1; + if input[i] == 0 { + input[i] = 9; + if i == 13 { + println!("tried everything"); + break; + } + } else { + break; + } + } + } + debug_input(&input); + */ + + + let mut state = initial_state.clone(); + for w in 1 .. 10 { + run_until(&mut state, &program, 18); // start of iteration 1 + run_until(&mut state, &program, 36); // start of iteration 2 + run_until(&mut state, &program, 54); // start of iteration 3 + run_until(&mut state, &program, 72); // start of iteration 4 + run_until(&mut state, &program, 90); // start of iteration 5 + run_until(&mut state, &program, 108); // start of iteration 6 + run_until(&mut state, &program, 126); // start of iteration 7 + run_until(&mut state, &program, 144); // start of iteration 8 + run_until(&mut state, &program, 162); // start of iteration 9 + run_until(&mut state, &program, 180); // start of iteration 10 + run_until(&mut state, &program, 198); // start of iteration 11 + run_until(&mut state, &program, 216); // start of iteration 12 + run_until(&mut state, &program, 234); // start of iteration 13 + + + Ok(()) +} + + +fn parse_expression(word: &str) -> Expression { + match word { + "w" => Expression::Variable(Variable::W), + "x" => Expression::Variable(Variable::X), + "y" => Expression::Variable(Variable::Y), + "z" => Expression::Variable(Variable::Z), + _ => Expression::Literal(word.parse::<i64>().unwrap()), + } +} + + +fn parse_variable(word: &str) -> Variable { + match word { + "w" => Variable::W, + "x" => Variable::X, + "y" => Variable::Y, + "z" => Variable::Z, + _ => panic!("not a variable name"), + } +} + + +#[allow(dead_code)] +fn run(state: &mut State, program: &Vec<Instruction>) { + loop { + if is_done(state, program) { + break; + } + iterate(state, program); + } +} + + +#[allow(dead_code)] +fn run_until(state: &mut State, program: &Vec<Instruction>, end: usize) { + loop { + if state.program_counter == end { + break; + } + iterate(state, program); + } +} + + +fn iterate(state: &mut State, program: &Vec<Instruction>) { + match &program[state.program_counter] { + Instruction::Inp(a) => { + //debug_state(state); + + let result = state.input.pop().unwrap(); + set_variable(state, &a, result); + }, + Instruction::Add(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value + b_value; + set_variable(state, &a, result); + }, + Instruction::Mul(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value * b_value; + set_variable(state, &a, result); + }, + Instruction::Div(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value / b_value; + set_variable(state, &a, result); + }, + Instruction::Mod(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = a_value % b_value; + set_variable(state, &a, result); + }, + Instruction::Eql(a, b) => { + let a_value = evaluate_variable(state, &a); + let b_value = evaluate_expression(state, &b); + let result = if a_value == b_value { 1 } else { 0 }; + set_variable(state, &a, result); + }, + } + + state.program_counter += 1; +} + + +fn evaluate_expression(state: &State, expression: &Expression) -> i64 { + match expression { + Expression::Variable(Variable::W) => state.w, + Expression::Variable(Variable::X) => state.x, + Expression::Variable(Variable::Y) => state.y, + Expression::Variable(Variable::Z) => state.z, + Expression::Literal(n) => *n, + } +} + + +fn evaluate_variable(state: &State, variable: &Variable) -> i64 { + match variable { + Variable::W => state.w, + Variable::X => state.x, + Variable::Y => state.y, + Variable::Z => state.z, + } +} + + +fn set_variable(state: &mut State, variable: &Variable, value: i64) { + match variable { + Variable::W => { state.w = value; }, + Variable::X => { state.x = value; }, + Variable::Y => { state.y = value; }, + Variable::Z => { state.z = value; }, + } +} + + +fn is_done(state: &State, program: &Vec<Instruction>) -> bool { + if state.program_counter >= program.len() { + return true; + } + + false +} + + +#[allow(dead_code)] +fn debug_input(input: &Vec<i64>) { + for digit in input.iter().rev() { + print!("{}", digit); + } + println!(""); +} + + +#[allow(dead_code)] +fn debug_state(state: &State) { + println!("line {}: {} {} {} {}", state.program_counter, state.w, + state.x, state.y, state.z); +} + + +#[allow(dead_code)] +fn run_fake(state: &mut State) { + // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 + let m = vec![1, 1, 1, 26, 1, 26, 1, 26, 1, 1, 26, 26, 26, 26]; + let n = vec![10, 13, 15, -12, 14, -2, 13, -12, 15, 11, -3, -13, -12, -13]; + let o = vec![10, 5, 12, 12, 6, 4, 15, 3, 7, 11, 2, 12, 4, 11]; + for i in 0 .. 14 { + state.w = state.input.pop().unwrap(); + state.x = state.z % 26; + state.z /= m[i]; + state.x = if state.x + n[i] != state.w { 1 } else { 0 }; + state.z = state.z * (25 * state.x + 1) + (state.w + o[i]) * state.x; + } +} + diff --git a/24/tests/main.rs b/24/tests/main.rs new file mode 100644 index 0000000..6f37464 --- /dev/null +++ b/24/tests/main.rs @@ -0,0 +1,17 @@ +use assert_cmd::prelude::*; +//use predicates::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_23")?; + + command.arg("input"); + command.assert().success().stdout( + "13336\n\ + 53308\n"); + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index 91ed6a8..48ca432 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -187,6 +187,14 @@ dependencies = [ ] [[package]] +name = "advent_24" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + +[[package]] name = "advent_lib" version = "0.1.0" dependencies = [ diff --git a/Cargo.toml b/Cargo.toml index 34c5520..679f317 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -24,4 +24,5 @@ members = [ "21", "22", "23", + "24", ] |