Парсер Хабра: Решение японских кроссвордов одним запросом SQL

пятница, 6 сентября 2013 г.

Решение японских кроссвордов одним запросом SQL


with INPUT as
(
  ----------------------------- Входные данные ---------------------------------
  -- Укажите список чисел задания для колонок и строк. Каждую колонку или строку
  -- разделяйте запятой. Группы (не более 5) внутри - пробелом.
  -- Если необходимо, скорректируйте размер игрового поля.
  -- Опционально можно указать символы-заполнители.
  select 
      '2, 1 1, 1 2, 3' as FIELD_COLS, -- значения колонок слева направо
      '2, 1 1, 1 2, 3' as FIELD_ROWS, -- значения строк сверху вниз
      4 as COL_COUNT, -- количество колонок игрового поля
      4 as ROW_COUNT, -- количество строк игрового поля
      '#' as FILL, -- символ-заполнитель заполненной ячейки
      ' ' as EMPT  -- символ-заполнитель пустой ячейки
  from dual
)

--------------------------------------------------------------------------------
-- Вывод: для каждой перестановки выбирается только одна строка с ответом.
select 
  max(RES) as SOLUTION
from
(
  -- Склейка строки с ответом (каждая ячейка перестановки содержит одно и то же)
  select 
    PERM,
    listagg(
      decode(VAL, '1', FILL, EMPT) || 
      decode(mod(CELL, COL_COUNT), 0, chr(13))
    ) within group (order by PERM, CELL) over (partition by PERM) as RES
  from
  (
    -- Фильтрация только возможных перестановок.
    select 
      CELL, PERM, VAL
    from
    (
      -- По значениям строки или колонки создается правило, например 
      -- '1011001110' -> '1 2 3', полученное правило сверяется с исходным. 
      -- Если правила по колонке и строке ячейки совпали, ячейка помечается 
      -- как возможная 1, иначе 0. Если в перестановке есть хоть одна 
      -- невозможная ячейка, все ячейки перестановки помечаются невозможными.
      select 
        CELL, PERM, VAL,
        min(
          case when 
            nvl(trim(replace(
              length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 1)) || ' ' ||
              length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 2)) || ' ' ||
              length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 3)) || ' ' ||
              length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 4)) || ' ' ||
              length(regexp_substr(VALUES_COL, REG, 1, 1, 'c', 5))
              ,' 0', ''
            )), '0') = RULE_COL
            and
            nvl(trim(replace(
              length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 1)) || ' ' ||
              length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 2)) || ' ' ||
              length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 3)) || ' ' ||
              length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 4)) || ' ' ||
              length(regexp_substr(VALUES_ROW, REG, 1, 1, 'c', 5))
              ,' 0', ''
            )), '0') = RULE_ROW 
            then 1
            else 0
          end
        ) over (partition by PERM) as IS_PERM_VALID
      from
      (
        -- Получение значений всех ячеек, составляющих строку и колонку 
        -- для каждой перестановки по оси X и Y, например '1011001110'.
        select 
          CELL, RULE_COL, RULE_ROW, PERM, VAL,
          listagg(VAL) 
            within group (order by PERM, X, CELL) 
            over (partition by PERM, X) as VALUES_COL,
          listagg(VAL) 
            within group (order by PERM, Y, CELL) 
            over (partition by PERM, Y) as VALUES_ROW,
          '0*(1*)0*(1*)0*(1*)0*(1*)0*(1*)0*' as REG
        from
        (
          -- Строки ячеек умножаются на строки перестановок.
          -- Генерация значений (1/0) каждой ячейки для каждой перестановки.
          select 
            CELL, X, Y, RULE_COL, RULE_ROW, PERM,
            to_char(mod(trunc(PERM / power(2, CELL -1)), 2)) as VAL
          from
          (
            -- Каждой ячейке выбирается соответствующее ей правило по осям X и Y
            -- путем извлечения подстроки динамически строящимся рег. выражением
            select 
              CELL, X, Y,
              trim(regexp_substr(
                FIELD_COLS, 
                substr(rpad('s', X * length(REG) +1, REG), 3), 
                1, 1, 'c', X
              )) as RULE_COL,
              trim(regexp_substr(
                FIELD_ROWS, 
                substr(rpad('s', Y * length(REG) +1, REG), 3), 
                1, 1, 'c', Y
              )) as RULE_ROW
            from 
            (
              -- Точка входа здесь!
              -- Получение строк в количестве ячеек игрового поля, 
              -- рассчет координат ячеек по осям X и Y. 
              select 
                LEVEL as CELL, -- номер поля
                mod(LEVEL -1, COL_COUNT) +1 as X,
                trunc((LEVEL -1) / COL_COUNT) +1 as Y,
                ',([^,]+)' as REG,
                FIELD_COLS, FIELD_ROWS
              from INPUT
              connect by LEVEL <= COL_COUNT * ROW_COUNT
            )
          ),
          (
            -- Генерация строк всех возможных перестановок
            select 
              LEVEL -1 as PERM -- номер перестановки, начиная с 0
            from INPUT
            connect by LEVEL <= power(2, COL_COUNT * ROW_COUNT)
          )
        )
      )
    )
    where IS_PERM_VALID = 1
  ),
  (
    -- Получение настроек для визуализации ответа 
    select COL_COUNT, FILL, EMPT from INPUT
  )
)
group by PERM;

This entry passed through the Full-Text RSS service — if this is your content and you're reading it on someone else's site, please read the FAQ at fivefilters.org/content-only/faq.php#publishers. Five Filters recommends: