23.12.2024 13:04
Kilor 0 375 Источник

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

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

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

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

Advent of Code 2024, Day 4: Ceres Search

--- День 4: Поиск Цереры ---

«Похоже, Шефа здесь нет. Следующий!» Один из Историков достает устройство и нажимает на нем единственную кнопку. После короткой вспышки вы узнаете интерьер станции мониторинга Цереры !

Пока поиски Шефа продолжаются, маленькая эльфийка, живущая на станции, дергает вас за рубашку; она хотела бы узнать, не могли бы вы помочь ей с поиском слов (вашим вводом в головоломку). Ей нужно найти только одно слово: XMAS.

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

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

Фактический поиск слова будет заполнен буквами. Например:

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX

В этом поиске слово XMASвстречается всего 18раз; вот тот же поиск слов снова, но буквы, не участвующие ни в одном из XMASзаменены на .:

....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

Взгляните на поиск слова маленьким эльфом. Сколько раз XMASвстречается?

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

Эльф вопросительно смотрит на тебя. Ты неправильно понял задание?

В поисках инструкций вы переворачиваете поиск слов и обнаруживаете, что это на самом деле не головоломка XMAS; это головоломка X-MAS, в которой вам нужно найти два MASв форме X. Один из способов, как это может выглядеть:

M.S
.A.
M.S

Нерелевантные символы снова были заменены на .в приведенной выше диаграмме. Внутри Xкаждый MASможет быть написан вперед или назад.

Вот тот же пример, что и раньше, но на этот раз все X-MAS были сохранены:

.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.
..........

В этом примере символ an X-MASпоявляется 9раз.

Сколько раз встречаетсяX-MAS?

Часть 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;

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

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