year2016/
day21.rs

1use utils::prelude::*;
2
3/// Unscrambling passwords.
4#[derive(Clone, Debug)]
5pub struct Day21 {
6    input_type: InputType,
7    operations: Vec<Operation>,
8}
9
10#[derive(Copy, Clone, Debug)]
11enum Operation {
12    SwapPosition(u32, u32),
13    SwapLetter(u8, u8),
14    RotateLeft(u32),
15    RotateRight(u32),
16    RotateLetter(u8),
17    RotateLetterReverse(u8),
18    Reverse(u32, u32),
19    Move(u32, u32),
20}
21
22impl Day21 {
23    pub fn new(input: &str, input_type: InputType) -> Result<Self, InputError> {
24        let (position, letter) = match input_type {
25            InputType::Example => (parser::number_range(0..=4), parser::byte_range(b'a'..=b'e')),
26            InputType::Real => (parser::number_range(0..=7), parser::byte_range(b'a'..=b'h')),
27        };
28
29        Ok(Self {
30            input_type,
31            operations: parser::one_of((
32                position
33                    .with_prefix("swap position ")
34                    .then(position.with_prefix(" with position "))
35                    .map(|(from, to)| Operation::SwapPosition(from, to)),
36                letter
37                    .with_prefix("swap letter ")
38                    .then(letter.with_prefix(" with letter "))
39                    .map(|(a, b)| Operation::SwapLetter(a, b)),
40                position
41                    .with_prefix("rotate left ")
42                    .with_suffix(" step".then("s".optional()))
43                    .map(Operation::RotateLeft),
44                position
45                    .with_prefix("rotate right ")
46                    .with_suffix(" step".then("s".optional()))
47                    .map(Operation::RotateRight),
48                letter
49                    .with_prefix("rotate based on position of letter ")
50                    .map(Operation::RotateLetter),
51                position
52                    .with_prefix("reverse positions ")
53                    .then(position.with_prefix(" through "))
54                    .map(|(start, end)| Operation::Reverse(start, end)),
55                position
56                    .with_prefix("move position ")
57                    .then(position.with_prefix(" to position "))
58                    .map(|(from, to)| Operation::Move(from, to)),
59            ))
60            .parse_lines(input)?,
61        })
62    }
63
64    #[must_use]
65    pub fn part1(&self) -> String {
66        let operations = self.operations.iter().copied();
67        let scrambled = match self.input_type {
68            InputType::Example => Scrambler::scramble(operations, *b"abcde").to_vec(),
69            InputType::Real => Scrambler::scramble(operations, *b"abcdefgh").to_vec(),
70        };
71        String::from_utf8(scrambled).unwrap()
72    }
73
74    #[must_use]
75    pub fn part2(&self) -> String {
76        let operations = self.operations.iter().rev().map(|&op| match op {
77            Operation::RotateLeft(shift) => Operation::RotateRight(shift),
78            Operation::RotateRight(shift) => Operation::RotateLeft(shift),
79            Operation::RotateLetter(shift) => Operation::RotateLetterReverse(shift),
80            Operation::Move(from, to) => Operation::Move(to, from),
81            _ => op,
82        });
83
84        let scrambled = match self.input_type {
85            InputType::Example => panic!("no part 2 example"),
86            InputType::Real => Scrambler::scramble(operations, *b"fbgdceah").to_vec(),
87        };
88        String::from_utf8(scrambled).unwrap()
89    }
90}
91
92struct Scrambler<const N: usize>;
93impl<const N: usize> Scrambler<N> {
94    const REVERSE_LETTER_ROTATIONS: Option<[usize; N]> = Self::reverse_letter_rotations();
95
96    fn scramble(operations: impl Iterator<Item = Operation>, mut password: [u8; N]) -> [u8; N] {
97        for operation in operations {
98            match operation {
99                Operation::SwapPosition(from, to) => {
100                    password.swap(from as usize, to as usize);
101                }
102                Operation::SwapLetter(a, b) => {
103                    let x = password.iter().position(|&c| c == a).unwrap();
104                    let y = password.iter().position(|&c| c == b).unwrap();
105                    password.swap(x, y);
106                }
107                Operation::RotateLeft(steps) => {
108                    password.rotate_left(steps as usize);
109                }
110                Operation::RotateRight(steps) => {
111                    password.rotate_right(steps as usize);
112                }
113                Operation::RotateLetter(letter) => {
114                    let i = password.iter().position(|&c| c == letter).unwrap();
115                    password.rotate_right(Self::rotate_letter_amount(i) % N);
116                }
117                Operation::RotateLetterReverse(letter) => {
118                    let reverse_rotations = Self::REVERSE_LETTER_ROTATIONS.unwrap_or_else(|| {
119                        panic!("letter rotation for {N} long passwords isn't unique")
120                    });
121                    let i = password.iter().position(|&c| c == letter).unwrap();
122                    password.rotate_left(reverse_rotations[i]);
123                }
124                Operation::Reverse(start, end) => {
125                    password[start as usize..=end as usize].reverse();
126                }
127                Operation::Move(from, to) => {
128                    let v = password[from as usize];
129                    if from < to {
130                        password.copy_within(from as usize + 1..=to as usize, from as usize);
131                    } else {
132                        password.copy_within(to as usize..from as usize, to as usize + 1);
133                    }
134                    password[to as usize] = v;
135                }
136            }
137        }
138
139        password
140    }
141
142    const fn rotate_letter_amount(i: usize) -> usize {
143        if i < 4 {
144            i + 1
145        } else {
146            i + 2
147        }
148    }
149
150    const fn reverse_letter_rotations() -> Option<[usize; N]> {
151        let mut reverse = [usize::MAX; N];
152        let mut i = 0;
153        while i < N {
154            let dest = (i + Self::rotate_letter_amount(i)) % N;
155            if reverse[dest] != usize::MAX {
156                return None;
157            }
158            reverse[dest] = (N + dest - i) % N;
159            i += 1;
160        }
161        Some(reverse)
162    }
163}
164
165examples!(Day21 -> (&'static str, &'static str) [
166    {file: "day21_example0.txt", part1: "decab"},
167]);
year2016/day21.rs

year2016/
day21.rs
