<jupyter_start><jupyter_text>The First MazeLeverage the "recursive backtracker" algorithm. It is a randomized version of the depth-first search algorithm. The Recursive Algorithm1. Given a current cell as a parameter, Mark the current cell as visited.2. While the current cell has any unvisited neighbor cells:  1. Choose one of the unvisited neighbors.  2. Remove the wall between the current cell and the chosen cell.  3. Invoke the routine recursively for a chosen cell. The Iterative AlgorithmTo avoid a deep recursive, a stack can be used.1. Choose the initial cell, mark it as visited and push it to the stack.2. While the stack is not empty:  1. Pop a cell from the stack and make it a current cell.  2. If the current cell has any neighbors which have not been visited:    1. Push the current cell to the stack.    2. Choose one of the unvisited neighbors.    3. Remove the wall between the current cell and the chosen cell.    4. Mark the chosen cell as visited and push it to the stack. The Data StructuresA maze is composed of traversable "cells". For my purposes a cell is defined as:- Fixed size. The cell cannot grow or shrink.- Fixed in place. Cells don't move.- All cells are the same size.- Composed of 4 sides: north, south, east, west.<jupyter_code># All class and type definitions
from collections import deque
from collections import namedtuple
from enum import Enum
from typing import List, Dict, Optional

"""
Convenience tuples for working with cell coordinates. 
"""
Point = namedtuple('Point', ['x','y'])
Corner = Point

class Direction(Enum):
  NORTH = 'NORTH'
  EAST = 'EAST'
  SOUTH = 'SOUTH'
  WEST = 'WEST'

DIR_OPPOSITES: dict[Direction, Direction] = {
  Direction.NORTH : Direction.SOUTH,
  Direction.SOUTH : Direction.NORTH,
  Direction.EAST : Direction.WEST,
  Direction.WEST : Direction.EAST
}

"""
Represents a traversable room in a maze.
"""
class MazeCell:
  _location: Point
  _walls: dict[Enum, bool]
  _visited:bool
  
  def __init__(self, x: int, y: int) -> None:
    self._location = Point(x,y)
    self._walls = {
      Direction.NORTH: True,
      Direction.EAST: True,
      Direction.SOUTH: True,
      Direction.WEST: True
    }
    self._visited:bool = False

  @property
  def location(self) -> Point: return self._location

  @property
  def north(self) -> bool: return self._walls[Direction.NORTH]
  
  @property
  def south(self) -> bool: return self._walls[Direction.SOUTH]
  
  @property
  def east(self) -> bool: return self._walls[Direction.EAST]
  
  @property
  def west(self) -> bool: return self._walls[Direction.WEST]

  def visit(self) -> None:
    self._visited = True

  @property
  def visited(self) -> bool:
    return self._visited

  def remove_wall(self, wall: Direction) -> None:
    self._walls[wall] = False

class Stack:
  """
  A FILO Queue built with collections.deque (Double Linked List).
  """
  _data: deque
  def __init__(self) -> None:
    self._data = deque()

  def push(self, cell: MazeCell) -> None:
    """
    Adds a point to the top of the stack.
    """
    self._data.appendleft(cell)

  def pop(self) -> Optional[MazeCell]:
    """
    Returns and removes the last item added to the stack.
    If the stack is empty then the function returns None.
    Check with "if val is not None: ..."
    """
    return self._data.popleft() if len(self._data) > 0 else None

  def empty(self) -> bool:
    """
    Returns True if the stack is empty.
    """
    return len(self._data) == 0

class Maze:
  """
  Represents a maze of connected cells. A "cell" is simple a space a person could occupy.
  """
  _grid: List[List[MazeCell]]
  _width: int
  _height: int
  starting_cell: MazeCell
  exit_cell: MazeCell

  def __init__(self, width: int, height: int) -> None:
    self._grid = []
    self._width = width
    self._height = height
    self._populate()

  @property 
  def width(self) -> int:
    return self._width 

  @property
  def height(self) -> int:
    return self._height

  def _populate(self) -> None:
    """
    Builds a rectangular grid of cells in which all the walls are intially closed.
    """
    for y in range(self.height):
      row: list[MazeCell] = []
      for x in range(self.width):
        row.append(MazeCell(x,y))
      self._grid.append(row)

  def cell(self, location: Point) -> Optional[MazeCell]:
    """
    Finds a cell in the maze by its x,y coordinate.
    The origin of the 2D grid (0,0) is the upper left corner.

    Returns:
      Returns an instance of a MazeCell if it exists, otherwise None.
    """
    found: Optional[MazeCell]
    if (location.x < 0 or location.x >= self.width) or (location.y < 0 or location.y >= self.height):
      found = None
    else:  
      found = self._grid[location.y][location.x]
    return found 

  def find_neighbors(self, cell: MazeCell) -> Dict[Direction, MazeCell]:
    """
    Finds a given cell's neighbors.
    """
    cell_loc = cell.location
    north = Point(cell_loc.x, cell_loc.y - 1)
    east = Point(cell_loc.x + 1, cell_loc.y)
    south = Point(cell_loc.x, cell_loc.y + 1)
    west = Point(cell_loc.x - 1, cell_loc.y)

    # Note: For cells on the border, some neighbors will return None.
    neighbors: dict[Direction, MazeCell] = {
      Direction.NORTH : self.cell(north), 
      Direction.EAST : self.cell(east), 
      Direction.SOUTH : self.cell(south), 
      Direction.WEST : self.cell(west)
    }
    return neighbors

# Maze Generation 

import random

