Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом / forpes.ru

Главная
Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом

Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом +73

10.09.2024 13:01

inetstar 31 9800 Источник

SQL — язык сверхвысокого уровня, а SQL-движки очень высоко оптимизированы. И поэтому во многих случаях с помощью него можно просто и быстро решать сложные задачи. Вы удивитесь, но даже существует шахматный движок на SQL.

Сегодня мы рассмотрим решение непростой загадки Джиндоша из замечательной игры Dishonored 2 с помощью SQL.

Загадка Джиндоша

Во время игры Dishonored 2 мы сталкиваемся с запертой изобретателем Джиндошем кодовой дверью, чтобы её открыть нужно решить весьма запутанную загадку, ну или бегать по всей карте, ища другие подсказки.

Вот сама задача:

Вот текст задачи для тех, кому неудобно читать с картинки:

На званом обеде были леди Уинслоу, доктор Марколла, графиня Конти, мадам Нациу и баронесса Финч.

Женщины сидели в ряд. Все они были одеты в разные цвета. Например, Леди Уинслоу носила причудливое синее пончо; Доктор Марколла левее всех, рядом с гостьей, одетой в белое. Дама, одетая в красное платье, сидела слева от гостьи, одетой в пурпурное. Я помню красное платье, потому что его обладательница пролила на него виски. Путешественница, недавно покинувшая Морли, была одета во всё зелёное. Когда одна гостья хвастливо демонстрировала Портсигар, женщина, сидевшая рядом с ней, заметила: «Мой родной Морли славится такими безделушками».

Тогда Баронесса Финч достала из сумочки свою фамильную ценность — Кулон с птицей. Дама, до того рассказывавшая, как красив в это время года её родной край, Фрейпорт, с усмешкой заметила, что её Перстень — куда большая редкость. Другая дама начала демонстративно рассматривать свою реликвию — Бриллиант; сидевшая рядом с ней гостья (помнится, её родина — Дануолл) чуть не выбила коктейль из рук своей соседки. Внезапно Графиня Конти, пившая исключительно абсент, предложила тост. Дама, которой предстояло навестить Серконос и которая весь вечер налегала на сидр, попыталась запрыгнуть на стол, но повалилась на гостью, сидевшую посередине, и та пролила ром. Затем Мадам Нациу завладела всеобщим вниманием, рассказав про Бейлтон времён своей юности.

Наутро под столом валялись 4 фамильные драгоценности: Портсигар, Орден, Перстень и Бриллиант.

Но кому принадлежит каждая из них?

Для каждого игрока меняются цвета, имена дам и т. п. Мы будем решать вариант, описанный выше.

На первый взгляд эта загадка кажется бредом, каким-то потоком сознания пьяной аристократки, но с помощью SQL, а точнее MySQL, мы её решим.

Подход к решению

Общий подход будет следующий: мы с помощью JOIN создадим все возможные комбинации дам, ценностей, мест, цветов и напитков, а потом ограничим это с помощью условий.

В подобных задачах SQL хорошо себя показывает по скорости, иногда даже лучше, чем компилируемые языки. Был случай в моей практике, когда более сложная переборная задача, чем эта, решалась SQL-запросом быстрее, чем скомпилированный код на Haskel.

SQL-база имеет планировщик, который замечательно выстраивает план запроса и выполняет перебор не полный, а с возвратом, оптимизированный, быстро сужая его область. SQL-движки уже многие десятилетия эволюционируют и тщательно оптимизированы для того, чтобы выдавать быстрый результат. Вплоть до того, что иногда используется внутренняя компиляция запроса в нативный код или байт-код.

Итак, для начала создадим таблицы, в которые занесём все классы информации, встретившиеся в этой задаче. Я установил MySQL на виртуальный сервер RUVDS, поэтому использую СУБД прямо из сессии SSH для решения этой загадки.

Решаем загадку

▍ Структуры данных

create database dis2;
use dis2;

-- Имена дам
create table Names (name char(10)) ENGINE=MEMORY;
insert into Names values ('Winslow'), ('Marcolla'), ('Contee'), ('Natsiou'), ('Finch');

-- Позиции дам за столом
create table Positions (pos int) ENGINE=MEMORY;
insert into Positions values (1), (2), (3), (4), (5);

-- Цвета платьев
create table Colors (color char(10)) ENGINE=MEMORY;
insert into Colors values ('red'), ('white'), ('purple'), ('blue'), ('green');

-- Родные города дам
create table Cities (city char(10)) ENGINE=MEMORY;
insert into Cities values ('Bailton'), ('Serkonos'), ('Freiport'), ('Morley'), ('Danuol');

-- Напитки дам
create table Drinks (drink char(10)) ENGINE=MEMORY;
insert into Drinks values ('absent'), ('coctail'), ('rum'), ('cider'), ('whiskey');

-- Ценности
create table Items (item char(10)) ENGINE=MEMORY;
insert into Items values ('ring'), ('diamond'), ('order'), ('cigar-case'), ('coulomb');

Я использую движок таблиц MEMORY для скорости. Это вещь специфичная для MySQL. В других SQL БД «ENGINE=MEMORY» указывать не нужно. Строго говоря, в этой задачке выбор движка MEMORY ни на что не повлияет, но если бы перебор был более значительным, то это увеличило бы скорость.

▍ Соединяем таблицы для создания всех возможных вариантов

Теперь подсоединим все таблички друг к другу и впишем условия. Соединить таблицы в MySQL мы можем через JOIN, INNER JOIN, CROSS JOIN и без JOIN вообще — через запятую.

Мы это делаем для того, чтобы создать абсолютно все варианты сочетаний имён, платьев, городов, ценностей и цветов. К каждой строке первой таблицы будут присоединены все варианты строк из всех остальных таблиц.

