Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic labyrinth solution in Uncategorized category for Open Labyrinth by ilpalazzo_sama
#Your code here
#You can import some modules or create additional functions
import types
import math
from functools import cmp_to_key
DIR_SOUTH = 'S'
DIR_NORTH = 'N'
DIR_EAST = 'E'
DIR_WEST = 'W'
DIR_NONE = '' #indicates start of motion
INFINITE_LOOP_INDICATOR = 1500
DIRECTIONS = [DIR_SOUTH, DIR_EAST, DIR_WEST, DIR_NORTH]
DEAD_END_MARKER = 2 #indicates that the route leads to a dead end
ALREADY_PASSED_MARKER = 3 #indicate points that were already passed to avoid getting stuck in a loop
END_POINT = [10, 10]
START_POINT = [1,1]
MAX_INDEX = 11
#get the direction opposite to the given
def oppositeDirection(dir):
return {
DIR_SOUTH: DIR_NORTH,
DIR_NORTH: DIR_SOUTH,
DIR_EAST: DIR_WEST,
DIR_WEST: DIR_EAST,
DIR_NONE: DIR_NONE
}[dir]
def initLabyrinthWalker():
walker = types.SimpleNamespace()
#walker has three attributes - a character list representing its previous path
#its current coordinates
#and the direction of its movement
walker.path = list()
walker.position = START_POINT
walker.direction = DIR_NONE
return walker
def dynamicLabyrinthWalker(labyrinth):
iterationCount = 0
labyrinthWalker = initLabyrinthWalker()
while True:
nextPosition = getFeasibleNodesAccordingToDirection(labyrinthWalker, labyrinth)
if nextPosition == -1:
return 'End point unreachable'
elif nextPosition == END_POINT:
return ''.join(labyrinthWalker.path)
else :
iterationCount+=1 #to prevent infinite loops
if iterationCount == INFINITE_LOOP_INDICATOR:
return 'Infinite loop, sorry'
def getFeasibleNodesAccordingToDirection(walker, labyrinth):
movementOptions = list()
for direct in DIRECTIONS:
#we do not move backwards
if direct == oppositeDirection(walker.direction):
continue
else :
index = transformIndexAccordingToDirection(walker.position, direct)
if isIndexFeasible(index) == True:
if labyrinth[index[0]][index[1]] == 0 : #feasible option
movementOptions.append([index, direct])
if len(movementOptions) == 0 :
#retreat, mark current position as dead-end
labyrinth[walker.position[0]][walker.position[1]] = DEAD_END_MARKER
backdirection = oppositeDirection(walker.path.pop())
backindex = transformIndexAccordingToDirection(walker.position, backdirection)
if labyrinth[backindex[0]][backindex[1]] == DEAD_END_MARKER:
return -1 #nowhere else to go
walker.position = backindex
walker.direction = backdirection
return backindex
#now that we have a list of possible movement options, a decision-making
#mechanism is required. My hunch is to sort it according to Euclidean metric
movementOptions.sort(key = cmp_to_key(euclideanSort))
nextPoint = movementOptions[0]
walker.path.append(nextPoint[1])
walker.direction = nextPoint[1]
walker.position = nextPoint[0]
changePointState(labyrinth, nextPoint[0])
return nextPoint[0]
def changePointState(labyrinth, index):
if labyrinth[index[0]][index[1]] == 0:
labyrinth[index[0]][index[1]] = ALREADY_PASSED_MARKER
else:
labyrinth[index[0]][index[1]] = DEAD_END_MARKER
return
def euclideanSort(option1, option2):
if euclideanDistance(option1[0], END_POINT) < euclideanDistance(option2[0], END_POINT):
return -1
elif euclideanDistance(option1[0], END_POINT) > euclideanDistance(option2[0], END_POINT):
return 1
else:
return 0
def isIndexFeasible(index) :
return index[0] >= 0 and index[0] <= MAX_INDEX and index[1] >= 0 and index[1] <= MAX_INDEX
def euclideanDistance(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def transformIndexAccordingToDirection(index, direction):
return {
DIR_SOUTH: [index[0]+1, index[1]],
DIR_NORTH: [index[0]-1, index[1]],
DIR_EAST: [index[0], index[1]+1],
DIR_WEST: [index[0], index[1]-1]
}[direction]
def checkio(data):
#Your code here
#It's main function. Don't remove this function
#It's using for auto-testing and must return a result for check.
#replace this for solution
#This is just example for first maze
return dynamicLabyrinthWalker(data)
#Some hints
#Look to graph search algorithms
#Don't confuse these with tree search algorithms
#This code using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
print(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, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]))
#be carefull with infinity loop
print(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, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]))
print(checkio([
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]))
July 28, 2013
