В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
В этой части совсем простая идея по одновременному решению систем линейных уравнений «пачками».
-
Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)
-
Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка «пузырьком»)
-
Решение Day 6: Guard Gallivant (рекурсивные циклы и их контроль)
-
Решение Day 8: Resonant Collinearity (генерация и подсчет уникальных комбинаций)
-
Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)
-
Решение Day 12: Garden Groups (волновой алгоритм и подсчет границ)
Оригинальная постановка задачи и ее перевод:
Advent of Code 2024, Day 13: Claw Contraption
— День 13: Устройство для когтей —
Далее: вестибюль курорта на тропическом острове. Историки на мгновение останавливаются, чтобы полюбоваться шестиугольными плитками пола, прежде чем разойтись.
К счастью, похоже, на курорте есть новый игровой зал! Может быть, вы сможете выиграть призы в игровых автоматах?
Игровые автоматы здесь немного необычны. Вместо джойстика или кнопок направления для управления когтем, эти автоматы имеют две кнопки с надписями Aи B. Хуже того, вы не можете просто вставить жетон и играть; нажатие кнопки стоит 3 жетонаA и 1 жетон для нажатия Bкнопки.
Проведя немного экспериментов, вы понимаете, что кнопки каждого аппарата настроены на перемещение захвата на определенную величину вправо ( вдоль Xоси) и на определенную величину вперед (вдоль Yоси) при каждом нажатии этой кнопки.
В каждом автомате находится один приз; чтобы выиграть приз, захват должен быть расположен точно над призом на обеих осях Xи Y.
Вы задаетесь вопросом: какое наименьшее количество жетонов вам придется потратить, чтобы выиграть как можно больше призов? Вы составляете список поведения кнопок каждого автомата и местонахождения призов (ваш ввод головоломки). Например:
Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176 Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=7870, Y=6450 Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=18641, Y=10279В этом списке описывается конфигурация кнопок и расположение призов четырех различных игровых автоматов.
А пока рассмотрим только первый в списке игрушку-когтевой автомат:
-
Нажатие кнопки
Aприводит к перемещению захвата на94узла вдоль осиXи на34узлов вдоль осиY. -
Нажатие кнопки
Bприведет к перемещению захвата на22узла вдоль осиXи на67узлов вдоль осиY. -
Приз находится в
X=8400,Y=5400; это означает, что из начального положения захвата ему необходимо будет переместиться ровно на8400единиц вдоль осиXи ровно на5400единиц вдоль осиY, чтобы идеально совпасть с призом в этом автомате.
Самый дешевый способ выиграть приз — нажать Aкнопку 80раз и Bкнопку 40раз. Это переместит клешню на 8400 по X (потому что 80*94 + 40*22 = 8400) и на 5400 по Y (потому что 80*34 + 40*67 = 5400). Это будет стоить 80*3жетонов за Aнажатия и 40*1за Bнажатия, всего 280жетонов.
Для машин со вторым и четвертым захватом не существует комбинации нажатий клавиш A и B, которая когда-либо выиграет приз.
Для третьего автомата-клешня самый дешевый способ выиграть приз — нажать Aкнопку 38раз и Bкнопку 86раз. Это обойдется в общую сумму 200жетонов.
Таким образом, максимальное количество призов, которые вы можете выиграть, равно двум; минимальное количество токенов, которое вам придется потратить, чтобы выиграть все (два) приза, составляет 480.
Вы оцениваете, что каждую кнопку нужно будет нажать не более 100раз, чтобы выиграть приз. Как еще можно было бы ожидать, что кто-то будет играть?
Придумайте, как выиграть как можно больше призов. Какое наименьшее количество жетонов вам придется потратить, чтобы выиграть все возможные призы?
— Часть вторая —
Когда вы идете за первым призом, вы обнаруживаете, что коготь находится совсем не там, где вы ожидали. Из-за ошибки преобразования единиц в ваших измерениях положение каждого приза на самом деле 10000000000000выше как по оси, так Xи Yпо оси!
Добавьте 10000000000000к Xи Yпозиции каждого приза. После внесения этого изменения пример выше будет выглядеть так:
Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=10000000008400, Y=10000000005400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=10000000012748, Y=10000000012176 Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=10000000007870, Y=10000000006450 Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=10000000018641, Y=10000000010279Теперь выиграть приз можно только на машинах второго и четвертого когтя. К сожалению, для этого понадобится гораздо больше, чем просто 100нажатий .
Используя исправленные координаты призов, выясните, как выиграть как можно больше призов. Какое наименьшее количество жетонов вам придется потратить, чтобы выиграть все возможные призы?
Часть 1
Путь решения практически в явном виде указан в самой постановке задачи. Перепишем известное нам на примере первого автомата:
94 * A + 22 * B = 8400 (по X) 34 * A + 67 * B = 5400 (по Y)Это ни что иное, как простейшая система линейных уравнений. Решить ее можно, например, так:
1. домножим оба выражения на коэффициенты при A в другом выражении: 3196 * A + 748 * B = 285600 (x 34) 3196 * A + 6298 * B = 507600 (x 94) Очевидно, при этом коэффициенты при A уравняются. 2. Вычтем из второго выражения первое и найдем коэффициент для B: 5550 * B = 222000 B = 222000 / 5550 B = 40 3. Подставим значение B в первое исходное выражение и найдем A: 94 * A + 22 * 40 = 8400 94 * A = 8400 - 880 94 * A = 7520 A = 80 4. Вычислим необходимое количество монет: 3 * A + B = 280Заметим, что решение этой системы должно быть достигнуто в целых числах, ведь нельзя нажать на кнопку «полразика». Рассмотрим на примере второго автомата:
26 * A + 67 * B = 12748 66 * A + 21 * B = 12176 1716 * A + 4422 * B = 841368 1716 * A + 546 * B = 316576 -3876 * B = -524792 (в отрицательных коэффициентах нет ничего страшного) B = 524792 / 3876 B = 135 + 1532 / 3876 (а вот этот остаток от деления нам все портит)То есть при наличии вот этого остатка от деления (если значения для A и B не делятся нацело), система не имеет решения в целых числах, и приз на таком автомате недостижим.
Теперь выразим наше решение на SQL — каждому автомату соответствует одна строка:
SELECT * FROM ( -- разбираем исходные данные в bigint SELECT m::bigint[] FROM regexp_matches($$ Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176 Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=7870, Y=6450 Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=18641, Y=10279 $$ , 'Button A: X\+(\d+), Y\+(\d+)[\r\n]+Button B: X\+(\d+), Y\+(\d+)[\r\n]+Prize: X=(\d+), Y=(\d+)' , 'g' ) m ) src , LATERAL ( SELECT m[1] a1 , m[3] b1 , m[5] r1 , m[2] a2 , m[4] b2 , m[6] r2 ) step0a1 | b1 | r1 | a2 | b2 | r2 94 | 22 | 8400 | 34 | 67 | 5400 26 | 67 | 12748 | 66 | 21 | 12176 17 | 84 | 7870 | 86 | 37 | 6450 69 | 27 | 18641 | 23 | 71 | 10279, LATERAL ( -- домножаем на коэффициенты при A SELECT b1 * a2 b1_1 , r1 * a2 r1_1 , b2 * a1 b2_1 , r2 * a1 r2_1 ) step1a1 | b1 | r1 | a2 | b2 | r2 | b1_1 | r1_1 | b2_1 | r2_1 94 | 22 | 8400 | 34 | 67 | 5400 | 748 | 285600 | 6298 | 507600 26 | 67 | 12748 | 66 | 21 | 12176 | 4422 | 841368 | 546 | 316576 17 | 84 | 7870 | 86 | 37 | 6450 | 7224 | 676820 | 629 | 109650 69 | 27 | 18641 | 23 | 71 | 10279 | 621 | 428743 | 4899 | 709251, LATERAL ( -- находим коэффициент при B и остаток SELECT abs(r2_1 - r1_1) / abs(b2_1 - b1_1) b , abs(r2_1 - r1_1) % abs(b2_1 - b1_1) br ) step2a1 | b1 | r1 | a2 | b2 | r2 | b1_1 | r1_1 | b2_1 | r2_1 | b | br 94 | 22 | 8400 | 34 | 67 | 5400 | 748 | 285600 | 6298 | 507600 | 40 | 0 26 | 67 | 12748 | 66 | 21 | 12176 | 4422 | 841368 | 546 | 316576 | 135 | 1532 17 | 84 | 7870 | 86 | 37 | 6450 | 7224 | 676820 | 629 | 109650 | 86 | 0 69 | 27 | 18641 | 23 | 71 | 10279 | 621 | 428743 | 4899 | 709251 | 65 | 2438, LATERAL ( -- находим коэффициент при A и остаток SELECT (r1 - b1 * b) / a1 a , (r1 - b1 * b) % a1 ar ) step3a1 | b1 | r1 | a2 | b2 | r2 | b1_1 | r1_1 | b2_1 | r2_1 | b | br | a | ar 94 | 22 | 8400 | 34 | 67 | 5400 | 748 | 285600 | 6298 | 507600 | 40 | 0 | 80 | 0 26 | 67 | 12748 | 66 | 21 | 12176 | 4422 | 841368 | 546 | 316576 | 135 | 1532 | 142 | 11 17 | 84 | 7870 | 86 | 37 | 6450 | 7224 | 676820 | 629 | 109650 | 86 | 0 | 38 | 0 69 | 27 | 18641 | 23 | 71 | 10279 | 621 | 428743 | 4899 | 709251 | 65 | 2438 | 244 | 50Осталось вычислить количество монет только для тех автоматов, где решение нашлось — то есть остатки br и ar нулевые:
SELECT sum(3 * a + b) FROM ( -- разбираем исходные данные SELECT m::bigint[] FROM regexp_matches($$ Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176 Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=7870, Y=6450 Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=18641, Y=10279 $$ , 'Button A: X\+(\d+), Y\+(\d+)[\r\n]+Button B: X\+(\d+), Y\+(\d+)[\r\n]+Prize: X=(\d+), Y=(\d+)' , 'g' ) m ) src , LATERAL ( SELECT m[1] a1 , m[3] b1 , m[5] r1 , m[2] a2 , m[4] b2 , m[6] r2 ) step0 , LATERAL ( -- домножаем на коэффициенты при A SELECT b1 * a2 b1_1 , r1 * a2 r1_1 , b2 * a1 b2_1 , r2 * a1 r2_1 ) step1 , LATERAL ( -- находим коэффициент при B и остаток SELECT abs(r2_1 - r1_1) / abs(b2_1 - b1_1) b , abs(r2_1 - r1_1) % abs(b2_1 - b1_1) br ) step2 , LATERAL ( -- находим коэффициент при A и остаток SELECT (r1 - b1 * b) / a1 a , (r1 - b1 * b) % a1 ar ) step3 WHERE (ar, br) = (0, 0);Часть 2
Во второй части к координатам призов предлагается добавить 10 триллионов — явно, чтобы исключить возможность решения моделированием. Но на нашем аналитическом решении это усложнение почти никак не сказывается, поскольку значения по-прежнему укладываются в диапазон bigint:
SELECT sum(3 * a + b) FROM ( SELECT m::bigint[] FROM regexp_matches($$ Button A: X+94, Y+34 Button B: X+22, Y+67 Prize: X=8400, Y=5400 Button A: X+26, Y+66 Button B: X+67, Y+21 Prize: X=12748, Y=12176 Button A: X+17, Y+86 Button B: X+84, Y+37 Prize: X=7870, Y=6450 Button A: X+69, Y+23 Button B: X+27, Y+71 Prize: X=18641, Y=10279 $$ , 'Button A: X\+(\d+), Y\+(\d+)[\r\n]+Button B: X\+(\d+), Y\+(\d+)[\r\n]+Prize: X=(\d+), Y=(\d+)' , 'g' ) m ) src , LATERAL ( SELECT m[1] a1 , m[3] b1 , m[5] + 10000000000000 r1 -- новые координаты призов , m[2] a2 , m[4] b2 , m[6] + 10000000000000 r2 ) step0 , LATERAL ( SELECT b1 * a2 b1_1 , r1 * a2 r1_1 , b2 * a1 b2_1 , r2 * a1 r2_1 ) step1 , LATERAL ( SELECT abs(r2_1 - r1_1) / abs(b2_1 - b1_1) b , abs(r2_1 - r1_1) % abs(b2_1 - b1_1) br ) step2 , LATERAL ( SELECT (r1 - b1 * b) / a1 a , (r1 - b1 * b) % a1 ar ) step3 WHERE (ar, br) = (0, 0);
ссылка на оригинал статьи https://habr.com/ru/articles/876852/
Добавить комментарий