summaryrefslogtreecommitdiff
path: root/2018/src/bin/day_14.rs
blob: cb166232c5fd5594ea82ec9a17cbc4799f6ff1f3 (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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
extern crate advent_of_code_2018;
use advent_of_code_2018::*;

use std::error::Error;
use std::path::PathBuf;

// cargo watch -cs "cargo run --release --bin day_14"

fn main() -> Result<(), Box<Error>> {
    let input = 540561;

    let scoreboard = find_ten_scoreboard_after(input);

    println!("Result: ");
    scoreboard.iter().for_each(|s| {
        print!("{}", s);
    });
    println!();

    let first_occurence = find_first_occurence_of(input);
    debug!(first_occurence);

    Ok(())
}

fn find_ten_scoreboard_after(input: usize) -> Vec<usize> {
    let mut scoreboard = vec!(3,7);
    let mut elf1_pos = 0;
    let mut elf2_pos = 1;

    while scoreboard.len() < (input + 10) {
        let next = scoreboard[elf1_pos] + scoreboard[elf2_pos];
        for digit in number_to_digits_vec(next) {
            scoreboard.push(digit);
        }

        elf1_pos = (elf1_pos + 1 + scoreboard[elf1_pos]) % scoreboard.len();
        elf2_pos = (elf2_pos + 1 + scoreboard[elf2_pos]) % scoreboard.len();
    }

    scoreboard.iter().skip(input).take(10).cloned().collect()
}

fn find_first_occurence_of(input: usize) -> usize {
    let target_sequence = number_to_digits_vec(input);
    debug!(target_sequence);

    let mut scoreboard = vec!(3,7);
    let mut elf1_pos = 0;
    let mut elf2_pos = 1;
    let mut target_index = None;

    while target_index.is_none() {
        let next = scoreboard[elf1_pos] + scoreboard[elf2_pos];
        for digit in number_to_digits_vec(next) {
            scoreboard.push(digit);
        }

        elf1_pos = (elf1_pos + 1 + scoreboard[elf1_pos]) % scoreboard.len();
        elf2_pos = (elf2_pos + 1 + scoreboard[elf2_pos]) % scoreboard.len();

        if scoreboard.len() >= target_sequence.len() + 2 {
            for potential_target_index in scoreboard.len()-target_sequence.len()-2..scoreboard.len()-target_sequence.len()+1 {
                let found = scoreboard.iter()
                    .skip(potential_target_index)
                    .take(target_sequence.len())
                    .zip(target_sequence.iter())
                    .all(|(a, b)| a == b);
                if found {
                    target_index = Some(potential_target_index);
                }
            }
        }
    }

    target_index.unwrap()
}

fn number_to_digits_vec(input: usize) -> Vec<usize> {
    if input == 0 {
        return vec!(0);
    }
    
    let mut result = Vec::new();
    let mut acc = input;
    while acc > 0 {
        result.push(acc % 10);
        acc /= 10;
    }
    result.reverse();
    result
}

#[test]
fn vectorification() {
    assert_eq!(number_to_digits_vec(10), vec!(1, 0));
    assert_eq!(number_to_digits_vec(1), vec!(1));
    assert_eq!(number_to_digits_vec(0), vec!(0));
}

#[test]
fn part1_examples() {
    assert_eq!(find_ten_scoreboard_after(9), vec!(5,1,5,8,9,1,6,7,7,9));
    assert_eq!(find_ten_scoreboard_after(2018), vec!(5,9,4,1,4,2,9,8,8,2));
}

#[test]
fn part2_examples() {
    assert_eq!(find_first_occurence_of(51589), 9);
    assert_eq!(find_first_occurence_of(59414), 2018);
}