#!/usr/bin/python3
# D. Vrajitoru, C463/B551/I400 Fall 2025 

# Implementation of a depth-first search for a solution to the
# goat-wolf-cabbage puzzle.

# Problem: a man is transporting a goat, a wolf, and a cabbage. He
# must cross a river and has a boat that can only carry 1 item
# beside himself at a time. He cannot leave the goat alone on one
# side of the river with the cabbage because the goat will eat the
# cabbage. The same thing with the wolf and the goat. Find a sequence
# of actions that the man can execute to get everybody on the other
# side safely.

entity = ['goat', 'wolf', 'cabbage']

# Defines who can eat whom
def eats(x, y):
    if x == 'goat' and y == 'cabbage':
        return True
    elif x == 'wolf' and y == 'goat':
        return True
    else:
        return False

# Defines if a pair of entities is safe to be left alone on one side
# of the river.
def safe_pair(x, y):
    if eats(x, y) or eats(y, x):
        return False
    else:
        return True

# Returns the state of the symbol who in the dictionary al. It
# returns its value and not a reference to it so it can be used for
# testing but not modified. If the symbol who is not part of the list
# it return nil.
def state_of(who, state):
    try:
        return state[who]
    except KeyError:
        state[who] = False
        return False

# Verifies if the state defined as an dictionary is safe. If the
# goat is on the same side as the man, then we're safe. Otherwise if
# the cabbage or the wolf is also on the other side, then we're not
# safe.
def safe_state(state):
    if state_of('man', state) == state_of('goat', state):
        return True
    elif state_of('goat', state) == state_of('wolf', state):
        return False
    elif state_of('goat', state) == state_of('cabbage', state):
        return False
    else:
        return True

# Moves the entity from one side to the other in the sate al. It is a
# list mutator. The positions of all the entities are defined by 0
# and 1 so the move replaces the current position with 1 - it. It
# returns the resulting list.
def move(who, state):
    if state[who] == 'left':
        state[who] = 'right'
    else:
        state[who] = 'left'
    return state

# Tests if the state has reached the goal. This is the case if all
# four entities are on the other side.
def goal_reach(state):
    if not state:
        return False
    return (state_of('man', state)=='right' and
            state_of('goat', state)=='right' and
            state_of('wolf', state)=='right' and
            state_of('cabbage',state)=='right')

# Checks if child is a safe state to move into, and if it is, it adds
# it to the list of states.
def check_add_child(child, list_states):
    if safe_state(child):
        list_states.append(child)
    return list_states

def expand_states(state):
    children = []
    child = state.copy()
    # the man can also move alone
    move('man', child)
    check_add_child(child, children)
    for ent in entity:
        # Move one object on the same side as the man
        if state_of(ent, state) == state_of('man', state):
            child = state.copy()
            move('man', child)
            move(ent, child)
            check_add_child(child, children)
        #else:
	#print("unsafe state", child)
    return children

# Searches for a solution from the initial state
def search_sol(state, path):
    path.append(state)
    nl = expand_states(state)
    next = None
    for child in nl:
        if goal_reach(child):
            path.append(child)
            return child
        if not (child in path):
            next = search_sol(child, path)
            if goal_reach(next):
                return next
            else:
                path.remove(child)
    return next

# Print a path in terms of what moves were made
def print_path(path):
    for i in range(len(path)-1):
        print("Move", end=" ") 
        count = 0
        for j in path[i]:
            if j != 'man' and path[i][j] != path[i+1][j]:
                print(j, path[i+1][j])
                count += 1
        if count == 0:
            print("man", path[i+1]['man'])

# Function running the whole problem and outputting the result
def solve_goat():
    # Initialization of the global variables
    initial_state = {}
    path = []
    initial_state['man'] = 'left'
    for e in entity:
        initial_state[e] = 'left'
        
    # print(initial_state)
    # {'cabbage': 'left', 'wolf': 'left', 'goat': 'left', 'man': 'left'}

    # To see what all the child states from the current one look like
    # print("Expanding initial state")
    # print(expand_states(initial_state))

    # Construct the full olution after evaluating the previous statements
    print("Searching for a solution from the initial state:")
    print(search_sol(initial_state, path))

    # Evaluate the variable path to see the solution backwards.
    print("The full path is:")
    for s in path:
        print(s)
    print("The list of moves is:")
    print_path(path)

if __name__ == '__main__':
    solve_goat()