summaryrefslogtreecommitdiff
path: root/2018/src/bin/day_9.rs
blob: 3f856208bb0c44892fcdaeedcaf19318d39c2b64 (plain)
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);
}