Наприкінці книги Гаррі Поттер і філософський камінь є цікава загадка. Гаррі та Герміона входять до кімнати, після чого входи в неї блокує чарівний вогонь, і вийти з неї вони зможуть лише вирішивши наступну загадку:
[з «народного перекладу» книги «Гаррі Поттер та філософський камінь»]Перед тобою - небезпека, а позаду - порятунок,
Допоможуть тобі двоє, кого знайдеш серед нас;
З однієї з сімох вперед продовжиш ти рух
Інша ж назад тебе зараз перенесе.
У двох із нас знайдеш ти лише кропив'яне вино,
А три несуть смерть, стоять у ряду потай.
Так вибирай же, з якої скуштувати судилося,
Для цього чотири підказки ми даємо.
Даремно отрута намагалася приховати свій смертоносний жар,
Завжди його знайдеш ти наліво від вина,
І знай, що ті, хто по краях, різний тримають дар,
Але якщо хочеш далі, не допоможе жодна.
Різнимся ми розміром все, від краю до краю,
Сидить не в меншій смерті, а й не в більшій теж;
Друга з правого кінця та з лівого друга
За смаком — неначе близнюки, хоч на вигляд несхожі.
Простіше кажучи, їм потрібно зрозуміти, в яких пляшках знаходяться якісь зілля.
У цій статті ми вирішимо всі 42 можливі варіанти цієї головоломки за допомогою програмування і намалюємо діаграму результатів (як на картинці вище, тільки набагато більшого розміру).
Секундочку, а звідки взялося 42 варіанти?
Все тому, що розташування «меншого» і «більшого» зілля не вказано. Велика може знаходитися на одному з семи місць, що дає 6 варіантів, що залишилися для меншої, разом 7 * 6 = 42. Дізнатися, яку саме розстановку мала на увазі Джоан Роулінг, вигадуючи цю загадку, не вийде, якщо тільки вона не розповість про це в своєму твіттері. Ну, а поки цей невідворотний день не настав, ми можемо вибрати випадкову версію і попрацювати з нею. Однак гарантій її розв'язання не буде, тому ми і працюємо на загальне благо, вирішуючи всі 42 варіанти загадки (або доводячи їхню нерозв'язність).
ТАК ВИРІШУЙ ВЖЕ
По-перше, ось усі обмеження загадки, переформульовані у простому вигляді:
- Є два невинні зілля, 3 отруєні, одне, що дозволяє пройти вперед, і одне, що дозволяє повернутися назад.
- З лівого боку від кожного з двох нешкідливих зілля стоїть отруйне.
- Зілля з обох боків різні, і жодна з них не дає пройти вперед.
- Найбільша та найменша пляшки не містять отрути.
- Друга пляшка зліва і друга пляшка праворуч містять одне й те саме зілля.
Як із цим бути? Розглянемо наступний варіант. Зазначимо, що, як мовиться в загадці, у ряді є 1 пляшка менше за всіх за розміром, і 1 пляшка більше за всіх інших.
Спробуємо тупо перебрати усі варіанти – брати по одній пляшці та підбирати усі можливі варіанти вмісту.
Наприклад, у першій пляшці не може утримуватися зілля, що просуває нас вперед через обмеження №3. Також вона не містить безпечного зілля через обмеження №2 – ліворуч від неї не може бути отрута. Це залишає нам варіанти з отруєним зіллям та зіллям, що повертає назад. Спробуємо обидва варіанти.
У наступних зображеннях зелені зілля позначають отруту, помаранчеві – безпечні напої, сині – зілля, що рухає назад, пурпурове – що рухає вперед.
Повторимо цей процес для обох робочих варіантів - візьмемо другу сулію і поперемінно спробуємо всі допустимі варіанти вмісту. Це дасть нам таке:
Продовжуючи діяти в цьому ключі, і відкидаючи всі робочі варіанти, в яких якусь сулію не можна заповнити зіллям, не порушивши перерахованих обмежень, ми прийдемо до єдиного допустимого варіанту:
Звісно, ми не мали гарантій знайти рішення. Рішення могло не бути, або їх могло бути кілька (а якщо у вас є кілька рішень, це рівнозначно тому, що загадку не можна вирішити, оскільки невідомо, яке із зіл вірне).
Застосування алгоритму до всіх варіантів дає наступні рішення. 8 варіантів загадки можна вирішити, у 8 немає рішень і у 26 є кілька рішень.
Докладніше про рішення
Чи є щось спільне у всіх розв'язуваних варіантів загадки? Так! Зверніть увагу, що в них найменша чи найбільша пляшки стоять на 2-му чи 6-му місцях. Це дозволяє зробити висновок, що 2-а і 6-я пляшка містять безпечні зілля через обмеження №4 і №5. Без цього кроку ми не можемо усунути можливість того, що у цих пляшках отрута, і в результаті приходимо до кількох можливих рішень. Також варіанти вимагають, щоб друга «особлива» пляшка (найменша або найбільша) стояли на 3-му або 4-му місці. Інакше точне розташування зілля, що рухає нас вперед, знайти не виходить.
Підсумки
Закінчу цитатою із книги.
Герміона з шумом видихнула, і Гаррі здивовано помітив, що вона посміхалася – це було останнє заняття, яке могло б спасти йому на думку. - Геніально, - сказала Герміона. – Це не магія – це логіка, загадка. У величезної кількості магів не набереться і грама логіки, і вони застрягли б тут надовго».
Але, зачекайте, може, ми зуміємо зрозуміти канонічну версію загадки на основі діалогу з книги:
«Зрозуміла, – сказала вона. – Найменша пляшка проведе нас через чорний вогонь, і до Каміння».
...
"А яка дасть тобі повернутися через пурпуровий вогонь?"
Герміона вказала на округлу сулію з правого боку ряду.
Дідька лисого. Цей варіант дає нам кілька рішень. Пишіть твіти, ДР.
Код
Якщо вам цікавий код для вирішення цієї загадки та малювання діаграм, його можна .
Джерело: habr.com