aoc/year2017/
day16.rs

1//! # Permutation Promenade
2//!
3//! The key insight is that a complete dance can be represented by just two transformations.
4//! The spin and exchange moves compose into a single transformation and the partner swaps compose
5//! into a second independent transformation.
6//!
7//! Each transformation can then be applied to itself to double the effect. For example, a single
8//! complete dance turns into two dances, then doubles to four dances and so on.
9//!
10//! This allows us to compute part two with a similar approach to
11//! [exponentiation by squaring](https://en.wikipedia.org/wiki/Exponentiation_by_squaring).
12use std::array::from_fn;
13
14use crate::util::parse::*;
15
16#[derive(Clone, Copy)]
17pub struct Dance {
18    /// The letter in each position from left to right
19    /// with `a` represented by 0, `b` by 1 and so on.
20    position: [usize; 16],
21    /// A map of initial letter to final letter taking into account all partner swaps.
22    /// `a` is at index 0, `b` at index 1. For convenience letters are represented by 0..15.
23    exchange: [usize; 16],
24}
25
26impl Dance {
27    /// Converts a Dance into a string representation.
28    fn apply(self) -> String {
29        self.position.iter().map(|&i| to_char(self.exchange[i])).collect()
30    }
31
32    /// Combines two Dances into a new Dance.
33    fn compose(self, other: Self) -> Self {
34        let position = self.position.map(|i| other.position[i]);
35        let exchange = self.exchange.map(|i| other.exchange[i]);
36        Self { position, exchange }
37    }
38}
39
40/// Reduces all 10,000 individual dance moves into just two independent transformations.
41pub fn parse(input: &str) -> Dance {
42    // Tokenize the input into two parallel iterators.
43    let mut letters = input.bytes().filter(u8::is_ascii_lowercase);
44    let mut numbers = input.iter_unsigned::<usize>();
45
46    // Start from the identity transformation.
47    let mut offset = 0;
48    let mut lookup: [usize; 16] = from_fn(|i| i);
49    let mut position: [usize; 16] = from_fn(|i| i);
50    let mut exchange: [usize; 16] = from_fn(|i| i);
51
52    while let Some(op) = letters.next() {
53        match op {
54            // Increasing the offset has the same effect as rotating elements to the right.
55            b's' => offset += 16 - numbers.next().unwrap(),
56            // Swap two elements taking into account the offset when calculating indices.
57            b'x' => {
58                let first = numbers.next().unwrap();
59                let second = numbers.next().unwrap();
60                position.swap((first + offset) % 16, (second + offset) % 16);
61            }
62            // First lookup the index of each letter, then swap the mapping.
63            b'p' => {
64                let first = from_byte(letters.next().unwrap());
65                let second = from_byte(letters.next().unwrap());
66                lookup.swap(first, second);
67                exchange.swap(lookup[first], lookup[second]);
68            }
69            _ => unreachable!(),
70        }
71    }
72
73    // Rotate the array once to apply all spins.
74    position.rotate_left(offset % 16);
75
76    Dance { position, exchange }
77}
78
79/// Apply the transformation once.
80pub fn part1(input: &Dance) -> String {
81    input.apply()
82}
83
84/// Repeatedly applying a transformation to itself allows the computation of exponentially
85/// more dances, until reaching the complete 1 billion transformations.
86pub fn part2(input: &Dance) -> String {
87    let mut dance = *input;
88
89    // 1 billion is 0b00111011_10011010_11001010_00000000, which is 30 bits, with 13 set. Typical
90    // exponentiation by squaring would be 30 doubles and 13 additions, or 43 calls to
91    // compose. Since one billion is a power of ten, we can do better by 9 cycles of
92    // reaching each next power of ten by two doubles, one addition, and one more double
93    // per cycle, for a total of only 36 calls to compose.
94    for _ in 0..9 {
95        let dance2 = dance.compose(dance);
96        let dance5 = dance2.compose(dance2).compose(dance);
97        dance = dance5.compose(dance5);
98    }
99
100    dance.apply()
101}
102
103fn from_byte(b: u8) -> usize {
104    (b - b'a') as usize
105}
106
107fn to_char(i: usize) -> char {
108    ((i as u8) + b'a') as char
109}
aoc/year2017/day16.rs

aoc/year2017/
day16.rs
