import random

def initialize(m, c, b):
    initial_state = {'m': m, 'c': c, 'b': b}
    return initial_state


def ending_state(state):
    if state['m'] == 0 and state['c'] == 0 and state['b'] == 0:
        return True
    return False


def is_valid_state(state):
    # verifica initializarea
    if state['m'] < 0 or state['c'] < 0 or state['m'] > 3 or state['c'] > 3 or (state['b'] != 0 and state['b'] != 1):
        return False
    # verifica sa nu fie mai multi canibali decat misionari in portul original
    if state['c'] > state['m'] and state['m'] > 0:
        return False
    # verifica sa nu fie mai multi canibali decat misionari in portul nou
    if state['c'] < state['m'] and state['m'] < 3:
        return False
    return True


def transition(state):
    # minim 1 "om" maxim 2
    if state['b'] == 1:
        sign = -1
        directie = "din portul original catre cel nou"
    else:
        sign = 1
        directie = " din portul nou catre cel original"

    for m in range(3):
        for c in range(3):
            new_state = {'m': state['m']+sign*m,
                         'c': state['c']+sign*c,
                         'b': state['b']+sign*1}
            if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True:
                print "ia %d misionari si %d canibali %s " % (m, c, directie)
                return new_state


def random_solution(state):
    print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
        state['m'], state['c'], state['b'], 0, 0, 0)
    nr = 0
    while(ending_state(state) != True):
        if state['b'] == 1:
            sign = -1
            directie = "din portul original catre cel nou"
        else:
            sign = 1
            directie = " din portul nou catre cel original"
        m = random.randrange(3)
        c = random.randrange(3)
        new_state = {'m': state['m']+sign*m,
                     'c': state['c']+sign*c,
                     'b': state['b']+sign*1}
        nr += 1
        if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True:
            print "ia %d misionari si %d canibali %s " % (m, c, directie)
            state = new_state
            print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
                state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])

    print "numarul de pasi:%d" % (nr)
    return


def check_state(state_list, new_state):
    if new_state in state_list:
        return False
    return True


def random_optimised_solution(state):
    state_list = []
    original_state = state
    print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
        state['m'], state['c'], state['b'], 0, 0, 0)
    nr = 0
    tries = 0
    state_list.append(state)
    while(ending_state(state) != True):
        if state['b'] == 1:
            sign = -1
            directie = "din portul original catre cel nou"
        else:
            sign = 1
            directie = " din portul nou catre cel original"
        m = random.randrange(3)
        c = random.randrange(3)
        new_state = {'m': state['m']+sign*m,
                     'c': state['c']+sign*c,
                     'b': state['b']+sign*1}
        nr += 1
        print nr
        if nr > 100:
            state = original_state
            nr = 0
            tries += 1
            state_list = []

        if m+c >= 1 and m+c <= 2 and is_valid_state(new_state) == True and check_state(state_list, new_state):
            print "ia %d misionari si %d canibali %s " % (m, c, directie)
            state = new_state
            print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
                state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
            state_list.append(state)

    print "numarul de pasi:%d si %d incercari" % (nr, tries)
    return


def DFS_solution(state, state_list):
    ok=0
        # generez de fiecare data chestia asta cu toate ca nu prea ajuta
    posibilitati = []
    for m in range(3):
        for c in range(3):
            if m+c >= 1 and m+c <= 2:
                posibilitati.append([m, c])

    for solutie in posibilitati:
        if ok == 1:
            return

        if state['b'] == 1:
            sign = -1
            directie = "din portul original catre cel nou"
        else:
            sign = 1
            directie = " din portul nou catre cel original"

        m = solutie[0]
        c = solutie[1]
        new_state = {'m': state['m']+sign*m,
                     'c': state['c']+sign*c,
                     'b': state['b']+sign*1}
        if is_valid_state(new_state) == True and check_state(state_list, new_state):
            print "ia %d misionari si %d canibali %s " % (m, c, directie)
            state = new_state
            print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
                state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])
            state_list.append(state)

            if ending_state(state) == True:
                ok = 1
                return
            else:
                DFS_solution(state, state_list)

    return


def BFS_solution(state, state_list):
    posibilitati = []
    for m in range(3):
        for c in range(3):
            if m+c >= 1 and m+c <= 2:
                posibilitati.append([m, c])
    stiva = posibilitati

    while ending_state(state) != True:
        for solutie in stiva:
            if state['b'] == 1:
                sign = -1
                directie = "din portul original catre cel nou"
            else:
                sign = 1
                directie = " din portul nou catre cel original"
            m = solutie[0]
            c = solutie[1]
            new_state = {'m': state['m']+sign*m,
                         'c': state['c']+sign*c,
                         'b': state['b']+sign*1}
            if is_valid_state(new_state) == True and check_state(state_list, new_state):
                print "ia %d misionari si %d canibali %s " % (m, c, directie)
                state = new_state
                print "port original ( %d, %d, %d ) ------ port nou ( %d, %d, %d ) " % (
                    state['m'], state['c'], state['b'], 3-state['m'], 3-state['c'], state['b'])

    return


def main():
    state = initialize(3, 3, 1)
    # random_solution(state)
    print "Random Optimized"

    random_optimised_solution(state)
    print "DFS"

    DFS_solution(state, [])
    print "BFS"
    BFS_solution(state, [])

    return 0


if __name__ == "__main__":
    main()