year2017/
day16.rs

1use std::array;
2use std::fmt::{Display, Formatter, Write};
3use std::ops::MulAssign;
4use utils::prelude::*;
5
6/// Composing permutations.
7///
8/// The key optimization is that all the index-based permutations (Spin and Exchange) can be
9/// combined into one permutation, and all the value-based permutations (Partner) can be combined
10/// into another.
11#[derive(Clone, Debug)]
12pub struct Day16 {
13    dance: Dance,
14}
15
16#[derive(Clone, Debug)]
17enum DanceMove {
18    Spin(u8),
19    Exchange(u8, u8),
20    Partner(u8, u8),
21}
22
23#[derive(Copy, Clone, Debug)]
24struct Dance {
25    index_perm: [usize; 16],
26    value_perm: [usize; 16],
27}
28
29impl Day16 {
30    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
31        let program = parser::byte_range(b'a'..=b'p').map(|b| b - b'a');
32        let position = parser::number_range(0..=15);
33
34        Ok(Self {
35            dance: parser::one_of((
36                position.with_prefix(b's').map(DanceMove::Spin),
37                position
38                    .with_prefix(b'x')
39                    .then(position.with_prefix(b'/'))
40                    .map(|(a, b)| DanceMove::Exchange(a, b)),
41                program
42                    .with_prefix(b'p')
43                    .then(program.with_prefix(b'/'))
44                    .map(|(a, b)| DanceMove::Partner(a, b)),
45            ))
46            .with_suffix(b','.or(parser::eof()))
47            .parse_iterator(input)
48            .collect::<Result<Dance, InputError>>()?,
49        })
50    }
51
52    #[must_use]
53    pub fn part1(&self) -> String {
54        self.dance.to_string()
55    }
56
57    #[must_use]
58    pub fn part2(&self) -> String {
59        // Exponentiation by squaring, but for dance permutations
60        let mut result = Dance::default();
61        let mut base = self.dance;
62        let mut exponent = 1_000_000_000;
63
64        while exponent > 0 {
65            if exponent % 2 == 1 {
66                result *= base;
67            }
68            exponent >>= 1;
69            base *= base;
70        }
71
72        result.to_string()
73    }
74}
75
76impl Default for Dance {
77    fn default() -> Self {
78        Dance {
79            index_perm: array::from_fn(|i| i),
80            value_perm: array::from_fn(|i| i),
81        }
82    }
83}
84
85impl FromIterator<DanceMove> for Dance {
86    #[inline]
87    fn from_iter<T: IntoIterator<Item = DanceMove>>(iter: T) -> Self {
88        let mut dance = Dance::default();
89        let mut value_positions: [usize; 16] = array::from_fn(|i| i);
90        let mut rotation = 0; // Rotate once at the end as it is expensive
91
92        for dance_move in iter {
93            match dance_move {
94                DanceMove::Spin(r) => rotation += 16 - r as usize,
95                DanceMove::Exchange(a, b) => {
96                    let a_idx = (a as usize + rotation) % 16;
97                    let b_idx = (b as usize + rotation) % 16;
98                    dance.index_perm.swap(a_idx, b_idx);
99                }
100                DanceMove::Partner(a, b) => {
101                    value_positions.swap(a as usize, b as usize);
102                    let a_idx = value_positions[a as usize];
103                    let b_idx = value_positions[b as usize];
104                    dance.value_perm.swap(a_idx, b_idx);
105                }
106            }
107        }
108        dance.index_perm.rotate_left(rotation % 16);
109
110        dance
111    }
112}
113
114impl Display for Dance {
115    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
116        for &i in &self.index_perm {
117            f.write_char((self.value_perm[i] as u8 + b'a') as char)?;
118        }
119        Ok(())
120    }
121}
122
123impl MulAssign for Dance {
124    fn mul_assign(&mut self, rhs: Self) {
125        self.index_perm = self.index_perm.map(|i| rhs.index_perm[i]);
126        self.value_perm = self.value_perm.map(|i| rhs.value_perm[i]);
127    }
128}
129
130examples!(Day16 -> (&'static str, &'static str) []);
year2017/day16.rs

year2017/
day16.rs
