В этой челлендж-серии статей, начатой, внезапно, с разбора задачи Day 11, попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.
Возможно, SQL не самый подходящий для этого язык, зато мы рассмотрим его различные возможности, о которых вы могли и не подозревать.
-
Решение Day 1: Historian Hysteria (регулярные выражения и условная агрегация)
-
Решение Day 5: Print Queue (поиск в словаре и массивах, сортировка «пузырьком»)
-
Решение Day 11: Plutonian Pebbles (агрегация внутри рекурсии)
Оригинальная постановка задачи и ее перевод:
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
-
Для начала, нам стоит преобразовать входящий текст в пары чисел, стоящих на каждой строке — для этого отлично подойдет функция
regexp_matches. -
Преобразуем полученные на каждой строке массивы из пары текстовых значений в пару числовых через преобразование типов
::numeric[]. -
«Соберем»
array_agg(... ORDER BY ...)упорядоченные массивы для каждого из списков: -
«Развернем» с помощью «параллельного»
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
Воспользуемся наработками из первой части, но заметим, что описанный алгоритм подсчета «схожести» сводится к «каждое из уникальных числовых значений в списках умножь на количество его появлений в первом и втором списках». Для этого:
-
С помощью
unnest(ARRAY[...])«размножим» строки, получив для каждого из чисел в списках по строке с признакомlst, к какому из списков оно относится. -
Вычислим метрику для каждого значения, используя подсчет с условием
count(*) FILTER(WHERE lst = ...). -
Останется лишь просуммировать полученные значения.
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мс.
ссылка на оригинал статьи https://habr.com/ru/articles/868964/
Добавить комментарий