<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Missionaries and Infidels
We illustrate the notion of a search problem with the following example, which is also known as the
<a href="https
Step1:  $\texttt{no_problem}(m, i)$ is true if there is no problem on either side.
$m$ and $i$ are the number of missionaries and infidels on the left shore.
Hence there are $3-m$ missionaries and $3-i$ infidels on the right shore.
Step2:  A state is represented as a triple.  The triple $(m, i, b)$ specifies that there are
  - $m$ missionaries,
  - $i$ infidels, and
  - $b$ boats
on the western shore of the river.  This implies that there are 
$3 - m$ missionaries, $3 - i$ infidels, and $1 - b$ boats on the eastern shore.
The function next_states takes a given state and computes the set of states that can be reached from state by one crossing of the river.
Step3:  Initially, all missionaries, all infidels and the boat are on the left shore.
The goal is to have everybody on the right shore, hence the numbers on the left shore
should all be $0$.
Step4:  In order to compute a solution of this search problem, we have to %run the notebook Breadth-First-Search.iypnb. 
Printing the Solution
To begin with, we display the transition relation that is generated by the function next_states.  To this end, we need the module graphviz.
Step6:  The function dot_graph(R) turns a given binary relation R into a graph.
Step7:  The function call createRelation(start) computes the transition relation.  It assumes that all states are reachable from start.
Step8:  The function call printPath(Path) prints the solution of the search problem.
<ASSISTANT_TASK:>
Python Code:
problem = lambda m, i: 0 < m < i
Explanation: Missionaries and Infidels
We illustrate the notion of a search problem with the following example, which is also known as the
<a href="https://en.wikipedia.org/wiki/Missionaries_and_cannibals_problem">missionaries and cannibals problem</a>:
Three missionaries and three infidels have to cross a river that runs from the north to the south.
Initially, both the missionaries and the infidels are on the western shore.  There is just one small boat and
that boat can carry at most two passengers.  Both the missionaries and the infidels can steer the boat.
However, if at any time the missionaries are confronted with a majority of infidels on either shore of the
river, then the missionaries have a problem. Below is an artist's rendition of the problem.
$\texttt{problem}(m, i)$ is True if there is a problem on a shore that has $m$ missionaries and $i$ infidels.
For a problem to arise, the number $m$ of missionaries needs to be greater than $0$ but less than the number $i$ of
infidels.
End of explanation
no_problem = lambda m, i: not problem(m, i) and not problem(3 - m, 3 - i)
Explanation: $\texttt{no_problem}(m, i)$ is true if there is no problem on either side.
$m$ and $i$ are the number of missionaries and infidels on the left shore.
Hence there are $3-m$ missionaries and $3-i$ infidels on the right shore.
End of explanation
def next_states(state):
    m, i, b = state
    if  b == 1:
        return { (m-mb, i-ib, 0) for mb in range(m+1)
                                 for ib in range(i+1)
                                 if 1 <= mb + ib <= 2 and no_problem(m-mb, i-ib) 
               }
    else:
        return { (m+mb, i+ib, 1) for mb in range(3-m+1)
                                 for ib in range(3-i+1)
                                 if 1 <= mb + ib <= 2 and no_problem(m+mb, i+ib) 
               }
Explanation: A state is represented as a triple.  The triple $(m, i, b)$ specifies that there are
  - $m$ missionaries,
  - $i$ infidels, and
  - $b$ boats
on the western shore of the river.  This implies that there are 
$3 - m$ missionaries, $3 - i$ infidels, and $1 - b$ boats on the eastern shore.
The function next_states takes a given state and computes the set of states that can be reached from state by one crossing of the river.
End of explanation
start = (3, 3, 1)
goal  = (0, 0, 0)
Explanation: Initially, all missionaries, all infidels and the boat are on the left shore.
The goal is to have everybody on the right shore, hence the numbers on the left shore
should all be $0$.
End of explanation
import graphviz as gv
def tripleToStr(t):
    return '(' + str(t[0]) + ',' + str(t[1]) + ',' + str(t[2]) + ')'
Explanation: In order to compute a solution of this search problem, we have to %run the notebook Breadth-First-Search.iypnb. 
Printing the Solution
To begin with, we display the transition relation that is generated by the function next_states.  To this end, we need the module graphviz.
End of explanation
def dot_graph(R):
    This function takes binary relation R as inputs and shows this relation as
       a graph using the module graphviz.
    
    dot = gv.Digraph()
    dot.attr(rankdir='LR')
    Nodes = { tripleToStr(a) for (a,b) in R } | { tripleToStr(b) for (a,b) in R }
    for n in Nodes:
        dot.node(n)
    for (x, y) in R:
        dot.edge(tripleToStr(x), tripleToStr(y))
    return dot
Explanation: The function dot_graph(R) turns a given binary relation R into a graph.
End of explanation
def createRelation(start):
    oldM = set()
    M    = { start }
    R    = set()
    while True:
        oldM = M.copy()
        M |= { y for x in M
                 for y in next_states(x)
             }
        if M == oldM:
            break
    return { (x, y) for x in M
                    for y in next_states(x)
           }
Explanation: The function call createRelation(start) computes the transition relation.  It assumes that all states are reachable from start.
End of explanation
def printPath(Path):
    print("Solution:\n")
    for i in range(len(Path) - 1):
        m1, k1, b1 = Path[i]
        m2, k2, b2 = Path[i+1]
        printState(m1, k1, b1)
        printBoat(m1, k1, b1, m2, k2, b2)
    m, k, b = Path[-1]
    printState(m, k, b)
def printState(m, k, b):
     print( fillCharsRight(m * "M", 6) + 
            fillCharsRight(k * "K", 6) + 
            fillCharsRight(b * "B", 3) + "    |~~~~~|    " + 
            fillCharsLeft((3 - m) * "M", 6) + 
            fillCharsLeft((3 - k) * "K", 6) + 
            fillCharsLeft((1 - b) * "B", 3) 
          )
def printBoat(m1, k1, b1, m2, k2, b2):
    if b1 == 1:
        if m1 < m2:
            print("Error in printBoat: negative number of missionaries in the boat!")
            return
        if k1 < k2:
            print("Error in printBoat: negative number of infidels in the boat!")
            return
        print(19*" " + "> " + fillCharsBoth((m1-m2)*"M" + " " + (k1-k2)*"K", 3) + " >")
    else:
        if m1 > m2:
            print("Error in printBoat: negative number of missionaries in the boat!")
            return
        if k1 > k2:
            print("Error in printBoat: negative number of infidels in the boat!")
            return
        print(19*" " + "< " + fillCharsBoth((m2-m1)*"M" + " " + (k2-k1)*"K", 3) + " <")
def fillCharsLeft(x, n):
    s = str(x)
    m = n - len(s)
    return m * " " + s
def fillCharsRight(x, n):
    s = str(x)
    m = n - len(s)
    return s + m * " "
def fillCharsBoth(x, n):
    s  = str(x)
    ml = (n     - len(s)) // 2
    mr = (n + 1 - len(s)) // 2
    return ml * " " + s + mr * " "
Explanation: The function call printPath(Path) prints the solution of the search problem.
End of explanation
<END_TASK>