Пример соединения таблиц через INNER JOIN:

SELECT COUNT(*) FROM Positions
INNER JOIN Names
INNER JOIN Colors
INNER JOIN Drinks
INNER JOIN Cities
INNER JOIN Items

Получим 15625 вариантов. Для краткости записи соединим таблицы через запятую и добавим условия, которые выудим из текста, чтобы уменьшить число вариантов.

▍ Добавляем условия для минимизации числа вариантов

Возьмём, к примеру, условие «путешественница покинувшая Морли была одета во всё зелёное». Из этого условия следуют ДВА взаимоисключающих условия для каждой строки на SQL:

```
city='Morley' AND color = 'green'
```
```
city!='Morley' AND color != 'green'
```

Поскольку условия взаимоисключающие, то они будут соединены через OR (ИЛИ). После этого такое комбинированное условие должно выполняться абсолютно на каждой строке вывода.

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

Однако мы не сможем записать абсолютно все условия, так как некоторые условия касаются позиции (левее, правее, рядом), а строки в SQL-выводе не связаны между собой. Это сделано по дизайну SQL, поэтому условиями, связанными с порядком, в котором сидели дамы, мы займёмся позже.

SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
    WHERE
    ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
    ORDER BY pos, name, item, color, city;

Получим 80 строк.

Смотреть результат запроса

+------+----------+------------+--------+---------+----------+
| pos  | name     | item       | color  | drink   | city     |
+------+----------+------------+--------+---------+----------+
|    1 | Marcolla | cigar-case | green  | coctail | Morley   |
|    1 | Marcolla | cigar-case | purple | coctail | Danuol   |
|    1 | Marcolla | cigar-case | purple | cider   | Serkonos |
|    1 | Marcolla | cigar-case | red    | whiskey | Danuol   |
|    1 | Marcolla | diamond    | green  | coctail | Morley   |
|    1 | Marcolla | diamond    | purple | coctail | Danuol   |
|    1 | Marcolla | diamond    | purple | cider   | Serkonos |
|    1 | Marcolla | diamond    | red    | whiskey | Danuol   |
|    1 | Marcolla | order      | green  | coctail | Morley   |
|    1 | Marcolla | order      | purple | coctail | Danuol   |
|    1 | Marcolla | order      | purple | cider   | Serkonos |
|    1 | Marcolla | order      | red    | whiskey | Danuol   |
|    1 | Marcolla | ring       | purple | coctail | Freiport |
|    1 | Marcolla | ring       | red    | whiskey | Freiport |
|    2 | Contee   | cigar-case | white  | absent  | Danuol   |
|    2 | Contee   | diamond    | white  | absent  | Danuol   |
|    2 | Contee   | order      | white  | absent  | Danuol   |
|    2 | Contee   | ring       | white  | absent  | Freiport |
|    2 | Finch    | coulomb    | white  | coctail | Danuol   |
|    2 | Finch    | coulomb    | white  | cider   | Serkonos |
|    2 | Natsiou  | cigar-case | white  | coctail | Bailton  |
|    2 | Natsiou  | diamond    | white  | coctail | Bailton  |
|    2 | Natsiou  | order      | white  | coctail | Bailton  |
|    3 | Finch    | coulomb    | green  | rum     | Morley   |
|    3 | Finch    | coulomb    | purple | rum     | Danuol   |
|    3 | Natsiou  | cigar-case | purple | rum     | Bailton  |
|    3 | Natsiou  | diamond    | purple | rum     | Bailton  |
|    3 | Natsiou  | order      | purple | rum     | Bailton  |
|    3 | Winslow  | cigar-case | blue   | rum     | Danuol   |
|    3 | Winslow  | diamond    | blue   | rum     | Danuol   |
|    3 | Winslow  | order      | blue   | rum     | Danuol   |
|    3 | Winslow  | ring       | blue   | rum     | Freiport |
|    4 | Contee   | cigar-case | green  | absent  | Morley   |
|    4 | Contee   | cigar-case | purple | absent  | Danuol   |
|    4 | Contee   | diamond    | green  | absent  | Morley   |
|    4 | Contee   | diamond    | purple | absent  | Danuol   |
|    4 | Contee   | order      | green  | absent  | Morley   |
|    4 | Contee   | order      | purple | absent  | Danuol   |
|    4 | Contee   | ring       | purple | absent  | Freiport |
|    4 | Finch    | coulomb    | green  | coctail | Morley   |
|    4 | Finch    | coulomb    | purple | coctail | Danuol   |
|    4 | Finch    | coulomb    | purple | cider   | Serkonos |
|    4 | Finch    | coulomb    | red    | whiskey | Danuol   |
|    4 | Natsiou  | cigar-case | purple | coctail | Bailton  |
|    4 | Natsiou  | cigar-case | red    | whiskey | Bailton  |
|    4 | Natsiou  | diamond    | purple | coctail | Bailton  |
|    4 | Natsiou  | diamond    | red    | whiskey | Bailton  |
|    4 | Natsiou  | order      | purple | coctail | Bailton  |
|    4 | Natsiou  | order      | red    | whiskey | Bailton  |
|    4 | Winslow  | cigar-case | blue   | coctail | Danuol   |
|    4 | Winslow  | cigar-case | blue   | cider   | Serkonos |
|    4 | Winslow  | diamond    | blue   | coctail | Danuol   |
|    4 | Winslow  | diamond    | blue   | cider   | Serkonos |
|    4 | Winslow  | order      | blue   | coctail | Danuol   |
|    4 | Winslow  | order      | blue   | cider   | Serkonos |
|    4 | Winslow  | ring       | blue   | coctail | Freiport |
|    5 | Contee   | cigar-case | green  | absent  | Morley   |
|    5 | Contee   | cigar-case | purple | absent  | Danuol   |
|    5 | Contee   | diamond    | green  | absent  | Morley   |
|    5 | Contee   | diamond    | purple | absent  | Danuol   |
|    5 | Contee   | order      | green  | absent  | Morley   |
|    5 | Contee   | order      | purple | absent  | Danuol   |
|    5 | Contee   | ring       | purple | absent  | Freiport |
|    5 | Finch    | coulomb    | green  | coctail | Morley   |
|    5 | Finch    | coulomb    | purple | coctail | Danuol   |
|    5 | Finch    | coulomb    | purple | cider   | Serkonos |
|    5 | Finch    | coulomb    | red    | whiskey | Danuol   |
|    5 | Natsiou  | cigar-case | purple | coctail | Bailton  |
|    5 | Natsiou  | cigar-case | red    | whiskey | Bailton  |
|    5 | Natsiou  | diamond    | purple | coctail | Bailton  |
|    5 | Natsiou  | diamond    | red    | whiskey | Bailton  |
|    5 | Natsiou  | order      | purple | coctail | Bailton  |
|    5 | Natsiou  | order      | red    | whiskey | Bailton  |
|    5 | Winslow  | cigar-case | blue   | coctail | Danuol   |
|    5 | Winslow  | cigar-case | blue   | cider   | Serkonos |
|    5 | Winslow  | diamond    | blue   | coctail | Danuol   |
|    5 | Winslow  | diamond    | blue   | cider   | Serkonos |
|    5 | Winslow  | order      | blue   | coctail | Danuol   |
|    5 | Winslow  | order      | blue   | cider   | Serkonos |
|    5 | Winslow  | ring       | blue   | coctail | Freiport |
+------+----------+------------+--------+---------+----------+
80 rows in set (0,00 sec)

