From ebf49fb576887a94aaeded1bbc1298d8b7b39ad0 Mon Sep 17 00:00:00 2001
From: Reiner Herrmann <reiner@reiner-h.de>
Date: Tue, 15 Dec 2020 14:15:06 +0100
Subject: day15

---
 src/main.rs | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 51 insertions(+), 1 deletion(-)

diff --git a/src/main.rs b/src/main.rs
index f0f0336..0f0649e 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1214,8 +1214,39 @@ fn day14() {
     println!("14b: {}", program.run_v2());
 }
 
+fn memory_number(numbers: &[usize], limit: usize) -> usize {
+    let mut memory = HashMap::new();
+    let mut last_number = 0;
+
+    for (i, number) in numbers.iter().enumerate() {
+        memory.insert(*number, (i, i, 0));
+        last_number = *number;
+    }
+
+    for i in memory.len()..limit {
+        let (pos0, pos1, count) = memory[&last_number];
+        last_number = match count {
+            0 => 0,
+            _ => pos1 - pos0,
+        };
+        let update = match memory.get(&last_number) {
+            None => (i, i, 0),
+            Some((_, p1, c)) => (*p1, i, c + 1),
+        };
+        memory.insert(last_number, update);
+    }
+    last_number
+}
+
+fn day15() {
+    let input = [1, 2, 16, 19, 18, 0];
+
+    println!("15a: {}", memory_number(&input, 2020));
+    println!("15b: {}", memory_number(&input, 30000000));
+}
+
 fn main() {
-    day14();
+    day15();
 }
 
 #[cfg(test)]
@@ -1492,4 +1523,23 @@ mod tests {
         let program = DockingProgram::new(&input);
         assert_eq!(program.run_v2(), 208);
     }
+
+    #[test]
+    fn test_day15() {
+        assert_eq!(memory_number(&[1, 3, 2], 2020), 1);
+        assert_eq!(memory_number(&[2, 1, 3], 2020), 10);
+        assert_eq!(memory_number(&[1, 2, 3], 2020), 27);
+        assert_eq!(memory_number(&[2, 3, 1], 2020), 78);
+        assert_eq!(memory_number(&[3, 2, 1], 2020), 438);
+        assert_eq!(memory_number(&[3, 1, 2], 2020), 1836);
+
+        // disabled due to long runtime
+        //assert_eq!(memory_number(&[0, 3, 6], 30000000), 175594);
+        //assert_eq!(memory_number(&[1, 3, 2], 30000000), 2578);
+        //assert_eq!(memory_number(&[2, 1, 3], 30000000), 3544142);
+        //assert_eq!(memory_number(&[1, 2, 3], 30000000), 261214);
+        //assert_eq!(memory_number(&[2, 3, 1], 30000000), 6895259);
+        //assert_eq!(memory_number(&[3, 2, 1], 30000000), 18);
+        //assert_eq!(memory_number(&[3, 1, 2], 30000000), 362);
+    }
 }
-- 
cgit v1.2.3