from collections import deque

"""
Explanation: Breadth First Search, Queue Based Implementation
Implementation
deque is the constructor for a double ended queue.
End of explanation
"""


def search(start, goal, next_states):
    Frontier = deque([start])
    Parent   = { start: start }
    while Frontier:
        state = Frontier.popleft()
        if state == goal:
            return path_to(state, Parent)
        for ns in next_states(state):
            if ns not in Parent:
                Parent[ns] = state
                Frontier.append(ns)

"""
Explanation: The function search takes three arguments to solve a search problem:
- start is the start state of the search problem,
- goal is the goal state, and
- next_states is a function with signature $\texttt{next_states}:Q \rightarrow 2^Q$, where $Q$ is the set of states.
   For every state $s \in Q$, $\texttt{next_states}(s)$ is the set of states that can be reached from $s$ in one step.
If successful, search returns a path from start to goal that is a solution of the search problem
$$ \langle Q, \texttt{next_states}, \texttt{start}, \texttt{goal} \rangle. $$
The implementation of search uses a queue based implementation of breadth first search to find a path from start to goal.
End of explanation
"""


def path_to(state, Parent):
    p = Parent[state]
    if p == state:
        return [state]
    return path_to(p, Parent) + [state]

"""
Explanation: Given a state and a parent dictionary Parent, the function path_to returns a path leading to the given state.
End of explanation
"""


%run Sliding-Puzzle.ipynb

%load_ext memory_profiler

%%time
Path = search(start, goal, next_states)

animation(Path)

"""
Explanation: Testing with the $3\times 3$ Sliding Puzzle
End of explanation
"""


