Сегодня двадцать первый день Advent of Code, и мы пытаемся угадать, что задумали обезьяны. Я призываю вас сначала попробовать решить ее самостоятельно https://adventofcode.com.

Вход

Наши входные данные сегодня — это список обезьян, где каждая обезьяна либо сообщает целочисленное значение, либо вычисляет выражение, основанное на значениях других обезьян. Поскольку в любом случае нас интересует конечное значение, мы спрячем это различие внутри класса Monkey, используя класс std::variant. Затем мы принимаем ввод как std::unordered_map<std::string, Monkey>, так как нам нужно будет искать обезьян по их именам.

Расчет

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

Поскольку у нас уже есть карта поиска с обезьянами, мы можем дать каждой обезьяне указатель на нее; однако более чистое решение состоит в том, чтобы дать каждой обезьяне функцию запроса, которая берет имя обезьяны и возвращает значение (эта дополнительная сложность пригодится во второй части).

Что за магическое число?

Во второй части у нас есть более сложная цель. Вместо того, чтобы “humn” быть обезьяной, это мы, и нам нужно придумать число, которое заставит корневую обезьяну получить одинаковые операнды.

Прежде чем мы начнем решать, нам нужны две вещи.

Во-первых, нам нужно настроить логику для корневой обезьяны (мы можем изменить ее на минус, чтобы она выдавала ноль, когда операнды совпадают).

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

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

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

Ссылки

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

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