aoc/year2016/
day12.rs

1//! # Leonardo's Monorail
2//!
3//! This problem is interesting in that the solution is all about *reading* code not writing code.
4//!
5//! We could implement a brute force virtual machine without understanding the underlying code
6//! but it's much more efficient to analyse the code instead.
7//!
8//! The first thing we notice is that the following idiom is repeated several times:
9//!
10//! ```none
11//!     inc x
12//!     dec y
13//!     jnz y -2
14//! ```
15//!
16//! This is equivalent to `x += y` only much less efficient. Replacing this in the code then
17//! rewriting the remainder to Rust the program becomes:
18//!
19//! ```none
20//!     let mut a = 1;
21//!     let mut b = 1;
22//!     let mut c = 0; // 1 in part two
23//!     let d = if c == 0 { 26 } else { 33 };
24//!     for _ in 0..d {
25//!         c = a;
26//!         a += b;
27//!         b = c;
28//!     }
29//!     a += q * r // q and r are the constants on lines 17 and 18.
30//! ```
31//!
32//! We can see that the code is calculating the 28th and 35th numbers in the Fibonacci sequence
33//! plus some constant offset. We can replace the entire code with a single multiplication.
34//! If we had emulated the raw instructions then it would have taken ~10,000,000 iterations to
35//! obtain the answer.
36use crate::util::parse::*;
37
38/// Extract the constant offset from the assembunny code.
39pub fn parse(input: &str) -> u32 {
40    let lines: Vec<_> = input.lines().collect();
41    let first: u32 = lines[16].unsigned();
42    let second: u32 = lines[17].unsigned();
43    first * second
44}
45
46/// 28th Fibonacci number plus some constant.
47pub fn part1(input: &u32) -> u32 {
48    317811 + input
49}
50
51/// 35th Fibonacci number plus some constant.
52pub fn part2(input: &u32) -> u32 {
53    9227465 + input
54}
aoc/year2016/day12.rs

aoc/year2016/
day12.rs
