Harry Potteri ja tarkade kivi lõpus on huvitav mõistatus. Harry ja Hermione sisenevad tuppa, mille järel selle sissepääsud blokeerib maagiline tuli ja nad saavad sealt lahkuda vaid lahendades järgmise mõistatuse:
Oht on teie ees ja pääste teie taga,
Kaks inimest, kelle leiate meie hulgast, aitavad teid;
Ühega seitsmest jätkate edasiliikumist
Teine viib teid kohe tagasi.
Meist kahest leiate ainult nõgeseveini,
Ja kolm toovad hävingu, seistes salaja reas.
Nii et valige, millist neist soovite maitsta,
Selleks anname neli nõuannet.
Asjatult üritas mürk oma surmavat kuumust varjata,
Leiad ta alati veinist vasakult,
Ja teadke, et need, kes on servadel, hoiavad teistsugust kingitust,
Aga kui tahad jätkata, siis keegi ei aita.
Me kõik oleme erineva suurusega, servast servani,
Sinu surm ei istu väiksemas, aga mitte ka suuremas;
Teine paremast otsast ja teine vasakult
Nad maitsevad nagu kaksikud, kuigi nad pole sarnased.
[raamatu "Harry Potter ja tarkade kivi" "rahvatõlkest"]
Lihtsamalt öeldes peavad nad aru saama, millised pudelid milliseid jooke sisaldavad.
Selles artiklis lahendame programmeerimise abil selle mõistatuse kõik 42 võimalikku varianti ja joonistame tulemuste diagrammi (nagu ülaltoodud pildil, ainult palju suurem).
Oota hetk, kust tulid 42 võimalust?
Seda seetõttu, et "väiksemate" ja "suuremate" jookide asukohti ei näidata. Suurem võib olla ühes seitsmest kohast, mis annab väiksemale 6 järelejäänud võimalust, kokku 7 * 6 = 42. Millist korraldust JK Rowling välja tulles silmas pidas, pole võimalik täpselt teada saada. selle mõistatusega, kui ta sellest teie Twitteris ei räägi. Noh, kuni selle vältimatu päevani saame valida juhusliku versiooni ja sellega töötada. Selle lahendatavus ei ole aga garanteeritud, mistõttu töötame ühise hüvangu nimel, lahendades kõik 42 mõistatuse varianti (või tõestades nende lahendamatust).
OTSUSTAGE JUBA
Esiteks on siin kõik mõistatuse piirangud, mis on lihtsas sõnastuses:
- Seal on kaks kahjutut jooki, 3 mürgist, üks, mis võimaldab teil edasi minna ja teine, mis võimaldab teil minna tagasi.
- Kahe kahjutu joogi vasakul küljel on mürgine.
- Mõlema poole joogid on erinevad ja ükski neist ei võimalda teil edasi liikuda.
- Suurimad ja väikseimad pudelid ei sisalda mürki.
- Vasakpoolne teine pudel ja parempoolne teine pudel sisaldavad sama jooki.
Kuidas sellega toime tulla? Vaatleme järgmist võimalust. Pange tähele, et nagu mõistatus ütleb, on reas 1 pudel väiksem kui kõik teised suuruselt ja 1 pudel suurem kui kõik teised.
Proovime kõik variandid rumalalt läbi käia – võta üks pudel korraga ja vali sisule kõik võimalikud valikud.
Näiteks ei saa esimene pudel sisaldada jooki, mis meid piirangu nr 3 tõttu edasi viib. Samuti ei sisalda see piirangu nr 2 tõttu ohutut jooki - sellest vasakul ei saa olla mürki. See jätab meile mürgijoogi ja tagasiviskejoogi valikud. Proovime mõlemat varianti.
Järgmistel piltidel tähistavad rohelised joogid mürki, oranžid on ohutud joogid, sinine on joogid, mis liiguvad tagasi ja lilla on joogid, mis liiguvad edasi.
Kordame seda protsessi mõlema töövaliku puhul – võtke teine pudel ja proovige vaheldumisi kõiki vastuvõetavaid sisuvalikuid. See annab meile järgmise:
Jätkates selles suunas tegutsemist ja loobudes kõigist töövõimalustest, mille puhul mõnda pudelit ei saa täita joogiga ilma loetletud piiranguid rikkumata, jõuame ainsa vastuvõetava võimaluseni:
Loomulikult ei olnud meil mingit garantiid lahenduse leidmiseks. Lahendust ei pruugi olla või võib olla mitu (ja kui teil on mitu lahendust, on see sama, et mõistatust on võimatu lahendada, kuna te ei tea, milline jook on õige).
Algoritmi rakendamine kõigile valikutele annab meile järgmised lahendused. 8 mõistatuse versiooni on lahendatavad, 8-l on lahenduseta ja 26-l on mitu lahendust.
Lahendustest lähemalt
Kas kõigil mõistatuse lahendatud versioonidel on midagi ühist? Jah! Pange tähele, et neis on kõige väiksemad või suurimad pudelid 2. või 6. kohal. See võimaldab järeldada, et 2. ja 6. pudel sisaldavad piirangute nr 4 ja 5 tõttu ohutuid jooke. Ilma selle sammuta ei saa me välistada võimalust, et need pudelid sisaldavad mürki, ja jõuame mitme võimaliku lahenduseni. Ka lahendatud variandid nõuavad, et teine "spetsiaalne" pudel (väikseim või suurim) asetataks 3. või 4. kohale. Vastasel juhul ei leia meid edasi viiva joogi täpset asukohta.
Tulemused
Lõpetan tsitaadiga raamatust.
Hermione hingas valjult välja ja Harry märkas imestusega, et ta naeratab – see oli viimane asi, mis talle pähe võis tulla. "Suurepärane," ütles Hermione. - See pole maagia - see on loogika, mõistatus. Paljudel suurimatel mustkunstnikel pole loogikat ja nad jääksid siia igaveseks kinni."
Kuid oodake veidi – ehk saame raamatust peetava dialoogi põhjal mõistatuse kanoonilise versiooni:
"Sain aru," ütles ta. "Kõige väiksem pudel viib meid läbi musta tule ja kivi juurde."
...
"Ja milline neist lubab teil läbi lilla tule tagasi pöörduda?"
Hermione osutas rea paremal küljel asuvale ümmargusele pudelile.
Pagan võtaks. See valik annab meile siiski mitu lahendust. Säuts, DR.
Kood
Kui olete huvitatud selle mõistatuse lahendamise ja diagrammide joonistamise koodist, saate seda teha .
Allikas: www.habr.com