import copy

class FCState:
    def __init__(self):
        self.left_c = 3
        self.left_f = 3
        self.right_c = 0
        self.right_f = 0
        self.boat_left = True # left
        self.prev_state = "NONE"
        
    def is_goal(self):
        return self.right_f == 3 and \
               self.right_c == 3
    
    def is_starting_state(self):
        return self.prev_state == "NONE"
    
    def next_states(self):
        next_states = []
        
        for f in range(3):
            for c in range(3):
                # check to make sure that someone is in the boat
                # AND only allow one person to go from right to left
                if (f+c) == 1 or (f+c) == 2:
                    temp_state = self.move(f,c)

                    if temp_state.is_valid_state():
                        next_states.append(temp_state)
                        
        return next_states
    
    def is_valid_state(self):
        # see if we moved too many people
        if self.left_c < 0 or self.left_f < 0 or \
           self.right_c < 0 or self.right_f < 0:
            return False
        
        # check the foxes <= chickens constraint
        if (self.left_f > self.left_c and self.left_c > 0) or \
           (self.right_f > self.right_c and self.right_c > 0):
            return False
        
        return True
        
    def move(self, f, c):
        # copy the current state
        new_state = copy.deepcopy(self)
        
        if self.boat_left:
            # move to the right shore
            new_state.left_f -= f
            new_state.left_c -= c
            new_state.right_f += f
            new_state.right_c += c
        else:
            # move to the left shore
            new_state.right_f -= f
            new_state.right_c -= c
            new_state.left_f += f
            new_state.left_c += c
            
        new_state.boat_left = not new_state.boat_left
        new_state.prev_state = self
        
        return new_state
    
    def __str__(self):
        result = ("F" * self.left_f + "C" * self.left_c).ljust(6)

        if self.boat_left:
            result += " B|~~~~~~| "
        else:
            result += "  |~~~~~~|B "

        result += "F" * self.right_f + "C" * self.right_c

        return result
    
def dfs(state, visited):
    """
    Recursive depth first search implementation
    
    Input:
    - A state.  The state class MUST have the following methods implemented:
      - is_goal(): returns True if the state is a goal state, False otherwise
      - next_states(): returns a list of the VALID states that can be
      reached from the current state
    - A visited dictionary.  Mapping from string representation of state
      to whether or not the state has been visited
    
    Output:
    Returns a list of ALL states that are solutions (i.e. is_goal
    returned True) that can be reached from the input state.
    """
    visited[str(state)] = True
    
    # if the current state is a goal state, then return it in a list
    if state.is_goal():
        return [state]
    else:
        # else, recurse on the possible next states
        result = []

        for s in state.next_states():
            # append all of the s
            if not(str(s) in visited):
                result += dfs(s, visited)

        return result

def print_solution(state):
    """
    Print out the full path of the solution, including this state AND
    all the states that led to this state from the starting state.
    """
    if state.is_starting_state():
        print(state)
    else:
        print_solution(state.prev_state)
        print(state)
        
start = FCState()

# search starting at the start state and let visited be empty
solutions = dfs(start, {})

# print out the solution
# in this case, the solution is a path!
print_solution(solutions[0])