Labirinto con stato
Maze with state

di leonardo maffi
by leonardo maffi

Ultima revisione: 28 Marzo 2005
Last revision: March 28 2005

Programma Python - Python program: state_maze.py

Un problema suggerito dalla pagina di Ed Pegg Jr:
A problem suggested by the page by Ed Pegg Jr:
http://www.maa.org/editorial/mathgames/mathgames_11_24_03.html

In questo speciale "labirinto" di carte non si può salire due volte di fila, e non si può scendere due volte di fila:
In this special "maze" of cards you could never go up twice in a row, or down twice in a row:


Immagine originale di Ed Pegg Jr:
Original image by Ed Pegg Jr:
http://www.maa.org/editorial/mathgames/EmynMuilMaze.gif


Ho costruito un semplice programma in Python per risolvere automaticamente questo problema, usando il mio modulo Graph. Per prima cosa ho codificato il disegno in un grafo:
I've created a simple Python script to automatically solve this problem, using my Graph module. First of all I've encoded the image in a graph:

# Il python e' comodo per elaborare testi, per cui ecco le mosse codificate a partire dal disegno:
arcs = """\
a -b
b a -j -l c
c -b l e -d
d c e
e -d l -c t
f g -i h
g -f i k -j
h -f -p
i f -g m -o
j g -k -l b
k -g m -l j
l -e -c b j k
m -i -k -r o t
o -m -r i p
p -s h -o
r -s -t o m
s p r
t -m -e u r
u -t"""

for s in arcs.split("\n"):
    nodes = s.split()
    n1 = nodes[0]
    g.addNode(n1)
    for n2 in nodes[1:]:
        if n2[0]=="-":
            if g.hasArc(n1, n2[1]): print "Error already present:", n1, n2
            if g.readArcw(n2[1], n1)==-1: print "Error w:", n1, n2
            g.addArc(n1, n2[1], w=-1)
        else:
            if g.hasArc(n1, n2): print "Error already present:", n1, n2
            if g.readArcw(n2, n1)==1: print "Error w:", n1, n2
            g.addArc(n1, n2, w=1)

Questo è il grafo risultante, la freccia indica i movimenti in salita. Le direzioni opposte alle frecce sono possibili, e corripondono alle discese:
This is the resulting graph, arrows stand for up directions. Going against the arrow means going down:


Immagine ottenuta col buon GraphViz:
Image produced by the good GraphViz:
http://www.research.att.com/sw/tools/graphviz/

Dopo un po' di debugging del grafo, ho rielaborato il tutto per averne una descrizione più compatta. Questo è il programma:
After some debugging of the graph, I've produced a shorter graph representation. This is the program:

state_maze.py

[Vai all'indice - Go back to index]

Pagina visitata volte dal 28 marzo 2005.