# -*- coding: utf-8 -*-
"""Missionaries_and_cannibals.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/18FiKma_HxV25I73fzJk6HItVVk8Yyfqu
"""

def get_boat_at_left_new_states(game_state):                                    #generating further steps to be taken.
    new_states = []                                                             #A new list to generate all the future states. 
    for missionary in range(game_state[0] + 1):                                 #traversing in loop for m+1 times and c+1 times
        for cannibal in range(game_state[1] + 1):                                
            if missionary + cannibal < 1 or missionary + cannibal > 2:          #at max, only two or min. 1 can travel on a boat. rest all cases to be eliminated.
                continue
            new_state = (game_state[0] - missionary, game_state[1] - cannibal,'right')       #If we have 1 or 2 people on the boat, we will consider them. 
            if 0 < new_state[0] < new_state[1]:                                 #if Cannibals outnumber Missionaries on the left side, we skip.
                print("Future State: " + str(new_state) + ": Missionaries Killed")
                continue
            if 0 < 3 - new_state[0] < 3 - new_state[1]:                         #if Cannibals outnumber Missionaries on the right side, we skip. 
                print("Future State: " + str(new_state) + ": Missionaries Killed")
                continue
            new_states.append(new_state)                                        #else, we can consider them a valid case and append it the list of future states. 
    return new_states

def get_boat_at_right_new_states(game_state):                                   #generating further steps to be taken.
    new_states = []
    for missionary in range(3 - game_state[0] + 1):
        for cannibal in range(3 - game_state[1] + 1):
            if missionary + cannibal < 1 or missionary + cannibal > 2:
                continue
            new_state = (game_state[0] + missionary, game_state[1] + cannibal,'left')
            if 0 < new_state[0] < new_state[1]:
                print("Future State: " + str(new_state) + ": Missionaries Killed")
                continue
            if 0 < 3 - new_state[0] < 3 - new_state[1]:
                print("Future State: " + str(new_state) + ": Missionaries Killed")                
                continue
            new_states.append(new_state)
    return new_states

def get_future_states(game_state):                                              #a function to generate future states. 
    if game_state[2] == 'left':                                                 
        return get_boat_at_left_new_states(game_state)
    else:
        return get_boat_at_right_new_states(game_state)

def bfs():
    state_stack = list()                                                        #maintaining a stack for the states.
    visited_states = set()                                                      #maintaining a set for visited states. (allowing only unique states to consider)
    initial_state = (3, 3, 'left')                                              #initialising our initial state. 
    visited_states.add(initial_state)                                           #visiting the initial state. 
    states = [initial_state]                                                    #maintaining a list of states in consideration at a time.
    all_states = [states]                                                       #maintaining a list of all the states taken in consideration throughout the game. 
    print("Initial state: " + str(initial_state))                               #initialising our initial state. 

    win = False                                                 
    while not win:                                                              #looping over until we win
        print("States: " + str(states))                                         #printing the current states in consideration.
        new_states = []
        for game_state in states:                                               #for every state in the states taken in consideration, checking for goal test condition
            print("Current State: " + str(game_state))
            state_stack.append(game_state)                                         
            if game_state[0] == game_state[1] == 0:   
                print("Win! Last state: " + str(game_state))
                win = True
                break
            future_states = get_future_states(game_state)                       #if goal not achieved, moving ahead and generating its future states.(children)
            for future_state in future_states:                                  #for every future state generated,
                if future_state not in visited_states:                          #ensuring, we have not visited it before
                    new_states.append(future_state)                             #only then we will consider it as our next state. 
                    visited_states.add(future_state)                            #visiting the state. 
                    print("Future State: " + str(future_state))       
                else:
                    print("Future State: " + str(future_state))       
                    print("We have visited " + str(future_state) +  " state before. let's move back")            
            print()
        if not win:                                                             
            states = new_states
            all_states.append(states)

bfs()