summaryrefslogtreecommitdiff
path: root/2018/src/bin/day_9.rs
diff options
context:
space:
mode:
Diffstat (limited to '2018/src/bin/day_9.rs')
-rw-r--r--2018/src/bin/day_9.rs91
1 files changed, 91 insertions, 0 deletions
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);
+}