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

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

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