aoc/year2019/
day07.rs

1//! # Amplification Circuit
2//!
3//! Brute force solution for both parts using the utility [`permutations`] method to test each of
4//! the possible 5! or 120 permutations of the phase settings.
5use std::array::from_fn;
6
7use super::intcode::*;
8use crate::util::parse::*;
9
10pub fn parse(input: &str) -> Vec<i64> {
11    input.iter_signed::<i64>().collect()
12}
13
14pub fn part1(input: &[i64]) -> i64 {
15    let mut result = 0;
16    let mut computer = Computer::new(input);
17
18    let sequence = |slice: &[i64]| {
19        let mut signal = 0;
20
21        // Send exactly 2 inputs and receive exactly 1 output per amplifier.
22        for &phase in slice {
23            computer.reset();
24            computer.input(phase);
25            computer.input(signal);
26            let State::Output(next) = computer.run() else { unreachable!() };
27            signal = next;
28        }
29
30        result = result.max(signal);
31    };
32
33    permutations(&mut [0, 1, 2, 3, 4], sequence);
34    result
35}
36
37pub fn part2(input: &[i64]) -> i64 {
38    let mut result = 0;
39    let mut computers: [Computer; 5] = from_fn(|_| Computer::new(input));
40
41    let feedback = |slice: &[i64]| {
42        // Reset state.
43        computers.iter_mut().for_each(Computer::reset);
44
45        // Send each initial phase setting exactly once.
46        for (computer, &phase) in computers.iter_mut().zip(slice) {
47            computer.input(phase);
48        }
49
50        // Chain amplifier inputs and outputs in a loop until all threads finish.
51        let mut signal = 0;
52
53        'outer: loop {
54            for computer in &mut computers {
55                computer.input(signal);
56                let State::Output(next) = computer.run() else { break 'outer };
57                signal = next;
58            }
59        }
60
61        result = result.max(signal);
62    };
63
64    permutations(&mut [5, 6, 7, 8, 9], feedback);
65    result
66}
67
68/// Generates all possible permutations of a mutable slice, passing them one at a time to a
69/// callback function.
70/// Uses [Heap's algorithm](https://en.wikipedia.org/wiki/Heap%27s_algorithm) for efficiency,
71/// modifying the slice in place.
72fn permutations(slice: &mut [i64], mut callback: impl FnMut(&[i64])) {
73    callback(slice);
74
75    let n = slice.len();
76    let mut c = vec![0; n];
77    let mut i = 1;
78
79    while i < n {
80        if c[i] < i {
81            let swap_index = if i.is_multiple_of(2) { 0 } else { c[i] };
82            slice.swap(swap_index, i);
83            callback(slice);
84            c[i] += 1;
85            i = 1;
86        } else {
87            c[i] = 0;
88            i += 1;
89        }
90    }
91}
aoc/year2019/day07.rs

aoc/year2019/
day07.rs
