# Due to a bus breaking down, n people need to cross a bridge at # night. They have one flashlight between them, which means that at # most two people can cross the bridge at any given time. The people # all take a different constant amount of time to cross, and when two # people cross, they must travel at the slower of the two paces. Find # the quickest crossing strategy as a function of the people's # crossing speeds. (Strategy depends on speed, because optimal # strategy is different for [1,2,5,10] than [1,4,5,10]. In fact, the strategy changes depending on what B-A is relative to D-C. # Note to self: imagine Tufte-style whisker graphs for representing # a state of the game. (One side of the river or the other.) def append_maximal(coll, x, comp, append_ties = True) : """Given a list of maximal elements coll, return a new list of maximal elements with x appended. The append_ties flag determines whether a new element that ties with an old elment is allowed. """ found_tie = False ret = [] for y in coll : c = comp(x,y) if c == -1 : # x < y return coll elif c != 1 : # x equal or incomparable to y found_tie = found_tie or (c == 0) ret += [y] if append_ties or not found_tie : return ret + [x] else : return ret def poly_increment(poly, index) : return [poly[i] + int(i == index) for i in range(len(poly))] def poly_new(n) : return [0] * n def poly_compare_faster(xs, ys) : # Same effect as poly_compare but optimized for speed rather than # readability. if xs == ys : return 0 cumulative = 0 sign = 0 for (x,y) in reversed(zip(xs, ys)) : cumulative += y - x if cumulative != 0 : if (cumulative > 0) != (sign > 0) : return None sign = 1 if cumulative > 0 else -1 #if cumulative * sign < 0 : # return None #sign = sign or cumulative # if cumulative : # sign = 1 if cumulative > 0 else -1 # elif (cumulative > 0) != (sign > 0) : # return None return sign #return 1 if sign > 0 else -1 def pretty_state(s) : return "".join([u'\u2E22' if x > 0 else u'\u2E24' for x in s]) def pretty_actions(actions) : ret = [] n = max(map(max, actions))+1 s = new_state(n) ret += [pretty_state(s)] for a in actions : s = apply_action(s, a) ret += [pretty_state(s)] return ret def poly_compare(xs, ys) : # Ensure that the differences between these integer lists are # compatible with being properly-nested parentheses. Negatives # count one type of parens while positives count the other type. # NOTE: The above description is incorrect, but the algorithm is # correct and works as intended. cumulative = 0 partial_sums = [] for (x,y) in reversed(zip(xs,ys)) : cumulative += y-x partial_sums += [cumulative] if all([u == 0 for u in partial_sums]) : return 0 elif all([u <= 0 for u in partial_sums]) : return -1 elif all([u >= 0 for u in partial_sums]) : return 1 else : return None # if xs != ys : # if all([x >= y for (x,y) in zip(xs,ys)]) : # return 1 # elif all([x <= y for (x,y) in zip(xs, ys)]) : # return -1 # cumulative = 0 # sign = 0 # for (x,y) in zip(xs, ys) : # cumulative += y - x # if cumulative != 0 : # if sign != 0 and (cumulative > 0) != (sign > 0) : # return None # sign = 1 if cumulative > 0 else -1 # if cumulative != 0 : # return None # return sign poly_compare = poly_compare_faster def poly_compare_reverse(xs, ys) : r = poly_compare(xs, ys) return r if r is None else -r def new_state(n) : return poly_new(n) def is_goal_state(state) : return all(state) def next_actions(state, flashlight_side=0) : ns = [i for i in range(len(state)) if state[i] == flashlight_side] A = [(x,) for x in ns] B = [(x,y) for x in ns for y in ns if x < y] return B + A if flashlight_side == 0 else A + B def apply_action(state, action) : return [1-state[i] if i in action else state[i] for i in range(len(state))] include_symmetry = True def invert_node((state, flashlight)) : return (tuple(apply_action(state, range(len(state)))), (1+flashlight)%2) def find_paths(n) : state = new_state(n) start_node = {"path" : [state], "actions" : [], "length" : poly_new(n)} seen = [] extended = {} agenda = [start_node] while agenda : node = agenda.pop(0) # print node flashlight = (1+len(node["path"])) % 2 state = node["path"][0] q = (tuple(state), flashlight) ext = append_maximal(extended.get(q, []), node, lambda a,b:poly_compare(a["length"],b["length"]), False) # if include_symmetry : # q_symmetric = invert_node(q) # ext = append_maximal(extended.get(q_symmetric, []), node, lambda a,b:poly_compare(a["length"],b["length"]), False) if ext != extended.get(q, []) : # found a shorter path than before extended[q] = ext if is_goal_state(state) : continue else : next_nodes = [{"path" : [t] + node["path"], "actions" : node["actions"] + [a], "length" : poly_increment(node["length"], a[-1])} for a in next_actions(state, flashlight) for t in [apply_action(state, a)] if t not in node["path"]] agenda = next_nodes + agenda return extended.get((tuple([1]*n), 1)) # print pretty_state(new_state(8)) E = find_paths(4) # print poly_compare([2,1,1,1],[2,3,1,1]) print for e in E : print e["actions"], e["length"] print " ".join(pretty_actions(e["actions"])) print