Find Cheese¶

Meta phone screen question (Software Engineer Machine Learning 2022).¶


Help a mouse in a maze find where the cheese is. 2 functions are given:

  • move: takes in input a direction (up, down, left or right) move the mouse from the current cell to the adjacent cell if possible (no wall or not on border) and return True if the move is possible and False otherwise,
  • hasCheese: return True if the current cell contains a cheese and False otherwise.


The goal is to write a function find that will move the mouse from origin to the cheese cell and return True if possible and return False otherwise.


No code is provided during the interview. The functions move and hasCheese do not need to be implemented neither the structure of the maze. More or less the structure of the find function should be structure free (the link with the structure being made by the move and hasCheese functions).

In [ ]:
# The example given during the interview is more or less like this
'''
|     |c|
| |_|  _|
|  __ | |
|m|     |
'''


Algorithm¶

The ideas of the algorithm is:

  • To apply a recursive function called each time the mouse move to a new cell,
  • To backtrack the mouse path until finding a cell with possible non tested direction when a dead end is encountered


To apply this strategy we need:

  • A stack (LIFO: Last In First Out) that stores:
    • The last moves
    • A set of already tried moves associated to the cell where the move has been done
    • Example of stack: [("up", {"up"}), ("right", {"up", "down", "right"})]
      • The last move to reach the current cell was "right" and from the previous cell the already tested direction are "up", "down" and "right",
      • The move before (to reach the previous cell) was "up" and is was the only direction tried for this cell


Implementation¶

In [1]:
from collections import deque

class MouseMaze:
    def __init__(self, maze, origin_i, origin_j, objective_i=None, objective_j=None):
        self.maze = maze
        self.i, self.j = origin_i, origin_j
        self.objective_i, self.objective_j = objective_i, objective_j
        
        
    # Moves to one of the 4 directions and returns false if you can't move and true if you can.
    def move(self, direction):
        # we do not care about border as the maze is well defined (example; for cells on top border can't go up)
        if direction in self.maze[self.i][self.j]:
            match direction:
                case 'up':
                    self.i -= 1 # bottom is N so up is -1
                case 'down':
                    self.i += 1 # top is 0 so down is +1
                case 'left':
                    self.j -= 1
                case 'right':
                    self.j += 1
            return(True)
        return(False)

    
    # Returns true if there is a cheese in the current cell.
    def hasCheese(self):
        return(self.i==self.objective_i and self.j==self.objective_j)

    
    # Return True and move to cheese position if mouse can find a cheese; otherwise return False and do not move
    def find(self):
        # dict to inverse last move when we need backtrack: if last move was up last cell was down from this one
        dict_inverse_move = {"up": "down", "down": "up", "left": "right", "right": "left"}
        # stack_moves is a stack of past moves + past tried moves (to backtrack if mouse reach a dead end)
        stack_moves = deque()
        
        # already_tried_moves is a set of moves already tried for this position 
        def dfs(stack_moves, already_tried_moves):
            if self.hasCheese():
                return(True)
            
            directions_not_tested = {"up", "down", "left", "right"} - already_tried_moves
            
            # check every possible move that has not already been tested
            for direction in directions_not_tested:
                already_tried_moves.add(direction) # add the current tried direction to the set
                
                if self.move(direction):
                    stack_moves.append((direction, already_tried_moves)) # if move is ok store it in stack
                    # recursion from next cell; already_tried_moves is set to the opposite of the move done
                    return(dfs(stack_moves, {dict_inverse_move[direction]})) 
            
            # if we reach a dead end ie no already tried possibilities of move then backtrack
            if stack_moves:
                last_move, last_tried_moves = stack_moves.pop() # pop last_move and info about last cell
                _ = self.move(dict_inverse_move[last_move]) # go back to this previous cell
                return(dfs(stack_moves, last_tried_moves)) # try again from this cell with another move
            else:
                return(False)
            
        return(dfs(stack_moves, set()))


Test 1: mouse starts a the bottom left with reachable cheese at the top right¶
In [2]:
# maze is a list of cells; each cell has two informations if the cell contains cheese and the reachable cells
maze = [[{"right"}, {"down", "left", "right"}, {"down", "left"}, {"down"}],
        [{"down", "right"}, {"up", "left"}, {"up", "down"}, {"up", "down"}],
        [{"up", "down"}, {"down"}, {"up", "down"}, {"up", "down"}],
        [{"up", "down"}, {"up", "down"}, {"up", "down"}, {"up", "down"}],
        [{"up"}, {"up", "right"}, {"up", "left", "right"}, {"up", "left"}]]
In [3]:
origin_i, origin_j = 4, 0
objective_i, objective_j = 0, 3
mouse_in_maze = MouseMaze(maze, origin_i, origin_j, objective_i, objective_j)

print("Initial position is: {}, {}".format(mouse_in_maze.i, mouse_in_maze.j))
print("Has the mouse reach the cheese?", mouse_in_maze.find())
print("Final position is: {}, {}".format(mouse_in_maze.i, mouse_in_maze.j))

Initial position is: 4, 0
Has the mouse reach the cheese? True
Final position is: 0, 3


Test 2: mouse starts a the bottom left with non reachable cheese at the top right¶
In [4]:
# maze is a list of cells; each cell has two informations if the cell contains cheese and the reachable cells
maze = [[{"right"}, {"down", "left", "right"}, {"down", "left"}, {"down"}],
        [{"down", "right"}, {"up", "left"}, {"up", "down"}, {"up"}],
        [{"up", "down"}, {"down"}, {"up", "down"}, {"down"}],
        [{"up", "down"}, {"up", "down"}, {"up", "down"}, {"up", "down"}],
        [{"up"}, {"up", "right"}, {"up", "left", "right"}, {"up", "left"}]]
In [5]:
origin_i, origin_j = 4, 0
objective_i, objective_j = 0, 3
mouse_in_maze = MouseMaze(maze, origin_i, origin_j, objective_i, objective_j)

print("Initial position is: {}, {}".format(mouse_in_maze.i, mouse_in_maze.j))
print("Has the mouse reach the cheese?", mouse_in_maze.find())
print("Final position is: {}, {}".format(mouse_in_maze.i, mouse_in_maze.j))

Initial position is: 4, 0
Has the mouse reach the cheese? False
Final position is: 4, 0