From 3b877bf4cc667eb8bcc787d145203600a4dba2d2 Mon Sep 17 00:00:00 2001
From: Prefetch
Date: Sat, 25 Feb 2023 11:41:27 +0100
Subject: Initial commit

---
 d14/src/main.rs | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 116 insertions(+)
 create mode 100644 d14/src/main.rs

(limited to 'd14/src/main.rs')

diff --git a/d14/src/main.rs b/d14/src/main.rs
new file mode 100644
index 0000000..52f9f1f
--- /dev/null
+++ b/d14/src/main.rs
@@ -0,0 +1,116 @@
+use md5;
+
+type Hash = Vec<char>;
+
+// Find first `char' appearing three time in a row in `h', if any
+fn find_triple(h: &Hash) -> Option<char> {
+    for i in 0..h.len() - 2 {
+        if h[i] == h[i + 1] && h[i] == h[i + 2] {
+            return Some(h[i]);
+        }
+    }
+    None
+}
+
+// Does `h' contain `c' five times in a row?
+fn has_quintuple(h: &Hash, c: char) -> bool {
+    let mut qs: Vec<char> = Vec::new();
+
+    for i in 0..h.len() - 4 {
+        if h[i] == h[i + 1] && h[i] == h[i + 2] && h[i] == h[i + 3] && h[i] == h[i + 4] {
+            qs.push(h[i])
+        }
+    }
+
+    qs.contains(&c)
+}
+
+struct HashCache<'a> {
+    salt: &'a str,
+    reps: usize,
+    vec: Vec<Hash>,
+}
+
+impl<'a> HashCache<'a> {
+    fn new(salt: &'a str, reps: usize) -> Self {
+        HashCache {
+            salt,
+            reps,
+            vec: Vec::new(),
+        }
+    }
+
+    // Generate hashes on demand, and always cache them for later use.
+    // Can't write this as `impl Index<usize> for HashCache' because
+    // the `Index' trait only allows an immutable borrow `&self'.
+    fn at_index(&mut self, i: usize) -> &Hash {
+        // If this hash is not in the cache yet...
+        if i >= self.vec.len() {
+            // ... calculate all hashes up to the requested one
+            for j in self.vec.len()..i + 1 {
+                let d = format!("{}{}", self.salt, j);
+                let mut h = format!("{:x}", md5::compute(d));
+
+                // Additional key stretching repetitions
+                for _k in 0..self.reps {
+                    h = format!("{:x}", md5::compute(h));
+                }
+
+                self.vec.push(h.chars().collect());
+            }
+        }
+
+        &self.vec[i]
+    }
+}
+
+fn solve_puzzle(salt: &str, reps: usize) -> usize {
+    // The 64 valid indices we want to find
+    let mut valid = Vec::new();
+
+    let mut hc = HashCache::new(salt, reps);
+    let mut i = 0;
+    while valid.len() < 64 {
+        // If `hc.at_index(i)' contains any `c' three times in a row
+        if let Some(c) = find_triple(hc.at_index(i)) {
+            for j in 1..1001 {
+                if has_quintuple(hc.at_index(i + j), c) {
+                    valid.push(i);
+                    break;
+                }
+            }
+        }
+
+        i += 1;
+    }
+
+    *valid.last().unwrap()
+}
+
+fn main() {
+    // My personal puzzle input
+    let salt = "yjdafjpo";
+
+    // Part 1 gives 25427 for me
+    println!("Part 1 solution: {}", solve_puzzle(salt, 0));
+
+    // Part 2 gives 22045 for me
+    println!("Part 2 solution: {}", solve_puzzle(salt, 2016));
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1_example1() {
+        let salt = "abc";
+        assert_eq!(solve_puzzle(salt, 0), 22728);
+    }
+
+    #[test]
+    fn part2_example1() {
+        let salt = "abc";
+        assert_eq!(solve_puzzle(salt, 2016), 22551);
+    }
+}
-- 
cgit v1.2.3