SQL HowTo: Загадка Эйнштейна, или снова Джиндош12.09.2024 15:45

Пару дней назад был опубликован пост с решением на MySQL загадки Джиндоша (она же загадка Эйнштейна).

Где-то на пути к решению

Предложенное решение показалось мне «неспортивным» — ведь помимо необходимости жестко учитывать в структуре запроса количество исходных элементов («джойнить» нужные таблицы нужное количество раз), так еще и условия в запросе приходилось многократно дублировать:

-- Рядом с дамой с портсигаром сидит дама из Морли
AND
 (
   (t1.item='cigar-case' AND t2.city='Morley') OR
   (t2.item='cigar-case' AND 'Morley' IN (t1.city, t3.city)) OR
   (t3.item='cigar-case' AND 'Morley' IN (t2.city, t4.city)) OR
   (t4.item='cigar-case' AND 'Morley' IN (t3.city, t5.city)) OR
   (t5.item='cigar-case' AND t4.city='Morley')
 )

Поэтому я попробовал решить эту задачу «в общем виде», используя возможности PostgreSQL, и вот что из этого получилось.

Полный текст загадки и ее перевод можно увидеть в оригинальном посте., здесь я буду пользоваться теми же значениями, которые приведены и там.

Для начала, договоримся, что все значения всех атрибутов (имена, цвета, города, напитки и ценности) у нас будут полностью уникальны, тогда их полный набор можно представить в виде двумерного текстового массива, а их названия и вовсе не будут нас интересовать:

-- исходные наборы атрибутов
WITH RECURSIVE attr AS (
	SELECT '{
		{Winslow,Marcolla,Contee,Natsiou,Finch}
	,	{red,white,purple,blue,green}
	,	{Bailton,Serkonos,Freiport,Morley,Danuol}
	,	{absent,coctail,rum,cider,whiskey}
	,	{ring,diamond,order,cigar-case,coulomb}
	}'::text[][] src
)

Вычислим размерность этого набора (она же — количество участвующих персон), чтобы использовать его в дальнейшем:

-- количество атрибутов (= персон)
, qty AS (
	SELECT array_length((TABLE attr), 1) qty
)

Сгенерируем все возможные комбинации атрибутов, воспользовавшись методикой из статьи «SQL HowTo: ломаем мозг об дерево — упорядочиваем иерархию с рекурсией и без». В нашем случае у нас всего 5 позиций по 5 вариантов в каждой — то есть 5 ^ 5 = 3125 комбинаций:

-- все комбинации атрибутов
, comb_attr AS (
	SELECT
		ARRAY(
			SELECT
				attr[j + 1][((i / (qty ^ j)::integer) % qty) + 1]
			FROM
				generate_series(0, qty - 1) j
		) c
	FROM
		attr
	,	qty
	,	generate_series(0, (qty ^ qty)::integer - 1) i
)

Фактически, здесь мы сгенерировали все возможные 5-значные числа в 5-ричной системе счисления:

  с
 text[]
{Winslow,red,Bailton,absent,ring}
{Marcolla,red,Bailton,absent,ring}
{Contee,red,Bailton,absent,ring}
{Natsiou,red,Bailton,absent,ring}
{Finch,red,Bailton,absent,ring}
{Winslow,white,Bailton,absent,ring}
{Marcolla,white,Bailton,absent,ring}
{Contee,white,Bailton,absent,ring}
...

Оставим среди них только те, которые соответствуют известным условиям для каждой отдельной персоны:

-- разрешенные комбинации
, cond_single AS (
	SELECT
		*
	FROM
		comb_attr
	,	unnest(ARRAY[1,2,3,4,5]) pos -- генерируем варианты мест
	WHERE
		-- Уинслоу ... синее
		('{Winslow,blue}'::text[] <@ c OR NOT ('{Winslow,blue}'::text[] && c)) AND
		-- Марколла левее всех
		(('Marcolla' = ANY(c) AND pos = 1) OR ('Marcolla' <> ALL(c) AND pos <> 1)) AND
		-- красное ... виски
		('{red,whiskey}'::text[] <@ c OR NOT ('{red,whiskey}'::text[] && c)) AND
		-- Морли ... зелёное
		('{Morley,green}'::text[] <@ c OR NOT ('{Morley,green}'::text[] && c)) AND
		-- Финч ... Кулон
		('{Finch,coulomb}'::text[] <@ c OR NOT ('{Finch,coulomb}'::text[] && c)) AND
		-- Фрейпорт ... Перстень
		('{Freiport,ring}'::text[] <@ c OR NOT ('{Freiport,ring}'::text[] && c)) AND
		-- Конти ... абсент
		('{Contee,absent}'::text[] <@ c OR NOT ('{Contee,absent}'::text[] && c)) AND
		-- Серконос ... сидр
		('{Serkonos,cider}'::text[] <@ c OR NOT ('{Serkonos,cider}'::text[] && c)) AND
		-- посередине ... ром
		(('rum' = ANY(c) AND pos = 3) OR ('rum' <> ALL(c) AND pos <> 3)) AND
		-- Нациу ... Бейлтон
		('{Natsiou,Bailton}'::text[] <@ c OR NOT ('{Natsiou,Bailton}'::text[] && c))
)

