import copy
import random

m = int(input('No. of missionaries: '))
c = int(input('No. of cannibals: '))
b = int(input('Boat capacity'))
is_final = False


def gen_state(b, b1, b2, m_load, c_load):
    return {
        'boat_pos': b,
        'bank1': {
            'c_count': b1['c_count'],
            'm_count': b1['m_count']
        },
        'bank2': {
            'c_count': b2['c_count'],
            'm_count': b2['m_count']
        },
        'm_to_shift': m_load,
        'c_to_shift': c_load
    }


initial_state = gen_state(1, {'c_count': c, 'm_count': m}, {
                          'c_count': 0, 'm_count': 0}, 0, 0)


def random_strategy(state) -> None:
    global m, c, b, is_final, initial_state
    turn = 0
    previous_states = []
    while not is_final:
        turn += 1
        if turn == 100:
            state = copy.deepcopy(initial_state)
            previous_states = []
            turn = 0
        # we pick the transition state
        state['boat_pos'] = 1
        copy_of_state = copy.deepcopy(state)
        # we pick a random amount of missionaires and a random amount of cannibals
        m_to_shift = random.randrange(0, state['bank1']['m_count']+1)
        c_to_shift = random.randrange(0, state['bank1']['c_count']+1)
        state['bank2']['m_count'] += m_to_shift
        state['bank1']['m_count'] -= m_to_shift
        state['bank2']['c_count'] += c_to_shift
        state['bank1']['c_count'] -= c_to_shift
        state['m_to_shift'] = m_to_shift
        state['c_to_shift'] = c_to_shift
        if not validate(state) or state in previous_states:
            print(state)
            print("Condition breached - reverting state")
            state = copy.deepcopy(copy_of_state)
            continue
        else:
            previous_states.append(state)
            state['boat_pos'] = 2
            print(state)
            print("Correct transition")
            state['m_to_shift'] = 0
            state['c_to_shift'] = 0
            if state['bank1']['m_count'] + state['bank1']['c_count'] == 0:
                is_final = True
    if is_final:
        print("Final state: ")
        print(state)

def backtracking_strategy(state) -> None:
    global m, c, b, is_final, initial_state
    state_stack = []
    turn = 0
    while not is_final:
        turn += 1
        if turn == 100:
            state = copy.deepcopy(initial_state)
            state_stack = []
        # we pick the transition state
        state['boat_pos'] = 1
        # we pick a random amount of missionaires and a random amount of cannibals
        m_to_shift = random.randrange(0, state['bank1']['m_count']+1)
        c_to_shift = random.randrange(0, state['bank1']['c_count']+1)
        state['bank2']['m_count'] += m_to_shift
        state['bank1']['m_count'] -= m_to_shift
        state['bank2']['c_count'] += c_to_shift
        state['bank1']['c_count'] -= c_to_shift
        state['m_to_shift'] = m_to_shift
        state['c_to_shift'] = c_to_shift
        if not validate(state):
            print(state)
            print("Condition breached - reverting state")
            if state_stack:
                state = copy.deepcopy(state_stack.pop())
            else:
                state = copy.deepcopy(initial_state)
            continue
        else:
            print(state)
            print("Correct transition.")
            state_stack.append(copy.deepcopy(state))
            state['boat_pos'] = 2
            state['m_to_shift'] = 0
            state['c_to_shift'] = 0
            if state['bank1']['m_count'] + state['bank1']['c_count'] == 0:
                is_final = True
    if is_final:
        print("Final state: ")
        print(state)


def validate(state) -> bool:
    global b
    if state['m_to_shift'] + state['c_to_shift'] > b:
        return False
    if state['bank1']['m_count'] < state['bank1']['c_count'] or state['bank2']['m_count'] < state['bank2']['c_count']:
        return False
    return True


backtracking_strategy(initial_state)