# -*- coding: utf-8 -*-
'''
Passengers: Peasant, grain, rooster, and fox
Space: Korea, Boat, Japan
What?:
  All the passengers are immigrating from Korea to Japan
  Only a peasant can control the boat.
  Boat can carry only two passengers.
  Fox eats Rooster.
  Rooster eats grain.
  Peasant saves everyone.
  How can all the passengers arrive Japan?

Step 1. {Pick passengers to be carried to Japan}
  In otherwords, pick two passengers whom will be left in land
  (either Korea or in Japan), who won't eat another.

  def is_good_chemistry(p1, p2):
    return not p1.eats(p2) and not p2.eats(p3)

  The relation between n passengers = n*(n - 1) / 2
  If the good chemistry can't be found between the passengers then it's over

Step 2. {Leave a passenger to Japan and decide whether you will carry sbd back}
  if is_good_chemistry(p1, p2) == True:
    leave the passenger

Step 3. if Japan.passengers.len == population: end!
'''
from sets import Set
import random
from itertools import *

class Passenger(object):
  """ Anything that gets on board on the boat.
  Assumed that there could be multiple captains """
  newid = count().next
  def __init__(self, species, food=None, is_captain=False):
    self.id = Passenger.newid()
    self.species = species
    self.food = food
    self.is_captain = is_captain

  def eat(self, other):
    return self.food == other.species

  def __eq__(self, other):
    return self.id == other.id

  def __hash__(self):
    return self.id.__hash__()

  def __str__(self):
    return "I am %s" % self.species

class Space(object):
  """docstring for """
  def __init__(self, name, residents=[]):
    self.name = name
    self.residents = residents
    self.captains = self.update_captains()

  def num_residents(self):
    return len(self.residents)

  ## e.g. send_off([traveller1, traveller2])
  def send_off(self, passengers):
    ''' Remove the passengers who left for the other land.
    It means that the number of captains in the land is changed. '''
    self.residents = list(Set(self.residents) - Set(passengers))
    self.captains = self.update_captains()

  ## e.g. welcome([sailing_captain, traveller])
  def welcome(self, passengers):
    ''' Append newcomers '''
    self.residents += passengers
    self.captains = self.update_captains()

  def update_captains(self):
    return [r for r in self.residents if r.is_captain]

  def pick_a_captain(self):
    ''' Pick a captain randomly '''
    return random.choice(self.captains)

  def print_resident_species(self):
    ''' Simply print out every species in the land.
    For debug purpose '''
    for r in self.residents:
      print r.species

  def get_resident_species(self):
    ''' e.g. Returns "fox, grain,"
    "fox, grain, peasant" '''
    species = [r.species for r in self.residents]
    return ', '.join(species)

  def __str__(self):
    return self.name + ": " + self.get_resident_species()


''' Stand-alone functions '''
def get_captains(residents):
  return [r for r in residents if r.is_captain]

def is_peaceful_pair(pair):
  ''' e.g. is_peaceful_pair([fox, rooster]) => False '''
  p1 = pair[0]
  p2 = pair[1]
  return not p1.eat(p2) and not p2.eat(p1)

def is_peaceful(residents):
  ''' e.g. is_peaceful([fox, rooster, grain]) => False '''
  for pair in list(permutations(residents, r=2)):
    if not is_peaceful_pair(pair):
      return False
  return True

def select_traveller(from_):
  for t in from_.residents:
      ## Figure out if the rest of the residents will get along
      if is_peaceful(list(Set(from_.residents) - Set([t]))):
        from_.send_off([t])
        return t
  return None

def get_sailing_captain(from_):
  sailing_captain = from_.pick_a_captain()
  from_.send_off([sailing_captain])
  return sailing_captain

## e.g. travel_to_destination(korea, japan)
## If succeeds, return passengers. If not, return None(stop the simulation)
def travel_to_destination(from_, to):
  '''
  Randomly pick one traveller and figures out whether the rest will be safe.
  Loop until find one and if not, this simulation should end.
  '''
  if len(from_.captains) == 0:
    ## No captain, no simulation
    print "There is no captain who can sail a boat :("
    return None
  sailing_captain = get_sailing_captain(from_)

  ## Shuffle the residents list so that you always get a random traveller
  random.shuffle(from_.residents)
  traveller = select_traveller(from_)
  if traveller != None:
    passengers = [sailing_captain, traveller]
    to.welcome(passengers)
    return passengers
  else:
    return None

## e.g. travel_back(japan, korea):
##
def travel_back(from_, to):
  sailing_captain = get_sailing_captain(from_)
  ## Shuffle the residents list so that you always get a random traveller
  if is_peaceful(from_.residents):
    to.welcome([sailing_captain])
    return [sailing_captain]
  else:
    ## Added(random.shuffle....) according to hamstergene's advice on
    ## http://stackoverflow.com/questions/31156337/mysterious-infinite-loop-in-python-2-7-9-on-mac-os-x-10-10-3
    random.shuffle(from_.residents)
    traveller = select_traveller(from_)
    passengers = [sailing_captain, traveller]
    to.welcome(passengers)
    return passengers

def get_passenger_name(passengers):
  return tuple(p.species for p in passengers)

def print_land_info(lands):
  for l in lands:
    print l

peasant2 = Passenger('human', is_captain=True)
peasant3 = Passenger('human', is_captain=True)
peasant = Passenger('human', is_captain=True)
fox2 = Passenger('fox', 'rooster')
fox = Passenger('fox', 'rooster')
rooster = Passenger('rooster', 'grain')
rooster2 = Passenger('rooster', 'grain')
grain = Passenger('grain')
grain2 = Passenger('grain')


korea = Space('Korea', [peasant, fox, rooster, grain])
japan = Space('Japan')

for r in korea.residents:
  print hash(r)

POPULATION = korea.num_residents()
CAPTAIN = get_captains(korea.residents)
i = 1
while True:
  print "Loop", i
  passengers = travel_to_destination(korea, japan)
  if passengers == None:
    print "The journey can't be continued"
    break
  if japan.num_residents() == POPULATION:
    print "Everyone has crossed the river safely!"
    print_land_info([korea, japan])
    break
  else:
    print "Korea ---> Japan", get_passenger_name(passengers)
    print_land_info([korea, japan])
    passengers = travel_back(japan, korea)
    print "Japan ---> Korea", get_passenger_name(passengers)
    print_land_info([korea, japan])
    print "========================"
  i += 1