From cfd9b4f2ad1a09bedf7f764f84448a61faab54a3 Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Tue, 19 Apr 2022 20:26:02 +0200
Subject: Refile for merging repos

---
 2018/src/bin/day_9.rs | 91 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 91 insertions(+)
 create mode 100644 2018/src/bin/day_9.rs

(limited to '2018/src/bin/day_9.rs')

diff --git a/2018/src/bin/day_9.rs b/2018/src/bin/day_9.rs
new file mode 100644
index 0000000..3f85620
--- /dev/null
+++ b/2018/src/bin/day_9.rs
@@ -0,0 +1,91 @@
+extern crate advent_of_code_2018;
+use advent_of_code_2018::*;
+
+use std::error::Error;
+
+use std::collections::LinkedList;
+
+// cargo watch -cs "cargo run --release --bin day_9"
+
+fn main() -> Result<(), Box<Error>> {
+    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()
+}
+
+// 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);
+}
+
+#[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);
+}
-- 
cgit v1.2.3