Kilor 12 сен в 15:45

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

Средний

7 мин

3.6K

Блог компании ТензорНенормальное программирование*PostgreSQL*SQL*Алгоритмы*

Мнение

Пару дней назад был опубликован пост с решением на 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
)

Фактически, здесь мы сгенерировали все возможные N-значные числа в N-ричной системе счисления, дающие нам все возможные комбинации, взяв для каждой "цифры" соответствующее значение атрибута:

  с
 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
)

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

Осталось определить те группы (то есть комбинации размещения персон), для которых выполняются все "парные" условия одновременно - для этого воспользуемся агрегатной функцией bool_or для каждого из них в HAVING-части запроса:

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;

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

Теги:

Хабы:

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

Публикации

Информация