aboutsummaryrefslogtreecommitdiffstats
path: root/src/year_2018/day1.rs
blob: cd3d3231bb1137e5f6a798f1877047d97c1dac89 (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
112
113
//! --- Day 1: Chronal Calibration ---

use std::collections::BTreeSet;

#[derive(Debug)]
struct FrequencyChange {
    operation: FrequencyOperation,
    magnitude: i64,
}

#[derive(Debug)]
enum FrequencyOperation {
    Add,
    Subtract,
}

/// After feeling like you've been falling for a few minutes, you look at the device's tiny screen. "Error: Device must be calibrated before first use. Frequency drift detected. Cannot maintain destination lock." Below the message, the device shows a sequence of changes in frequency (your puzzle input). A value like +6 means the current frequency increases by 6; a value like -3 means the current frequency decreases by 3.
///
/// For example, if the device displays frequency changes of +1, -2, +3, +1, then starting from a frequency of zero, the following changes would occur:
///
///     Current frequency  0, change of +1; resulting frequency  1.
///     Current frequency  1, change of -2; resulting frequency -1.
///     Current frequency -1, change of +3; resulting frequency  2.
///     Current frequency  2, change of +1; resulting frequency  3.
///
/// In this example, the resulting frequency is 3.
///
/// Here are other example situations:
///
///     +1, +1, +1 results in  3
///     +1, +1, -2 results in  0
///     -1, -2, -3 results in -6
///
/// Starting with a frequency of zero, what is the resulting frequency after all of the changes in frequency have been applied?
pub fn part1() {
    let input = crate::common::read_stdin_to_string();
    let changes = build_changes(&input);

    let mut frequency: i64 = 0;
    for change in changes.iter() {
        frequency = match change.operation {
            FrequencyOperation::Add => frequency + change.magnitude,
            FrequencyOperation::Subtract => frequency - change.magnitude,
        }
    }

    println!("the resulting frequency: {}", frequency);
}

/// You notice that the device repeats the same frequency change list over and over. To calibrate the device, you need to find the first frequency it reaches twice.
///
/// For example, using the same list of changes above, the device would loop as follows:
///
///     Current frequency  0, change of +1; resulting frequency  1.
///     Current frequency  1, change of -2; resulting frequency -1.
///     Current frequency -1, change of +3; resulting frequency  2.
///     Current frequency  2, change of +1; resulting frequency  3.
///     (At this point, the device continues from the start of the list.)
///     Current frequency  3, change of +1; resulting frequency  4.
///     Current frequency  4, change of -2; resulting frequency  2, which has already been seen.
///
/// In this example, the first frequency reached twice is 2. Note that your device might need to repeat its list of frequency changes many times before a duplicate frequency is found, and that duplicates might be found while in the middle of processing the list.
///
/// Here are other examples:
///
///     +1, -1 first reaches 0 twice.
///     +3, +3, +4, -2, -4 first reaches 10 twice.
///     -6, +3, +8, +5, -6 first reaches 5 twice.
///     +7, +7, -2, -7, -4 first reaches 14 twice.
///
/// What is the first frequency your device reaches twice?
pub fn part2() {
    let input = crate::common::read_stdin_to_string();
    let changes = build_changes(&input);

    let mut frequency: i64 = 0;
    let mut frequency_seen: BTreeSet<i64> = BTreeSet::new();
    'find_duplicate: loop {
        for change in changes.iter() {
            frequency = match change.operation {
                FrequencyOperation::Add => frequency + change.magnitude,
                FrequencyOperation::Subtract => frequency - change.magnitude,
            };
            if frequency_seen.contains(&frequency) {
                break 'find_duplicate;
            }
            frequency_seen.insert(frequency);
        }
    }

    println!("the first duplicate resulting frequency: {}", frequency);
}

fn build_changes(input: &str) -> Vec<FrequencyChange> {
    let mut changes = Vec::new();

    for line in input.lines() {
        changes.push(FrequencyChange {
            operation: match line.chars().next() {
                Some('+') => FrequencyOperation::Add,
                Some('-') => FrequencyOperation::Subtract,
                Some(not_found) => panic!("Unhandled operation: '{}'", not_found),
                None => panic!(),
            },
            magnitude: line
                .trim_start_matches(|c| c == '+' || c == '-')
                .parse()
                .unwrap_or_else(|_| panic!("parsing frequency change magnitude '{}'", line)),
        })
    }

    changes
}