SQL HowTo: пошагово решаем СЛУ (Advent of Code 2024, Day 13: Claw Contraption) / Хабр

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.

В этой части совсем простая идея по одновременному решению систем линейных уравнений "пачками".

Оригинальная постановка задачи и ее перевод:

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
  ) step0

a1 | 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
  ) step1

a1 | 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
  ) step2

a1 | 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
  ) step3

a1 | 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);

SQL HowTo: пошагово решаем СЛУ (Advent of Code 2024, Day 13: Claw Contraption)

--- День 13: Устройство д��я когтей ---

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

Часть 1

Часть 2

Публикации

Информация