Далее мы вставим получившийся вывод в таблицу s.


create table s (pos int, name char(10), item char(10), color char(10), drink char(10), city char(10)) ENGINE=MEMORY;

INSERT INTO s
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
    WHERE
    ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'));

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

Но нам нужно 5 строк с разными именами дам. Поэтому теперь мы наложим условие, чтобы те элементы (имя, цвет, город, предмет, напиток), которые были использованы в первой строке (и последующих строках) не были использованы далее. Но в SQL мы не можем обращаться к произвольным строкам вывода по дизайну. Обойдём это ограничение, выведя всю нужную информацию в одну строку.

Для этого мы будем теперь присоединять полученную таблицу s саму к себе, и накладывать эти условия. Хоть эти условия и выглядят многословно и сложно, по сути они очень просты.

Для того, чтобы присоединять таблицу s саму к себе, нам потребуется при каждом присоединении давать ей новый псевдоним. Это будут t1, t2, t3, t4, t5.

Запросили в одну строку имя первой дамы, потом её предмет, потом имя второй дамы и её предмет, и так далее.

SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1

JOIN s t2 ON t2.name != t1.name
  AND t2.item != t1.item
  AND t2.color != t1.color
  AND t2.drink != t1.drink
  AND t2.city != t1.city
 
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
  AND t3.item NOT IN (t1.item, t2.item)
  AND t3.color NOT IN (t1.color, t2.color)
  AND t3.drink NOT IN (t1.drink, t2.drink)
  AND t3.city NOT IN (t1.city, t2.city)
 
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
 AND t4.item NOT IN (t1.item, t2.item, t3.item)
 AND t4.color NOT IN (t1.color, t2.color, t3.color)
 AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
 AND t4.city NOT IN (t1.city, t2.city, t3.city)
 
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
 AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
 AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
 AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
 AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)

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

▍ Добавляем условия, связанные с относительным расположением дам на банкете

WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
   (t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
 )
-- Рядом с дамой с портсигаром сидит дама из Морли
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')
 )
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
 (
   (t1.item='diamond' AND t2.city='Danuol') OR
   (t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.item='diamond' AND t4.city='Danuol')
 )
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
 (
   (t1.drink='coctail' AND t2.city='Danuol') OR 
   (t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.drink='coctail' AND t4.city='Danuol')
 );

Решение головоломки

В итоге мы получим:

+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
| name     | item    | name   | item       | name    | item | name    | item  | name  | item    |
+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
| Marcolla | diamond | Contee | cigar-case | Winslow | ring | Natsiou | order | Finch | coulomb |
+----------+---------+--------+------------+---------+------+---------+-------+-------+---------+
1 row in set (0,00 sec)

Более того, мы решили головоломку даже сильнее, чем требовалось. Если заменить первую строку последнего запроса на это:

SELECT t1.*, t2.*, t3.*, t4.*, t5.* FROM s t1

то мы получим полную информацию о каждой из дам: позицию в ряду, принадлежащую ей драгоценность, её город, напиток и цвет платья.

А можно ли было обойтись без промежуточной таблицы s?

В MySQL, начиная с версии 8, поддерживается SQL-оператор WITH. Мы могли бы сделать такой запрос-монстр:

WITH s(pos, name, item, color, drink, city) AS
(
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
    WHERE
    ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
)
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
  AND t3.item NOT IN (t1.item, t2.item)
  AND t3.color NOT IN (t1.color, t2.color)
  AND t3.drink NOT IN (t1.drink, t2.drink)
  AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
 AND t4.item NOT IN (t1.item, t2.item, t3.item)
 AND t4.color NOT IN (t1.color, t2.color, t3.color)
 AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
 AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
 AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
 AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
 AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
 AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
   (t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
 )
-- Рядом с дамой с портсигаром сидит дама из Морли
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')
 )
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
 (
   (t1.item='diamond' AND t2.city='Danuol') OR
   (t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.item='diamond' AND t4.city='Danuol')
 )
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
 (
   (t1.drink='coctail' AND t2.city='Danuol') OR 
   (t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.drink='coctail' AND t4.city='Danuol')
 );

