The mysterious endless loop in Python 2.7.9 on Mac OS X 10.10.3
I wrote a Python script that solves the "Fox, goose and bag beans puzzle" . I wrote the code in ABM (Agent Based Model). Every item that needs to be transported along the river is a Passenger's object. Also, two lands near the river are space objects.
The code works fine to fix the original problem. However, as soon as I try to initialize objects (eg peasant2, fox2) an infinite loop happens. I mean I only initialized. I never put them in a real simulation. So, if you disassemble line 170 (# fox2 = Passenger ("fox", "rooster")), an endless loop occurs. The funny thing is that you can initialize an extra grain or rooster, but not a farmer or fox. I thought it might be due to a random module, so I tried to set the seed with
random.seed(some_int)
But that didn't solve anything.
Here's the interesting part; the code works fine on Windows 10 Python 2.7.4. I tried with another Mac, but it would also have an infinite loop. Is this a Mac issue or a Python issue? What's wrong with my codes?
Error free code
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 """
def __init__(self, species, food=None, is_captain=False):
self.species = species
self.food = food
self.is_captain = is_captain
def eat(self, something):
return self.food == something.species
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:
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
peasant = Passenger('human', is_captain=True)
''' IF I UNCOMMENT THE NEXT LINE OUT, THE INFINITE LOOP HAPPENS!!! '''
#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')
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([japan, korea])
break
else:
print "Korea ---> Japan", get_passenger_name(passengers)
print_land_info([japan, korea])
passengers = travel_back(japan, korea)
print "Japan ---> Korea", get_passenger_name(passengers)
print_land_info([japan, korea])
print "========================"
i += 1
Endless loop code
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 """
def __init__(self, species, food=None, is_captain=False):
self.species = species
self.food = food
self.is_captain = is_captain
def eat(self, something):
return self.food == something.species
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:
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
peasant = Passenger('human', is_captain=True)
peasant2 = Passenger('human', is_captain=True)
''' IF I UNCOMMENT THE NEXT LINE OUT, THE INFINITE LOOP HAPPENS!!! '''
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')
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([japan, korea])
break
else:
print "Korea ---> Japan", get_passenger_name(passengers)
print_land_info([japan, korea])
passengers = travel_back(japan, korea)
print "Japan ---> Korea", get_passenger_name(passengers)
print_land_info([japan, korea])
print "========================"
i += 1
Edit: I updated the code as per @hamstergene's advice. I fixed the error in
travel_back(...)
and added
__eq__ and __hash__
for a passenger (). However, I'm not sure if the problem is completely fixed or not.
source to share
The reason for the infinite loop is a bug in your algorithm: travel_back
does not randomly reshuffle, but instead picks the first unsafe passenger. If it is one that has just arrived, it becomes a non-op that repeats endlessly. If you add a random shuffle, the program will always terminate:
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:
random.shuffle(from_.residents) # <---
# ....
The reason for the "mysterious" dependence on the creation of an additional object is that sets and dictionaries rely on __hash__
and operations __eq__
, the default implementation of which (in custom classes) simply uses the object's memory address.
In your case, allocating an additional object changes the memory addresses of subsequent allocations, which in turn changes the sorting order of objects after the operation list(Set(...)-Set(...))
in send_off
and affects the choice of the passenger travel_back
. Without shuffling, there will always be the same object: either a good choice (no loop) or a bad choice, depending on their memory addresses.
Adding hash / equality operators will remove the mysterious dependency on having one extra object or not and make your program's behavior more deterministic: it will either always loop in an infinite loop (if you haven't committed yet travel_back
) or never:
class Passenger(object):
# [...skipped...]
def __eq__(self, other):
return self.species == other.species
def __hash__(self):
return self.species.__hash__()
source to share