# 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