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    /// Creates a new Dance that represents the identity transformation.
27    fn new() -> Dance {
28        Dance { position: from_fn(|i| i), exchange: from_fn(|i| i) }
29    }
30
31    /// Converts a Dance into a string representation.
32    fn apply(self) -> String {
33        self.position.iter().map(|&i| to_char(self.exchange[i])).collect()
34    }
35
36    /// Combines two Dances into a new Dance.
37    fn compose(self, other: Dance) -> Dance {
38        let position = self.position.map(|i| other.position[i]);
39        let exchange = self.exchange.map(|i| other.exchange[i]);
40        Dance { position, exchange }
41    }
42}
43
44/// Reduces all 10,000 individual dance moves into just two independent transformations.
45pub fn parse(input: &str) -> Dance {
46    // Tokenize the input into two parallel iterators
47    let mut letters = input.bytes().filter(u8::is_ascii_lowercase);
48    let mut numbers = input.iter_unsigned::<usize>();
49
50    let mut offset = 0;
51    let mut lookup: [usize; 16] = from_fn(|i| i);
52    let Dance { mut position, mut exchange } = Dance::new();
53
54    while let Some(op) = letters.next() {
55        match op {
56            // Increasing the offset has the same effect as rotating elements to the right.
57            b's' => {
58                offset += 16 - numbers.next().unwrap();
59            }
60            // Swap two elements taking into account the offset when calculating indices.
61            b'x' => {
62                let first = numbers.next().unwrap();
63                let second = numbers.next().unwrap();
64                position.swap((first + offset) % 16, (second + offset) % 16);
65            }
66            // First lookup the index of each letter, then swap the mapping.
67            b'p' => {
68                let first = from_byte(letters.next().unwrap());
69                let second = from_byte(letters.next().unwrap());
70                lookup.swap(first, second);
71                exchange.swap(lookup[first], lookup[second]);
72            }
73            _ => unreachable!(),
74        }
75    }
76
77    // Rotate the array once to apply all spins.
78    position.rotate_left(offset % 16);
79
80    Dance { position, exchange }
81}
82
83/// Apply the transformation once.
84pub fn part1(input: &Dance) -> String {
85    input.apply()
86}
87
88/// If a bit is set in the binary representation of 1 billion apply the current transformation,
89/// then apply the transformation to itself to double the number of complete dances.
90pub fn part2(input: &Dance) -> String {
91    let mut e = 1_000_000_000;
92    let mut dance = *input;
93    let mut result = Dance::new();
94
95    while e > 0 {
96        if e & 1 == 1 {
97            result = result.compose(dance);
98        }
99
100        e >>= 1;
101        dance = dance.compose(dance);
102    }
103
104    result.apply()
105}
106
107fn from_byte(b: u8) -> usize {
108    (b - b'a') as usize
109}
110
111fn to_char(i: usize) -> char {
112    ((i as u8) + b'a') as char
113}
aoc/year2017/day16.rs

aoc/year2017/
day16.rs
