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 substrluego, 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;