Skip to content

Instantly share code, notes, and snippets.

@jmoy

jmoy/thugs_suitcase.py

Last active May 29, 2017
Embed
What would you like to do?
River crossing puzzle
import itertools as it
NTHUGS = 3
NCASES = 2
BOATCAP = 3
thugs = set()
cases = set()
owner = dict()
nresults = 0
for i in range(NTHUGS):
t = "thug"+str(i)
thugs.add(t)
for j in range(NCASES):
c = "case"+str(i)+str(j)
cases.add(c)
owner[c] = t
def is_valid(config):
cs = cases & config
ts = thugs & config
if not ts:
return True
else:
for c in cs:
if owner[c] not in ts:
return False
return True
def is_end(config):
return len(config) == NTHUGS*(1 + NCASES)
def print_result(steps):
global nresults
nresults +=1
print("\nResult {}".format(nresults))
print("----------------")
for s in steps:
print(s)
def solve_further(configs_seen,steps,boat_side,off_side,where):
if where=="right" and is_end(boat_side):
print_result(steps)
return
nxt = "left" if where=="right" else "right"
for n in range(1,BOATCAP+1):
for p in it.combinations(boat_side,n):
passengers = set(p)
# Must have at least one thug in the boat
if not (passengers & thugs):
continue
off_side2 = boat_side - passengers
boat_side2 = off_side | passengers
if not (is_valid(boat_side2) and is_valid(off_side2)):
continue
nconfig = (boat_side2,off_side2)
# Do not repeat configurations
if nconfig in configs_seen:
continue
solve_further(configs_seen+[nconfig],steps+[passengers],
boat_side2,off_side2,nxt)
start = thugs|cases
solve_further([],[],start,set(),"left")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.