SQL HowTo: «экспоненциальная» рекурсия (Advent of Code 2024, Day 7: Bridge Repair)09.01.2025 12:00

--- День 7: Ремонт моста ---

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

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

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

Например:

190: 10 19
3267: 81 40 27
83: 17 5
156: 15 6
7290: 6 8 6 15
161011: 16 10 13
192: 17 8 14
21037: 9 7 18 13
292: 11 6 16 20

Каждая строка представляет собой одно уравнение. Тестовое значение появляется перед двоеточием в каждой строке; ваша задача — определить, можно ли объединить оставшиеся числа с операторами для получения тестового значения.

Операторы всегда оцениваются слева направо, а не в соответствии с правилами приоритета. Более того, числа в уравнениях нельзя переставлять. Заглянув в джунгли, можно увидеть слонов, держащих два разных типа операторов: сложить (+) и умножить (*).

Только три из приведенных выше уравнений можно сделать истинными, вставив операторы:

190: 10 19имеет только одну позицию, которая принимает оператор: между 10и 19. Выбор +даст 29, но выбор *даст тестовое значение ( 10 * 19 = 190).
3267: 81 40 27имеет две позиции для операторов. Из четырех возможных конфигураций операторов, две заставляют правую сторону соответствовать тестовому значению: 81 + 40 * 27и 81 * 40 + 27обе равны 3267(при оценке слева направо)!
292: 11 6 16 20можно решить только одним способом: 11 + 6 * 16 + 20.

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

Определите, какие уравнения могли бы быть верными. Каков их общий результат калибровки?

--- Часть вторая ---

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

Оператор конкатенации (||) объединяет цифры из левого и правого входов в одно число. Например, 12 || 345станет 12345. Все операторы по-прежнему оцениваются слева направо.

Теперь, помимо трех уравнений, которые можно сделать истинными, используя только сложение и умножение, в приведенном выше примере есть еще три уравнения, которые можно сделать истинными, вставив операторы:

156: 15 6можно сделать истинным с помощью одной конкатенации: 15 || 6 = 156.
7290: 6 8 6 15можно сделать истинным, используя 6 * 8 || 6 * 15.
192: 17 8 14можно сделать истинным, используя 17 || 8 + 14.

Суммирование всех шести тестовых значений (трех, которые можно было получить ранее, используя только +, и *новых трех, которые теперь можно получить, также используя ||) дает новый общий результат калибровки 11387.

Используя ваши новые знания о местах укрытия слонов, определите, какие уравнения могут быть верными. Каков их общий результат калибровки?