Но он отработал бы за несколько суток. Видимо, планировщик в MySQL недостаточно умён, чтобы самостоятельно создать временную таблицу с которой всё отработало бы моментально. Поэтому этот подход в MySQL бесполезен. В PostgreSQL он отработает быстро.

Обходимся без дополнительной таблицы s в MySQL 8.* благодаря VALUES и ROW()

Пользователь asmm предложил трюк, как можно решить головоломку всего одним запросом:

WITH Positions(pos) AS (
    VALUES ROW(1), ROW(2), ROW(3), ROW(4), ROW(5)
)
, Names(name) AS (
    VALUES ROW('Winslow'), ROW('Marcolla'), ROW('Contee'), ROW('Natsiou'), ROW('Finch')
)
, Colors(color) AS (
    VALUES ROW('red'), ROW('white'), ROW('purple'), ROW('blue'), ROW('green')
)
, Cities(city) AS (
    VALUES ROW('Bailton'), ROW('Serkonos'), ROW('Freiport'), ROW('Morley'), ROW('Danuol')
)
, Drinks(drink) AS (
    VALUES ROW('absent'), ROW('coctail'), ROW('rum'), ROW('cider'), ROW('whiskey')
)
, Items(item) AS (
    VALUES ROW('ring'), ROW('diamond'), ROW('order'), ROW('cigar-case'), ROW('coulomb')
)
, s AS (
    SELECT DISTINCT *
    FROM Positions, Names, Items, Colors, Drinks, Cities
    WHERE ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
)
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
  AND t3.item NOT IN (t1.item, t2.item)
  AND t3.color NOT IN (t1.color, t2.color)
  AND t3.drink NOT IN (t1.drink, t2.drink)
  AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
 AND t4.item NOT IN (t1.item, t2.item, t3.item)
 AND t4.color NOT IN (t1.color, t2.color, t3.color)
 AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
 AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
 AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
 AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
 AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
 AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
   (t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
 )
-- Рядом с дамой с портсигаром сидит дама из Морли
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')
 )
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
 (
   (t1.item='diamond' AND t2.city='Danuol') OR
   (t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.item='diamond' AND t4.city='Danuol')
 )
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
 (
   (t1.drink='coctail' AND t2.city='Danuol') OR
   (t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.drink='coctail' AND t4.city='Danuol')
 );

Полный текст всех запросов для MySQL (тестировано на 5.* и выше)

drop database if exists dis2;
create database dis2;
use dis2;

-- Имена дам
create table Names (name char(10)) ENGINE=MEMORY;
insert into Names values ('Winslow'), ('Marcolla'), ('Contee'), ('Natsiou'), ('Finch');

-- Позиции дам за столом
create table Positions (pos int) ENGINE=MEMORY;
insert into Positions values (1), (2), (3), (4), (5);

-- Цвета платьев
create table Colors (color char(10)) ENGINE=MEMORY;
insert into Colors values ('red'), ('white'), ('purple'), ('blue'), ('green');

-- Родные города дам
create table Cities (city char(10)) ENGINE=MEMORY;
insert into Cities values ('Bailton'), ('Serkonos'), ('Freiport'), ('Morley'), ('Danuol');

-- Напитки дам
create table Drinks (drink char(10)) ENGINE=MEMORY;
insert into Drinks values ('absent'), ('coctail'), ('rum'), ('cider'), ('whiskey');

-- Ценности
create table Items (item char(10)) ENGINE=MEMORY;
insert into Items values ('ring'), ('diamond'), ('order'), ('cigar-case'), ('coulomb');

-- Таблица предварительных вариантов для просеивания
create table s (pos int, name char(10), item char(10), color char(10), drink char(10), city char(10)) ENGINE=MEMORY;

INSERT INTO s
SELECT pos, name, item, color, drink, city FROM Positions, Names, Colors, Drinks, Cities, Items
    WHERE
    ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'));

SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
  AND t3.item NOT IN (t1.item, t2.item)
  AND t3.color NOT IN (t1.color, t2.color)
  AND t3.drink NOT IN (t1.drink, t2.drink)
  AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
 AND t4.item NOT IN (t1.item, t2.item, t3.item)
 AND t4.color NOT IN (t1.color, t2.color, t3.color)
 AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
 AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
 AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
 AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
 AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
 AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
   (t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
 )
-- Рядом с дамой с портсигаром сидит дама из Морли
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')
 )
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
 (
   (t1.item='diamond' AND t2.city='Danuol') OR
   (t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.item='diamond' AND t4.city='Danuol')
 )
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
 (
   (t1.drink='coctail' AND t2.city='Danuol') OR 
   (t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.drink='coctail' AND t4.city='Danuol')
 );

Запросы для PostgreSQL в онлайн-редакторе с возможностью теста

ИТОГИ

Полученный запрос не назовёшь кратким (как и задачу), но он решает проблему. Я уверен, что другие читатели смогут в комментариях предложить более короткие решения. Возможно, существенно более короткое решение есть для PostgreSQL, которая богата разными функциями.

Но, тем не менее, мы практически человеческим языком описали условия из задачи в SQL-запросы и получили правильный результат.

Использованный подход по самосоединению таблиц под разными псевдонимами, а потом с сужением области результатов условиями, позволяет эффективно решать различные переборные задачи.

© 2024 ООО «МТ ФИНАНС»

Telegram-канал со скидками, розыгрышами призов и новостями IT ?

Комментарии (31)