"""
1. Choose the initial cell, mark it as visited and push it to the stack.
2. While the stack is not empty:
  1. Pop a cell from the stack and make it a current cell.
  2. If the current cell has any neighbors which have not been visited:
    1. Push the current cell to the stack.
    2. Choose one of the unvisited neighbors at random.
    3. Remove the wall between the current cell and the chosen cell.
    4. Push the current cell back on the stack (back tracking)
    5. Mark the chosen cell as visited and push it to the stack. (Continue exploring with)
"""
def generate_maze_walls(maze: Maze) -> Maze:
  """
  Traverses the grid of cells creates a maze by opening walls in place.

  Returns:
    The modified grid.
  """
  stack = Stack()
  
  # Establish Starting Cell
  starting_cell_loc: Point = Point(random.randint(0, maze.width - 1), 0) # Randomly select a cell in the north most row.
  starting_cell = maze.cell(starting_cell_loc)
  starting_cell.remove_wall(Direction.NORTH) # Create an opening in the maze
  maze.starting_cell = starting_cell #Saving a pointer for visualization and and solving.

  # Establish Target Cell. This is the exit of the maze.
  exit_cell_loc: Point = Point(random.randint(0, maze.width - 1), maze.height-1) # Randomly select a cell in the South most row.
  exit_cell = maze.cell(exit_cell_loc)
  exit_cell.remove_wall(Direction.SOUTH) # Create an opening in the maze for the exit.
  maze.exit_cell = exit_cell #Saving a pointer for visualization and and solving.
  print(f"Exit cell: {exit_cell_loc}")

  starting_cell.visit() 
  stack.push(starting_cell)

  while not stack.empty():
    current_cell = stack.pop()
    neighbors: Dict[Direction, MazeCell]  = maze.find_neighbors(current_cell)

    # Filter out None and visited neighbors.
    unvisited_neighbors = dict(filter(lambda n : n[1] is not None and not n[1].visited, neighbors.items()))
    if len(unvisited_neighbors) > 0: 
      # Attempt 1: Grab the first non-visited MazeCell if there are any. Seems like this just goes North or South.
      # unvisited_neighbor = list(unvisited_neighbors.items())[0] # Type: List[(direction, MazeCell)]
      
      # Attempt 2. Randomize which unvisited neighbor is traversed next.
      pick_cell = random.randint(0, len(unvisited_neighbors) - 1)
      unvisited_neighbor: List[(Direction, MazeCell)] = list(unvisited_neighbors.items())[pick_cell]

      # Remove the wall between the current cell and the chosen cell.
      wall_to_remove = unvisited_neighbor[0]
      unvisited_cell = unvisited_neighbor[1]
      current_cell.remove_wall(wall_to_remove)
      unvisited_cell.remove_wall(DIR_OPPOSITES[wall_to_remove])
      unvisited_cell.visit()
      
      # Save the current cell for further exploration (backtracking...)
      stack.push(current_cell)
      
      # Save the unvisited neighbor for further exploration.
      stack.push(unvisited_cell)
# Handle Rendering

def draw_wall(canvas: Canvas, start: Corner, stop: Corner) -> None:
  canvas.move_to(start.x, start.y)
  canvas.line_to(stop.x, stop.y)
  canvas.stroke()

def draw_cell_walls(cell: MazeCell, canvas: Canvas, room_size_width: int, room_size_height: int, color='black') -> None:
  canvas.begin_path()
  canvas.stroke_style = color

  cell_index,row_index =  cell.location.x, cell.location.y 
  upper_left_corner = Corner(cell_index*room_size_width, row_index*room_size_height)
  upper_right_corner = Corner(upper_left_corner.x + room_size_width, upper_left_corner.y)
  lower_right_corner = Corner(upper_right_corner.x, upper_right_corner.y + room_size_height)
  lower_left_corner = Corner(lower_right_corner.x - room_size_width, lower_right_corner.y)

  if cell.north: draw_wall(canvas, upper_left_corner, upper_right_corner)
  if cell.east: draw_wall(canvas, upper_right_corner, lower_right_corner)
  if cell.south: draw_wall(canvas, lower_right_corner, lower_left_corner)
  if cell.west: draw_wall(canvas, lower_left_corner, upper_left_corner)
  
  return

"""Draws the maze."""
def draw_maze(maze: Maze, canvas: Canvas) -> Canvas:
  room_size_width: int =  20
  room_size_height: int = 20
  
  with hold_canvas(canvas):
    canvas.line_width = 5
    for row_index in range(maze.height):
      for cell_index in range(maze.width):
        cell = maze.cell(Point(cell_index, row_index))
        draw_cell_walls(cell, canvas, room_size_width, room_size_height)
    # Draw the first cell, for debugging
    draw_cell_walls(maze.starting_cell, canvas, room_size_width, room_size_height, 'red')
  return canvas
# Generate a maze.
from ipycanvas import Canvas,  hold_canvas

maze: Maze = Maze(40, 40)
generate_maze_walls(maze)
canvas = Canvas(width=800, height=800)
canvas = draw_maze(maze, canvas)
display(canvas)<jupyter_output>Exit cell: Point(x=25, y=39)
{'fraction_non_alphanumeric': 0.09537317812775115, 'fraction_numerical': 0.006749486452117774, 'mean_word_length': 3.50992501102779, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 31, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '571189', 'license': 'MIT', 'n_tokens_mistral': 3429, 'n_tokens_neox': 3252, 'n_words': 1094, 'path': 'mazes/maze-generation.ipynb', 'repo_name': 'sholloway/mazes', 'size': '10223'}