10.09.2024 13:01
inetstar 15 1800 Источник


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:

  1. city='Morley' AND color = 'green'
  2. 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 он отработает быстро.

Полный текст всех запросов для 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 ?

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


  1. Suoriks
    10.09.2024 13:15
    #27272960

    ChatGPT решает эту задачку с легкостью, но решение на SQL конечно интересное


    1. inetstar Автор
      10.09.2024 13:15
      #27273046
      +1

      Можете прислать как конкретно ответила нейросеть?

      Я задал эту загадку Copilot (bing.com) и получил неверный ответ:

      Вот распределение драгоценностей по именам дам:

      1. Леди Уинслоу - Орден

      2. Доктор Марколла - Портсигар

      3. Графиня Конти - Перстень

      4. Мадам Нациу - Бриллиант

      5. Баронесса Финч - Кулон с птицей


      1. gotch
        10.09.2024 13:15
        #27273094
        +1

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

        Определим местоположение каждой дамы и цвет их одежды:

        Доктор Марколла сидит левее всех и рядом с гостьей в белом. Значит, у нас есть две дамы, сидящие на первом и втором местах. Поскольку она сидит левее всех, она на первой позиции.

        Дама в красном сидела слева от дамы в пурпурном. Это дает нам относительное расположение двух дам.

        Путешественница в зелёном только что покинула Морли. Это может помочь нам с местоположением.

        Графиня Конти пила абсент и предложила тост, а дама, которая пила сидр, собиралась посетить Серконос и упала на середину.

        Привяжем драгоценности к дамам:

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

        Баронесса Финч продемонстрировала Кулон с птицей. Значит, Кулон с птицей принадлежит Баронессе Финч.

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

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

        Разберём цвет одежды и драгоценности:

        Синяя одежда у леди Уинслоу.

        Дама в зелёном только что покинула Морли (это ещё раз подтверждает, что она не из Морли).

        Дама, которая сидела посередине, пролила ром, а Графиня Конти предложила тост, что указывает на то, что Графиня Конти не была в середине.

        Определение каждой дамы и драгоценности:

        Леди Уинслоу носила синее пончо, следовательно, её фамильная драгоценность не Портсигар, Орден или Бриллиант. Это может быть Перстень.

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

        Путешественница в зелёном (не из Морли) скорее всего с Орденом, так как у нас остался Портсигар и Бриллиант, и Графиня Конти уже пила абсент и не могла носить Бриллиант.

        Из оставшегося цвета, Портсигар должен принадлежать даме из Морли, а Бриллиант даме из Дануолла.

        Таким образом:

        Леди Уинслоу носит Перстень.

        Доктор Марколла, сидящая первой, носит Бриллиант.

        Графиня Конти, сидящая с абсентом, имеет Портсигар.

        Мадам Нациу, с её рассказом о Бейлтоне, носит Орден.

        Баронесса Финч носит Кулон с птицей.

        Эти выводы вытекают из анализа всех условий и указанных драгоценностей.

        Это ответ ChatGPT, честно говоря я его не понимаю )


        1. 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)

          Рассуждения сомнительные, однако ответ верный.


          1. alhimik45
            10.09.2024 13:15
            #27273394
            +1

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


            1. inetstar Автор
              10.09.2024 13:15
              #27273432

              Да, её разжёвывали множество раз в сети.


          1. gotch
            10.09.2024 13:15
            #27273666

            Да это как раз то, что привело меня в замешательство, очевидно неверные выводы и правильное общее решение.


  1. firstmixon
    10.09.2024 13:15
    #27273100

    Это старая задача, и уже описывалась, там вопрос кто живет в доме(цветном), не помню в каком, тут же на сайте было ее решение при помощи SQL

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

    http://akmych.org/various/einstein.html


    1. inetstar Автор
      10.09.2024 13:15
      #27273298
      +2

      На Хабре решения головоломки Эйнштейна на SQL я не нашёл. С трудом я нашел то, о чём вы говорите.

      IMHO, моё решение короче, элегантнее и содержит меньше условий, но суть похожа.


  1. artptr86
    10.09.2024 13:15
    #27273122

    В статье https://dkalemis.wordpress.com/2014/08/23/using-sql-server-to-solve-einsteins-puzzles/ использован другой подход: создаётся временная таблица со всеми возможными комбинациями, а затем последовательно удаляются все неподходящие под условия задачи строки. В результате остаются только строки, соответствующие решению.


    1. inetstar Автор
      10.09.2024 13:15
      #27273240
      +1

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

      И этот вариант головоломки Эйнштейна не включает относительное местоположение, что заметно упрощает её, в сравнении с задачей Джиндоша.


      1. artptr86
        10.09.2024 13:15
        #27273486

        Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций. Для задачи про 5 участников с 5 атрибутами для каждого получается 5^5=3125 комбинаций, для 6^6=46656 комбинаций. Уже задача 10x10 даёт 10 млрд комбинаций, что, впрочем, по силам для хранения в БД на диске.

        А неявный джойн с ограничениями будет решать задачу эффективнее?


        1. inetstar Автор
          10.09.2024 13:15
          #27273604

          С помощью ограничений мы сжимаем задачу всего лишь до 80 вариантов, что есть в статье.

          Без этого можно столкнуться с тем, что таблицу с 5^5 строк нам придётся джойнить саму к себе, что даст гораздо больше вариантов, а именно (5^5=3125)^5, что сильно меньше, чем 80^5.

          А без этого второго джойна будет трудно обработать условия относительного местоположения.

          В похожей задачке человек обошёлся одним мегаджойном, который без учёта условий тоже даёт (5^5)^5 строк. Я значительно облегчил работу планировщику запросов, а он отдал всю оптимизацию на откуп планировщику. SQL Server справился (не знаю за какое время), MySQL сделал это по моей технике за время меньшее миллисекунды.

          А явный или неявный джойн - это значения не имеет.


        1. HardWrMan
          10.09.2024 13:15
          #27274016

          Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций.

          Так вроде вариантов сильно меньше же. Ведь все атрибуты должны быть использованы и каждый только 1 раз, а результат - лишь их порядок (каждому обладателю атрибута присвоим порядковый номер). А значит это обычный факториал. Для 5 атрибутов "всего" 120 вариантов.


          1. artptr86
            10.09.2024 13:15
            #27274054

            На этапе джойна всё-таки будет декартово произведение