1 files changed, 144 insertions, 0 deletions
diff --git a/2016/src/bin/day21.rs b/2016/src/bin/day21.rs
new file mode 100644
index 0000000..982bf8a
--- /dev/null
+++ b/2016/src/bin/day21.rs
@@ -0,0 +1,144 @@
+use std::io::{self, Read};
+
+#[derive(Clone, Copy)]
+enum Operation {
+    SwapPosition(usize, usize),
+    SwapLetter(u8, u8),
+    RotateLeft(usize),
+    RotateRight(usize),
+    RotateLetter(u8),
+    Reverse(usize, usize),
+    Move(usize, usize),
+}
+
+impl Operation {
+    fn apply(self, slice: &mut [u8]) {
+        match self {
+            Operation::SwapPosition(i, j) => slice.swap(i, j),
+            Operation::SwapLetter(a, b) => {
+                let i = slice.iter().position(|&x| x == a).unwrap();
+                let j = slice.iter().position(|&x| x == b).unwrap();
+                slice.swap(i, j);
+            },
+            Operation::RotateLeft(n) => {
+                let n = n % slice.len();
+                slice[0..n].reverse();
+                slice[n..].reverse();
+                slice.reverse();
+            },
+            Operation::RotateRight(n) => {
+                let n = n % slice.len();
+                slice.reverse();
+                slice[0..n].reverse();
+                slice[n..].reverse();
+            },
+            Operation::RotateLetter(a) => {
+                let mut n = 1 + slice.iter().position(|&x| x == a).unwrap();
+                if n >= 5 { n += 1 }
+                n %= slice.len();
+                slice.reverse();
+                slice[0..n].reverse();
+                slice[n..].reverse();
+            },
+            Operation::Reverse(i, j) => slice[i..(j + 1)].reverse(),
+            Operation::Move(i, j) if i < j => {
+                let a = slice[i];
+                for k in i..j {
+                    slice[k] = slice[k + 1];
+                }
+                slice[j] = a;
+            },
+            Operation::Move(i, j) => {
+                let a = slice[i];
+                for k in (j..i).rev() {
+                    slice[k + 1] = slice[k];
+                }
+                slice[j] = a;
+            },
+        }
+    }
+}
+
+impl<'a> From<&'a str> for Operation {
+    fn from(s: &'a str) -> Self {
+        let mut iter = s.split_whitespace();
+        match (iter.next().unwrap(), iter.next().unwrap()) {
+            ("swap", "position") => Operation::SwapPosition(
+                iter.next().unwrap().parse().unwrap(),
+                iter.nth(2).unwrap().parse().unwrap(),
+            ),
+            ("swap", "letter") => Operation::SwapLetter(
+                iter.next().unwrap().as_bytes()[0],
+                iter.nth(2).unwrap().as_bytes()[0],
+            ),
+            ("rotate", "left") => Operation::RotateLeft(iter.next().unwrap().parse().unwrap()),
+            ("rotate", "right") => Operation::RotateRight(iter.next().unwrap().parse().unwrap()),
+            ("rotate", "based") => Operation::RotateLetter(iter.nth(4).unwrap().as_bytes()[0]),
+            ("reverse", _) => Operation::Reverse(
+                iter.next().unwrap().parse().unwrap(),
+                iter.nth(1).unwrap().parse().unwrap(),
+            ),
+            ("move", _) => Operation::Move(
+                iter.next().unwrap().parse().unwrap(),
+                iter.nth(2).unwrap().parse().unwrap(),
+            ),
+            (x, y) => panic!("invalid operation {} {}", x, y),
+        }
+    }
+}
+
+fn solve1(password: &str, input: &str) -> String {
+    let mut password = password.as_bytes().to_owned();
+
+    for operation in input.lines().map(Operation::from) {
+        operation.apply(&mut password);
+    }
+
+    String::from_utf8(password).unwrap()
+}
+
+fn solve2(scrambled: &str, input: &str) -> String {
+    let operations: Vec<_> = input.lines().map(Operation::from).collect();
+
+    let mut password = "abcdefgh".as_bytes().to_owned();
+    let len = password.len();
+
+    loop {
+        let k = (0..(len - 1)).rev().find(|&k| password[k] < password [k + 1]).unwrap();
+        let l = ((k + 1)..len).rev().find(|&l| password[k] < password[l]).unwrap();
+        password.swap(k, l);
+        password[(k + 1)..].reverse();
+
+        let mut candidate = password.clone();
+        for operation in &operations {
+            operation.apply(&mut candidate);
+        }
+
+        if candidate == scrambled.as_bytes() {
+            return String::from_utf8(password).unwrap();
+        }
+    }
+}
+
+fn main() {
+    let mut input = String::new();
+    io::stdin().read_to_string(&mut input).unwrap();
+
+    println!("Part 1: {}", solve1("abcdefgh", &input));
+    println!("Part 2: {}", solve2("fbgdceah", &input));
+}
+
+#[test]
+fn part1() {
+    let input = "
+swap position 4 with position 0
+swap letter d with letter b
+reverse positions 0 through 4
+rotate left 1 step
+move position 1 to position 4
+move position 3 to position 0
+rotate based on position of letter b
+rotate based on position of letter d
+";
+    assert_eq!("decab", solve1("abcde", input.trim()));
+}