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

aoc/year2017/
day16.rs
