year2018/
day19.rs

1use crate::elfcode::{HookControlFlow, Instruction, Interpreter};
2use utils::number::sum_of_divisors;
3use utils::prelude::*;
4
5/// Interpreting assembly to calculate the sum of divisors.
6///
7/// See also [day 16](crate::Day16) and [day 21](crate::Day21).
8#[derive(Clone, Debug)]
9pub struct Day19 {
10    interpreter: Interpreter,
11}
12
13impl Day19 {
14    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
15        Ok(Self {
16            interpreter: Interpreter::new(input)?,
17        })
18    }
19
20    #[must_use]
21    pub fn part1(&self) -> u32 {
22        self.run(0)
23    }
24
25    #[must_use]
26    pub fn part2(&self) -> u32 {
27        self.run(1)
28    }
29
30    fn run(&self, reg0: u32) -> u32 {
31        let mut reg = [reg0, 0, 0, 0, 0, 0];
32
33        self.interpreter.run(&mut reg, |instructions, instruction_pointer, reg| {
34            let addr = reg[instruction_pointer] as usize;
35
36            // Recognize the naive sum of divisors loop and replace it with a native implementation.
37            //  loop0: seti #1 $div
38            //  loop1: seti #1 $mul
39            //         mulr $div $mul $tmp
40            //         eqrr $tmp $tgt $tmp
41            //         addr $tmp $ip $ip
42            //         addi $ip #1 $ip
43            //         addr $div $sum $sum
44            //         addi $mul #1 $mul
45            //         gtrr $mul $tgt $tmp
46            //         addr $ip $tmp $ip
47            //         seti #loop1 $ip
48            //         addi $div #1 $div
49            //         gtrr $div $tgt $tmp
50            //         addr $tmp $ip $ip
51            //         seti #loop0 $ip
52            #[rustfmt::skip]
53            if let [
54                Instruction::Seti(1, div),
55                Instruction::Seti(1, mul),
56                Instruction::Mulr(div2, mul2, tmp),
57                Instruction::Eqrr(tmp2, tgt, tmp3),
58                Instruction::Addr(tmp4, ip, ip2),
59                Instruction::Addi(ip3, 1, ip4),
60                Instruction::Addr(div3, sum, sum2),
61                Instruction::Addi(mul3, 1, mul4),
62                Instruction::Gtrr(mul5, tgt2, tmp5),
63                Instruction::Addr(ip5, tmp6, ip6),
64                Instruction::Seti(loop1, ip7),
65                Instruction::Addi(div4, 1, div5),
66                Instruction::Gtrr(div6, tgt3, tmp7),
67                Instruction::Addr(tmp8, ip8, ip9),
68                Instruction::Seti(loop0, ip10),
69                ..,
70            ] = instructions[addr..]
71                && div == div2 && div == div3 && div == div4 && div == div5 && div == div6
72                && mul == mul2 && mul == mul3 && mul == mul4 && mul == mul5
73                && tmp == tmp2 && tmp == tmp3 && tmp == tmp4 && tmp == tmp5 && tmp == tmp6 && tmp == tmp7 && tmp == tmp8
74                && tgt == tgt2 && tgt == tgt3
75                && ip == ip2 && ip == ip3 && ip == ip4 && ip == ip5 && ip == ip6 && ip == ip7 && ip == ip8 && ip == ip9 && ip == ip10
76                && sum == sum2
77                && ip == instruction_pointer
78                && loop0 as usize == addr
79                && loop1 as usize == addr + 1
80            {
81                reg[sum] += sum_of_divisors(reg[tgt])
82                    .expect("the target's sum of divisors should fit within a u32");
83                reg[div] = reg[tgt] + 1;
84                reg[mul] = reg[tgt] + 1;
85                reg[tmp] = 1;
86                reg[ip] += 15;
87                return HookControlFlow::Next
88            };
89
90            HookControlFlow::Execute
91        });
92
93        reg[0]
94    }
95}
96
97examples!(Day19 -> (u32, u32) [
98    {
99        input: "#ip 0\n\
100            seti 5 0 1\n\
101            seti 6 0 2\n\
102            addi 0 1 0\n\
103            addr 1 2 3\n\
104            setr 1 0 0\n\
105            seti 8 0 4\n\
106            seti 9 0 5",
107        part1: 7,
108    },
109]);
year2018/day19.rs

year2018/
day19.rs
