Комментарии 38
ChatGPT решает эту задачку с легкостью, но решение на SQL конечно интересное
Можете прислать как конкретно ответила нейросеть?
Я задал эту загадку Copilot (bing.com) и получил неверный ответ:
Вот распределение драгоценностей по именам дам:
Леди Уинслоу - Орден
Доктор Марколла - Портсигар
Графиня Конти - Перстень
Мадам Нациу - Бриллиант
Баронесса Финч - Кулон с птицей
Давайте разберёмся по порядку. У нас есть пять дам, каждая из которых одета в определённый цвет и имеет уникальную фамильную драгоценность. Используем информацию из условия и метод исключения для определения всех соответствий.
Определим местоположение каждой дамы и цвет их одежды:
Доктор Марколла сидит левее всех и рядом с гостьей в белом. Значит, у нас есть две дамы, сидящие на первом и втором местах. Поскольку она сидит левее всех, она на первой позиции.
Дама в красном сидела слева от дамы в пурпурном. Это дает нам относительное расположение двух дам.
Путешественница в зелёном только что покинула Морли. Это может помочь нам с местоположением.
Графиня Конти пила абсент и предложила тост, а дама, которая пила сидр, собиралась посетить Серконос и упала на середину.
Привяжем драгоценности к дамам:
Портсигар был продемонстрирован одной дамой, а другая заметила, что её родной Морли славится такими вещами, значит Портсигар принадлежит даме из Морли.
Баронесса Финч продемонстрировала Кулон с птицей. Значит, Кулон с птицей принадлежит Баронессе Финч.
Дама, которая рассказывала о своём родном Фрейпорте, упоминала Перстень, значит, Перстень принадлежит даме из Фрейпорта.
Бриллиант был продемонстрирован одной дамой, и другая дама, из Дануолла, почти уронила коктейль, значит, Бриллиант принадлежит даме, сидящей рядом с дамой из Дануолла.
Разберём цвет одежды и драгоценности:
Синяя одежда у леди Уинслоу.
Дама в зелёном только что покинула Морли (это ещё раз подтверждает, что она не из Морли).
Дама, которая сидела посередине, пролила ром, а Графиня Конти предложила тост, что указывает на то, что Графиня Конти не была в середине.
Определение каждой дамы и драгоценности:
Леди Уинслоу носила синее пончо, следовательно, её фамильная драгоценность не Портсигар, Орден или Бриллиант. Это может быть Перстень.
Доктор Марколла была первой, сидящей левее, а ее драгоценность должна быть одна из оставшихся.
Путешественница в зелёном (не из Морли) скорее всего с Орденом, так как у нас остался Портсигар и Бриллиант, и Графиня Конти уже пила абсент и не могла носить Бриллиант.
Из оставшегося цвета, Портсигар должен принадлежать даме из Морли, а Бриллиант даме из Дануолла.
Таким образом:
Леди Уинслоу носит Перстень.
Доктор Марколла, сидящая первой, носит Бриллиант.
Графиня Конти, сидящая с абсентом, имеет Портсигар.
Мадам Нациу, с её рассказом о Бейлтоне, носит Орден.
Баронесса Финч носит Кулон с птицей.
Эти выводы вытекают из анализа всех условий и указанных драгоценностей.
Это ответ ChatGPT, честно говоря я его не понимаю )
Ответ верный, но в рассуждениях есть ошибки.
Портсигар был продемонстрирован одной дамой, а другая заметила, что её родной Морли славится такими вещами, значит Портсигар принадлежит даме из Морли.
Нет. Это значит только, что рядом с дамой с портсигаром сидела дама из Морли.
Дама в зелёном только что покинула Морли (это ещё раз подтверждает, что она не из Морли).
Это подтверждает, что она из Морли. Если это условие выкинуть вообще, так как, в теории, путешественница могла посещать вообще что угодно, то есть 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)
Рассуждения сомнительные, однако ответ верный.
Возможно эта задача просто была в обучающей выборке, так как её на каких-нибудь игровых форумах разжёвывали
Да, её разжёвывали множество раз в сети.
Пусть ее разжевывали много раз в сети. Но ведь игра каждый раз выдает новый вариант задачи, и задачу с условиями в точности как у вас я не нашел (может плохо искал, конечно).
В одном из разжёвываний был сказан очень простой алгоритм, где думать вообще не требуется. Но опять таки, я не гуглил решения этой загадки на английском.
Думаю, всё-таки как-то ChatGPT решила загадку, но вот если придумать аналогичные, то не факт, что справится.
Да это как раз то, что привело меня в замешательство, очевидно неверные выводы и правильное общее решение.
Это какая версия выдала правильный ответ?
Новенькая GPT o1 не смогла решить эту загадку с нескольких попыток)
Чтобы решить эту загадку, давайте систематизируем всю информацию:
Персонажи:
Леди Уинслоу
Доктор Марколла
Графиня Конти
Мадам Нациу
Баронесса Финч
Цвета одежды:
Синий (Леди Уинслоу)
Белый
Красный
Пурпурный
Зелёный
Фамильные драгоценности:
Портсигар
Кулон с птицей (Баронесса Финч)
Перстень
Бриллиант
Орден
Напитки:
Виски
Абсент (Графиня Конти)
Сидр
Ром
Коктейль
Места за столом (слева направо):
Доктор Марколла (левее всех)
Гостья в белом
Гостья в зелёном (путешественница, недавно покинувшая Морли)
Гостья в красном
Гостья в пурпурном
Выводы:
Доктор Марколла сидит на первом месте и владеет портсигаром.
Гостья в белом (второе место) — Графиня Конти, пьёт сидр, собирается посетить Серконос, владеет перстнем.
Леди Уинслоу сидит посередине, носит синий пончо, пьёт ром, владеет бриллиантом.
Мадам Нациу сидит на четвёртом месте, носит красное платье, пьёт виски, владеет орденом.
Баронесса Финч сидит на пятом месте, носит пурпурное, пьёт коктейль, владеет кулоном с птицей (который не был найден под столом).
Ответ:
Доктор Марколла — владелица портсигара.
Графиня Конти — владелица перстня.
Леди Уинслоу — владелица бриллианта.
Мадам Нациу — владелица ордена.
Это старая задача, и уже описывалась, там вопрос кто живет в доме(цветном), не помню в каком, тут же на сайте было ее решение при помощи SQL
задача Эйнштейна
http://akmych.org/various/einstein.html
На Хабре решения головоломки Эйнштейна на SQL я не нашёл. С трудом я нашел то, о чём вы говорите.
IMHO, моё решение короче, элегантнее и содержит меньше условий, но суть похожа.
В статье https://dkalemis.wordpress.com/2014/08/23/using-sql-server-to-solve-einsteins-puzzles/ использован другой подход: создаётся временная таблица со всеми возможными комбинациями, а затем последовательно удаляются все неподходящие под условия задачи строки. В результате остаются только строки, соответствующие решению.
В общем случае, это плохой подход, так как вариантов может быть настолько много, что не хватит всех жёстких дисков мира, чтобы создать все комбинации.
И этот вариант головоломки Эйнштейна не включает относительное местоположение, что заметно упрощает её, в сравнении с задачей Джиндоша.
Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций. Для задачи про 5 участников с 5 атрибутами для каждого получается 5^5=3125 комбинаций, для 6^6=46656 комбинаций. Уже задача 10x10 даёт 10 млрд комбинаций, что, впрочем, по силам для хранения в БД на диске.
А неявный джойн с ограничениями будет решать задачу эффективнее?
С помощью ограничений мы сжимаем задачу всего лишь до 80 вариантов, что есть в статье.
Без этого можно столкнуться с тем, что таблицу с 5^5 строк нам придётся джойнить саму к себе, что даст гораздо больше вариантов, а именно (5^5=3125)^5, что сильно меньше, чем 80^5.
А без этого второго джойна будет трудно обработать условия относительного местоположения.
В похожей задачке человек обошёлся одним мегаджойном, который без учёта условий тоже даёт (5^5)^5 строк. Я значительно облегчил работу планировщику запросов, а он отдал всю оптимизацию на откуп планировщику. SQL Server справился (не знаю за какое время), MySQL сделал это по моей технике за время меньшее миллисекунды.
А явный или неявный джойн - это значения не имеет.
Обычно задача формулируется так, что получается матрица n*n, то есть возможно n^n комбинаций.
Так вроде вариантов сильно меньше же. Ведь все атрибуты должны быть использованы и каждый только 1 раз, а результат - лишь их порядок (каждому обладателю атрибута присвоим порядковый номер). А значит это обычный факториал. Для 5 атрибутов "всего" 120 вариантов.
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)
Месье знает толк в извращениях :)
Следующий шаг переписать чат ГПТ на sql.
:)
Можно ли убрать какое-нибудь условие из задачи так, чтобы решение было все еще единственным?
Можно.
Условие "женщина из Даунолла сидела рядом с женщиной, пившей коктейль" -- избыточно.
Браво! Хотел поднять вам карму, но без статей выше 4х Хабр не разрешает.
Как доказать, что теперь набор условий минимальный (кроме перебора)?
А чем вас перебор не устраивает?
Выкидываем каждое условие по очереди, находим как минимум два возможных решения. Следовательно, все условия необходимы.
Если запрос уже написан - на каждом шаге достаточно закомментировать кусок кода.
Возможно, но интересно получить минимальный набор условий алгоритмически. В студенчестве баловался с sql и судоку. Вроде работало для 6x6. Идея та же, что в данной статье - загрузить все возможные комбинации, а потом выбирать по условиям. Очевидно, такую систему можно использовать для обратной задачи: выбираем случайный квадрат, и начинаем убирать из него случайные цифры до тех пор, пока остается единственное решение. У меня получались задачи с очень малым количеством условий и единственным решением, к которым было вообще непонятно как подступиться с точки зрения традиционного судоку (ни одна из стандартных проверок не срабатывала, можно было только ставить случайную цифру, пытаться решить, а в случае неудачи откатываться).
В копилку, отличная задача для теста на собеседованиях ))
Мой вариант работает на 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... Коротко и наглядно
Для комментария получилось многовато, оформил альтернативный вариант постом.
интересные конечно гримасы у перевода, в игре города - Fraeport, Dunwall, Baleton, Dabokva, Karnaca, а Morley и Serkonos - острова.
интересные конечно гримасы у перевода, в игре города - Fraeport, Dunwall, Baleton, Dabokva, Karnaca, а Morley и Serkonos - острова.
Такое лучше решать с помощью SMT солвера, а не SQL. Например, z3.
@inetstarнасколько я помню, что позиционка в игре не играет роли, эти данные даны только за тем, чтобы логически решить задачу.
По итогу на двери важно выставить верные связки дама-предмет, в ЛЮБОМ порядке.
Решаем загадку Джиндоша из Dishonored 2 на SQL перебором с возвратом