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    let n = input - 2;
62    n * n
63}
64
65/// Count the number of composite numbers in a range calculated from the input number.
66pub fn part2(input: &u32) -> usize {
67    let start = 100_000 + 100 * input;
68    let end = start + 17001;
69    (start..end).step_by(17).filter(|&n| is_composite(n)).count()
70}
71
72/// Simple [prime number check](https://en.wikipedia.org/wiki/Primality_test)
73/// of all factors from 2 to √n inclusive.
74fn is_composite(n: u32) -> bool {
75    if n.is_multiple_of(2) {
76        return true;
77    }
78
79    let root = n.isqrt() + 1;
80    for f in (3..root).step_by(2) {
81        if n.is_multiple_of(f) {
82            return true;
83        }
84    }
85
86    false
87}
aoc/year2017/day23.rs

aoc/year2017/
day23.rs
