year2017/
day16.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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
use std::array;
use std::fmt::{Display, Formatter, Write};
use std::ops::MulAssign;
use utils::prelude::*;

/// Composing permutations.
///
/// The key optimization is that all the index-based permutations (Spin and Exchange) can be
/// combined into one permutation, and all the value-based permutations (Partner) can be combined
/// into another.
#[derive(Clone, Debug)]
pub struct Day16 {
    dance: Dance,
}

#[derive(Clone, Debug)]
enum DanceMove {
    Spin(u8),
    Exchange(u8, u8),
    Partner(u8, u8),
}

#[derive(Copy, Clone, Debug)]
struct Dance {
    index_perm: [usize; 16],
    value_perm: [usize; 16],
}

impl Day16 {
    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
        let program = parser::byte_range(b'a'..=b'p').map(|b| b - b'a');
        let position = parser::number_range(0..=15);

        Ok(Self {
            dance: parser::one_of((
                position.with_prefix(b's').map(DanceMove::Spin),
                position
                    .with_prefix(b'x')
                    .then(position.with_prefix(b'/'))
                    .map(|(a, b)| DanceMove::Exchange(a, b)),
                program
                    .with_prefix(b'p')
                    .then(program.with_prefix(b'/'))
                    .map(|(a, b)| DanceMove::Partner(a, b)),
            ))
            .with_suffix(b','.or(parser::eof()))
            .parse_iterator(input)
            .collect::<Result<Dance, InputError>>()?,
        })
    }

    #[must_use]
    pub fn part1(&self) -> String {
        self.dance.to_string()
    }

    #[must_use]
    pub fn part2(&self) -> String {
        // Exponentiation by squaring, but for dance permutations
        let mut result = Dance::default();
        let mut base = self.dance;
        let mut exponent = 1_000_000_000;

        while exponent > 0 {
            if exponent % 2 == 1 {
                result *= base;
            }
            exponent >>= 1;
            base *= base;
        }

        result.to_string()
    }
}

impl Default for Dance {
    fn default() -> Self {
        Dance {
            index_perm: array::from_fn(|i| i),
            value_perm: array::from_fn(|i| i),
        }
    }
}

impl FromIterator<DanceMove> for Dance {
    #[inline]
    fn from_iter<T: IntoIterator<Item = DanceMove>>(iter: T) -> Self {
        let mut dance = Dance::default();
        let mut value_positions: [usize; 16] = array::from_fn(|i| i);
        let mut rotation = 0; // Rotate once at the end as it is expensive

        for dance_move in iter {
            match dance_move {
                DanceMove::Spin(r) => rotation += 16 - r as usize,
                DanceMove::Exchange(a, b) => {
                    let a_idx = (a as usize + rotation) % 16;
                    let b_idx = (b as usize + rotation) % 16;
                    dance.index_perm.swap(a_idx, b_idx);
                }
                DanceMove::Partner(a, b) => {
                    value_positions.swap(a as usize, b as usize);
                    let a_idx = value_positions[a as usize];
                    let b_idx = value_positions[b as usize];
                    dance.value_perm.swap(a_idx, b_idx);
                }
            }
        }
        dance.index_perm.rotate_left(rotation % 16);

        dance
    }
}

impl Display for Dance {
    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
        for &i in &self.index_perm {
            f.write_char((self.value_perm[i] as u8 + b'a') as char)?;
        }
        Ok(())
    }
}

impl MulAssign for Dance {
    fn mul_assign(&mut self, rhs: Self) {
        self.index_perm = self.index_perm.map(|i| rhs.index_perm[i]);
        self.value_perm = self.value_perm.map(|i| rhs.value_perm[i]);
    }
}

examples!(Day16 -> (&'static str, &'static str) []);