from random import choice
from typing import Optional

from base.cell import Cell, is_cell
from base.grid import Grid
from algorithms.base_algorithm import Algorithm


class RecursiveBacktracker(Algorithm):
    """
    Recursive Backtracker algorithm picks a random starting cell and randomly walks.
    It cannot walk on an already visited cell, and if finds at a dead-end (no more unvisited cells around current one),
    goes back in its steps until has a cell at least one visited neighbor; then starts walking again.
    """

    def __init__(self, starting_cell: Optional[Cell] = None) -> None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) -> None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError("Starting point of the algorithm must be a valid cell in the grid")

        # We'll use the list as a stack to do very easily any backtracking
        walked_path = []
        walked_path.append(self.starting_cell)

        while len(walked_path) > 0:
            current_cell = walked_path[-1]

            unvisited_neighbors = [neighbor for neighbor in current_cell.neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

8d3fcf7a04f85ab2733ae095edd36200caa9d661
<mask token>


class RecursiveBacktracker(Algorithm):
    <mask token>
    <mask token>

    def on(self, grid: Grid) ->None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError(
                'Starting point of the algorithm must be a valid cell in the grid'
                )
        walked_path = []
        walked_path.append(self.starting_cell)
        while len(walked_path) > 0:
            current_cell = walked_path[-1]
            unvisited_neighbors = [neighbor for neighbor in current_cell.
                neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

<mask token>


class RecursiveBacktracker(Algorithm):
    <mask token>

    def __init__(self, starting_cell: Optional[Cell]=None) ->None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) ->None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError(
                'Starting point of the algorithm must be a valid cell in the grid'
                )
        walked_path = []
        walked_path.append(self.starting_cell)
        while len(walked_path) > 0:
            current_cell = walked_path[-1]
            unvisited_neighbors = [neighbor for neighbor in current_cell.
                neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

<mask token>


class RecursiveBacktracker(Algorithm):
    """
    Recursive Backtracker algorithm picks a random starting cell and randomly walks.
    It cannot walk on an already visited cell, and if finds at a dead-end (no more unvisited cells around current one),
    goes back in its steps until has a cell at least one visited neighbor; then starts walking again.
    """

    def __init__(self, starting_cell: Optional[Cell]=None) ->None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) ->None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError(
                'Starting point of the algorithm must be a valid cell in the grid'
                )
        walked_path = []
        walked_path.append(self.starting_cell)
        while len(walked_path) > 0:
            current_cell = walked_path[-1]
            unvisited_neighbors = [neighbor for neighbor in current_cell.
                neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

from random import choice
from typing import Optional
from base.cell import Cell, is_cell
from base.grid import Grid
from algorithms.base_algorithm import Algorithm


class RecursiveBacktracker(Algorithm):
    """
    Recursive Backtracker algorithm picks a random starting cell and randomly walks.
    It cannot walk on an already visited cell, and if finds at a dead-end (no more unvisited cells around current one),
    goes back in its steps until has a cell at least one visited neighbor; then starts walking again.
    """

    def __init__(self, starting_cell: Optional[Cell]=None) ->None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) ->None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError(
                'Starting point of the algorithm must be a valid cell in the grid'
                )
        walked_path = []
        walked_path.append(self.starting_cell)
        while len(walked_path) > 0:
            current_cell = walked_path[-1]
            unvisited_neighbors = [neighbor for neighbor in current_cell.
                neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)

from random import choice
from typing import Optional

from base.cell import Cell, is_cell
from base.grid import Grid
from algorithms.base_algorithm import Algorithm


class RecursiveBacktracker(Algorithm):
    """
    Recursive Backtracker algorithm picks a random starting cell and randomly walks.
    It cannot walk on an already visited cell, and if finds at a dead-end (no more unvisited cells around current one),
    goes back in its steps until has a cell at least one visited neighbor; then starts walking again.
    """

    def __init__(self, starting_cell: Optional[Cell] = None) -> None:
        self.starting_cell = starting_cell

    def on(self, grid: Grid) -> None:
        if self.starting_cell is None:
            self.starting_cell = grid.random_cell()
        if not is_cell(self.starting_cell) or self.starting_cell not in grid:
            ValueError("Starting point of the algorithm must be a valid cell in the grid")

        # We'll use the list as a stack to do very easily any backtracking
        walked_path = []
        walked_path.append(self.starting_cell)

        while len(walked_path) > 0:
            current_cell = walked_path[-1]

            unvisited_neighbors = [neighbor for neighbor in current_cell.neighbors if len(neighbor.links) == 0]
            if len(unvisited_neighbors) == 0:
                walked_path.pop()
            else:
                neighbor = choice(unvisited_neighbors)
                current_cell += neighbor
                walked_path.append(neighbor)
