SQL HowTo: работа с массивами (Advent of Code 2024, Day 4: Ceres Search)

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

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

В этой части немного поработаем с массивами.

• Решение Day 1

• Решение Day 2

• Решение Day 3

• Решение Day 4

• Решение Day 11

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

..X... .SAMX. .A..A. XMAS.S .X....

MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASX

....XXMAS. .SAMXMS... ...S..A... ..A.A.MS.X XMASAMX.MM X.....XA.A S.S.S.S.SS .A.A.A.A.A ..M.M.M.MM .X.X.XMASX

M.S .A. M.S

.M.S...... ..A..MSMS. .M.S.MAA.. ..A.ASMSM. .M.S.M.... .......... S.S.S.S.S. .A.A.A.A.. M.M.M.M.M. ..........

Часть 1

1. Преобразуем цепочкой regexp_split_to_table -> regexp_split_to_array -> array_agg входную строку в двухмерный массив символов.

2. Используем уже встречавшуюся нам функцию generate_subscripts для получения всех комбинаций координат в матрице.

3. Для каждой исходной точки формируем 8 слов искомой длины во всех горизонтальных, вертикальных и диагональных направлениях, сразу «разворачивая» их в строки с помощью unnest(ARRAY[...]).

4. Считаем количество получившихся искомых слов.

WITH matrix AS(   SELECT     array_agg(regexp_split_to_array(line, '')) m   FROM     regexp_split_to_table($$ MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASX     $$, '[\r\n]+') line   WHERE     btrim(line) <> '' ) SELECT   count(*) FILTER(WHERE word = 'XMAS') -- подсчитываем кол-во слов 'XMAS' FROM   matrix , generate_subscripts(m, 1) x -- первый уровень массива , generate_subscripts(m, 2) y -- второй уровень , LATERAL (     SELECT       unnest(ARRAY[ -- генерируем слова во всех 8 возможных направлениях сразу         string_agg(m[x + i][y], '')       , string_agg(m[x - i][y], '')       , string_agg(m[x][y + i], '')       , string_agg(m[x][y - i], '')       , string_agg(m[x + i][y + i], '')       , string_agg(m[x + i][y - i], '')       , string_agg(m[x - i][y + i], '')       , string_agg(m[x - i][y - i], '')       ]) word     FROM       generate_series(0, length('XMAS') - 1) i -- генерируем смещения по кол-ву букв искомого слова   ) T;

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

Часть 2

1. Немного изменим подход к генерации — будем генерировать диагональные слова, считая точку не началом слова, а центром X.

2. Очевидно, что перебирать тогда можно уже не [1..x], а только [2..x-1] — для клеток на границе «слово» не сформируется все равно.

3. Останется лишь подсчитать количество ячеек, где получилось ровно 2 'MAS'.

WITH matrix AS(   SELECT     array_agg(regexp_split_to_array(line, '')) m   FROM     regexp_split_to_table($$ MMMSXXMASM MSAMXMSMSA AMXSXMAAMM MSAMASMSMX XMASAMXAMM XXAMMXXAMA SMSMSASXSS SAXAMASAAA MAMMMXMMMM MXMXAXMASX     $$, '[\r\n]+') line   WHERE     btrim(line) <> '' ) SELECT   count(*) FROM   (     SELECT       x     , y     FROM       matrix     , generate_series(2, array_length(m, 1)) x     , generate_series(2, array_length(m, 2)) y     , LATERAL (         SELECT           unnest(ARRAY[ -- только диагонали             string_agg(m[x + i][y + i], '')           , string_agg(m[x + i][y - i], '')           , string_agg(m[x - i][y + i], '')           , string_agg(m[x - i][y - i], '')           ]) word         FROM           generate_series(-1, 1) i -- [-1, 0, 1]       ) T     WHERE       word = 'MAS'     GROUP BY       1, 2     HAVING       count(*) = 2 -- ровно 2 слова 'MAS' через этот центр   ) T;

Слова короче, перебираем мы меньше, поэтому результат почти втрое быстрее: