aoc/year2019/day21.rs
1//! # Springdroid Adventure
2//!
3//! Jumps are always 4 tiles wide, landing on `D`. If needed we can jump again immediately
4//! landing on `H`. The intcode program runs faster if the springscript is shorter, so although
5//! multiple scripts work, any solution that treats intcode as a black box will be better if
6//! the script is minimized.
7//!
8//! ## Part One
9//!
10//! We jump if any of `A`, `B` or `C` are holes and there is ground where we will land at `D`.
11//! This takes 7 instructions:
12//!
13//! `J = (NOT A OR NOT B OR NOT C) AND D`
14//!
15//! Using [De Morgan's laws](https://en.wikipedia.org/wiki/De_Morgan%27s_laws) we can simplify
16//! to 5 instructions:
17//!
18//! `J = NOT (A AND B AND C) AND D`
19//!
20//! But in practice, all input files are set up so that part 1 is just the 7 possible sets of
21//! 4 positions with a leading hole but not 4 consecutive holes; this can be solved without ever
22//! probing position `B`, simplifying to 4 instructions:
23//!
24//! `J = NOT (A AND C) AND D`
25//!
26//! ## Part Two
27//!
28//! Now the input files have 153 sets of 9 positions, but again with never more than three
29//! consecutive holes. Checking `B` now matters, and we also need a new rule to jump if `H` is
30//! ground when `C` is a hole, to trigger a double jump. But overall, this can be done in six
31//! instructions. Surprisingly, we never needed to use register `T`.
32use super::intcode::*;
33use crate::util::parse::*;
34
35const WALK: &str = "\
36OR A J
37AND C J
38NOT J J
39AND D J
40WALK
41";
42
43const RUN: &str = "\
44NOT H J
45OR C J
46AND B J
47AND A J
48NOT J J
49AND D J
50RUN
51";
52
53pub fn parse(input: &str) -> Vec<i64> {
54 input.iter_signed().collect()
55}
56
57pub fn part1(input: &[i64]) -> i64 {
58 survey(input, WALK)
59}
60
61pub fn part2(input: &[i64]) -> i64 {
62 survey(input, RUN)
63}
64
65fn survey(input: &[i64], springscript: &str) -> i64 {
66 let mut computer = Computer::new(input);
67 computer.input_ascii(springscript);
68
69 let mut result = 0;
70 while let State::Output(next) = computer.run() {
71 result = next;
72 }
73 result
74}