Advent of Code: задача 1.2

Фото: Kevin Utting (CC BY 2.0), кадрировано.
Решаю вторую часть первого дня Advent of Code. Задача продолжает первую часть первого дня.
Условие такое:
Вы замечаете, что устройство раз за разом повторяет один и тот же список изменений частоты. Чтобы откалибровать устройство, нужно найти первую частоту, которая встретится дважды.
Смотрим на решение из первой части:
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);
}
Задача кажется простой: надо всего лишь собирать результаты и найти первый повтор! Первая мысль — складывать их в массив и на каждой итерации проверять, есть ли там уже текущий результат. Но поиск по массиву — это O(n), и если итераций понадобится много, код начнёт тормозить. Хеш-таблица тут, пожалуй, лучше — доступ за O(1). Вот только в хеше к каждому ключу нужно хранить какое-то значение, а мне оно ни к чему. Значит, нужна коллекция с дешёвой вставкой и проверкой на вхождение. Посмотрим, что есть в стандартной библиотеке Rust: коллекции.
В Rust четыре основные категории коллекций:
- Последовательности:
Vec,VecDeque,LinkedList - Словари:
HashMap,BTreeMap - Множества:
HashSet,BTreeSet - Разное:
BinaryHeap
Документация вполне приличная и объясняет плюсы и минусы каждого типа…
Вам нужно просто запомнить, какие ключи вы уже видели.
С ключами не связано никакого осмысленного значения.
Вам просто нужно множество.
Похоже, ровно то, что мне нужно. Есть BTreeSet и HashSet. Мне кажется, у второго вставка дешевле, так что возьму его.
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
}
}
}
По сути всё то же самое, что и раньше, только теперь каждый результат добавляется в HashSet. Метод insert возвращает false, если значение уже есть в множестве.
Запускаю — и ничего не выводится.
Не может быть! Включаю отладочный вывод (по результату на строку) и сравниваю средствами шелла:
cargo run > nums.txt
wc -l nums.txt
989 nums.txt
uniq nums.txt > nums2.txt
wc -l nums2.txt
989 nums2.txt
Количество уникальных значений то же самое — повторов нет. Внимательно перечитываю условие и вижу то, что в первый раз пропустил:
Учтите, что устройству может понадобиться повторить свой список изменений частоты много раз, прежде чем найдётся повторяющаяся частота, и что повтор может обнаружиться посреди обработки списка.
Ясно. Значит, надо проходить по строкам снова и снова, пока не попадётся повторяющееся число. Но input.lines() возвращает структуру Lines, то есть итератор, а он, дойдя до конца последовательности, просто останавливается. Первой мыслью было превратить итератор в список и дальше по старинке крутить бесконечный цикл с ручной вознёй с индексами + break, как только значение найдено. Но, покопавшись в документации по итераторам, я нашёл способ зациклить итератор: std::iter::iterator#cycle. input.lines() возвращает структуру Lines, реализующую трейт Iterator. Судя по всему, это значит, что можно вызвать cycle() и бесконечно ходить по значениям по кругу.
Добавляю вызов .cycle() на 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
Отправляю ответ:
Это правильный ответ! Вы на одну золотую звезду ближе к починке потока времени.
Код запушен на GitHub.
Выводы
- Внимательно читайте условие :)
- Навыки работы в Unix-шелле всё ещё в цене
- Всё, что мне нужно знать об итераторах в Rust, — на одной странице