GuillermoPena · June 2, 2014 12:39 · Jun 5, 2014 · Jun 5, 2014 · Jun 2, 2014
diff --git a/checkio.1.11.openLabyrinth.py b/checkio.1.11.openLabyrinth.py
@@ -1,4 +1,4 @@
-# CheckIO - Challenge 11 : Open Labyrinth
+# CheckIO - Home Challenge 11 : Open Labyrinth
 # http://checkio.org
 
 # The labyrinth has no walls, but pits surround the path on each side. 

diff --git a/checkio.1.11.openLabyrinth.py b/checkio.1.11.openLabyrinth.py
@@ -0,0 +1,93 @@
+# CheckIO - Challenge 11 : Open Labyrinth
+# http://checkio.org
+
+# The labyrinth has no walls, but pits surround the path on each side. 
+# If a players falls into a pit, they lose.
+# The labyrinth is presented as a matrix (a list of lists): 1 is a pit and 0 is part of the path. 
+# The labyrinth's size is 12 x 12 and the outer cells are also pits. 
+# Players start at cell (1,1). The exit is at cell (10,10). 
+# You need to find a route through the labyrinth.
+# Input: A labyrinth map as a list of lists with 1 and 0.
+# Output: The route as a string that contains "W", "E", "N" and "S".
+# Precondition: labyrinth is 12x12 cells
+
+
+def checkio(maze_map):
+    MOVES=[(1, 0),(-1, 0),(0, -1),(0, 1)]
+    CARDINALS=["S","N","W","E"]
+    GOAL=(10, 10)
+    nodes=[(1,1)] # Node: a cell with >1 optional path
+    cells=[(1,1)] # Coords of cells of path
+    path=""       # String of cardinal points of each movement
+
+    # Repeat until victory!
+    while cells[-1]!=GOAL:
+
+        # Checking options of current cell
+        options=[]
+        for m in range(0,4):
+            next={"cardinal":CARDINALS[m], "coords":tuple([x+y for x,y in zip(cells[-1],MOVES[m])])}
+            if maze_map[next["coords"][0]][next["coords"][1]]==0 and cells.count(next["coords"])==0:
+                options.append(next)
+
+        # If new cell is a bifurcation...
+        if len(options)>1 and nodes.count(cells[-1])==0: 
+            nodes.append(cells[-1])
+
+        # Running path...
+        if len(options)>0:
+            path+=options[0]["cardinal"]
+            cells.append(options[0]["coords"])
+
+        # No options. Go back...
+        if len(options)==0 and cells[-1]!=GOAL:
+            nodeFound=False
+            while nodeFound==False: # De-running path until nearest node
+                path=path[:-1]
+                if nodes.count(cells[-2])>0: 
+                    maze_map[cells[-1][0]][cells[-1][1]]=1 # Blocking blind alley
+                    nodes.remove(cells[-2])
+                    nodeFound=True
+                cells=cells[:-1]
+
+    print("Final Path: " + path)
+    return path
+
+
+if __name__ == '__main__':
+    #This code using only for self-checking and not necessary for auto-testing
+    def check_route(func, labyrinth):
+        MOVE = {"S": (1, 0), "N": (-1, 0), "W": (0, -1), "E": (0, 1)}
+        #copy maze
+        route = func([row[:] for row in labyrinth])
+        pos = (1, 1)
+        goal = (10, 10)
+        for i, d in enumerate(route):
+            move = MOVE.get(d, None)
+            if not move:
+                print("Wrong symbol in route")
+                return False
+            pos = pos[0] + move[0], pos[1] + move[1]
+            if pos == goal:
+                return True
+            if labyrinth[pos[0]][pos[1]] == 1:
+                print("Player in the pit")
+                return False
+        print("Player did not reach exit")
+        return False
+
+    # These assert are using only for self-testing as examples.
+    assert check_route(checkio, [
+        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
+        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
+        [1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1],
+        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
+        [1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1],
+        [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],
+        [1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1],
+        [1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1],
+        [1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1],
+        [1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
+        [1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1],
+        [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]), "The big dead end."
+    print("The local tests are done.")
No results found