year2018/
day21.rs

1use crate::elfcode::{HookControlFlow, Instruction, Interpreter, Register};
2use std::collections::HashSet;
3use utils::prelude::*;
4
5/// Interpreting assembly to find the longest running input.
6///
7/// See also [day 16](crate::Day16) and [day 19](crate::Day19).
8#[derive(Clone, Debug)]
9pub struct Day21 {
10    interpreter: Interpreter,
11}
12
13impl Day21 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        let interpreter = Interpreter::new(input)?;
16
17        let instruction_pointer = interpreter.instruction_pointer();
18        if instruction_pointer == Register::A {
19            return Err(InputError::new(input, 0, "expected #ip to be non-zero"));
20        }
21
22        let instructions = interpreter.instructions();
23        if instructions
24            .iter()
25            .flat_map(|i| i.registers())
26            .filter(|&r| r == Register::A)
27            .count()
28            != 1
29        {
30            return Err(InputError::new(
31                input,
32                0,
33                "expected exactly one use of register 0",
34            ));
35        }
36
37        if let [
38            ..,
39            Instruction::Eqrr(_, Register::A, tmp),
40            Instruction::Addr(tmp2, ip, ip2),
41            Instruction::Seti(_, ip3),
42        ] = *instructions
43            && tmp == tmp2
44            && ip == ip2
45            && ip == ip3
46            && ip == instruction_pointer
47            && tmp != instruction_pointer
48        {
49            // Register 0 is used in exactly one place, in the 3rd last instruction, and the outer
50            // loop terminates when it matches a computed value.
51            Ok(Self { interpreter })
52        } else {
53            Err(InputError::new(
54                input,
55                input.len() - 1,
56                "expected register 0 matching to control termination of the outer loop",
57            ))
58        }
59    }
60
61    #[must_use]
62    pub fn part1(&self) -> u32 {
63        self.next(&mut [0; 6])
64    }
65
66    #[must_use]
67    pub fn part2(&self) -> u32 {
68        // Using a HashSet is faster than using Brent's algorithm as it minimizes the number of next
69        // calls, which are slow.
70        let mut reg = [0; 6];
71        let mut seen = HashSet::with_capacity(20000);
72        let mut last_first_seen = 0;
73        loop {
74            let target = self.next(&mut reg);
75            if seen.insert(target) {
76                last_first_seen = target;
77            } else {
78                break;
79            }
80        }
81        last_first_seen
82    }
83
84    fn next(&self, reg: &mut [u32; 6]) -> u32 {
85        let mut target = None;
86
87        self.interpreter
88            .run(reg, |instructions, instruction_pointer, reg| {
89                let addr = reg[instruction_pointer] as usize;
90
91                if let Instruction::Eqrr(tgt, Register::A, tmp) = instructions[addr] {
92                    target = Some(reg[tgt]);
93
94                    // Simulate r0 not equaling the target, so the program always continues when
95                    // the interpreter is next resumed.
96                    reg[tmp] = 0;
97                    reg[instruction_pointer] += 1;
98
99                    return HookControlFlow::Halt;
100                }
101
102                // Recognize the division by 256 and replace it with a native computation.
103                //  start: seti #0 $quo
104                //         addi $quo #1 $tmp
105                //         muli $tmp #256 $tmp
106                //         gtrr $tmp $num $tmp
107                //         addr $tmp $ip $ip
108                //         addi $ip #1 $ip
109                //         seti #end $ip
110                //         addi $quo #1 $quo
111                //  end:   seti #start $ip
112                #[rustfmt::skip]
113                if let [
114                    Instruction::Seti(0, quo),
115                    Instruction::Addi(quo2, 1, tmp),
116                    Instruction::Muli(tmp2, 256, tmp3),
117                    Instruction::Gtrr(tmp4, num, tmp5),
118                    Instruction::Addr(tmp6, ip, ip2),
119                    Instruction::Addi(ip3, 1, ip4),
120                    Instruction::Seti(end, ip5),
121                    Instruction::Addi(quo3, 1, quo4),
122                    Instruction::Seti(start, ip6),
123                    ..,
124                ] = instructions[addr..]
125                    && quo == quo2 && quo == quo3 && quo == quo4
126                    && tmp == tmp2 && tmp == tmp3 && tmp == tmp4 && tmp == tmp5 && tmp == tmp6
127                    && ip == ip2 && ip == ip3 && ip == ip4 && ip == ip5 && ip == ip6
128                    && start as usize == addr
129                    && end as usize == addr + 8
130                {
131                    reg[quo] = reg[num] >> 8;
132                    reg[tmp] = 1;
133                    reg[ip] += 9;
134                    return HookControlFlow::Next;
135                };
136
137                HookControlFlow::Execute
138            });
139
140        target.expect("no solution found")
141    }
142}
143
144examples!(Day21 -> (u32, u32) [
145    // Custom example
146    {
147        // Equivalent to
148        //
149        //  r2 = 0;
150        //  do {
151        //    r2++;
152        //    if (r2 == 100) r2 = 1;
153        //  } while (r2 != r0);
154        //
155        // Produces sequence 1, 2, 3, ..., 98, 99, 1, 2, 3, ..., 98, 99, 1, ...
156        input: "#ip 4\n\
157            seti 0 0 2\n\
158            addi 2 1 2\n\
159            eqri 2 100 1\n\
160            addr 1 4 4\n\
161            addi 4 1 4\n\
162            seti 1 0 2\n\
163            eqrr 2 0 1\n\
164            addr 1 4 4\n\
165            seti 0 0 4",
166        part1: 1,
167        part2: 99,
168    },
169]);
year2018/day21.rs

year2018/
day21.rs
