# Through a Maze Darkly

Subscribe to Tech With Tim!

### Problem

This is an intermediate level programming problem. It shouldn’t take you more than 20 minutes to complete. For your reference it took me (Tech With Tim) 5 minutes to complete.
maze

### Testing

To test your own solution simply download the test files from above and place your code in the function “run()”. Here’s the testing script in case you’re curious. The “.in” and “.out” files need to be in the same directory as your script!

```"""
maze.py
Maze Problem from CCC Waterloo

Author: Tim
Date Modified: Mar-28-2019
"""
from os import listdir
from os.path import isfile
import time
from queue import Queue

"""
My automated tester! Just goes through all the .in and .out files
in the current directory and checks output/expected output
"""

print("* Testing Maze Problem *")

onlyFiles = [f for f in listdir() if f.split(".")[-1] != "py" and isfile(f)]
count = 0
cases = 0
wrong = 0
timeOut = 0

results = []
while count < len(onlyFiles):
cases+= 1
_in = [x.strip() for x in inp]
_out = [x.strip() for x in out]

start = time.time()
ans = run(_in)

if ans == _out:
print("Found in " + str(time.time() - start)[:5] + "ms", end=" | ")
print("CORRECT")
results.append("# ")
elif ans == None:
timeOut += 1
print("TIMEOUT")
results.append("T ")
else:
wrong += 1
print("Found in " + str(time.time() - start)[:5] + "ms", end=" | ")
print("INCORRECT")
print("Excpected: ")
print(_out)
print(ans)
results.append("_")

count += 2

# OUTPUT RESULTS
print("***** Results *****")
print("Problems: " + str(cases))
print("Correct: " + str(cases-wrong-timeOut))
print("Timed Out: " + str(timeOut))
print("Incorrect: " + str(wrong))
print("Score: " + str(cases-wrong-timeOut) + "/" + str(cases))
print(*results)
print("* DONE Testing Maze Problem *")

# YOUR CODE HERE, return the answer as a list of strings
def run():
pass

```

### Solution

Watch the video for a full explanation of the solution.

```"""
maze.py
Maze Problem from CCC Waterloo

Author: Tim
Date Modified: Mar-28-2019
"""
from os import listdir
from os.path import isfile
import time
from queue import Queue

"""
My automated tester! Just goes through all the .in and .out files
in the current directory and checks output/expected output
"""

print("* Testing Maze Problem *")

onlyFiles = [f for f in listdir() if f.split(".")[-1] != "py" and isfile(f)]
count = 0
cases = 0
wrong = 0
timeOut = 0

results = []
while count < len(onlyFiles):
cases+= 1
_in = [x.strip() for x in inp]
_out = [x.strip() for x in out]

start = time.time()
ans = run(_in)

if ans == _out:
print("Found in " + str(time.time() - start)[:5] + "ms", end=" | ")
print("CORRECT")
results.append("# ")
elif ans == None:
timeOut += 1
print("TIMEOUT")
results.append("T ")
else:
wrong += 1
print("Found in " + str(time.time() - start)[:5] + "ms", end=" | ")
print("INCORRECT")
print("Excpected: ")
print(_out)
print(ans)
results.append("_")

count += 2

# OUTPUT RESULTS
print("***** Results *****")
print("Problems: " + str(cases))
print("Correct: " + str(cases-wrong-timeOut))
print("Timed Out: " + str(timeOut))
print("Incorrect: " + str(wrong))
print("Score: " + str(cases-wrong-timeOut) + "/" + str(cases))
print(*results)
print("* DONE Testing Maze Problem *")

class Node:
"""
Node class,
simply stores neighboring nodes of a node
"""
def __init__(self, neighbors):
"""
neighbors are stored as ints *NOT <code>Node</code>'s*
"""
self.neighbors = neighbors

def __str__(self):
return str(self.neighbors)

def run(inp):
# Basic principle here is I have a dict that stores all my Node objects
# when I want a nodes neighbors I use the node number or id as a key to access it's neighbors.
# For the BFS I simply store lists containing the current path, so the last number in the list
# will be the current node (ie the one that neighbors need to be explored next),
# when the last node is the same as the first node in the list we have
# achieved the goal.

# key i is node i
maze = {}  # dict to store nodes

# Split the input into two parts
info = inp[1:int(inp[0])+1]
start_rooms = inp[int(inp[0])+2:]  # these are all of the start rooms

start = time.time()  # so we can timeout

# Convert each line of input into a list full of ints
for i in range(1, len(info)+1):
formatLine = list(map(lambda x: int(x), info[i-1].strip().split(" ")[1:]))
maze[i] = Node(formatLine)

out = []
for room in start_rooms:  # have to loop for each room asked of us
room = int(room)
mx = 0  # current max value

# Simple FIFO Queue
q = Queue()
for n in maze[room].neighbors:
q.put([room,n])  # Start the queue with each of the starting room nodes

while not q.empty():  # BFS!

# just timeout after 0.5 seconds
if time.time() - start > 0.5:
return None

current = q.get()  # dequeue

if current[-1] == room:  # if we end up back in the same room
if len(current) > mx:
mx = len(current)
else:
new = current[:]  # copy the current path
if len(maze[current[-1]].neighbors) == 1: # check if the current node has only one neighbor
new.append(maze[current[-1]].neighbors[0])
else:
# here we are going to determine which neighbor we go to next, we have to go clockwise because of
# the problem specifications

last_pos = maze[current[-1]].neighbors.index(current[-2]) # find what hallway we came through

if last_pos + 1 >= len(maze[current[-1]].neighbors):  # if the hallway we came through was the last in the
last_pos = -1                                     # neighbor list (so most clockwise?) just go back to the first hall
# were just trying to figure out what hall to chose next

add = maze[current[-1]].neighbors[last_pos + 1]  # add one to the last position and add that as next node

if new[-1] == room:  # if the last element is the room we started in
if len(current)+1 > mx:
mx = len(current) + 1
else:
q.put(new)  # add new path to check

out.append(str(mx-1))

return out