Здесь '{Winslow,blue}'::text[] <@ c означает вхождение массива значений в массив комбинации — то есть оба элемента присутствуют в наборе, а NOT ('{Winslow,blue}'::text[] && c) — обратное ему «не присутствует ни один». Соответственно, 'Marcolla' = ANY(c) AND pos = 1 и обратное ему 'Marcolla' <> ALL(c) AND pos <> 1 учитывают условие позиции.

Тут мы не делаем никаких дополнительных логических вычислений, типа »Марколла левее всех, рядом с гостьей, одетой в белое, значит, одетая в белое — на втором месте» — нет, просто заносим исходные условия.

Теперь воспользуемся мощью рекурсии и сгенерируем все варианты «рассадки» по местам (pos), так, чтобы ни одно значение ни одного атрибута не повторялось:

-- рекурсивно отсекаем повторяемость значений
, r AS (
	SELECT
		0 pos
	,	'{}'::text[] acc
UNION ALL
	SELECT
		cs.pos
	,	r.acc || cs.c -- добавляем комбинацию в накопленное
	FROM
		r
	JOIN
		cond_single cs
			ON cs.pos = r.pos + 1 AND -- следующая позиция
			NOT (cs.c && r.acc) -- нет пересечений атрибутов
)

Среди всех таких «цепочек» нас интересуют только те, которые дошли до последней позиции — то есть когда удалось рассадить всех (pos = qty). Пронумеруем их с помощью row_number() OVER() на группы и «нарежем» в наборы для каждой персоны:

-- комбинации размещения
, comb_person AS (
	SELECT
		grp
	,	i + 1 pos
	,	acc[i * qty + 1 : (i + 1) * qty] c -- слайс массива
	FROM
		qty
	,	LATERAL (
			SELECT
				row_number() OVER() grp -- нумеруем группы
			,	*
			FROM
				r
			WHERE
				pos = qty -- только полные размещения
		) T
	,	generate_series(0, qty - 1) i
)

Осталось совсем немного — определить те группы (то есть комбинации размещения персон), для которых выполняются «парные» условия. Для этого воспользуемся агрегатной функцией bool_or:

SELECT
	grp
FROM
	comb_person X
JOIN
	comb_person Y
		USING(grp)
GROUP BY
	1
