aoc/year2019/
day02.rs

1//! # 1202 Program Alarm
2//!
3//! Substituting symbols instead of numbers into the program shows that it calculates the value of
4//!
5//! `a * noun + b * verb + c`
6//!
7//! We can isolate the value of the constants a, b, c in order to speed up subsequent calculations.
8//!
9//! As the equation is monotonically increasing in both noun and verb, we can efficiently solve
10//! part two by binary searching in two dimensions, instead of a slow brute force check of all
11//! possible 10,000 combinations.
12use crate::util::parse::*;
13use std::cmp::Ordering::*;
14
15type Input = [i32; 3];
16
17pub fn parse(input: &str) -> Input {
18    let code: Vec<_> = input.iter_unsigned().collect();
19
20    let c = check(&code, 0, 0) as i32;
21    let a = check(&code, 1, 0) as i32;
22    let b = check(&code, 0, 1) as i32;
23
24    [a - c, b - c, c]
25}
26
27pub fn part1([a, b, c]: &Input) -> i32 {
28    a * 12 + b * 2 + c
29}
30
31pub fn part2(input: &Input) -> i32 {
32    search(input, 0, 99, 0, 99).unwrap()
33}
34
35fn check(input: &[usize], first: usize, second: usize) -> usize {
36    let code = &mut input.to_vec();
37    code[1] = first;
38    code[2] = second;
39
40    execute(code)
41}
42
43fn execute(code: &mut [usize]) -> usize {
44    let mut pc = 0;
45
46    loop {
47        match code[pc] {
48            1 => code[code[pc + 3]] = code[code[pc + 1]] + code[code[pc + 2]],
49            2 => code[code[pc + 3]] = code[code[pc + 1]] * code[code[pc + 2]],
50            _ => break code[0],
51        }
52        pc += 4;
53    }
54}
55
56fn search(input: &Input, x1: i32, x2: i32, y1: i32, y2: i32) -> Option<i32> {
57    if x1 > x2 || y1 > y2 {
58        return None;
59    }
60
61    let x = x1.midpoint(x2);
62    let y = y1.midpoint(y2);
63    let [a, b, c] = input;
64    let result = a * x + b * y + c;
65
66    match result.cmp(&19690720) {
67        Equal => Some(100 * x + y),
68        Less => search(input, x + 1, x2, y1, y2).or_else(|| search(input, x1, x2, y + 1, y2)),
69        Greater => search(input, x1, x - 1, y1, y2).or_else(|| search(input, x1, x2, y1, y - 1)),
70    }
71}
aoc/year2019/day02.rs

aoc/year2019/
day02.rs
