From 83336085cc3f1c9900ab24e164643d32b7c38c01 Mon Sep 17 00:00:00 2001
From: June McEnroe <june@causal.agency>
Date: Wed, 21 Dec 2016 23:33:00 -0500
Subject: Day 21 part 2

---
 src/bin/day21.rs | 30 +++++++++++++++++++++++++++---
 1 file changed, 27 insertions(+), 3 deletions(-)

(limited to 'src/bin/day21.rs')

diff --git a/src/bin/day21.rs b/src/bin/day21.rs
index c9abb76..982bf8a 100644
--- a/src/bin/day21.rs
+++ b/src/bin/day21.rs
@@ -87,7 +87,7 @@ impl<'a> From<&'a str> for Operation {
     }
 }
 
-fn solve(password: &str, input: &str) -> String {
+fn solve1(password: &str, input: &str) -> String {
     let mut password = password.as_bytes().to_owned();
 
     for operation in input.lines().map(Operation::from) {
@@ -97,11 +97,35 @@ fn solve(password: &str, input: &str) -> String {
     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: {}", solve("abcdefgh", &input));
+    println!("Part 1: {}", solve1("abcdefgh", &input));
+    println!("Part 2: {}", solve2("fbgdceah", &input));
 }
 
 #[test]
@@ -116,5 +140,5 @@ move position 3 to position 0
 rotate based on position of letter b
 rotate based on position of letter d
 ";
-    assert_eq!("decab", solve("abcde", input.trim()));
+    assert_eq!("decab", solve1("abcde", input.trim()));
 }
-- 
cgit 1.4.1