HAVING
	-- Марколла ... рядом с ... белое
	bool_or('Marcolla' = ANY(X.c) AND 'white' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
	-- красное ... слева от ... пурпурное
	bool_or('red' = ANY(X.c) AND 'purple' = ANY(Y.c) AND X.pos = Y.pos - 1) AND
	-- Портсигар ... рядом с ... Морли
	bool_or('cigar-case' = ANY(X.c) AND 'Morley' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
	-- Портсигар ... рядом с ... Морли
	bool_or('diamond' = ANY(X.c) AND 'Danuol' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
	-- Дануолл ... коктейль ... соседки
	bool_or('Danuol' = ANY(X.c) AND 'coctail' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1)

Здесь условия »рядом с» и »соседки» мы трансформировали в abs(X.pos - Y.pos) = 1.

Остался последний шаг — вывести содержимое всех групп, удовлетворяющих всем условиям сразу:

SELECT
	pos
,	c person
FROM
	comb_person
WHERE
	grp IN (
		...
	)
ORDER BY
	grp, pos;

В нашем примере решение единственное:

 pos    |  person
integer | text[]
      1 | {Marcolla,green,Morley,coctail,diamond}
      2 | {Contee,white,Danuol,absent,cigar-case}
      3 | {Winslow,blue,Freiport,rum,ring}
      4 | {Natsiou,red,Bailton,whiskey,order}
      5 | {Finch,purple,Serkonos,cider,coulomb}

Весь итоговый запрос принимает такой вид:

-- исходные наборы атрибутов
WITH RECURSIVE attr AS (
	SELECT '{
		{Winslow,Marcolla,Contee,Natsiou,Finch}
	,	{red,white,purple,blue,green}
	,	{Bailton,Serkonos,Freiport,Morley,Danuol}
	,	{absent,coctail,rum,cider,whiskey}
	,	{ring,diamond,order,cigar-case,coulomb}
	}'::text[][] attr
)
-- количество атрибутов (= персон)
, qty AS (
	SELECT array_length((TABLE attr), 1) qty
)
-- все комбинации атрибутов
, comb_attr AS (
	SELECT
		ARRAY(
			SELECT
				attr[j + 1][((i / (qty ^ j)::integer) % qty) + 1]
			FROM
				generate_series(0, qty - 1) j
		) c
	FROM
		attr
	,	qty
	,	generate_series(0, (qty ^ qty)::integer - 1) i
)
-- разрешенные комбинации
, cond_single AS (
	SELECT
		*
	FROM
		comb_attr
	,	unnest(ARRAY[1,2,3,4,5]) pos -- генерируем варианты мест
	WHERE
		-- Уинслоу ... синее
		('{Winslow,blue}'::text[] <@ c OR NOT ('{Winslow,blue}'::text[] && c)) AND
		-- Марколла левее всех
		(('Marcolla' = ANY(c) AND pos = 1) OR ('Marcolla' <> ALL(c) AND pos <> 1)) AND
		-- красное ... виски
		('{red,whiskey}'::text[] <@ c OR NOT ('{red,whiskey}'::text[] && c)) AND
		-- Морли ... зелёное
		('{Morley,green}'::text[] <@ c OR NOT ('{Morley,green}'::text[] && c)) AND
		-- Финч ... Кулон
		('{Finch,coulomb}'::text[] <@ c OR NOT ('{Finch,coulomb}'::text[] && c)) AND
		-- Фрейпорт ... Перстень
		('{Freiport,ring}'::text[] <@ c OR NOT ('{Freiport,ring}'::text[] && c)) AND
		-- Конти ... абсент
		('{Contee,absent}'::text[] <@ c OR NOT ('{Contee,absent}'::text[] && c)) AND
		-- Серконос ... сидр
		('{Serkonos,cider}'::text[] <@ c OR NOT ('{Serkonos,cider}'::text[] && c)) AND
		-- посередине ... ром
		(('rum' = ANY(c) AND pos = 3) OR ('rum' <> ALL(c) AND pos <> 3)) AND
		-- Нациу ... Бейлтон
		('{Natsiou,Bailton}'::text[] <@ c OR NOT ('{Natsiou,Bailton}'::text[] && c))
)
-- рекурсивно отсекаем повторяемость значений
, r AS (
	SELECT
		0 pos
	,	'{}'::text[] acc
UNION ALL
	SELECT
		cs.pos
	,	r.acc || cs.c -- добавляем комбинацию в накопленное
	FROM
		r
	JOIN
		cond_single cs
			ON cs.pos = r.pos + 1 AND -- следующая позиция
			NOT (cs.c && r.acc) -- нет пересечений атрибутов
)
-- комбинации размещения
, comb_person AS (
	SELECT
		grp
	,	i + 1 pos
	,	acc[i * qty + 1 : (i + 1) * qty] c -- слайс массива
	FROM
		qty
	,	LATERAL (
			SELECT
				row_number() OVER() grp
			,	*
			FROM
				r
			WHERE
				pos = qty -- только полные размещения
		) T
	,	generate_series(0, qty - 1) i
)
SELECT
	pos
,	c person
FROM
	comb_person
WHERE
	grp IN (
		SELECT
			grp
		FROM
			comb_person X
		JOIN
			comb_person Y
				USING(grp)
		GROUP BY
			1
		HAVING
			-- Марколла ... рядом с ... белое
			bool_or('Marcolla' = ANY(X.c) AND 'white' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
			-- красное ... слева от ... пурпурное
			bool_or('red' = ANY(X.c) AND 'purple' = ANY(Y.c) AND X.pos = Y.pos - 1) AND
			-- Портсигар ... рядом с ... Морли
			bool_or('cigar-case' = ANY(X.c) AND 'Morley' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
			-- Портсигар ... рядом с ... Морли
			bool_or('diamond' = ANY(X.c) AND 'Danuol' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1) AND
			-- Дануолл ... коктейль ... соседки
			bool_or('Danuol' = ANY(X.c) AND 'coctail' = ANY(Y.c) AND abs(X.pos - Y.pos) = 1)
	)
ORDER BY
	grp, pos;

При этом нас больше не волнует ни общее количество атрибутов в задаче, ни их названия — только лишь вбивай известные условия.

© Habrahabr.ru