01.12.2025 11:47
Kilor 0 3500 Источник

Сегодня стартовал Advent of Code 2025!

Осторожно, спойлеры! Не читайте, пока хотите решить задачу самостоятельно.

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

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

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

Advent of Code 2025, Day 1: Secret Entrance

--- День 1: Секретный вход ---

У эльфов есть хорошие и плохие новости.

Хорошая новость в том, что они открыли для себя управление проектами! Это дало им инструменты, необходимые для предотвращения обычных рождественских чрезвычайных ситуаций. Например, теперь они знают, что украшение Северного полюса нужно закончить как можно скорее, чтобы успеть начать другие важные задачи.

Плохая новость в том, что они поняли, что у них другая чрезвычайная ситуация: согласно их плану ресурсов, ни у кого из них не осталось времени на украшение Северного полюса!

Чтобы спасти Рождество, эльфам нужно, чтобы вы закончили украшать Северный полюс к 12 декабря.

Собирайте звёзды, решая головоломки. Каждый день будут доступны две головоломки; вторая откроется после решения первой. Каждая головоломка даёт одну звезду. Удачи!

Вы прибываете к секретному входу на базу «Северный полюс», готовые начать украшать её. К сожалению, пароль, похоже, сменился, так что попасть внутрь невозможно. Документ, приклеенный к стене, услужливо объясняет:

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

Сейф оснащён циферблатом, на котором изображена только стрелка; по кругу расположены числа от 0 до 99 по порядку. При повороте циферблата раздаётся тихий щелчок при достижении каждой цифры.

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

Итак, если циферблат был направлен на 11, поворот на R8приведёт к тому, что циферблат будет направлен на 19. После этого поворот на L19приведёт к тому, что циферблат будет направлен на 0.

Поскольку циферблат имеет форму круга, поворот циферблата влево от0 о на один щелчок приведёт к тому, что он укажет на 99. Аналогично, поворот циферблата вправо от99 на один щелчок приведёт к тому, что он укажет на 0.

Итак, если циферблат был направлен на 5, поворот на L10приведёт к тому, что он укажет на 95. После этого поворот на R5может привести к тому, что он укажет на 0.

Циферблат начинается с указания на 50.

Вы могли бы следовать инструкциям, но на недавнем обязательном официальном обучающем семинаре по безопасности секретного входа на Северный полюс вас убедили, что сейф на самом деле — обманка. Настоящий пароль — это количество раз, когда диск остаётся в положении 0после любого поворота в последовательности.

Например, предположим, что прикрепленный документ содержит следующие повороты:

L68
L30
R48
L5
R60
L55
L1
L99
R14
L82

После этих поворотов циферблат будет двигаться следующим образом:

  • циферблат установлен на 50

  • поворачиваем L68- теперь указывает на 82

  • поворачиваем L30- теперь указывает на 52

  • поворачиваем R48- теперь указывает на 0

  • поворачиваем L5- теперь указывает на 95

  • поворачиваем R60- теперь указывает на 55

  • поворачиваем L55- теперь указывает на 0

  • поворачиваем L1- теперь указывает на 99

  • поворачиваем L99- теперь указывает на 0

  • поворачиваем R14- теперь указывает на 14

  • поворачиваем L82- теперь указывает на 32

Поскольку в ходе этого процесса циферблат указывает на 0всего три раза, пароль в этом примере — 3.

Проанализируйте повороты в приложенном документе. Какой на самом деле пароль для открытия двери?

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

Ты уверен, что это правильный пароль, но дверь не открывается. Ты стучишь, но никто не отвечает. Ты лепишь снеговика, пока думаешь.

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

В связи с новыми протоколами безопасности, пожалуйста, используйте метод пароля 0x434C49434B до дальнейшего уведомления.

Вы помните из обучающего семинара, что «метод 0x434C49434B» означает, что на самом деле вам нужно подсчитать, сколько раз любой щелчок заставляет циферблат указывать на 0, независимо от того, происходит ли это во время вращения или в конце него.

