1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
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);
}
|
