На крају Хари Потера и камена филозофа налази се занимљива загонетка. Хари и Хермиона улазе у собу, након чега улазе у њу блокира магична ватра, а могу је напустити само решавањем следеће загонетке:
Пред тобом је опасност, а иза тебе спас,
Двоје људи које нађете међу нама помоћи ће вам;
Са једним од седам наставићете да се крећете напред
Други ће те одмах вратити назад.
У нас двоје ћете наћи само вино од коприве,
А три доносе пропаст, стојећи у низу тајно.
Зато изаберите који вам је предодређен за укус,
Да бисмо то урадили, дајемо четири савета.
Узалуд је отров покушавао да сакрије своју смртоносну топлоту,
Увек ћеш га наћи лево од вина,
И знај да они на ивици имају другачији дар,
Али ако желите да наставите, нико вам неће помоћи.
Сви се разликујемо по величини, од ивице до ивице,
Твоја смрт не седи у мањем, али ни у већем;
Други са десног краја и други са леве стране
Имају укус као близанци, иако не личе.
[из "народног превода" књиге "Хари Потер и камен мудраца"]
Једноставно речено, они морају да разумеју које боце садрже које напитке.
У овом чланку ћемо решити све 42 могуће варијације ове слагалице помоћу програмирања и нацртати дијаграм резултата (као на слици изнад, само много већи).
Чекај мало, одакле су дошле 42 опције?
То је зато што локације „мањих“ и „већих“ напитака нису назначене. Већи може бити на једном од седам места, што даје 6 преосталих опција за мање, укупно 7 * 6 = 42. Неће се моћи тачно сазнати какав је аранжман имала на уму ЈК Ровлинг када је дошла са овом загонетком, осим ако она не прича о томе на вашем Твитеру. Па, док не дође тај неизбежни дан, можемо да бирамо случајну верзију и радимо са њом. Међутим, неће бити гаранције за њену решивост, због чега радимо за опште добро, решавајући све 42 варијанте загонетке (или доказујући њихову нерешивост).
ОДЛУЧИТЕ ВЕЋ
Прво, овде су сва ограничења слагалице, поново изречена једноставним речима:
- Постоје два безопасна напитка, 3 отровна, један који вам омогућава да идете напред, а други који вам омогућава да се вратите назад.
- На левој страни сваког од два безопасна напитка налази се по један отрован.
- Напитци са обе стране су различити и ниједан од њих вам не дозвољава да кренете напред.
- Највеће и најмање боце не садрже отров.
- Друга боца лево и друга боца десно садрже исти напитак.
Како се носити са овим? Хајде да размотримо следећу опцију. Имајте на уму да, као што загонетка каже, у реду је 1 боца мања од свих осталих по величини и 1 боца већа од свих осталих.
Хајде да покушамо да глупо прођемо кроз све опције - узмите једну по једну бочицу и изаберите све могуће опције за садржај.
На пример, прва боца не може да садржи напитак који нас покреће напред због ограничења број 3. Такође не садржи безбедан напитак због ограничења број 2 - лево од њега не може бити отрова. Ово нам оставља опције напитка отрова и напитка за враћање. Хајде да пробамо обе опције.
На следећим сликама, зелени напитци представљају отров, наранџасти су безбедна пића, плави су напитци који се крећу уназад, а љубичасти су напитци који се крећу напред.
Поновимо овај процес за обе радне опције - узмите другу боцу и наизменично испробајте све прихватљиве опције садржаја. Ово ће нам дати следеће:
Настављајући да се понашамо у овом правцу, и одбацујући све радне опције у којима се нека боца не може напунити напитком без кршења наведених ограничења, доћи ћемо до једине прихватљиве опције:
Наравно, нисмо имали гаранције да ћемо наћи решење. Решења не може бити, или их може бити неколико (а ако имате неколико решења, ово је исто као да је загонетку немогуће решити јер не знате који је напитак исправан).
Примена алгоритма на све опције даје нам следећа решења. 8 верзија загонетке је решиво, 8 нема решења, а 26 има више решења.
Више о решењима
Да ли све решене верзије загонетке имају нешто заједничко? Да! Имајте на уму да се у њима најмање или највеће флаше налазе на 2. или 6. месту. Ово нам омогућава да закључимо да 2. и 6. боца садрже сигурне напитке због ограничења #4 и #5. Без овог корака не можемо елиминисати могућност да ове боце садрже отров, а на крају имамо неколико могућих решења. Такође решене опције захтевају да се друга "специјална" боца (најмања или највећа) постави на 3. или 4. место. Иначе, тачна локација напитка који нас покреће напред не може се пронаћи.
Резултати
Завршићу цитатом из књиге.
Хермиона је гласно издахнула, а Хари је био зачуђен када је приметио да се смеје – било је то последње што му је могло пасти на памет. "Бриљантно", рече Хермиона. - Ово није магија - ово је логика, загонетка. Многи од највећих мађионичара немају ни трунке логике, и остали би заглављени овде заувек."
Али сачекај мало - можда можемо да схватимо канонску верзију загонетке на основу дијалога из књиге:
"Схватила", рекла је. „Најмања флаша води нас кроз црну ватру и до Камена.
...
„А који ће вам омогућити да се вратите кроз љубичасту ватру?“
Хермиона је показала на округлу боцу на десној страни реда.
Дођавола. Ова опција нам и даље даје неколико решења. Твеет, ДР.
Код
Ако сте заинтересовани за код за решавање ове загонетке и цртање дијаграма, можете .
Извор: ввв.хабр.цом