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.
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:
- Sequences:
Vec,VecDeque,LinkedList - Maps:
HashMap,BTreeMap - Sets:
HashSet,BTreeSet - Misc:
BinaryHeap
The documentation is pretty nice and explains pros and cons of each type...
Use theSetvariant of any of theseMaps 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
}
}
}
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
That's the right answer! You are one gold star closer to fixing the time stream.
Findings
- Read requirements carefully :)
- Unix shell skills are still relevant
- Everything I need to know about iterators in rust on one page