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

aoc/year2019/
day07.rs
