Advent of Code: задача 1.2

· обновлено · #rust

Фото: 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 четыре основные категории коллекций:

Документация вполне приличная и объясняет плюсы и минусы каждого типа…

Используйте Set-вариант любого из этих Map, когда:

Вам нужно просто запомнить, какие ключи вы уже видели.

С ключами не связано никакого осмысленного значения.

Вам просто нужно множество.

Похоже, ровно то, что мне нужно. Есть 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.


Выводы


Дисклеймер