Да, я знаю, что в заголовках моих постов есть ошибки.

В своей последней статье я посетовал, что работа над проектом застопорилась. Что ж, написание этого поста было толчком, который мне был нужен, чтобы снова сесть на лошадь или, так сказать, на верблюда. И вот, через несколько дней я решил 14-й день Advent of Code, и более того: мне это понравилось. (и тогда, конечно, мне потребовалось два месяца, чтобы опубликовать эту статью).

Две причины для этого: лучшие инструменты и забавная проблема.

Лучшие инструменты

По причинам, связанным с работой, я недавно потратил некоторое время на то, чтобы WSL стал меньше отстойным. Я настроил некоторые базовые вещи, установил или обновил некоторые пакеты, подправил некоторые настройки. Я стиснул зубы и узнал о .vimrc. Результат: мой WSL теперь представляет собой пригодную для использования оболочку Linux.

Попутно я установил opam, и это открыло несколько крутых инструментов OCaml: merlin для автодополнения и utop для лучшего REPL. Важно отметить, что с помощью простого opam switch 4.10.0 я перешел на последнюю версию Ocaml, оставив немного устаревшую версию Ubuntu 4.05. Это дало мне доступ к языковой функции (to_seq), которую я хотел использовать для решения проблемы. Итак, большой шаг вперед в отделе инструментов.

У меня до сих пор нет приличной IDE для OCaml, но я уже привык к vim; Стокгольмский синдром, наверное.

Веселая проблема

День 14 звучит подозрительно легко, когда вы впервые читаете его. Вам предоставляется список реакций, которые представляют собой рецепты для создания химических соединений из различных исходных химических веществ. Все химические вещества в конечном итоге могут быть получены из исходного сырья, называемого «РУДА». Учитывая все это, вас спрашивают, сколько входов «РУДА» требуется для производства одного выхода «ТОПЛИВО».

Просто, верно? Вы неоднократно заменяете каждое химическое вещество его входными компонентами, пока не останется только РУДА. Хитрость заключается в порядке выполнения замен: если вы сделаете это неправильно, вы в конечном итоге будете использовать больше ORE, чем необходимо. Чтобы получить правильное количество, вы должны заменить каждое химическое вещество ровно один раз.

Короче говоря, это требует выполнения топологической сортировки на ориентированном ациклическом графе. (Причудливые термины, правда? Полдела было найти какие слова в гугле. Я их выучил, когда решал эту задачу, так что не корите себя). Эта отличная статья охватывает теорию и дает не один, а два алгоритма топологической сортировки!

Оттуда легко закодировать решение.

Я не особо увлекался структурами данных; все решение вылеплено из хеш-таблиц. Конечно, есть более элегантный способ построения и обхода DAG, но я не смог придумать ни одного. Это нормально. Хеш-таблицы не осуждают вас, когда вы пишете уродливый код. Они просто рады помочь.

К моему изумлению, мой код сразу дал правильный ответ. Ну, после того, как я исправил все синтаксические ошибки, разумеется. Так что считайте это чистой победой командного проекта! День 15 требует интерпретации нажатий на клавиатуру, это будет целая «червячная банка», с которой нужно справиться.

Приложение

К тому времени, когда я написал черновик для этого поста и публикации, я решил первую часть дня 15. Решение было не таким сложным, как могло бы быть, но будет время улучшить подпрограммы ввода-вывода, если я закончу повторное использование их для другой проблемы.