Решаем загадку Джиндоша на SQL в пять строчек

В недавней статье обсуждалось решение логической задачи с помощью SQL.

Решение было правильным, но сам запрос получился очень громоздким, с большим количеством копипаста.

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

Для решения я буду использовать БД Oracle 19c, но аналогичный запрос с минимальными изменениями можно написать на любом другом диалекте SQL. Приступим.

Подготовка данных

Зачастую правильный выбор структуры данных позволяет значительно упростить алгоритм. В данном случае это весьма актуально.

Пронумеруем все позиции за столом числами от 1 до 5 и составим все возможные перестановки этих 5 чисел:

with positions as (
        select level id from dual connect by level <= 5),
     permutations as (
	    select p1.id a, p2.id b, p3.id c, p4.id d, p5.id e
        from positions p1, positions p2, positions p3, positions p4, positions p5
        where p1.id <> p2.id and p1.id <> p3.id and p1.id <> p4.id and p1.id <> p5.id and
                                 p2.id <> p3.id and p2.id <> p4.id and p2.id <> p5.id and
                                                    p3.id <> p4.id and p3.id <> p5.id and
                                                                       p4.id <> p5.id),

Результат. Тут нет ничего сложного, мы используем CTE чтобы хранить все данные в памяти и не заводить лишних таблиц, а оператор connect by -- чтобы получить набор чисел.

Теперь опишем все остальные признаки (дам, цвета, города, напитки и ценности). В оригинальной статье для каждого признака заводилась таблица с одной колонкой и пятью строками, в которые писалось значение признака. Мы поступим иначе: для каждого признака заведём таблицу из пяти колонок. Название колонки будет соответствовать значению признака, а значение в этой колонке - позиции за столом:

     Names as (
	    select a Winslow, b Marcolla, c Contee, d Natsiou, e Finch from permutations),
     Colors as (
	    select a red, b white, c purple, d blue, e green from permutations),
     Cities as (
	    select a Bailton, b Serkonos, c Freiport, d Morley, e Danuol from permutations),
     Drinks as (
	    select a absent, b coctail, c rum, d cider, e whiskey from permutations),
     Items as (
	    select a ring, b diamond, c medal, d cigarcase, e coulomb from permutations),

Результат. Обратите внимание, в каждой таблице будет 120 строк, по числу перестановок.

На этом подготовка данных закончена, настало время описать условия отбора. Если у вас есть немного свободного времени и желания поработать головой - переходите по ссылке и попробуйте написать условия самостоятельно. Результат должен вам понравиться. Если же времени/желания нет - переходите к следующему разделу.

Описание логики

Посмотрим на первое условие:

Леди Уинслоу носила причудливое синее пончо

Как для каждой перестановки дам получить номер позиции леди Уинслоу? Элементарно, select Winslow from Names.

Как для каждой перестановки цветов одежды получить номер позиции синего пончо? Элементарно, select blue from Colors.

Перефразируем условие: дама с фамилией Уинслоу находится на той же позиции, что дама в синем пончо. Как нам получить все такие перестановки? Элементарно, select * from Names, Colors where Winslow = blue.

Посмотрим второе условие:

Доктор Марколла левее всех

Марколла находится на позиции с номером 1, select * from Names where Marcolla = 1.

Доктор Марколла левее всех, рядом с гостьей, одетой в белое

Из этой фразы мы можем сделать вывод, что дама в белом находится на позиции с номером 2. Можем, но не будем! Это логический вывод из двух посылок. Нам рассуждениями заниматься не надо, вместо нас это сделает БД. Мы просто запишем условие о том, что доктор Марколла сидела рядом с дамой в белом. Номера их позиций отличаются на 1: select * from Names, Colors where abs(Marcolla - white) = 1.

Все остальные условия описываются аналогично. Соберём всё вместе:

     solution as ( 
	    select *
        from Names, Colors, Cities, Drinks, Items
        where Winslow = blue and Marcolla = 1 and abs(Marcolla - white) = 1 and
              red + 1 = purple and red = whiskey and Morley = green and
              abs(cigarcase - Morley) = 1 and Finch = coulomb and Freiport = ring and
              abs(diamond - Danuol) = 1 and abs(Danuol - coctail) = 1 and Contee = absent and
              Serkonos = cider and rum = 3 and Natsiou = Bailton)

Пять строчек логики, как я и обещал. Результат -- одна строчка, а значит решение единственно.

Заключение

Осталось красиво оформить ответ:

select id as position,
       case id
            when Winslow then 'Winslow'
            when Marcolla then 'Marcolla'
            when Contee then 'Contee'
            when Natsiou then 'Natsiou'
            when Finch then 'Finch'
          end as Name,
       case id
            when red then 'red'
            when white then 'white'
            when purple then 'purple'
            when blue then 'blue'
            when green then 'green'
          end as Color,
       case id
            when Bailton then 'Bailton'
            when Serkonos then 'Serkonos'
            when Freiport then 'Freiport'
            when Morley then 'Morley'
            when Danuol then 'Danuol'
          end as City,
       case id
            when absent then 'absent'
            when coctail then 'coctail'
            when rum then 'rum'
            when cider then 'cider'
            when whiskey then 'whiskey'
          end as Drink,
       case id
            when ring then 'ring'
            when diamond then 'diamond'
            when medal then 'medal'
            when cigarcase then 'cigarcase'
            when coulomb then 'coulomb'
          end as Item
from positions, solution
order by id

Интересно, можно ли сократить этот код PIVOT'ом?

Запрос и результат целиком доступны по ссылке. Перебор 2,5x10¹⁰ вариантов занимает доли секунды:

Исходная статья размещена в хабе "Ненормальное программирование". Я считаю это не совсем корректным. Декларативный язык программирования SQL идеально подходит для решения подобных задач.