Na konci knihy „Harry Potter a Kámen mudrců“ je zajímavá hádanka. Harry a Hermiona vstoupí do místnosti, kterou pak uzavře kouzelný oheň, a dostat se z ní budou moct jen vyřešením následující hádanky:
Před tebou je nebezpečí, a za tebou spása,
Pomohou ti dva, které najdeš mezi námi;
S jednou ze sedmi vpřed pokračuješ,
Druhá tě hned vzad přenese.
V obou z nás najdeš jen kopřivové víno,
A tři nesou smrt, stojí v řadě potají.
Tak si vyber, z jaké ochutnáš,
Pro toto čtyři nápovědy ti dáváme.
Zbytečně se jed snažil skrýt svůj smrtící žár,
Vždy ho najdeš nalevo od vína,
A věz, že ti, co na okrajích, mají různé dary,
Ale pokud chceš jít dál, žádná ti nepomůže.
Všichni máme stejnou velikost, od okraje k okraji,
Tvá smrt nesedí v menším, ale ani v větším;
Druhá zprava a zleva druhá
Podle chuti – jako dvojčata, i když na pohled se liší.
[z „lidového překladu“ knihy „Harry Potter a Kámen mudrců“]
Jednoduše řečeno, musí pochopit, v jakých lahvích se jaké lektvary nacházejí.
V tomto článku vyřešíme všech 42 možných variant této hádanky pomocí programování a nakreslíme diagram výsledků (jako na obrázku výše, jen o hodně větší).
Chvilku, odkud přišlo 42 variant?
Všechno je to proto, že umístění „menšího“ a „většího“ lektvaru není uvedeno. Větší může být na jednom ze sedmi míst, což dává 6 zbývajících variant pro menší, celkem 7 * 6 = 42. Zjistit, jaké rozestavení měla na mysli J.K. Rowlingová, když tuto hádanku vymýšlela, nebude možné, pokud to sama neřekne na svém Twitteru. Dokud však ten nevyhnutelný den nenastane, můžeme si vybrat náhodnou verzi a pracovat s ní. Nemůžeme však zaručit, že bude řešitelná, proto pracujeme pro obecné blaho a řešíme všech 42 variant hádanky (nebo dokazujeme jejich neřešitelnost).
UŽ TO VYŘEŠ
Za prvé, zde jsou všechna omezení hádanky, přeformulovaná jednoduše:
- Jsou dvě neškodná lektvary, 3 otrávené, jedna, která umožňuje jít vpřed, a jedna, která umožňuje vrátit se zpět.
- Na levé straně od každého ze dvou neškodných lektvarů je jedovaté.
- Elixíry na obou stranách jsou různé a žádný z nich neumožňuje postoupit dál.
- Největší a nejmenší lahvičky neobsahují jed.
- Druhá lahvička zleva a druhá lahvička zprava obsahují to samé elixír.
Jak s tímto nakládat? Podívejme se na následující variantu. Poznamenejme, že jak se říká v hádance, v řadě je 1 lahvička menší než všechny ostatní, a 1 lahvička větší než všechny ostatní.
Zkusíme prostě procházet všechny varianty – brát jednu lahvičku po druhé a vybírat všechny možné varianty obsahu.
Například v první lahvičce nemůže být elixír, který nás posune vpřed kvůli omezení č. 3. Rovněž neobsahuje bezpečný elixír z důvodu omezení č. 2 – vlevo od ní nemůže být jed. To nám ponechává varianty s jedovatým elixírem a elixírem, který nás posune zpět. Zkusíme obě varianty.
V následujících obrázcích zelené elixíry znamenají jed, oranžové – bezpečné nápoje, modré – elixír, který posune zpět, fialové – posune vpřed.
Opakujeme tento proces pro obě pracovní varianty – vezmeme druhou lahvičku a postupně vyzkoušíme všechny povolené varianty obsahu. To nám dá následující:
Pokračováním v tomto duchu, a vylučováním všech pracovních variant, ve kterých nelze nějakou lahvičku naplnit elixírem, aniž by se porušila uvedená omezení, dospějeme k jedině přípustné variantě:
Samozřejmě, že jsme neměli záruku najít řešení. Řešení nemuselo existovat, nebo jich mohlo být několik (a pokud máte více řešení, je to ekvivalentní tomu, že hádanku nelze vyřešit, protože není známo, které z elixírů je správné).
Aplikace algoritmu na všechny varianty nám dává následující řešení. 8 variant hádanky je řešitelných, 8 nemá řešení a 26 má několik řešení.
Více o řešeních
Existuje něco společného u všech řešitelných variant hádanky? Ano! Všimněte si, že nejmenší nebo největší láhve jsou na 2. nebo 6. místě. To nám umožňuje usoudit, že 2. a 6. lahev obsahují bezpečné lektvary díky omezením č. 4 a č. 5. Bez tohoto kroku nemůžeme vyloučit možnost, že v těchto lahvích je jed, a nakonec se dostáváme k několika možným řešením. Také řešitelné varianty vyžadují, aby druhá „speciální“ lahev (nejmenší nebo největší) byla na 3. nebo 4. místě. Jinak se nepodaří najít přesnou polohu lektvaru, který nás posune vpřed.
Závěry
Dokončím citací z knihy.
Hermiona hlučně vydechla a Harry s úžasem zaznamenal, že se usmívá – to byla poslední lekce, která by ho mohla napadnout. „Genialita,“ řekla Hermiona. „To není magie – to je logika, hádanka. Mnoho z největších mágů nemá ani gram logiky a uvízli by tu navždy.“
Ale počkej – možná budeme schopni pochopit kanonickou verzi hádanky na základě dialogu z knihy:
„Pochopila jsem,“ řekla. „Nejmenší lahev nás provede černým ohněm a k Kameni.“
…
„A která ti dá vrátit se přes purpurový oheň?“
Hermiona ukázala na kulatou lahev na pravé straně řady.
Sakra. Tato varianta nám i tak poskytuje několik řešení. Pište tweety, D.R.
Kód
Pokud vás zajímá kód na řešení této hádanky a kreslení diagramů, můžete ho .
Zdroj: habr.com
