Hi ha un enigma interessant al final de Harry Potter i la pedra filosofal. En Harry i l'Hermione entren a l'habitació, després d'això les entrades queden bloquejades per foc màgic, i només poden sortir-ne resolent l'enigma següent:
Hi ha perill davant teu i salvació darrere teu,
Dues persones que trobis entre nosaltres t'ajudaran;
Amb un dels set seguiràs avançant
L'altre et portarà de tornada immediatament.
En nosaltres dos només trobareu vi d'ortiga,
I tres porten la destrucció, dempeus en fila en secret.
Així que tria quin estàs destinat a tastar,
Per fer-ho, donem quatre consells.
En va el verí va intentar amagar la seva calor mortal,
Sempre el trobaràs a l'esquerra del vi,
I sabeu que els de les vores tenen un regal diferent,
Però si vols continuar, ningú t'ajudarà.
Tots variem de mida, d'una vora a una altra,
La teva mort no s'assenta en el menor, però tampoc en el més gran;
El segon des de l'extrem dret i el segon des de l'esquerra
Tenen gust de bessons, tot i que no s'assemblen.
[de la "traducció popular" del llibre "Harry Potter i la pedra filosofal"]
En poques paraules, han d'entendre quines ampolles contenen quines pocions.
En aquest article, resoldrem les 42 variacions possibles d'aquest trencaclosques mitjançant la programació i dibuixarem un diagrama dels resultats (com la imatge de dalt, només molt més gran).
Espera un moment, d'on han sortit 42 opcions?
Això es deu al fet que no s'indiquen les ubicacions de les pocions "més petita" i "més gran". El més gran pot estar en un dels set llocs, cosa que ofereix 6 opcions restants per al més petit, un total de 7 * 6 = 42. No serà possible esbrinar exactament quina disposició tenia en ment JK Rowling quan va sorgir. amb aquest enigma, tret que en parli al teu Twitter. Bé, fins que arribi aquest dia inevitable, podem triar una versió aleatòria i treballar-hi. No obstant això, no hi haurà garantia de la seva solubilitat, per això treballem pel bé comú, resolent les 42 variants de l'enigma (o demostrant-ne la irresolubilitat).
DECIDEIX JA
En primer lloc, aquí teniu totes les limitacions del trencaclosques, reformulades en termes senzills:
- Hi ha dues pocions inofensives, 3 de verinoses, una que permet avançar i una altra que permet tornar enrere.
- Al costat esquerre de cadascuna de les dues pocions inofensives hi ha una de verinosa.
- Les pocions d'ambdós costats són diferents i cap d'elles permet avançar.
- Les ampolles més grans i petites no contenen verí.
- La segona ampolla de l'esquerra i la segona ampolla de la dreta contenen la mateixa poció.
Com fer front a això? Considerem la següent opció. Fixeu-vos que, com diu l'endevinalla, a la fila hi ha 1 ampolla més petita que totes les altres de mida, i 1 ampolla més gran que totes les altres.
Intentem revisar estúpidament totes les opcions: agafeu una ampolla a la vegada i seleccioneu totes les opcions possibles per al contingut.
Per exemple, la primera ampolla no pot contenir una poció que ens avança a causa de la restricció número 3. Tampoc conté una poció segura a causa de la restricció núm. 2: no hi pot haver verí a l'esquerra. Això ens deixa amb les opcions de poció de verí i poció de retrocés. Anem a provar les dues opcions.
A les imatges següents, les pocions verdes representen verí, el taronja són begudes segures, el blau són pocions que es mouen cap enrere i el morat són pocions que avancen.
Repetim aquest procés per a les dues opcions de treball: agafeu la segona ampolla i proveu alternativament totes les opcions de contingut acceptables. Això ens donarà el següent:
Seguint actuant en aquest sentit i descartant totes les opcions de treball en què alguna ampolla no es pot omplir amb una poció sense violar les restriccions enumerades, arribarem a l'única opció acceptable:
Naturalment, no teníem cap garantia de trobar una solució. No podria haver-hi solució, o podria haver-hi diverses (i si tens diverses solucions, això és el mateix que l'enigma és impossible de resoldre perquè no saps quina poció és correcta).
L'aplicació de l'algorisme a totes les opcions ens dóna les següents solucions. 8 versions de l'enigma són resolubles, 8 no tenen solucions i 26 tenen múltiples solucions.
Més sobre solucions
Tenen alguna cosa en comú totes les versions resoltes de l'enigma? Sí! Tingueu en compte que en elles les ampolles més petites o més grans es troben en 2n o 6è llocs. Això ens permet concloure que les ampolles 2n i 6 contenen pocions segures a causa de les restriccions #4 i #5. Sense aquest pas, no podem eliminar la possibilitat que aquestes ampolles continguin verí, i acabem amb diverses solucions possibles. També les opcions resoltes requereixen que la segona ampolla "especial" (la més petita o la més gran) es col·loqui en 3r o 4t lloc. En cas contrari, no es pot trobar la ubicació exacta de la poció que ens mou cap endavant.
Resultats de
Acabaré amb una cita del llibre.
L'Hermione va exhalar en veu alta, i en Harry es va sorprendre al notar que estava somrient; era l'última cosa que se li podia haver passat. "Genial", va dir l'Hermione. - Això no és màgia, això és lògica, un enigma. Molts dels mags més grans no tenen ni una mica de lògica i es quedarien aquí per sempre".
Però espera un minut; potser podem esbrinar la versió canònica de l'enigma basant-nos en el diàleg del llibre:
"Ho entenc", va dir. "L'ampolla més petita ens conduirà a través del foc negre i fins a la Pedra".
...
"I quin et permetrà tornar pel foc porpra?"
L'Hermione va assenyalar una ampolla rodona al costat dret de la fila.
Maleït sigui. Aquesta opció encara ens ofereix diverses solucions. Tuitejar, DR.
Codi
Si us interessa el codi per resoldre aquest trencaclosques i dibuixar els diagrames, podeu fer-ho .
Font: www.habr.com