Day 9: Inserting into very big lists

1 files changed, 77 insertions, 4 deletions

diff --git a/src/bin/day_9.rs b/src/bin/day_9.rs
index 3aaf640..3f85620 100644
--- a/src/bin/day_9.rs
+++ b/src/bin/day_9.rs
@@ -2,17 +2,90 @@ extern crate advent_of_code_2018;
 use advent_of_code_2018::*;
 
 use std::error::Error;
-use std::path::PathBuf;
+
+use std::collections::LinkedList;
 
 // cargo watch -cs "cargo run --release --bin day_9"
 
 fn main() -> Result<(), Box<Error>> {
-    let input = read_file(&PathBuf::from("inputs/9.txt"))?;
+    debug!(get_winning_player_score(438, 71626));
+    debug!(get_winning_player_score(438, 71626*100));
+    
+    Ok(())
+}
+
+
+fn get_winning_player_score(players: usize, last_marble_score: u32) -> u32 {
+    let mut marbles_head = LinkedList::new();
+    let mut marbles_tail = LinkedList::new();
+    marbles_head.push_back(0);
+    
+    let mut current_player = 0;
+    let mut next_marble = 1;
+    let mut scores = vec!(0; players);
+    
+    while next_marble <= last_marble_score {
+        if next_marble % 23 == 0 {
+            move_backwards(&mut marbles_head, &mut marbles_tail, 7);
+            let removed = marbles_head.pop_back().expect("Going backwards should have ended with pushing to head");
+            move_forward(&mut marbles_head, &mut marbles_tail, 1);
+            
+            let score = next_marble + removed;
+            scores[current_player] += score;
+        } else {
+            move_forward(&mut marbles_head, &mut marbles_tail, 1);
+            marbles_head.push_back(next_marble);
+        }
+        
+        next_marble += 1;
+        current_player = (current_player + 1) % players;
+    }
+    
+    scores.iter().max().unwrap().clone()
+}
 
-    println!("Input: {:?}", input);
+// WARNING: These don't play well with empty lists
+fn move_forward(marbles_head: &mut LinkedList<u32>, marbles_tail: &mut LinkedList<u32>, i: usize) {
+    if i != 0 {
+        match marbles_tail.pop_front() {
+            Some(marble) => {
+                marbles_head.push_back(marble);
+                move_forward(marbles_head, marbles_tail, i-1);
+            },
+            None => {
+                marbles_tail.append(marbles_head);
+                move_forward(marbles_head, marbles_tail, i);
+            },
+        }
+    }
+}
 
+fn move_backwards(marbles_head: &mut LinkedList<u32>, marbles_tail: &mut LinkedList<u32>, i: usize) {
+    if i != 0 {
+        match marbles_head.pop_back() {
+            Some(marble) => {
+                marbles_tail.push_front(marble);
+                move_backwards(marbles_head, marbles_tail, i-1);
+            },
+            None => {
+                marbles_head.append(marbles_tail);
+                move_backwards(marbles_head, marbles_tail, i);
+            },
+        }
+    }
+}
 
 
+#[test]
+fn trivial() {
+    assert_eq!(get_winning_player_score(9, 32), 32);
+}
 
-    Ok(())
+#[test]
+fn examples() {
+    assert_eq!(get_winning_player_score(10, 1618), 8317);
+    assert_eq!(get_winning_player_score(13, 7999), 146373);
+    assert_eq!(get_winning_player_score(17, 1104), 2764);
+    assert_eq!(get_winning_player_score(21, 6111), 54718);
+    assert_eq!(get_winning_player_score(30, 5807), 37305);
 }