Suoriks
10.09.2024 13:15
#27272960
ChatGPT решает эту задачку с легкостью, но решение на SQL конечно интересное
1. inetstar Автор
  10.09.2024 13:15
  #27273046
  +3
  Можете прислать как конкретно ответила нейросеть?
  
  Я задал эту загадку Copilot (bing.com) и получил неверный ответ:
  
  Вот распределение драгоценностей по именам дам:
  
  Леди Уинслоу - Орден
  
  Доктор Марколла - Портсигар
  
  Графиня Конти - Перстень
  
  Мадам Нациу - Бриллиант
  
  Баронесса Финч - Кулон с птицей
  1. gotch
    10.09.2024 13:15
    #27273094
    +2
    
    Давайте разберёмся по порядку. У нас есть пять дам, каждая из которых одета в определённый цвет и имеет уникальную фамильную драгоценность. Используем информацию из условия и метод исключения для определения всех соответствий.
    
    Определим местоположение каждой дамы и цвет их одежды:
    
    Доктор Марколла сидит левее всех и рядом с гостьей в белом. Значит, у нас есть две дамы, сидящие на первом и втором местах. Поскольку она сидит левее всех, она на первой позиции.
    
    Дама в красном сидела слева от дамы в пурпурном. Это дает нам относительное расположение двух дам.
    
    Путешественница в зелёном только что покинула Морли. Это может помочь нам с местоположением.
    
    Графиня Конти пила абсент и предложила тост, а дама, которая пила сидр, собиралась посетить Серконос и упала на середину.
    
    Привяжем драгоценности к дамам:
    
    Портсигар был продемонстрирован одной дамой, а другая заметила, что её родной Морли славится такими вещами, значит Портсигар принадлежит даме из Морли.
    
    Баронесса Финч продемонстрировала Кулон с птицей. Значит, Кулон с птицей принадлежит Баронессе Финч.
    
    Дама, которая рассказывала о своём родном Фрейпорте, упоминала Перстень, значит, Перстень принадлежит даме из Фрейпорта.
    
    Бриллиант был продемонстрирован одной дамой, и другая дама, из Дануолла, почти уронила коктейль, значит, Бриллиант принадлежит даме, сидящей рядом с дамой из Дануолла.
    
    Разберём цвет одежды и драгоценности:
    
    Синяя одежда у леди Уинслоу.
    
    Дама в зелёном только что покинула Морли (это ещё раз подтверждает, что она не из Морли).
    
    Дама, которая сидела посередине, пролила ром, а Графиня Конти предложила тост, что указывает на то, что Графиня Конти не была в середине.
    
    Определение каждой дамы и драгоценности:
    
    Леди Уинслоу носила синее пончо, следовательно, её фамильная драгоценность не Портсигар, Орден или Бриллиант. Это может быть Перстень.
    
    Доктор Марколла была первой, сидящей левее, а ее драгоценность должна быть одна из оставшихся.
    
    Путешественница в зелёном (не из Морли) скорее всего с Орденом, так как у нас остался Портсигар и Бриллиант, и Графиня Конти уже пила абсент и не могла носить Бриллиант.
    
    Из оставшегося цвета, Портсигар должен принадлежать даме из Морли, а Бриллиант даме из Дануолла.
    
    Таким образом:
    
    Леди Уинслоу носит Перстень.
    
    Доктор Марколла, сидящая первой, носит Бриллиант.
    
    Графиня Конти, сидящая с абсентом, имеет Портсигар.
    
    Мадам Нациу, с её рассказом о Бейлтоне, носит Орден.
    
    Баронесса Финч носит Кулон с птицей.
    
    Эти выводы вытекают из анализа всех условий и указанных драгоценностей.
    
    Это ответ ChatGPT, честно говоря я его не понимаю )
    
    inetstar Автор
    10.09.2024 13:15
    #27273220
    Ответ верный, но в рассуждениях есть ошибки.
    
    Портсигар был продемонстрирован одной дамой, а другая заметила, что её родной Морли славится такими вещами, значит Портсигар принадлежит даме из Морли.
    
    Нет. Это значит только, что рядом с дамой с портсигаром сидела дама из Морли.
    
    Дама в зелёном только что покинула Морли (это ещё раз подтверждает, что она не из Морли).
    
    Это подтверждает, что она из Морли. Если это условие выкинуть вообще, так как, в теории, путешественница могла посещать вообще что угодно, то есть 7 вариантов решения задачи.
    
    Скрытый текст
    
    +------+----------+------------+-------+---------+----------+------+---------+------------+-------+---------+---------+------+---------+------------+-------+-------+----------+------+---------+------------+-------+---------+---------+------+---------+---------+--------+---------+----------+ | pos | name | item | color | drink | city | pos | name | item | color | drink | city | pos | name | item | color | drink | city | pos | name | item | color | drink | city | pos | name | item | color | drink | city | +------+----------+------------+-------+---------+----------+------+---------+------------+-------+---------+---------+------+---------+------------+-------+-------+----------+------+---------+------------+-------+---------+---------+------+---------+---------+--------+---------+----------+ | 1 | Marcolla | cigar-case | green | cider | Serkonos | 2 | Contee | order | white | absent | Morley | 3 | Winslow | ring | blue | rum | Freiport | 4 | Finch | coulomb | red | whiskey | Danuol | 5 | Natsiou | diamond | purple | coctail | Bailton | | 1 | Marcolla | order | green | cider | Serkonos | 2 | Natsiou | diamond | white | coctail | Bailton | 3 | Winslow | cigar-case | blue | rum | Danuol | 4 | Finch | coulomb | red | whiskey | Morley | 5 | Contee | ring | purple | absent | Freiport | | 1 | Marcolla | cigar-case | green | cider | Serkonos | 2 | Finch | coulomb | white | coctail | Morley | 3 | Winslow | order | blue | rum | Danuol | 4 | Natsiou | diamond | red | whiskey | Bailton | 5 | Contee | ring | purple | absent | Freiport | | 1 | Marcolla | order | green | cider | Serkonos | 2 | Finch | coulomb | white | coctail | Morley | 3 | Winslow | cigar-case | blue | rum | Danuol | 4 | Natsiou | diamond | red | whiskey | Bailton | 5 | Contee | ring | purple | absent | Freiport | | 1 | Marcolla | ring | green | coctail | Freiport | 2 | Contee | order | white | absent | Danuol | 3 | Winslow | diamond | blue | rum | Morley | 4 | Natsiou | cigar-case | red | whiskey | Bailton | 5 | Finch | coulomb | purple | cider | Serkonos | | 1 | Marcolla | ring | green | coctail | Freiport | 2 | Contee | cigar-case | white | absent | Danuol | 3 | Winslow | diamond | blue | rum | Morley | 4 | Natsiou | order | red | whiskey | Bailton | 5 | Finch | coulomb | purple | cider | Serkonos | | 1 | Marcolla | diamond | green | coctail | Morley | 2 | Contee | cigar-case | white | absent | Danuol | 3 | Winslow | ring | blue | rum | Freiport | 4 | Natsiou | order | red | whiskey | Bailton | 5 | Finch | coulomb | purple | cider | Serkonos | +------+----------+------------+-------+---------+----------+------+---------+------------+-------+---------+---------+------+---------+------------+-------+-------+----------+------+---------+------------+-------+---------+---------+------+---------+---------+--------+---------+----------+ 7 rows in set (0.04 sec)
    
    Рассуждения сомнительные, однако ответ верный.
    
    alhimik45
    10.09.2024 13:15
    #27273394
    +4
    Возможно эта задача просто была в обучающей выборке, так как её на каких-нибудь игровых форумах разжёвывали
    
    inetstar Автор
    10.09.2024 13:15
    #27273432
    +1
    Да, её разжёвывали множество раз в сети.
    
    gotch
    10.09.2024 13:15
    #27282268
    Пусть ее разжевывали много раз в сети. Но ведь игра каждый раз выдает новый вариант задачи, и задачу с условиями в точности как у вас я не нашел (может плохо искал, конечно).
    
    inetstar Автор
    10.09.2024 13:15
    #27282320
    В одном из разжёвываний был сказан очень простой алгоритм, где думать вообще не требуется. Но опять таки, я не гуглил решения этой загадки на английском.
    
    Думаю, всё-таки как-то ChatGPT решила загадку, но вот если придумать аналогичные, то не факт, что справится.
    
    gotch
    10.09.2024 13:15
    #27273666
    Да это как раз то, что привело меня в замешательство, очевидно неверные выводы и правильное общее решение.

