summary refs log tree commit diff homepage
diff options
context:
space:
mode:
authorJune McEnroe <programble@gmail.com>2016-12-21 23:33:00 -0500
committerJune McEnroe <programble@gmail.com>2016-12-21 23:33:00 -0500
commit40419ed0dc6d6236282b2d4712ec361c0e70bb5d (patch)
tree66f45fa77e177940da2007b1197395296f281abd
parentFuck (diff)
downloadaoc-40419ed0dc6d6236282b2d4712ec361c0e70bb5d.tar.gz
aoc-40419ed0dc6d6236282b2d4712ec361c0e70bb5d.zip
Day 21 part 2
-rw-r--r--src/bin/day21.rs30
1 files changed, 27 insertions, 3 deletions
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()));
 }
This handles upside-down graphics much better than reverse did. 2018-02-05Remove gfxx reverse optionJune McEnroe 2018-02-04Fix gfxx draw stop conditionJune McEnroe Would not draw the last partially visible column when mirrored. 2018-02-04Reuse CGColorSpace and CGDataProvider in gfcocoaJune McEnroe 2018-02-04Mark mac target phonyJune McEnroe 2018-02-04Set up Makefile for gfxx-cocoa or gfxx-fbJune McEnroe 2018-02-04Avoid doing excessive work in gfxxJune McEnroe By stopping when the next column would be off the edge of the buffer. 2018-02-04Handle window resizing in gfcocoaJune McEnroe 2018-02-04Set cinoptionsJune McEnroe 2018-02-04Tweak colorscheme moreJune McEnroe 2018-02-04Color MatchParen DarkYellowJune McEnroe White is not obvious enough. 2018-02-04Add palette sampling to gfxxJune McEnroe 2018-02-04Add 4-bit RGB to gfxxJune McEnroe Replace default palette with alternating black and white. 2018-02-04Add Quit menu item to gfcocoaJune McEnroe 2018-02-04Switch back to sane Objective-C styleJune McEnroe 2018-02-04Quit gfcocoa when window closesJune McEnroe 2018-02-03Apparently this is how people write Objective-CJune McEnroe