summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--2018/21_notes.txt100
-rw-r--r--2018/input/21.txt32
-rw-r--r--2018/src/day21.rs68
-rw-r--r--2018/src/device.rs2
-rw-r--r--2018/src/main.rs4
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"))
}
}