Пару дней назад был опубликован пост с решением на MySQL загадки Джиндоша (она же загадка Эйнштейна).
![Где-то на пути к решению Где-то на пути к решению](https://habrastorage.org/getpro/habr/upload_files/2e6/dae/17a/2e6dae17a947988f7256ebb09c25a40c.png)
Предложенное решение показалось мне "неспортивным" - ведь помимо необходимости жестко учитывать в структуре запроса количество исходных элементов ("джойнить" нужные таблицы нужное количество раз), так еще и условия в запросе приходилось многократно дублировать:
-- Рядом с дамой с портсигаром сидит дама из Морли
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;
При этом нас больше не волнует ни общее количество атрибутов в задаче, ни их названия - только лишь вбивай известные условия.
Комментарии (4)
IVNSTN
12.09.2024 12:58+2Поэтому я попробовал решить эту задачу "в общем виде"
но получился опять хардкод
Kilor Автор
12.09.2024 12:58Я уж не стал выносить комбинации условий в отдельный массив, который можно передать параметром извне... иначе даже для этого хаба будет чересчур.
dreesh
Честно на загадку из вики у меня ушло 30-40 минут на решение в уме, но зачем писать программу для ее решения? загадки на то и загадки, что бы ими мозги разминать!
Зы: каждый раз у меня возникает чувство недоумения на подобное!
Kilor Автор
Потому что "написать программу для решения" - это тоже головоломка.