Идет седьмой день Пришествия Кода, и мы анализируем вывод терминала нашего устройства системы связи. Я призываю вас сначала решить ее самостоятельно. https://adventofcode.com

Вход

Наш ввод — это текст с терминала. Поэтому наша первая цель — понять это и преобразовать в удобный формат.

Первое наблюдение заключается в том, что вывод команды $ ls — это то, что мы хотим сохранить как информацию о каталоге. Другая часть необходимой нам информации — это команды $ cd somewhere, которые сообщают нам, какие из $ ls выходных данных принадлежат каким каталогам. Итак, наконец, нам нужна структура данных для хранения этой информации.

Tree хранит все данные, что позволяет нам использовать необработанные (не принадлежащие) указатели в остальной части структуры данных. Эти указатели будут действительны до тех пор, пока экземпляр Tree, который их выдал, жив.

Как уже упоминалось, вывод $ ls будет храниться в Directory, поэтому мы можем реализовать его с помощью оператора извлечения потока. Помимо этого, нам понадобится закрывающая функция, которая вернет проанализированный экземпляр Tree и реализацию обхода для команды $ cd.

Мы полагаемся на метод std::istream::peek для определения конца вывода $ ls и конца файла и различения каталогов и файлов в выводе $ ls.

Мы читаем каждую команду и действуем соответственно, пропуская информацию о каталоге в выводе $ ls, поскольку каталог актуален только после того, как мы $ cd вошли в него.

Суммирование размеров небольших каталогов

В первой части перед нами стоит задача обработать проанализированную информацию и просуммировать размеры небольших каталогов.

Чтобы облегчить это, нам сначала нужно добавить способ вычисления рекурсивного размера каталога и быстрого выполнения повторных вызовов, и мы будем кэшировать вычисленное значение.

Собрав это вместе, все, что нам нужно, это рекурсивная сумма, которая пропускает каталоги выше порога.

Обратите внимание, что std::reduce пустого диапазона равно 0, поэтому локальная сумма всегда правильно инициализируется.

Наименьший каталог, который является достаточно большим

Во второй части перед нами стоит задача определить (по размеру) наименьший каталог, превышающий заданный порог.

Мы можем использовать тот же подход, что и в первой части, за исключением того, что теперь нам нужно фильтровать.

Обратите внимание, что нам не нужно проверять, находится ли наш текущий каталог в пределах порога, так как он будет отфильтрован на один уровень выше.

Ссылки

Репозиторий с полным решением (включая парсинг ввода) доступен здесь: https://github.com/HappyCerberus/moderncpp-aoc-2022.

Я ежедневно размещаю контент на современном C++ в Twitter, LinkedIn, Mastodon, Medium и Substack.