firstmixon
10.09.2024 13:15
#27273100
+2
Это старая задача, и уже описывалась, там вопрос кто живет в доме(цветном), не помню в каком, тут же на сайте было ее решение при помощи SQL

задача Эйнштейна

http://akmych.org/various/einstein.html
1. inetstar Автор
  10.09.2024 13:15
  #27273298
  +3
  На Хабре решения головоломки Эйнштейна на SQL я не нашёл. С трудом я нашел то, о чём вы говорите.
  
  IMHO, моё решение короче, элегантнее и содержит меньше условий, но суть похожа.

artptr86
10.09.2024 13:15
#27273122
+1
В статье https://dkalemis.wordpress.com/2014/08/23/using-sql-server-to-solve-einsteins-puzzles/ использован другой подход: создаётся временная таблица со всеми возможными комбинациями, а затем последовательно удаляются все неподходящие под условия задачи строки. В результате остаются только строки, соответствующие решению.
1. inetstar Автор
  10.09.2024 13:15
  #27273240
  +2
  В общем случае, это плохой подход, так как вариантов может быть настолько много, что не хватит всех жёстких дисков мира, чтобы создать все комбинации.
  
  И этот вариант головоломки Эйнштейна не включает относительное местоположение, что заметно упрощает её, в сравнении с задачей Джиндоша.
  1. artptr86
    10.09.2024 13:15
    #27273486
    +1
    Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций. Для задачи про 5 участников с 5 атрибутами для каждого получается 5^5=3125 комбинаций, для 6^6=46656 комбинаций. Уже задача 10x10 даёт 10 млрд комбинаций, что, впрочем, по силам для хранения в БД на диске.
    
    А неявный джойн с ограничениями будет решать задачу эффективнее?
    
    inetstar Автор
    10.09.2024 13:15
    #27273604
    +1
    С помощью ограничений мы сжимаем задачу всего лишь до 80 вариантов, что есть в статье.
    
    Без этого можно столкнуться с тем, что таблицу с 5^5 строк нам придётся джойнить саму к себе, что даст гораздо больше вариантов, а именно (5^5=3125)^5, что сильно меньше, чем 80^5.
    
    А без этого второго джойна будет трудно обработать условия относительного местоположения.
    
    В похожей задачке человек обошёлся одним мегаджойном, который без учёта условий тоже даёт (5^5)^5 строк. Я значительно облегчил работу планировщику запросов, а он отдал всю оптимизацию на откуп планировщику. SQL Server справился (не знаю за какое время), MySQL сделал это по моей технике за время меньшее миллисекунды.
    
    А явный или неявный джойн - это значения не имеет.
    
    HardWrMan
    10.09.2024 13:15
    #27274016
    Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций.
    
    Так вроде вариантов сильно меньше же. Ведь все атрибуты должны быть использованы и каждый только 1 раз, а результат - лишь их порядок (каждому обладателю атрибута присвоим порядковый номер). А значит это обычный факториал. Для 5 атрибутов "всего" 120 вариантов.
    
    artptr86
    10.09.2024 13:15
    #27274054
    На этапе джойна всё-таки будет декартово произведение

