diff options
| -rw-r--r-- | 2018/21_notes.txt | 100 | ||||
| -rw-r--r-- | 2018/input/21.txt | 32 | ||||
| -rw-r--r-- | 2018/src/day21.rs | 68 | ||||
| -rw-r--r-- | 2018/src/device.rs | 2 | ||||
| -rw-r--r-- | 2018/src/main.rs | 4 |
5 files changed, 204 insertions, 2 deletions
diff --git a/2018/21_notes.txt b/2018/21_notes.txt new file mode 100644 index 0000000..905f861 --- /dev/null +++ b/2018/21_notes.txt @@ -0,0 +1,100 @@ +L0: // r4 <- 123 + // r4 <- 72 + // r4 <- 1 + jmp L1 + // jmp L0 +L1: r4 <- 0 +L2: r3 <- r4 | 65536 + r4 <- 3730679 +L3: // r5 <- r3 & 255 + // r4 <- r4 + (r3 & 255) + // r4 <- (r4 + (r3 & 255)) & 16777215 + // r4 <- ((r4 + (r3 & 255)) & 16777215) * 65899 + r4 <- (((r4 + (r3 & 255)) & 16777215) * 65899) & 16777215 + // r5 <- 256 > r3 + if (r3 >= 256) + then jmp L4 + else jmp L8 +L4: r5 <- 0 +L5: r2 <- r5 + 1 + r2 <- r2 * 256 + // r2 <- r2 > r3 + if (r2 <= r3) + then jmp L6 + else jmp L7 +L6: r5 <- r5 + 1 + jmp L5 +L7: r3 <- r5 + jmp L3 +L8: // r5 <- r4 == r0 + if (r4 != r0) + then jmp L2 + [else exit] + + + ↓‾‾‾‾‾‾‾‾‾‾‾| +0 → 1 → 2 → 3 → 4 → 5 → 7 + ↑ ↓ ↕ + └── 8 6 + ↓ + * + +L5: +loop { + r2 = (r5 + 1) * 256; + if r2 > r3 { jmp L7; } + r5 += 1; +} + +L5: +Let x = ceil((r3 + 1) / 256). +Set r5 = x - 1; r2 = x * 256. +Jump to L7. +This takes (x+1)*5+2*x = 7*x+5 instructions. + + +// -------------------------- + + +L0: jmp L1 [4 instrs] +L1: r4 <- 0 +L2: r3 <- r4 | 65536 + r4 <- 3730679 +L3: r4 <- (((r4 + (r3 & 0xff)) & 0xffffff) * 65899) & 0xffffff [6 instrs] + if (r3 >= 256) + then jmp L4 + else jmp L8 +L4: Set r3 = ceil((r3 + 1) / 256) - 1. [7*ceil((r3+1)/256)+6 instrs] + jmp L3 +L8: // r5 <- r4 == r0 + if (r4 != r0) + then jmp L2 + [else exit] + + + ↓‾‾‾| +0 → 1 → 2 → 3 → 4 + ↑ ↓ + └── 8 + ↓ + * + + +// -------------------------- + + +Earliest exit is if r0 is equal to the value in r4 on the first arrival at L8. + + +L3: +loop { + r4 = (((r4 + (r3 & 0xff)) & 0xffffff) * 65899) & 0xffffff [6 instrs] + if r3 < 256 { jmp L8 } + r3 = ceil((r3 + 1) / 256) - 1 [7*ceil((r3+1)/256)+6 instrs] +} + +exit at 8 +-> r4 == r0 at end of 3, jmp to 8 +-> r4 == r0 and r3 < 256 at end of 3 +-> r3 < 256 and r0 == (((r4 + (r3 & 255)) & 16777215) * 65899) & 16777215 at start of 3 +-> r3 < 256 and r0 == (r4 + r3) * 65899 (mod 2^24) at start of 3 diff --git a/2018/input/21.txt b/2018/input/21.txt new file mode 100644 index 0000000..2dcaca7 --- /dev/null +++ b/2018/input/21.txt @@ -0,0 +1,32 @@ +#ip 1 +seti 123 0 4 +bani 4 456 4 +eqri 4 72 4 +addr 4 1 1 +seti 0 0 1 +seti 0 1 4 +bori 4 65536 3 +seti 3730679 4 4 +bani 3 255 5 +addr 4 5 4 +bani 4 16777215 4 +muli 4 65899 4 +bani 4 16777215 4 +gtir 256 3 5 +addr 5 1 1 +addi 1 1 1 +seti 27 1 1 +seti 0 0 5 +addi 5 1 2 +muli 2 256 2 +gtrr 2 3 2 +addr 2 1 1 +addi 1 1 1 +seti 25 1 1 +addi 5 1 5 +seti 17 1 1 +setr 5 2 3 +seti 7 6 1 +eqrr 4 0 5 +addr 5 1 1 +seti 5 1 1 diff --git a/2018/src/day21.rs b/2018/src/day21.rs new file mode 100644 index 0000000..e0983a3 --- /dev/null +++ b/2018/src/day21.rs @@ -0,0 +1,68 @@ +use std::io; +use std::io::BufRead; +use std::collections::HashSet; +use crate::device::*; + +#[allow(dead_code)] +fn optimise(mut instrs: Vec<Instr>, ip_reg: usize) -> Vec<Instr> { + for i in 0..instrs.len() { + instrs[i].inline_reg(ip_reg, Oper::Num(i)); + } + + instrs +} + +#[allow(dead_code)] +fn run_program(instrs: &[Instr], r0: usize, ip_reg: usize) -> usize { + let mut m = Machine { regs: [r0, 0, 0, 0, 0, 0] }; + m.exec_program(&instrs, ip_reg); + m.regs[0] +} + +pub fn main<T: BufRead>(reader: T) -> io::Result<(String, String)> { + let (ip_reg, instrs) = parse_program(reader)?; + + let instrs = optimise(instrs, ip_reg); + + // for instr in &instrs { println!("{}", instr); } + + let part1; + + let mut ip = 0; + let mut m = Machine { regs: [0, 0, 0, 0, 0, 0] }; + loop { + assert!(ip < instrs.len()); + if ip == 28 { + part1 = m.regs[4]; + break; + } + m.regs[ip_reg] = ip; + m.exec(&instrs[ip]); + ip = m.regs[ip_reg] + 1; + } + + let mut part2 = None; + + let mut seen_machines = HashSet::new(); + let mut seen_values = HashSet::new(); + + loop { + assert!(ip < instrs.len()); + if ip == 28 { + // println!("{:?}", m); + if seen_machines.contains(&m) { + break; + } + seen_machines.insert(m.clone()); + if !seen_values.contains(&m.regs[4]) { + part2 = Some(m.regs[4]); + seen_values.insert(m.regs[4]); + } + } + m.regs[ip_reg] = ip; + m.exec(&instrs[ip]); + ip = m.regs[ip_reg] + 1; + } + + Ok((part1.to_string(), part2.unwrap().to_string())) +} diff --git a/2018/src/device.rs b/2018/src/device.rs index 7eaf8d3..cf6d94e 100644 --- a/2018/src/device.rs +++ b/2018/src/device.rs @@ -181,7 +181,7 @@ impl fmt::Display for Instr { } } -#[derive(PartialEq, Eq, Clone)] +#[derive(PartialEq, Eq, Clone, Hash, Debug)] pub struct Machine { pub regs: [usize; 6], } diff --git a/2018/src/main.rs b/2018/src/main.rs index 34c3964..fa1cab8 100644 --- a/2018/src/main.rs +++ b/2018/src/main.rs @@ -26,8 +26,9 @@ mod day17; mod day18; mod day19; mod day20; +mod day21; -static NUM_DAYS: i32 = 20; +static NUM_DAYS: i32 = 21; fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { match day { @@ -51,6 +52,7 @@ fn day_switch<T: BufRead>(day: i32, reader: T) -> io::Result<(String, String)> { 18 => day18::main(reader), 19 => day19::main(reader), 20 => day20::main(reader), + 21 => day21::main(reader), _ => Err(Error::new(ErrorKind::Other, "Invalid day")) } } |