#################################################
# python solves the puzzle of crossing the bridge
# wolfgang.urban@schule.at      6/2004
#################################################
# here      list of people on this side
# there     list of people on other side
# walktime  handy list of individual walk durations (global)
# min_time  minimal time calculated so far (global)
# time      minutes (time ticks) passed
# sequence  collected sequence of movements
#
# start with solve([list_of_EachPersonsWalktime])
# e.g. solve([2,8,3]) or solve([1,5,8,10,16])
# output: only the last lines showing minimal time are important!
#################################################################


# start finding the solutions
def solve(list_of_walktimes=[1,2,5,10]):
    global min_time,walktime
    min_time = 10000
    # we name our persons 1,2,3,4,...
    walktime = [None]+list_of_walktimes

    action(range(1,len(walktime)),[],0,[])

#################################################################

# get two (different) persons out of a group
def two_of(group):
    two = []
    for x in range(len(group)-1):
        for y in range(x+1,len(group)):
            two.append((group[x],group[y]))
    return two


# two persons cross the bridge from here to there
def cross(here,there,person1,person2,time):
    global walktime
    here.remove(person1); there.append(person1)
    here.remove(person2); there.append(person2)
    return here,there,time+max(walktime[person1],walktime[person2])

# one person goes back from there to here
def goback(here,there,person,time):
    global walktime
    there.remove(person); here.append(person)
    return here,there,time+walktime[person]

#################################################################

# let's see action
def action(here,there,time,sequence):
    global min_time,walktime

    # cutoff for tremendous speedup
    if time>=min_time: return
    
    for (x,y) in two_of(here):
        # phase 1: two people cross the bridge
        here1,there1,time1 = cross(here[:],there[:],x,y,time)
        # if all have crossed the bridge
        if here1==[]:
            if time1<=min_time:
                print sequence+[(x,y)],"in",time1,"minutes"
                min_time = time1
                return
        for z in there1:
            # phase 2: one comes back    
            here2,there2,time2 = goback(here1[:],there1[:],z,time1)
            # and the action goes on with the new situation
            action(here2[:],there2[:],time2, sequence+[(x,y),z])