asmm

10.09.2024 13:15

#27274828

WITH Positions(pos) AS (
    VALUES ROW(1), ROW(2), ROW(3), ROW(4), ROW(5)
)
, Names(name) AS (
    VALUES ROW('Winslow'), ROW('Marcolla'), ROW('Contee'), ROW('Natsiou'), ROW('Finch')
)
, Colors(color) AS (
    VALUES ROW('red'), ROW('white'), ROW('purple'), ROW('blue'), ROW('green')
)
, Cities(city) AS (
    VALUES ROW('Bailton'), ROW('Serkonos'), ROW('Freiport'), ROW('Morley'), ROW('Danuol')
)
, Drinks(drink) AS (
    VALUES ROW('absent'), ROW('coctail'), ROW('rum'), ROW('cider'), ROW('whiskey')
)
, Items(item) AS (
    VALUES ROW('ring'), ROW('diamond'), ROW('order'), ROW('cigar-case'), ROW('coulomb')
)
, s AS (
    SELECT DISTINCT *
    FROM Positions, Names, Items, Colors, Drinks, Cities
    WHERE ((name='Winslow' AND color = 'blue') OR (name!='Winslow' AND color != 'blue'))
    AND
    ((name='Marcolla' AND pos = 1) OR (name!='Marcolla' AND pos != 1))
    AND
    ((color='white' AND pos = 2) OR (color!='white' AND pos != 2))
    AND
    ((color='red' AND drink = 'whiskey') OR (color!='red' AND drink != 'whiskey'))
    AND
    ((city='Morley' AND color = 'green') OR (city!='Morley' AND color != 'green'))
    AND
    ((name='Finch' AND item = 'coulomb') OR (name!='Finch' AND item != 'coulomb'))
    AND
    ((city='Freiport' AND item = 'ring') OR (city!='Freiport' AND item != 'ring'))
    AND
    ((name='Contee' AND drink = 'absent') OR (name!='Contee' AND drink != 'absent'))
    AND
    ((city='Serkonos' AND drink = 'cider') OR (city!='Serkonos' AND drink != 'cider'))
    AND
    ((pos=3 AND drink = 'rum') OR (pos!=3 AND drink != 'rum'))
    AND
    ((name='Natsiou' AND city = 'Bailton') OR (name!='Natsiou' AND city != 'Bailton'))
)
SELECT t1.name, t1.item, t2.name, t2.item, t3.name, t3.item, t4.name, t4.item, t5.name, t5.item
FROM s t1
JOIN s t2 ON t2.name != t1.name AND t2.item != t1.item AND t2.color != t1.color AND t2.drink != t1.drink AND t2.city != t1.city
JOIN s t3 ON t3.name NOT IN (t1.name, t2.name)
  AND t3.item NOT IN (t1.item, t2.item)
  AND t3.color NOT IN (t1.color, t2.color)
  AND t3.drink NOT IN (t1.drink, t2.drink)
  AND t3.city NOT IN (t1.city, t2.city)
JOIN s t4 ON t4.name NOT IN (t1.name, t2.name, t3.name)
 AND t4.item NOT IN (t1.item, t2.item, t3.item)
 AND t4.color NOT IN (t1.color, t2.color, t3.color)
 AND t4.drink NOT IN (t1.drink, t2.drink, t3.drink)
 AND t4.city NOT IN (t1.city, t2.city, t3.city)
JOIN s t5 ON t5.name NOT IN (t1.name, t2.name, t3.name, t4.name)
 AND t5.item NOT IN (t1.item, t2.item, t3.item, t4.item)
 AND t5.color NOT IN (t1.color, t2.color, t3.color, t4.color)
 AND t5.drink NOT IN (t1.drink, t2.drink, t3.drink, t4.drink)
 AND t5.city NOT IN (t1.city, t2.city, t3.city, t4.city)
WHERE
-- Мы хотим вывести дам в том порядке, в котором они сидели
t1.pos = 1 AND t2.pos=2 AND t3.pos = 3 AND t4.pos=4 AND t5.pos=5
-- Дама в красном сидит левее дамы в пурпурном, но место 2 занято дамой в белом, поэтому остаются места 3 и 4
AND (
   (t3.color='red' AND t4.color='purple' ) OR (t4.color='red' AND t5.color='purple')
 )
-- Рядом с дамой с портсигаром сидит дама из Морли
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')
 )
-- Рядом с дамой с бриллиантом сидит дама из Дануолл
AND
 (
   (t1.item='diamond' AND t2.city='Danuol') OR
   (t2.item='diamond' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.item='diamond' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.item='diamond' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.item='diamond' AND t4.city='Danuol')
 )
-- Рядом с дамой из Дануолла другая дама пила коктейль
AND
 (
   (t1.drink='coctail' AND t2.city='Danuol') OR
   (t2.drink='coctail' AND 'Danuol' IN (t1.city, t3.city)) OR
   (t3.drink='coctail' AND 'Danuol' IN (t2.city, t4.city)) OR
   (t4.drink='coctail' AND 'Danuol' IN (t3.city, t5.city)) OR
   (t5.drink='coctail' AND t4.city='Danuol')
 )

MySQL 8, 1.81ms

EXPLAIN ANALYZE
....
-> Filter: ((((t4.color = 'purple') ........city))) (cost=852 rows=0.0682) (actual time=1.81..1.82 rows=1 loops=1)

inetstar Автор
10.09.2024 13:15
#27274940
Отлично! Удивительно, почему планировщик MySQL не смог справиться с запросом, когда использовались реальные таблицы... Есть идеи?

inetstar Автор
10.09.2024 13:15
#27276738
Добавил информацию в статью об этом способе со ссылкой на вас и ваш комментарий.

