summaryrefslogtreecommitdiff
path: root/2018/src/bin/day_12.rs
blob: 65a966d0db90e994e4f16fb92125a66a32a542f3 (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
extern crate advent_of_code_2018;
use advent_of_code_2018::*;

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

use std::str::FromStr;

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

use std::collections::HashSet;

#[derive(Debug)]
struct Rule {
    input: [bool; 5],
    output: bool
}

impl FromStr for Rule {
    type Err = Box<Error>;

    fn from_str(s: &str) -> Result<Self, Self::Err> {
        //##..# => #
        let mut input = [false; 5];
        let mut iter = s.chars().filter(|c| *c == '#' || *c == '.');
        for (i, c) in iter.by_ref().take(5).enumerate() {
            if c == '#' {
                input[i] = true;
            }
        }
        Ok(Rule {
            input,
            output: iter.next() == Some('#')
        })
    }
}

impl Rule {
    fn matches(&self, state: &HashSet<i64>, index: i64) -> bool {
        self.input.iter().enumerate().all(|(i, expected)| {
            let pot_index = index - 2 + i as i64;
            *expected == state.contains(&pot_index)
        })
    }
}

fn main() -> Result<(), Box<Error>> {
    let input = read_file(&PathBuf::from("inputs/12.txt"))?;

    println!("Input: {:?}", input);

    let mut initial_state: HashSet<i64> = HashSet::new();
    for (i, c) in input[0].chars().filter(|c| *c == '#' || *c == '.').enumerate() {
        if c == '#' {
            initial_state.insert(i as i64);
        }
    }
    let rules = input.iter().skip(1).map(|line| line.parse()).collect::<Result<Vec<Rule>, Box<Error>>>()?;

    debug!(initial_state);
    debug!(rules);

    let part1_time = 20;
    let part2_time = 50000000000;

    let part1_final_state = iterate_states(&initial_state, &rules, part1_time);
    let sum_of_part1_pot_numbers: i64 = part1_final_state.iter().sum();
    debug!(sum_of_part1_pot_numbers);

    let part2_final_state = iterate_states(&initial_state, &rules, part2_time);
    let sum_of_part2_pot_numbers: i64 = part2_final_state.iter().sum();
    debug!(sum_of_part2_pot_numbers);
    
    Ok(())
}

fn iterate_states(initial_state: &HashSet<i64>, rules: &[Rule], time: i64) -> HashSet<i64> {
    let mut current_state = initial_state.clone();
    for current_time in 0..time {        
        let mut new_state = HashSet::new();
        let min = current_state.iter().min().cloned().unwrap_or(-1) - 2;
        let max = current_state.iter().max().cloned().unwrap_or(-1) + 2;

        for i in min..max+1 {
            if rules.iter().find(|r| r.matches(&current_state, i)).expect("No matching rule").output {
                new_state.insert(i as i64);
            }
        }

        if current_state.iter().map(|v| v + 1).collect::<HashSet<i64>>() == new_state {
            // Iterations are just shifting 1 to the right at this
            // point. Found by inspecting a debugging log of the
            // generations.

            let remaining_iterations = time-current_time;
            return current_state.iter().map(|v| v + remaining_iterations).collect::<HashSet<i64>>();
        }
        
        current_state = new_state;
    }
    current_state
}