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