aoc/year2017/
day23.rs

1//! # Coprocessor Conflagration
2//!
3//! Just like [`Day 18`] reverse engineering the code is essential. The entire input can be reduced
4//! to only the very first number.
5//!
6//! ```none
7//!     set b $NUMBER       if a == 0 {
8//!     set c b                 b = $NUMBER;
9//!     jnz a 2                 c = b;
10//!     jnz 1 5             } else {
11//!     mul b 100               b = 100000 + 100 * $NUMBER;
12//!     sub b -100000           c = b + 17000;
13//!     set c b             }
14//!     sub c -17000
15//!     set f 1             for b in (b..=c).step_by(17) {
16//!     set d 2                 f = 1;
17//!     set e 2                 for d in 2..b {
18//!     set g d                     for e in 2..b {
19//!     mul g e                         if d * e == b {
20//!     sub g b                             f = 0;
21//!     jnz g 2                         }
22//!     set f 0
23//!     sub e -1
24//!     set g e
25//!     sub g b
26//!     jnz g -8                    }
27//!     sub d -1
28//!     set g d
29//!     sub g b
30//!     jnz g -13               }
31//!     jnz f 2
32//!     sub h -1                if f == 0 {
33//!     set g b                     h += 1;
34//!     sub g c                 }
35//!     jnz g 2
36//!     jnz 1 3
37//!     sub b -17
38//!     jnz 1 -23           }
39//!  ```
40//!
41//! ## Part One
42//!
43//! The number of `mul` operations is the product of the two inner loops from 2 to `n` exclusive.
44//!
45//! ## Part Two
46//!
47//! Counts the number of composite numbers starting from `100,000 + 100 * n` checking the next
48//! 1,000 numbers in steps of 17. The raw code take `O(n²)` complexity for each number so emulating
49//! this directly would take at least 10⁵.10⁵.10³ = 10¹³ = 10,000,000,000,000 steps.
50//!
51//! [`Day 18`]: crate::year2017::day18
52use crate::util::parse::*;
53
54/// We only need the very first number from the input.
55pub fn parse(input: &str) -> u32 {
56    input.unsigned()
57}
58
59/// The number of `mul` operations is `(n - 2)²`
60pub fn part1(input: &u32) -> u32 {
61    (input - 2) * (input - 2)
62}
63
64/// Count the number of composite numbers in a range calculated from the input number.
65pub fn part2(input: &u32) -> usize {
66    (0..=1000).filter_map(|n| composite(100_000 + 100 * input + 17 * n)).count()
67}
68
69/// Simple [prime number check](https://en.wikipedia.org/wiki/Primality_test)
70/// of all factors from 2 to √n inclusive.
71fn composite(n: u32) -> Option<u32> {
72    if n.is_multiple_of(2) {
73        return Some(n);
74    }
75    for f in (3..).step_by(2).take_while(|m| m * m <= n) {
76        if n.is_multiple_of(f) {
77            return Some(n);
78        }
79    }
80
81    None
82}
aoc/year2017/day23.rs

aoc/year2017/
day23.rs
