23.12.2024 11:01
Kilor 0 420 Источник

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

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

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

Advent of Code 2024, Day 1: Historian Hysteria

--- День 1: Истерия историка ---

...

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

Есть только одна проблема: если держать два списка рядом (ваш пазл), то быстро становится ясно, что списки не очень похожи. Может быть, вы можете помочь Историкам согласовать их списки?

Например:

3   4
4   3
2   5
1   3
3   9
3   3

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

В каждой паре выясните, насколько далеко друг от друга находятся два числа; вам нужно будет сложить все эти расстояния. Например, если вы соедините 3из левого списка с 7из правого списка, расстояние между ними будет 4; если вы соедините 9с 3, расстояние между ними будет 6.

В приведенном выше примере списка пары и расстояния будут следующими:

  • Наименьшее число в левом списке — 1, а наименьшее число в правом списке — 3. Расстояние между ними — 2.

  • Второе наименьшее число в левом списке — 2, а второе наименьшее число в правом списке — еще одно 3. Расстояние между ними — 1.

  • Третье наименьшее число в обоих списках — 3, поэтому расстояние между ними — 0.

  • Следующие числа, которые нужно объединить в пары, — это 3и 4, на расстоянии 1.

  • Пятыми по величине числами в каждом списке являются 3и 5, расстояние между которыми равно 2.

  • Наконец, наибольшее число в левом списке — 4, а наибольшее число в правом списке — 9; они находятся на расстоянии 5друг от друга.

Чтобы найти общее расстояние между левым списком и правым списком, сложите расстояния между всеми найденными вами парами. В примере выше это , 2 + 1 + 0 + 1 + 2 + 5общее расстояние 11!

Ваши фактические левые и правые списки содержат много идентификаторов местоположений. Каково общее расстояние между вашими списками?

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

Ваш анализ только подтвердил то, чего все опасались: два списка идентификаторов местоположений действительно сильно различаются.

Или нет?

Историки не могут прийти к единому мнению о том, какая группа допустила ошибки или как читать большую часть почерка Шефа, но в суматохе вы замечаете интересную деталь: в обоих списках появляется много идентификаторов местоположений! Возможно, другие числа — это вовсе не идентификаторы местоположений, а неверно истолкованный почерк.

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

Вот те же примеры списков еще раз:

3   4
4   3
2   5
1   3
3   9
3   3

Для этих списков-примеров процесс нахождения показателя схожести выглядит следующим образом:

  • Первое число в левом списке — 3. Оно появляется в правом списке три раза, поэтому показатель сходства увеличивается на .3 * 3 = 9

  • Второе число в левом списке — 4. Оно появляется в правом списке один раз, поэтому показатель схожести увеличивается на .4 * 1 = 4

  • Третье число в левом списке — 2. Оно не отображается в правом списке, поэтому показатель сходства не увеличивается ( 2 * 0 = 0).

  • Четвертый номер, 1, также не отображается в правом списке.

  • Пятое число, 3, появляется в правом списке три раза; показатель сходства увеличивается на 9.

  • Последнее число, 3, появляется в правом списке три раза; показатель сходства снова увеличивается на 9.

Итак, для этих списков-примеров оценка сходства в конце этого процесса составляет 31( 9 + 4 + 0 + 0 + 9 + 9).

Еще раз рассмотрите ваши левый и правый списки. Какова их степень сходства?

Часть 1

  1. Для начала, нам стоит преобразовать входящий текст в пары чисел, стоящих на каждой строке - для этого отлично подойдет функция regexp_matches.

  2. Преобразуем полученные на каждой строке массивы из пары текстовых значений в пару числовых через преобразование типов ::numeric[].

  3. "Соберем" array_agg(... ORDER BY ...) упорядоченные массивы для каждого из списков:

  4. "Развернем" с помощью "параллельного" unnest оба массива одновременно и просуммируем модуль разности значений:

SELECT
  sum(abs(v2 - v1)) -- суммируем разницу значений
FROM
  (
    SELECT
      array_agg(line[1] ORDER BY line[1]) lst1 -- упорядочиваем элементы каждого списка
    , array_agg(line[2] ORDER BY line[2]) lst2
    FROM
      (
        SELECT
          line::numeric[]   -- переводим строковые представления в числовые значения
        FROM
          regexp_matches($$
3   4
4   3
2   5
1   3
3   9
3   3
$$
          , '(\d+)\s+(\d+)' -- каждая пара чисел, невзирая на переводы строк
          , 'g'
          ) line
      ) T
  ) T
, unnest(lst1, lst2) u(v1, v2); -- "разворачиваем" оба массива параллельно

На входном наборе из задачи ответ получается примерно за 5.5мс:

Часть 2

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

  1. С помощью unnest(ARRAY[...]) "размножим" строки, получив для каждого из чисел в списках по строке с признаком lst, к какому из списков оно относится.

  2. Вычислим метрику для каждого значения, используя подсчет с условием count(*) FILTER(WHERE lst = ...).

  3. Останется лишь просуммировать полученные значения.

SELECT
  sum(sym) -- суммарная "схожесть"
FROM
  (
    SELECT
      v * count(*) FILTER(WHERE lst = 0) * count(*) FILTER(WHERE lst = 1) sym -- "схожесть" для конкретного значения
    FROM
      (
        SELECT
          array_agg(line[1] ORDER BY line[1]) lst1
        , array_agg(line[2] ORDER BY line[2]) lst2
        FROM
          (
            SELECT
              line::numeric[]
            FROM
              regexp_matches($$
3   4
4   3
2   5
1   3
3   9
3   3
$$
              , '(\d+)\s+(\d+)'
              , 'g'
              ) line
          ) T
      ) T
    , unnest(lst1, lst2) u(v1, v2)
    , unnest(ARRAY[v1, v2], ARRAY[0, 1]) g(v, lst) -- "размножаем" строки
    GROUP BY
      v
  ) T;

В этот раз вычисления заняли чуть больше времени - порядка 8мс.

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