После тех же поворотов, что и в примере выше, циферблат указывает на ноль еще несколько раз во время поворотов:

  • циферблат установлен на 50

  • поворачиваем L68- теперь указывает на 82; во время поворота происходит проход через 0

  • поворачиваем L30- теперь указывает на 52

  • поворачиваем R48- теперь указывает на 0

  • поворачиваем L5- теперь указывает на 95

  • поворачиваем R60- теперь указывает на 55; во время поворота происходит проход через 0

  • поворачиваем L55- теперь указывает на 0

  • поворачиваем L1- теперь указывает на 99

  • поворачиваем L99- теперь указывает на 0

  • поворачиваем R14- теперь указывает на 14

  • поворачиваем L82- теперь указывает на 32; во время поворота происходит проход через 0

В этом примере стрелка циферблата указывает на 03 раза в конце поворота, а также ещё 3 раза в ходе поворота. Таким образом, в этом примере новый пароль будет 6.

Будьте осторожны: если бы циферблат указывал на 50, один поворот R1000заставил бы циферблат указывать на 010 раз, прежде чем вернуться в положение 50!

Используя метод пароля 0x434C49434B, какой пароль поможет открыть дверь?

Часть 1

Представим, что у нас не "зацикленный" по кругу циферблат, а вся числовая ось, тогда каждый шаг перемещает нас по ней влево или вправо, а условие "указывает на 0" превращается в "делится на 100".

Для решения нам понадобится выполнить несколько действий:

  1. с помощью регулярных выражений разбираем ввод и нумеруем строки с помощью WITH ORDINALITY - нумерация будет с 1

  2. добавляем в начало выборки "нулевой" шаг с исходным состоянием 50

  3. с помощью оконной функции суммирования вычисляем накопительный итог после каждого шага - текущую позицию циферблата

  4. подсчитываем количество позиций кратных 100

SELECT
  count(*) FILTER(WHERE dst % 100 = 0) -- подсчет по условию кратности 100
FROM
  (
    SELECT
      sum(step) OVER(ORDER BY i) dst -- суммирование с накопительным итогом
    FROM
      (
          SELECT
            0 i
          , 50 step -- исходное положение циферблата
        UNION ALL
          SELECT
            i
          , CASE step[1]
              WHEN 'R' THEN +step[2]::bigint -- поворот направо
              WHEN 'L' THEN -step[2]::bigint -- поворот налево
            END step
          FROM
            regexp_matches($$
L68
L30
R48
L5
R60
L55
L1
L99
R14
L82
$$, '(L|R)(\d+)', 'g')
              WITH ORDINALITY T(step, i)
      ) T
  ) T;

Часть 2

Во второй части вопрос сложнее - сколько всего проходов через 0 циферблата было.

Теперь решение станет чуть сложнее:

  1. вынесем вычисление позиций в отдельную CTE

  2. составим с помощью оконной функции lag возьмем предыдущую позицию циферблата, чтобы собрать пары "откуда"-"куда" (src, dst) мы крутили

  3. в этом случае количество проходов через ноль будет равно разности округленных вниз количества полных сотен в номерах позиций, когда мы вращаем вправо

    * не забываем привести src/dst к double precision, иначе при целочисленном делении на 100, что 50, что -50 дадут одно и то же значение 0

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

WITH clock AS (
  SELECT
    *
  , sum(step) OVER(ORDER BY i)::bigint dst
  FROM
    (
      SELECT
        0 i
      , 50 step
    UNION ALL
      SELECT
         i
      , CASE step[1]
          WHEN 'R' THEN +step[2]::bigint
          WHEN 'L' THEN -step[2]::bigint
        END step
      FROM
        regexp_matches($$
L68
L30
R48
L5
R60
L55
L1
L99
R14
L82
$$, '(L|R)(\d+)', 'g')
          WITH ORDINALITY T(step, i)
    ) T
)
SELECT
  sum(
    abs((floor(dst::double precision / 100) - floor(src::double precision / 100))::bigint) + -- количество переходов через 0
      (dst < src)::integer * ((dst % 100 = 0)::integer - (src % 100 = 0)::integer) -- учет "нулей" при повороте влево
  )
FROM
  (
    SELECT
      (lag(dst) OVER(ORDER BY i))::bigint src -- предыдущая позиция
    , dst
    FROM
      clock
  ) T;

Собственно, и все!

Комментарии (0)