Det er en interessant gåte på slutten av Harry Potter og De vises stein. Harry og Hermine går inn i rommet, hvoretter inngangene til det blokkeres av magisk ild, og de kan bare forlate det ved å løse følgende gåte:
[fra "folkeoversettelsen" av boken "Harry Potter and the Philosopher's Stone"]Det er fare foran deg, og frelse bak deg,
To personer du finner blant oss vil hjelpe deg;
Med en av de syv vil du fortsette å bevege deg fremover
Den andre vil ta deg tilbake umiddelbart.
Hos oss to finner du bare brenneslevin,
Og tre bringer ødeleggelse, stående på rad i hemmelighet.
Så velg hvilken du er bestemt til å smake fra,
For å gjøre dette gir vi fire tips.
Forgjeves prøvde giften å skjule sin dødelige hete,
Du vil alltid finne ham til venstre for vinen,
Og vet at de på kantene har en annen gave,
Men hvis du vil fortsette, er det ingen som hjelper.
Vi varierer alle i størrelse, fra kant til kant,
Din død sitter ikke i det mindre, men heller ikke i det større;
Den andre fra høyre ende og den andre fra venstre
De smaker som tvillinger, selv om de ikke ser like ut.
Enkelt sagt må de forstå hvilke flasker som inneholder hvilke eliksirer.
I denne artikkelen skal vi løse alle 42 mulige varianter av dette puslespillet ved hjelp av programmering og tegne et diagram over resultatene (som bildet over, bare mye større).
Vent litt, hvor kom 42 alternativer fra?
Dette er fordi plasseringen av de "mindre" og "større" drikkene ikke er angitt. Den større kan være på en av syv steder, noe som gir 6 gjenværende alternativer for den minste, totalt 7 * 6 = 42. Det vil ikke være mulig å finne ut nøyaktig hvilken ordning JK Rowling hadde i tankene da hun kom opp med denne gåten, med mindre hun snakker om det på Twitter. Vel, inntil den uunngåelige dagen kommer, kan vi velge en tilfeldig versjon og jobbe med den. Det vil imidlertid ikke være noen garanti for dens løselighet, og det er grunnen til at vi jobber for felles beste, og løser alle 42 varianter av gåten (eller beviser deres uløselighet).
BESTEMME ALLEREDE
For det første, her er alle begrensningene i puslespillet, gjengitt i enkle termer:
- Det er to ufarlige drikker, 3 giftige, en som lar deg gå fremover, og en som lar deg gå tilbake.
- På venstre side av hver av de to ufarlige drikkene er en giftig.
- Drikkene på begge sider er forskjellige, og ingen av dem lar deg gå fremover.
- De største og minste flaskene inneholder ikke gift.
- Den andre flasken til venstre og den andre flasken til høyre inneholder den samme miksen.
Hvordan håndtere dette? La oss vurdere følgende alternativ. Merk at, som gåten sier, i raden er det 1 flaske mindre enn alle de andre i størrelse, og 1 flaske større enn alle de andre.
La oss prøve å gå dumt gjennom alle alternativene - ta en flaske om gangen og velg alle mulige alternativer for innholdet.
For eksempel kan den første flasken ikke inneholde en trylledrikk som beveger oss fremover på grunn av begrensning nr. 3. Den inneholder heller ikke en sikker potion på grunn av restriksjon nr. 2 - det kan ikke være gift til venstre for den. Dette etterlater oss med alternativene for giftdrikk og tilbakevendingsdrikk. La oss prøve begge alternativene.
På de følgende bildene representerer grønne eliksirer gift, oransje er trygge drikker, blå er eliksirer som beveger seg bakover, og lilla er eliksirer som beveger seg fremover.
La oss gjenta denne prosessen for begge arbeidsalternativene - ta den andre flasken og prøv vekselvis alle de akseptable innholdsalternativene. Dette vil gi oss følgende:
Hvis vi fortsetter å handle på denne måten, og forkaster alle arbeidsalternativer der en flaske ikke kan fylles med en trylledrikk uten å bryte de oppførte restriksjonene, kommer vi til det eneste akseptable alternativet:
Naturligvis hadde vi ingen garanti for å finne en løsning. Det kan ikke være noen løsning, eller det kan være flere (og hvis du har flere løsninger, er dette det samme som at gåten er umulig å løse fordi du ikke vet hvilken potion som er riktig).
Å bruke algoritmen på alle alternativene gir oss følgende løsninger. 8 versjoner av gåten er løsbare, 8 har ingen løsninger og 26 har flere løsninger.
Mer om løsninger
Har alle løste versjoner av gåten noe til felles? Ja! Vær oppmerksom på at i dem er de minste eller største flaskene på 2. eller 6. plass. Dette lar oss konkludere med at den andre og sjette flasken inneholder trygge drikker på grunn av restriksjoner #2 og #6. Uten dette trinnet kan vi ikke eliminere muligheten for at disse flaskene inneholder gift, og vi ender opp med flere mulige løsninger. Også løste alternativer krever at den andre "spesielle" flasken (minste eller største) plasseres på 4. eller 5. plass. Ellers kan den nøyaktige plasseringen av eliksiren som beveger oss fremover ikke bli funnet.
Resultater av
Jeg avslutter med et sitat fra boken.
Hermine pustet ut høyt, og Harry ble overrasket over å legge merke til at hun smilte – det var det siste som kunne ha falt ham inn. "Strålende," sa Hermine. – Dette er ikke magi – dette er logikk, en gåte. Mange av de største magikerne har ikke en unse av logikk, og de vil bli sittende fast her for alltid."
Men vent litt – kanskje vi kan finne ut av den kanoniske versjonen av gåten basert på dialogen fra boken:
"Fikk det," sa hun. "Den minste flasken vil føre oss gjennom den svarte ilden og til steinen."
...
"Og hvem vil tillate deg å vende tilbake gjennom den lilla ilden?"
Hermine pekte på en rund flaske på høyre side av raden.
Faen. Dette alternativet gir oss fortsatt flere løsninger. Tweet, DR.
Kode
Hvis du er interessert i koden for å løse dette puslespillet og tegne diagrammene, kan du .
Kilde: www.habr.com