Blanco y negro (Puzzle Hunt 2010) / Хабр
Algunos acertijos se pueden resolver en SQL solo por diversión, y algunos se pueden expresar en este lenguaje declarativo incluso de manera más efectiva que otros, los imperativos.
Se me pidió que intentara crear una solución más visual y, al mismo tiempo, presentara algunas capacidades no triviales de PostgreSQL en una publicación sobre cómo resolver un problema en Python. En blanco y negro.
Descripción de la publicación original.
En blanco y negro – uno de los acertijos interesantes del juego Búsqueda de rompecabezas Universidad de Melbourne 2010. En la trama del juego, persigues a un misterioso participante de un programa de televisión con la esperanza de revelar su identidad. Consigues entrar primero al estudio y luego a su camerino.
“Organiza cada uno de los cuadros a continuación en tiras de 1×1, 1×2 o 1×3 para que ninguna cuadrícula contenga tiras con el mismo patrón en blanco y negro, incluidas las rotaciones”.
El rompecabezas consta de 25 campos cuadrados dispuestos en 5 filas y 5 columnas. A su vez, cada campo se divide en 25 celdas mediante líneas horizontales y verticales. Las celdas tienen un fondo blanco o negro y cada una de ellas contiene una letra.
Usemos el razonamiento del original.
Primero, determinemos qué tiras podemos utilizar para solucionar este problema. Hay 6 tiras diferentes de 1×3 (WWW, WWB, WBW, WBB, BWB y BBB), 3 tiras diferentes de 1×2 (WW, WB y BB) y 2 tiras diferentes de 1×1 (W y B). En total, todas estas tiras contienen 26 celdas. Esto significa que para descomponer cada campo tendrás que utilizar todas las tiras de 1×3, todas las tiras de 1×2 y solo una de las tiras de 1×1. Dado que la ubicación de la tira de 1 celda se deriva de la ubicación de las 9 tiras restantes, se puede ignorar durante la descomposición. Por tanto, el problema se puede reformular de la siguiente manera: necesita ser posicionado en cada campo 6 tiras únicas de tamaño 1×3 y 3 tiras únicas de tamaño 1×2 para que coincidan los colores de las celdas del campo y los colores de las celdas de la tira.
Comencemos a “ensamblar” el CTE para la consulta del solucionador enumerando todas las franjas válidas:
-- перечисляем возможные по условию полоски
, blks AS (
SELECT
*
FROM
unnest(ARRAY('www', 'wwb', 'wbw', 'wbb', 'bwb', 'bbb', 'ww', 'wb', 'bb'))
WITH ORDINALITY T(blk, i) -- автонумерация строк
)
Usamos la función desnudar para convertir la matriz en una lista de cadenas con su numeración automática usando WITH ORDINALITY
:
blk | i
text | bigint
www | 1
wwb | 2
wbw | 3
wbb | 4
bwb | 5
bbb | 6
ww | 7
wb | 8
bb | 9
A propósito, presenté “franjas” más largas de 3 celdas cada una para reducir la cantidad de búsqueda, ya que obviamente hay menos opciones para colocarlas en el campo que las cortas.
Matriz de campo
-- переводим "матрицу" в координаты
, grid AS (
SELECT
x
, y
, c(1)
FROM
(
VALUES('
bwwbb
bwwbw
wbwbw
bwbbb
bwbww
') -- исходная "матрица" поля
) T(src)
, regexp_matches(src, '(bw)+', 'g')
WITH ORDINALITY y(line, y) -- выделяем и нумеруем строки
, regexp_matches(line(1), '(bw)', 'g')
WITH ORDINALITY x(c, x) -- нумеруем клетки и получаем их значения
)
Expresiones regulares (función regexp_matches
) obtenemos de la representación textual del campo los valores en cada celda de coordenadas:
x | y | c
bigint | bigint | text
1 | 1 | b
2 | 1 | w
3 | 1 | w
4 | 1 | b
5 | 1 | b
1 | 2 | b
2 | 2 | w
3 | 2 | w
4 | 2 | b
...
Filas “por columnas”
Para que sea más conveniente determinar la superposición de franjas en el campo no solo “horizontalmente”, sino también “verticalmente”, crearemos una representación de texto para cada una de las columnas (y para las filas al mismo tiempo):
-- формируем массивы строк/столбцов
, grid_both AS (
SELECT
array_agg(line ORDER BY x) FILTER(WHERE y IS NOT NULL) gridh
, array_agg(line ORDER BY y) FILTER(WHERE x IS NOT NULL) gridv
FROM
(
SELECT
x
, y
, string_agg(c, '' ORDER BY x, y) line
FROM
grid
GROUP BY
GROUPING SETS (x, y)
) T
)
Al usar conjuntos de agrupación “agregamos” las líneas en ambas proyecciones a la vez:
x | y | line
bigint | bigint | text
1 | | bbwbb
2 | | wwbww
3 | | wwwbb
4 | | bbbbw
5 | | bwwbw
| 1 | bwwbb
| 2 | bwwbw
| 3 | wbwbw
| 4 | bwbbb
| 5 | bwbww
… y luego los convertimos en dos matrices, descomponiendo tanto la “matriz” original como la transpuesta en líneas:
gridh | gridv
text() | text()
{bwwbb,bwwbw,wbwbw,bwbbb,bwbww} | {bbwbb,wwbww,wwwbb,bbbbw,bwwbw}
Posibles ubicaciones
En lugar de intentar “colocar” el mosaico en las celdas del campo que coinciden con el patrón, resolveremos el problema inverso: para cada celda formaremos todas las franjas horizontales/verticales posibles de longitudes 2 y 3.
-- формируем для каждой координаты все варианты горизонтальных (вправо) и вертикальных (вниз) полосок длин 2 и 3
, placement AS (
SELECT
x
, y
, ln
, d
, blk
FROM
grid_both
, generate_subscripts(gridh, 1) y -- перебираем индексы массивов
, generate_subscripts(gridv, 1) x
, unnest(ARRAY(2, 3)) ln
, LATERAL (
VALUES
('h', substr(gridh(y), x, ln)) -- формируем горизонтальную ...
, ('v', substr(gridv(x), y, ln)) -- ... и вертикальную полоски
) T(d, blk)
WHERE
length(blk) = ln -- отсекаем "вылезшие" за границы поля
)
Ya que cortamos la “tira” con la función substr
luego, cuando vaya más allá de los límites del campo, su longitud será menor que la deseada y el exceso se corta inmediatamente:
x | y | ln | d | blk
1 | 1 | 2 | h | bw
1 | 1 | 3 | h | bww
1 | 1 | 2 | v | bb
1 | 1 | 3 | v | bbw
1 | 2 | 2 | h | bw
1 | 2 | 3 | h | bww
1 | 2 | 2 | v | bw
...
Enumeración recursiva de posibles ubicaciones.
Entonces, para cada tira del conjunto original, podemos intentar “colocarla” en un lugar accesible en una posición “recta” o “espejada”. Para una ubicación adecuada, complete la matriz de celdas ocupadas y su pertenencia. Apliquemos el mismo enfoque que en la solución anterior: si los arreglos tienen celdas ya ocupadas y ocupadas en este paso sin intersecciones – puedes colocar una tira y agregar las coordenadas de sus celdas:
-- рекурсивно для каждой полоски перебираем варианты ее размещения
, r AS (
SELECT
1::bigint i
, '{}'::text() acc_cell -- массив занятых ячеек
, '{}'::text() acc_blk -- принадлежность занятых ячеек
UNION ALL
SELECT
i + 1
, acc_cell || fill_cell
, acc_blk || fill_blk
FROM
r
JOIN
blks
USING(i)
JOIN
placement p
ON p.blk IN (blks.blk, reverse(blks.blk)) -- прямое и зеркальное размещение
, LATERAL (
SELECT
array_agg(ARRAY(cx, cy)::text) fill_cell
, array_agg(ARRAY(cx, cy, i)::text) fill_blk
FROM -- набор координат ячеек, занимаемых полоской
generate_series(0, ln - 1) j
, LATERAL (
SELECT
CASE d
WHEN 'h' THEN x + j
WHEN 'v' THEN x
END cx
, CASE d
WHEN 'h' THEN y
WHEN 'v' THEN y + j
END cy
) T
) T
WHERE
NOT (fill_cell && acc_cell) -- планируемое размещение не имеет пересечений
)
La matriz de celdas ocupadas contiene representaciones de texto de pares de coordenadas. (x, y)
y si una célula pertenece a una franja particular está determinada por el triplete (x, y, i)
:
i | acc_cell | acc_blk
bigint | text() | text()
1 | {} | {}
2 | {{3,1},{3,2},{3,3}} | {{3,1,1},{3,2,1},{3,3,1}}
3 | {{3,1},{3,2},{3,3},{2,1},{2,2},{2,3}} | {{3,1,1},{3,2,1},{3,3,1},{2,1,2},{2,2,2},{2,3,2}}
...
Como puedes ver, la primera tira. www
yacía en el único lugar válido según las coordenadas (3;1)
verticalmente hacia abajo, y el siguiente wwb
-V (2;1)
.
Matriz de ocupación
Supongamos que la combinación de ubicación requerida es única. Entonces basta con tomar la matriz de membresía de la fila con el número más alto y “expandirla” en celdas de fila:
-- переводим массив в координаты
, grid_fill AS (
SELECT
cell(1) x
, cell(2) y
, cell(3) i
FROM
unnest(( -- разворачиваем финальное размещение
SELECT
acc_blk
FROM
r
ORDER BY
i DESC
LIMIT 1
))
, LATERAL (
SELECT
unnest::integer() cell -- превращаем текстовый массив в целочисленный
) T
)
x | y | i
integer | integer | integer
3 | 1 | 1
3 | 2 | 1
3 | 3 | 1
2 | 1 | 2
2 | 2 | 2
2 | 3 | 2
2 | 5 | 3
...
Salida de matriz
Simplemente puede determinar las coordenadas de la celda “faltante”, pero para la autoprueba crearemos un resultado hermoso, demostrando qué franja cubre qué celda, pero olvidándonos de reemplazar la única celda vacía con '.'
:
SELECT
string_agg(coalesce(i::text, '.') || c, ' ' ORDER BY x)
FROM
grid
NATURAL LEFT JOIN
grid_fill
GROUP BY
y
ORDER BY
y;
string_agg
text
4b 2w 1w 9b 9b
4b 2w 1w 6b 7w
4w 2b 1w 6b 7w
5b 5w 5b 6b 8b
.b 3w 3b 3w 8w
El solucionador de consultas final no parece más complicado que el código Python de la publicación original.
Texto completo de la solicitud
-- перечисляем возможные по условию полоски
WITH RECURSIVE blks AS (
SELECT
*
FROM
unnest(ARRAY('www', 'wwb', 'wbw', 'wbb', 'bwb', 'bbb', 'ww', 'wb', 'bb'))
WITH ORDINALITY T(blk, i) -- автонумерация строк
)
-- переводим "матрицу" в координаты
, grid AS (
SELECT
x
, y
, c(1)
FROM
(
VALUES('
bwwbb
bwwbw
wbwbw
bwbbb
bwbww
') -- исходная "матрица" поля
) T(src)
, regexp_matches(src, '(bw)+', 'g')
WITH ORDINALITY y(line, y) -- выделяем и нумеруем строки
, regexp_matches(line(1), '(bw)', 'g')
WITH ORDINALITY x(c, x) -- нумеруем клетки и получаем их значения
)
-- формируем массивы строк/столбцов
, grid_both AS (
SELECT
array_agg(line ORDER BY x) FILTER(WHERE y IS NOT NULL) gridh
, array_agg(line ORDER BY y) FILTER(WHERE x IS NOT NULL) gridv
FROM
(
SELECT
x
, y
, string_agg(c, '' ORDER BY x, y) line
FROM
grid
GROUP BY
GROUPING SETS (x, y)
) T
)
-- формируем для каждой координаты все варианты горизонтальных (вправо) и вертикальных (вниз) полосок длин 2 и 3
, placement AS (
SELECT
x
, y
, ln
, d
, blk
FROM
grid_both
, generate_subscripts(gridh, 1) y -- перебираем индексы массивов
, generate_subscripts(gridv, 1) x
, unnest(ARRAY(2, 3)) ln
, LATERAL (
VALUES
('h', substr(gridh(y), x, ln)) -- формируем горизонтальную ...
, ('v', substr(gridv(x), y, ln)) -- ... и вертикальную полоски
) T(d, blk)
WHERE
length(blk) = ln -- отсекаем "вылезшие" за границы поля
)
-- рекурсивно для каждой полоски перебираем варианты ее размещения
, r AS (
SELECT
1::bigint i
, '{}'::text() acc_cell -- массив занятых ячеек
, '{}'::text() acc_blk -- принадлежность занятых ячеек
UNION ALL
SELECT
i + 1
, acc_cell || fill_cell
, acc_blk || fill_blk
FROM
r
JOIN
blks
USING(i)
JOIN
placement p
ON p.blk IN (blks.blk, reverse(blks.blk)) -- прямое и зеркальное размещение
, LATERAL (
SELECT
array_agg(ARRAY(cx, cy)::text) fill_cell
, array_agg(ARRAY(cx, cy, i)::text) fill_blk
FROM -- набор координат ячеек, занимаемых полоской
generate_series(0, ln - 1) j
, LATERAL (
SELECT
CASE d
WHEN 'h' THEN x + j
WHEN 'v' THEN x
END cx
, CASE d
WHEN 'h' THEN y
WHEN 'v' THEN y + j
END cy
) T
) T
WHERE
NOT (fill_cell && acc_cell) -- планируемое размещение не имеет пересечений
)
-- переводим массив в координаты
, grid_fill AS (
SELECT
cell(1) x
, cell(2) y
, cell(3) i
FROM
unnest(( -- разворачиваем финальное размещение
SELECT
acc_blk
FROM
r
ORDER BY
i DESC
LIMIT 1
))
, LATERAL (
SELECT
unnest::integer() cell -- превращаем текстовый массив в целочисленный
) T
)
SELECT
string_agg(coalesce(i::text, '.') || c, ' ' ORDER BY x)
FROM
grid
NATURAL LEFT JOIN
grid_fill
GROUP BY
y
ORDER BY
y;