I slutet av boken "Harry Potter och de vises sten" finns en intressant gÄta. Harry och Hermione gÄr in i ett rum, varefter magisk eld blockerar ingÄngarna, och de kan bara gÄ ut om de löser följande gÄta:
Framför dig finns fara, bakom dig finns rÀddning,
TvÄ ska hjÀlpa dig, som du finner bland oss;
Med en av de sju kommer du att fortsÀtta framÄt
Den andra kommer genast att föra dig tillbaka.
I de tvÄ av oss finner du endast nÀsselsvin,
Men tre bÀr pÄ undergÄng, stÄr fördolda i rad.
SÄ vÀlj nu, vilken du för det ödet ska smaka,
För detta ger vi fyra ledtrÄdar.
FörgÀves har giftet försökt att dölja sin dödliga hetta,
Du hittar alltid den till vÀnster om vinet,
Och vet att de som stÄr i kanterna hÄller olika gÄvor,
Men om du vill vidare, kommer ingen att hjÀlpa.
Vi Àr alla lika stora, frÄn kant till kant,
Ditt liv Àr inte mindre i en, men inte heller större;
Den andra frÄn höger och den andra frÄn vÀnster
I smaken â som tvillingar, fast de ser olika ut.
[frÄn "folköversÀttningen" av boken "Harry Potter och de vises sten"]
Enkelt uttryckt, de behöver förstÄ vilka flaskor som innehÄller vilka drycker.
I den hÀr artikeln kommer vi att lösa alla 42 möjliga varianter av denna gÄta med hjÀlp av programmering och rita en diagram över resultaten (som pÄ bilden ovan, men mycket större).
Ett ögonblick, var kommer de 42 varianterna ifrÄn?
Allt beror pÄ att placeringarna för de "mindre" och "större" dryckerna inte anges. Den större kan finnas pÄ en av sju platser, vilket ger 6 kvarstÄende varianter för den mindre, totalt 7 * 6 = 42. Att veta vilken arrangemang Joanne Rowling hade i Ätanke nÀr hon uppfann denna gÄta, kommer inte att vara möjligt, om hon inte berÀttar om detta pÄ sin Twitter. Men tills dess ofrÄnkomliga dag kommer, kan vi vÀlja en slumpmÀssig version och arbeta med den. Men det finns inga garantier för att den gÄr att lösa, sÄ vi arbetar för det allmÀnna bÀsta, genom att lösa alla 42 varianter av gÄtan (eller bevisa deras olösbarhet).
LĂS DET REDAN
Först, hÀr Àr alla begrÀnsningar av gÄtan, omformulerade i enkel form:
- Det finns tvÄ ofarliga drycker, 3 förgiftade, en som lÄter dig gÄ framÄt och en som lÄter dig ÄtervÀnda.
- Till vÀnster om varje av de tvÄ ofarliga dryckerna stÄr en giftig.
- Dryckerna pÄ bÄda sidor Àr olika, och ingen av dem lÄter oss gÄ vidare.
- Den största och den minsta flaskan innehÄller inget gift.
- Den andra flaskan till vÀnster och den andra flaskan till höger innehÄller samma dryck.
Vad ska vi göra Ät detta? LÄt oss övervÀga följande alternativ. LÄt oss notera att, som det sÀgs i gÄtan, finns det 1 flaska som Àr mindre Àn alla andra i storlek och 1 flaska som Àr större Àn alla andra.
LĂ„t oss försöka rĂ€kna ut alla alternativ â ta en flaska i taget och prova alla möjliga innehĂ„ll.
Till exempel kan den första flaskan inte innehĂ„lla en dryck som för oss framĂ„t pĂ„ grund av begrĂ€nsning nr 3. Den innehĂ„ller inte heller en sĂ€ker dryck pĂ„ grund av begrĂ€nsning nr 2 â det kan inte finnas nĂ„got gift till vĂ€nster om den. Detta lĂ€mnar oss med alternativ med gift och dryck som tar oss tillbaka. LĂ„t oss prova bĂ„da alternativen.
I de kommande bilderna representerar gröna drycker gift, orange representerar sÀkra drycker, blÄ drycker tar oss tillbaka och lila drycker tar oss framÄt.
Vi upprepar denna process för bĂ„da arbetsalternativen â vi tar den andra flaskan och provar vĂ€xelvis alla tillĂ„tna alternativ för innehĂ„llet. Detta ger oss följande:
Genom att fortsÀtta pÄ detta sÀtt och utesluta alla arbetsalternativ dÀr en flaska inte kan fyllas med en dryck utan att bryta mot de angivna begrÀnsningarna kommer vi fram till det enda tillÄtna alternativet:
SjÀlvklart hade vi inga garantier för att hitta en lösning. Det kunde ha funnits ingen lösning, eller det kunde ha funnits flera (och om du har flera lösningar, Àr det desamma som att gÄtan inte kan lösas, eftersom det inte Àr klart vilken av dryckerna som Àr korrekt).
TillÀmpningen av algoritmen pÄ alla alternativ ger oss följande lösningar. 8 alternativ till gÄtan kan lösas, 8 har inga lösningar och 26 har flera lösningar.
Mer om lösningarna
Finns det nÄgot gemensamt för alla lösningar av gÄtan? Ja! Observera att den nÀst minsta eller nÀst största flaskan stÄr pÄ 2:a eller 6:e plats. Det gör att vi kan dra slutsatsen att flaskorna 2 och 6 innehÄller sÀkra drycker pÄ grund av begrÀnsningarna nr 4 och nr 5. Utan detta steg kan vi inte utesluta möjligheten att det finns gift i dessa flaskor, och i slutÀndan hamnar vi med flera möjliga lösningar. Dessutom krÀver de lösningar som Àr aktuella att den andra "speciella" flaskan (den nÀst minsta eller nÀst största) stÄr pÄ 3:e eller 4:e plats. Annars kan vi inte hitta den exakta platsen för drycken som driver oss framÄt.
Sammanfattning
Jag avslutar med ett citat frÄn boken.
Hermione suckade högt, och Harry sĂ„g förvĂ„nat att hon log â det var den sista lektionen han kunde tĂ€nka sig. "Genialiskt," sa Hermione. "Det Ă€r inte magi â det Ă€r logik, en gĂ„ta. MĂ„nga av de största trollkarlarna har inte ens en gram logik, och de skulle ha fastnat hĂ€r för alltid."
Men, vĂ€nta lite â kanske kan vi förstĂ„ den kanoniska versionen av gĂ„tan baserat pĂ„ dialogen frĂ„n boken:
"FörstÄtt," sa hon. "Den minsta flaskan kommer att föra oss genom den svarta elden, och till stenen."
âŠ
"Men vilken ger dig möjlighet att ÄtervÀnda genom den purpurfÀrgade elden?"
Hermione pekade pÄ den rundade flaskan pÄ höger sida av raden.
Jaha. Denna variant ger oss ÀndÄ flera lösningar. Skriv tweets, DR.
Kod
Om du Àr intresserad av koden för att lösa denna gÄta och rita diagram, kan den .
KĂ€lla: habr.com
