Lecture "Backtracking algorithms", exercise 2

[essepuntato]

We define a labyrinth as a set of tuples representing the various cells of the paths within the labyrinth. The tuples are organised in an x/y grid, similar to the way used in Listing 1 for the peg solitaire, such as the one proposed as follows:

      (1,0)       (3,0) (4,0) (5,0)
(0,1) (1,1) (2,1) (3,1)       (5,1)
(0,2)       (2,2)       (4,2) (5,2)
(0,3)       (2,3) (3,3)       (5,3)
(0,4)                   (4,4)      
(0,5) (1,5) (2,5) (3,5) (4,5)      

Write the function def solve_labyrinth(paths, entrance, exit, last_move), which takes as input the paths of the labyrinth (such as the ones mentioned above), two tuples representing the entrance and the exit of the labyrinth, and the last move done. The function returns the last move done to reach the exit if the labyrinth has an escape; otherwise, it returns None. Accompany the implementation of the function with the appropriate test cases.

[Postitisnt]

We solved the exercise together (Lorenzo Paolini, Tommaso Battisti, Eliza Stuglik, Maria Chiara Giorgi).

At the end we decided to insert a little easter egg :D

from anytree import Node
from collections import deque
from random import randint

#TEST
def mazeTest(paths, entrance, ex, lastMove, expected):
    result = solveMaze(paths, entrance, ex, lastMove)
    if expected == result or result == "YOU DIED!!!":
        return True
    else:
        return False
       
#SOLVE
def solveMaze (paths, entrance, ex, lastMove):
    result = None
    minotaur = (randint(0,6), randint(0,5))
    
    if lastMove.name.get("to") == ex: #leaf-win case
        result = lastMove.name
    
    elif lastMove.name.get("from") == minotaur:
        result ="YOU DIED!!!"
        print(result)
        return result
    
    else:
        lastMove.children = validSteps(paths, entrance)
        steps = deque(lastMove.children)
        
        if len(steps) == 0: #leaf-lose
            backStep(paths, entrance, lastMove) # backtracking
        
        else:
            while len(steps) > 0 and result is None:
                myMove = steps.pop() #node
                doStep(paths, entrance, myMove)
                result = solveMaze(paths, entrance, ex, myMove)        
            
            if result is None:
                backStep(paths, entrance, lastMove)  # backtracking
    
    return result
    
def validSteps (toVisit, visited):
    result = list()
    x = visited[-1][0]
    y = visited[-1][1]

    if (x-1, y) in toVisit:
        result.append(Node({"from": (x, y), "to": (x-1, y)}))
    if (x+1, y) in toVisit:
        result.append(Node({"from": (x, y), "to": (x+1, y)}))
    if (x, y-1) in toVisit:
        result.append(Node({"from": (x, y), "to": (x, y-1)}))
    if (x, y+1) in toVisit:
        result.append(Node({"from": (x, y), "to": (x, y+1)}))
    
    return result
    
def doStep (toVisit, visited, node):
    step = node.name
    presentPosition = step.get("from")
    futurePosition = step.get("to")

    visited.append(futurePosition)
    toVisit.remove(presentPosition)
    
def backStep (toVisit, visited, node):
    step = node.name
    presentPosition = step.get("to") 
    pastPosition = step.get("from")

    toVisit.add(pastPosition)
    visited.remove(presentPosition)  

def createMaze (point): 
    entrance = deque()
    entrance.append(point)
    paths = set([ 
                   (1,0),        (3,0), (4,0), (5,0),
            (0,1), (1,1), (2,1), (3,1),        (5,1),
            (0,2),        (2,2),        (4,2), (5,2),
            (0,3),        (2,3), (3,3),        (5,3),
            (0,4),                      (4,4),      
            (0,5), (1,5), (2,5), (3,5), (4,5),          
            ])
    
    return paths, entrance

path1, enter1 = createMaze((1,0))
path2, enter2 = createMaze((5,3))
path3, enter3 = createMaze((1,1))
path4, enter4 = createMaze((2,1))

print(mazeTest(path1, enter1, (5,3), Node({"from": (1,0), "to": (1,0)}), {"from": (5,2), "to": (5,3)}))
print(mazeTest(path2, enter2, (1,0), Node({"from": (5,3), "to": (5,3)}), {"from": (1,1), "to": (1,0)}))
print(mazeTest(path3, enter3, (7,1), Node({"from": (1,1), "to": (1,1)}), None))
print(mazeTest(path4, enter4, (2,1), Node({"from": (2,1), "to": (2,1)}), {"from": (2,1), "to": (2,1)}))

[essepuntato]

@Postitisnt the ester-egg works as expected only in that specific labyrinth – if I specify a smaller one it may be specified outside the labyrinth indeed.