Na konci Harryho Pottera a kamene mudrců je zajímavá hádanka. Harry a Hermiona vstoupí do místnosti, poté jsou vchody do ní zablokovány magickým ohněm a mohou ji opustit pouze vyřešením následující hádanky:
[z "lidového překladu" knihy "Harry Potter a Kámen mudrců"]Před tebou je nebezpečí a za tebou spása,
Dva lidé, které mezi námi najdete, vám pomohou;
S jedním ze sedmi budete pokračovat v pohybu vpřed
Ten druhý vás okamžitě vezme zpět.
V nás dvou najdete jen kopřivové víno,
A tři přinášejí zkázu, tajně stojící v řadě.
Vyberte si tedy, kterou jste předurčeni ochutnat,
K tomu nabízíme čtyři tipy.
Marně se jed snažil skrýt své smrtící horko,
Vždy ho najdeš nalevo od vína,
A vězte, že ti na okrajích mají jiný dar,
Ale pokud chcete pokračovat, nikdo vám nepomůže.
Všichni se lišíme velikostí, od okraje k okraji,
Vaše smrt nesedí v menším, ale ani ve větším;
Druhý z pravého konce a druhý zleva
Chutnají jako dvojčata, i když nevypadají stejně.
Jednoduše řečeno, musí pochopit, které lahvičky obsahují jaké lektvary.
V tomto článku vyřešíme všech 42 možných variant tohoto hlavolamu pomocí programování a nakreslíme diagram výsledků (jako obrázek výše, jen mnohem větší).
Počkejte chvíli, odkud se vzalo 42 možností?
Je to proto, že umístění „menších“ a „větších“ lektvarů není uvedeno. Větší může být na jednom ze sedmi míst, což dává 6 zbývajících možností pro menší, celkem 7 * 6 = 42. Nebude možné přesně zjistit, jaké uspořádání měla JK Rowlingová na mysli, když přišla s touto hádankou, pokud o tom nemluví na vašem Twitteru. No, dokud nepřijde ten nevyhnutelný den, můžeme si vybrat náhodnou verzi a pracovat s ní. Nebude však zaručena její řešitelnost, proto pracujeme pro obecné dobro, řešíme všech 42 variant hádanky (nebo prokazujeme jejich neřešitelnost).
JIŽ SE ROZHODNOUT
Za prvé, zde jsou všechna omezení hádanky, zjednodušeně řečeno:
- Existují dva neškodné lektvary, 3 jedovaté, jeden, který vám umožní jít vpřed, a jeden, který vám umožní vrátit se.
- Na levé straně každého ze dvou neškodných lektvarů je jeden jedovatý.
- Lektvary na obou stranách se liší a žádný z nich vám nedovolí postupovat vpřed.
- Největší a nejmenší lahvičky neobsahují jed.
- Druhá lahvička nalevo a druhá lahvička napravo obsahují stejný lektvar.
Jak se s tím vypořádat? Zvažme následující možnost. Všimněte si, že jak říká hádanka, v řadě je 1 láhev menší velikosti než všechny ostatní a 1 láhev větší než všechny ostatní.
Zkusme si hloupě projít všechny možnosti – vezměte jednu láhev po druhé a vyberte všechny možné možnosti obsahu.
Například první lahvička nemůže obsahovat lektvar, který nás posouvá vpřed kvůli omezení č. 3. Neobsahuje ani bezpečný lektvar kvůli omezení č. 2 - nalevo od něj nemůže být jed. To nám ponechává možnosti lektvaru jedu a lektvaru návratu. Zkusme obě možnosti.
Na následujících obrázcích zelené lektvary představují jed, oranžové jsou bezpečné nápoje, modré jsou lektvary, které se pohybují dozadu, a fialové jsou lektvary, které se pohybují vpřed.
Zopakujme tento postup pro obě pracovní možnosti – vezměte druhou láhev a střídavě vyzkoušejte všechny přijatelné možnosti obsahu. Tím získáme následující:
Budeme-li pokračovat v tomto duchu a zahodit všechny pracovní možnosti, ve kterých nelze některou láhev naplnit lektvarem bez porušení uvedených omezení, dojdeme k jediné přijatelné možnosti:
Přirozeně jsme neměli žádnou záruku, že najdeme řešení. Nemůže existovat žádné řešení, nebo jich může být několik (a pokud máte několik řešení, je to stejné jako hádanku, kterou nelze vyřešit, protože nevíte, který lektvar je správný).
Použití algoritmu na všechny možnosti nám poskytne následující řešení. 8 verzí hádanky je řešitelných, 8 nemá řešení a 26 má více řešení.
Více o řešeních
Mají všechny vyřešené verze hádanky něco společného? Ano! Upozorňujeme, že v nich jsou nejmenší nebo největší lahve na 2. nebo 6. místě. To nám umožňuje dojít k závěru, že 2. a 6. lahvička obsahují bezpečné lektvary kvůli omezením #4 a #5. Bez tohoto kroku nemůžeme vyloučit možnost, že tyto lahve obsahují jed, a nakonec máme několik možných řešení. Také řešené možnosti vyžadují, aby druhá „speciální“ láhev (nejmenší nebo největší) byla umístěna na 3. nebo 4. místě. Jinak přesné umístění lektvaru, který nás posouvá vpřed, nelze najít.
Výsledky
Zakončím citátem z knihy.
Hermiona hlasitě vydechla a Harry si s úžasem všiml, že se usmívá – to bylo to poslední, co ho mohlo napadnout. "Skvělé," řekla Hermiona. - To není magie - to je logika, hádanka. Spousta největších kouzelníků nemá ani špetku logiky a zůstali by tady navždy."
Ale počkejte chvíli – možná na základě dialogu z knihy vymyslíme kanonickou verzi hádanky:
"Rozumím," řekla. "Nejmenší lahvička nás zavede skrz černý oheň a ke Kameni."
...
"A který z nich ti umožní vrátit se přes fialový oheň?"
Hermiona ukázala na kulatou láhev na pravé straně řady.
Sakra. Tato možnost nám stále nabízí několik řešení. Tweet, DR.
Kód
Pokud vás zajímá kód k vyřešení této hádanky a nakreslení diagramů, můžete .
Zdroj: www.habr.com