23.12.2024 11:45
Kilor 0 356 Источник

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

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

В этой части с решением нам помогут логические агрегаты bool_and/bool_or.

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

Advent of Code 2024, Day 2: Red-Nosed Reports

--- День 2: Отчеты о красноносых ---

К счастью, первое место, которое хотят исследовать историки, находится недалеко от офиса главного историка.

В то время как завод ядерного синтеза/деления Red-Nosed Reindeer, похоже, не содержит никаких признаков Главного Историка, инженеры там подбегают к вам, как только видят вас. По-видимому, они все еще говорят о том времени, когда Рудольф был спасен с помощью молекулярного синтеза из одного электрона.

Они быстро добавляют, что — поскольку вы уже здесь — они были бы очень признательны за вашу помощь в анализе необычных данных с реактора Red-Nosed. Вы поворачиваетесь, чтобы проверить, ждут ли вас Историки, но они, похоже, уже разделились на группы, которые сейчас обыскивают каждый уголок объекта. Вы предлагаете помочь с необычными данными.

Необычные данные (ваш ввод головоломки) состоят из множества отчетов, по одному отчету на строку. Каждый отчет представляет собой список чисел, называемых уровнями, которые разделены пробелами. Например:

7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9

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

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

  • Уровни либо все увеличиваются, либо все уменьшаются.

  • Любые два соседних уровня отличаются не менее чем на один и не более чем на три.

В приведенном выше примере отчеты можно считать безопасными или небезопасными, проверив следующие правила:

  • 7 6 4 2 1: Безопасно, поскольку все уровни уменьшаются на 1 или 2.

  • 1 2 7 8 9: Небезопасно, так как 2 7увеличение составляет 5.

  • 9 7 6 2 1: Небезопасно, так как 6 2это уменьшение на 4.

  • 1 3 2 4 5: Небезопасно, так как 1 3увеличивается, но 3 2уменьшается.

  • 8 6 4 4 1: Небезопасно, так как 4 4не является ни увеличением, ни уменьшением.

  • 1 3 6 7 9: Безопасно, поскольку все уровни увеличиваются на 1, 2 или 3.

Итак, в этом примере 2отчета безопасны.

Проанализируйте необычные данные от инженеров. Сколько отчетов безопасны?

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

Инженеры удивлены малым количеством безопасных отчетов, пока не понимают, что забыли рассказать вам о демпфере проблем .

Problem Dampener — это модуль, устанавливаемый на реакторе, который позволяет системам безопасности реактора выдерживать один плохой уровень в том, что в противном случае было бы безопасным отчетом. Как будто плохой уровень никогда не был!

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

Больше отчетов из приведенного выше примера теперь безопасны:

  • 7 6 4 2 1: Безопасно без удаления какого-либо уровня.

  • 1 2 7 8 9: Небезопасно независимо от того, какой уровень удален.

  • 9 7 6 2 1: Небезопасно независимо от того, какой уровень удален.

  • 1 3 2 4 5: Безопасно, удалив второй уровень, 3.

  • 8 6 4 4 1: Безопасно, удалив третий уровень, 4.

  • 1 3 6 7 9: Безопасно без удаления какого-либо уровня.

Благодаря Problem Dampener 4отчета действительно безопасны!

Обновите свой анализ, обрабатывая ситуации, в которых Problem Dampener может удалить один уровень из небезопасных отчетов. Сколько отчетов теперь безопасны?

Часть 1

  1. В этот раз воспользуемся regexp_split_to_table и btrim, чтобы разбить ввод на все непустые строки.

  2. Каждую строку с помощью string_to_array превращаем в массив чисел.

  3. Для каждого массива перебираем индексы с 1 до предпоследнего и проверяем с выполнение условия "для каждого" агрегатной функцией bool_and.

  4. Остается подсчитать количество записей с подходящим условием.

SELECT
  count(*) FILTER(WHERE cond) -- количество с выполнившимся условием
FROM
  (
    SELECT
      string_to_array(line, ' ')::numeric[] rpt -- преобразуем строку в массив чисел
    FROM
      regexp_split_to_table($$
7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9
$$, '[\r\n]+') line -- разбиение по строкам
    WHERE
      btrim(line) <> '' -- фильтрация пустых строк
  ) T
, LATERAL (
    SELECT
      (
        bool_and(rpt[i] < rpt[i + 1]) OR -- все возрастают
        bool_and(rpt[i] > rpt[i + 1])    -- все убывают
      ) AND
      bool_and(abs(rpt[i] - rpt[i + 1]) BETWEEN 1 AND 3) cond -- все разницы между 1..3
    FROM
      generate_series(1, array_length(rpt, 1) - 1) i -- перебор без последнего элемента
  ) cond;

На все вычисления понадобилось всего 74мс:

Часть 2

  1. По условию, нас спрашивают, будет ли отчет безопасен при удалении лишь одного уровня - так давайте породим все эти возможные отчеты "без одного элемента" с помощью generate_subscripts и "склеивания слайсов".

  2. Для каждого такого отчета мы уже умеем вычислять условие, а для исходного получим его "по ИЛИ" - через bool_or.

SELECT
  count(*) FILTER(WHERE cond)
FROM
  (
    SELECT
      rptno
    , bool_or(cond) cond -- хоть один удовлетворяет условию?
    FROM
      (
        SELECT
          row_number() OVER() rptno -- нумеруем "исходные" отчеты
        , string_to_array(line, ' ')::numeric[] rpts
        FROM
          regexp_split_to_table($$
7 6 4 2 1
1 2 7 8 9
9 7 6 2 1
1 3 2 4 5
8 6 4 4 1
1 3 6 7 9
$$, '[\r\n]+') line
        WHERE
          btrim(line) <> ''
      ) T
    , LATERAL ( -- генерируем все возможные подотчеты
        SELECT
          rpts[:i-1] || rpts[i+1:] rpt   -- "клеим" массив до/после индекса
        FROM
          generate_subscripts(rpts, 1) i -- перебираем все индексы
      ) rptn
    , LATERAL (
        SELECT
          (
            bool_and(rpt[i] < rpt[i + 1]) OR
            bool_and(rpt[i] > rpt[i + 1])
          ) AND
          bool_and(abs(rpt[i] - rpt[i + 1]) BETWEEN 1 AND 3) cond
        FROM
          generate_series(1, array_length(rpt, 1) - 1) i
      ) cond
    GROUP BY
      1
  ) T;

Итоговый вариант работает около 155мс:

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