Kahelman
10.09.2024 13:15
#27275226
+1
Месье знает толк в извращениях :)
Следующий шаг переписать чат ГПТ на sql.
:)

Kasheftin
10.09.2024 13:15
#27275772
+2
Можно ли убрать какое-нибудь условие из задачи так, чтобы решение было все еще единственным?
1. AxelLx
  10.09.2024 13:15
  #27277670
  +9
  Можно.
  
  Условие "женщина из Даунолла сидела рядом с женщиной, пившей коктейль" -- избыточно.
  1. inetstar Автор
    10.09.2024 13:15
    #27277824
    Браво! Хотел поднять вам карму, но без статей выше 4х Хабр не разрешает.
  1. Kasheftin
    10.09.2024 13:15
    #27285306
    Как доказать, что теперь набор условий минимальный (кроме перебора)?
    
    AxelLx
    10.09.2024 13:15
    #27285336
    А чем вас перебор не устраивает?
    
    Выкидываем каждое условие по очереди, находим как минимум два возможных решения. Следовательно, все условия необходимы.
    
    Если запрос уже написан - на каждом шаге достаточно закомментировать кусок кода.
    
    Kasheftin
    10.09.2024 13:15
    #27285480
    Возможно, но интересно получить минимальный набор условий алгоритмически. В студенчестве баловался с sql и судоку. Вроде работало для 6x6. Идея та же, что в данной статье - загрузить все возможные комбинации, а потом выбирать по условиям. Очевидно, такую систему можно использовать для обратной задачи: выбираем случайный квадрат, и начинаем убирать из него случайные цифры до тех пор, пока остается единственное решение. У меня получались задачи с очень малым количеством условий и единственным решением, к которым было вообще непонятно как подступиться с точки зрения традиционного судоку (ни одна из стандартных проверок не срабатывала, можно было только ставить случайную цифру, пытаться решить, а в случае неудачи откатываться).

Badtoro

10.09.2024 13:15

#27282554

В копилку, отличная задача для теста на собеседованиях ))
Мой вариант работает на postgresql:

WITH RECURSIVE
	serie(i) AS (SELECT generate_series (1, 5)),
	permutate AS (SELECT ARRAY[i] p FROM serie UNION ALL SELECT p || i FROM permutate, serie WHERE i<>ALL(p)),
	permatations AS (SELECT p FROM permutate WHERE array_length(p, 1)=5),
	names(Winslow, Marcolla, Contee, Natsiou, Finch) AS (SELECT p[1], p[2], p[3], p[4], p[5] FROM permatations),
	colors(blue, white, red, purple, green) AS (SELECT p[1], p[2], p[3], p[4], p[5] FROM permatations),
	homelands(Morley, Fraeport, Dunwall, Serkonos, Bailton) AS (SELECT p[1], p[2], p[3], p[4], p[5] FROM permatations),
	drinks(whiskey, coctail, absinthe, cider, rum) AS (SELECT p[1], p[2], p[3], p[4], p[5] FROM permatations),
	items(cigar_case, pendant, ring, diamond, medallion) AS (SELECT p[1], p[2], p[3], p[4], p[5] FROM permatations),
	matching AS (
		SELECT ROW_NUMBER() OVER () solution_no, * FROM names, colors, homelands, drinks, items
		WHERE Winslow = blue
		  AND Marcolla = 1
		  AND Marcolla+1 = white
		  AND red = purple-1
		  AND red = whiskey
		  AND Morley = green
		  AND cigar_case IN (Morley-1, Morley+1)
		  AND Finch = pendant
		  AND Fraeport = ring
		  AND diamond IN (Dunwall-1, Dunwall+1)
		  AND coctail IN (Dunwall-1, Dunwall+1)
		  AND Contee = absinthe
		  AND Serkonos = cider
		  AND rum = 3
		  AND Natsiou = Bailton
	)
--в принципе, задача уже решена, дальнейший код для наглядного вывода результата
SELECT solution_no, value chair, string_agg(KEY, ', ') FROM matching
JOIN LATERAL json_each_text(row_to_json(matching.*)) name_pair ON key<>'solution_no'
GROUP BY solution_no, value
ORDER BY solution_no, value

Основная идея, что по каждому из признаков (имя, цвет, предмет...) имеем 120 перестановок, а общее количество комбинаций 120^5. Создаём таблицу перестановок для каждого признака, "перемножаем" их, получаем общую таблицу на 20kkk строк. Колонки - значения признаков (Конти, синий, портсигар ...), в ячейках - номер стула. Дальше условия отбора сводятся к сравнению номера стула: Уинслоу = синий, красный = виски, ром = 3... Коротко и наглядно

inetstar Автор
10.09.2024 13:15
#27282804
Спасибо за краткое оригинальное решение.
Но!
IMHO условия крайне ненаглядные. Сравниваются яблоки с апельсинами.
```
Winslow = blue
		  AND Marcolla+1 = white
		  AND red = whiskey
		  AND Morley = green
		  AND cigar_case IN (Morley-1, Morley+1)
		  AND Finch = pendant
		  AND Fraeport = ring
```

Kilor
10.09.2024 13:15
#27282972
+2
Для комментария получилось многовато, оформил альтернативный вариант постом.
1. inetstar Автор
  10.09.2024 13:15
  #27283468
  Похоже по оригинальности решения вы превзошли всех!

Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом +73

Загадка Джиндоша

Подход к решению

Решаем загадку

▍ Структуры данных

▍ Соединяем таблицы для создания всех возможных вариантов

▍ Добавляем условия для минимизации числа вариантов

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

▍ Добавляем условия, связанные с относительным расположением дам на банкете

Решение головоломки

ИТОГИ

Комментарии (31)

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор

inetstar Автор