Advent of code: Puzzle 1.2

by Anton Vasiljev
Advent of code: Puzzle 1.2

Photo by Kevin Utting (CC BY 2.0) Cropped.


Solving part 2 of day 1 in advent of code challenge. Puzzle is based on day 1 part 1.

The task is:

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.

So taking a look to solution from part one:

fn main() {
    let input = read_puzzle_input(1);
    let mut result: i32 = 0;

    for line in input.lines() {
        let num = line.parse::<i32>().unwrap();
        result += num;
    }

    println!("{}", result);
}

The task looks like easy one: i just need to collect results and find first duplicate! First idea is to use array and then check wherever it includes current result on each iteration. But arrays search complexity is O(n) and it will slow down the code when i'll need too many iterations. Hash might be better here with O(1) access complexity. However hash should keep some kind of value which is not required for my task. So i need some kind of collection with inexpensive inserts and inclusion checks. Let's see what rust provide in standard library: collections.

Rust has 4 major categories of collections:

The documentation is pretty nice and explains pros and cons of each type...

Use the Set variant of any of these Maps when:
You just want to remember which keys you've seen.
There is no meaningful value to associate with your keys.
You just want a set.

Looks like exactly what i need. There is an BTreeSet and a HashSet. I believe second is cheaper for inserts so i'll use it.

fn part_two() {
    let input = read_puzzle_input(1);
    let mut result: i32 = 0;
    let mut seen_freqs: HashSet<i32> = HashSet::new();

    seen_freqs.insert(result);

    for line in input.lines() {
        let num = line.parse::<i32>().unwrap();
        result += num;

        if !seen_freqs.insert(result) {
            println!("Repeating frequency: {}", result);
            break
        }
    }
}

Basically doing the same work as before but this time inserting each result to HashSet. Insert method returns boolean false if value is already in set.

Running this and getting no output.

I cant believe! Getting debug output (one result per line) and comparing using shell tools:

cargo run > nums.txt
wc -l nums.txt
989 nums.txt
uniq nums.txt > nums2.txt
wc -l nums2.txt
989 nums2.txt

Looks like the same number of unique values: no duplicates. Carefully rereading the task and seeing something i had missed first time:

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.

Okay. It means I must iterate over lines again and wait for repeating number. But input.lines() returns Lines struct which is iterator so when it reach the end of sequence it will stop. First idea was to convert iterator to list and then use old good endless loop with index manipulation + break the loop once value found. However after digging in iterator docs i found a way to restart iterator: std::iter::iterator#cycle. input.lines() returns Lines struct which implements Iterator Trait. This fact probably means i can use cycle() to endlessly iterate over some values.

Adding .cycle() call on Lines:

fn part_two() {
    let input = read_puzzle_input(1);
    let mut result: i32 = 0;
    let mut seen_freqs: HashSet<i32> = HashSet::new();

    seen_freqs.insert(result);

    for line in input.lines().cycle() {
        let num = line.parse::<i32>().unwrap();
        result += num;

        if !seen_freqs.insert(result) {
            println!("Repeating frequency: {}", result);
            break
        }
    }
}

Running the code:

cargo run
   Compiling aoc2018 v0.1.0 (file:///Users/antono/Code/rust/aoc2018)
    Finished dev [unoptimized + debuginfo] target(s) in 0.62 secs
     Running `target/debug/1`
Sum of freq adjustments: 493
Repeating frequency: 413

Submitting result:

That's the right answer! You are one gold star closer to fixing the time stream.

Code pushed to GitHub.


Findings


Disclaimer

December 9, 2018
by Anton Vasiljev
rust
aoc