# individual crossing times are variables A < B < C < D < ... etc.
# The cost of a crossing is therefore always a nonnegative integer linear combination of these costs.
# Given the inequality A < B < C < ... , some combinations are always greater than others
# regardless of the specific values of A,B,C,..., in which case those paths are never optimal
# and can be ignored.
# Conversely, the paths which are not universally less than any other path are, for some
# combination of values, the optimal path. Comparing the costs of the paths divides up the
# (A,B,C,...) space into regions of differing optimal paths.
class Path() :
def __init__(self,n) :
self.n = n # how many musicians
self.cost = [0]*n # coefficients of linear combination
self.state_seq = [[True]*n] # list of booleans describing who's on the side with the boat
self.move_seq = [] # list of moves --- indices of people, either one or two at a time.
self.original_side = True
def is_goal_state(self) :
return (not self.original_side) and all([x == True for x in self.state_seq[-1]])
def clone(self) :
ret = Path(self.n)
ret.cost = self.cost[:]
ret.state_seq = self.state_seq[:]
ret.move_seq = self.move_seq[:]
ret.original_side = self.original_side
return ret
def move(self, m) :
ret = self.clone()
ret.original_side = not ret.original_side
ret.move_seq += [m]
n = self.n
s = ret.state_seq[-1]
bits = [(not b) or (k in m) for (b,k) in zip(s,range(n))]
ret.state_seq += [bits]
ret.cost = [ret.cost[k] + int(k == max(m)) for k in range(n)]
return ret
# def path_compare(path_1, path_2) :
# """Return -1, 0, or 1 if the cost of abstract path_1 is less than, equal to, or greater than the cost of abstract path_2. Return None if incomparable."""
# cost1 = path_1.cost
# cost2 = path_2.cost
# if cost1 == cost2 :
# return 0
# cumulative = 0
# sign = 0
# for (x,y) in zip(cost1, cost2) :
# cumulative += x - y
# if cumulative != 0 :
# if ((cumulative > 0) and (sign < 0)) or ((cumulative < 0) and (sign > 0)) :
# return None # incomparable
# sign = 1 if cumulative > 0 else -1
# return sign
def accumulate(cost1, cost2) :
total = 0
for (x,y) in zip(cost1[::-1], cost2[::-1]) :
total += (x-y)
yield total
def path_compare(path_1, path_2) :
"""Compare the cost of the two paths. If the first is smaller, return
-1. If the first is larger, return 1. If the two are equal, return
0. If the costs are incomparable, return None."""
cost1 = path_1.cost
cost2 = path_2.cost
if cost1 == cost2 :
return 0
accumulation = [x for x in accumulate(cost1, cost2)]
if all([x >= 0 for x in accumulation]) :
return 1
if all([x <= 0 for x in accumulation]) :
return -1
return None
# p = Path(4)
# q = Path(4)
# p.cost = [1,2,3,1]
# q.cost = [0,1,4,6]
# print(p.cost, q.cost)
# print(path_compare(p, q))
def has_loop(p) :
seen = set([])
for x in p.state_seq[::2] :
y = tuple(x)
if y in seen :
return True
seen += [y]
seen = set([])
for x in p.state_seq[1::2] :
y = tuple(x)
if y in seen :
return True
seen += [y]
return False
def introduces_loop(p) :
"""Does the final state of p appear anywhere else in the list of states?"""
x = p.state_seq[-1]
for y in p.state_seq[-3::-2] :
if x == y :
return True
return False
def available_moves(path) :
n = path.n
s = path.state_seq[-1]
one_mover = [(x,) for (x,b) in zip(range(n), s) if b]
two_movers = [(x,y)
for (x,b) in zip(range(n), s)
for (y,c) in zip(range(n), s)
if b and c and (x", p.state_seq[-1], p.original_side)
if any([(q.original_side == p.original_side) and
(q.state_seq[-1] == p.state_seq[-1]) and
path_compare(p,q) in [0,1] # p costs more than existing q
for q in extended]) :
# An already-extended path to this state is shorter
#print("skip")
continue
extended += [p]
print(str(p.cost) + " " + "\t"*(2*(not p.original_side))+"".join(["o" if b else "-" for b in p.state_seq[-1]]))
# if len([x for x in p.state_seq[-1] if x]) <= 2 and p.original_side == True :
# print("nearly there")
if p.is_goal_state() :
#print(" goal")
# print("goal", p.state_seq[-1], p.original_side)
goals += [p]
continue
if not shortcut:
new_paths = [p.move(m) for m in available_moves(p) if p.original_side or len(m) == 1]
else :
new_paths = [p.move(m) for m in available_moves(p) if p.original_side or list(m) == [0] or list(m) == [1]]
new_paths = [q for q in new_paths if not introduces_loop(q)]
new_paths = new_paths if p.original_side else new_paths[::-1] # prefer two-moves on odd states and one-move on even
agenda = agenda + new_paths
# NOW FILTER FOR MAXIMAL (UNSURPASSED) PATHS
def append_maximal(coll, x, append_ties = True) :
# If x is worse than any member of coll, return coll. (assume coll itself already fits the maximality constraint.)
# If any member of coll is worse than x, exclude that member from inclusion.
# If x is tied with any member of coll and ties are disallowed, exclude x.
# If x is incomparable or better than all members of coll, include it.
found_tie = False
ret = []
for y in coll :
c = path_compare(x, y)
# print("---- (new, old)", c, x.cost, y.cost, tuple([p for p in accumulate(x.cost,y.cost)]))
if c == 1 : # x is longer than an existing path; skip it
return coll
elif c != -1 : # x is equal to or incomparable with y
found_tie = found_tie or (c == 0)
ret += [y]
else :
# x is better than the existing path y; don't include y
continue
# print([x.cost for x in coll], x.cost, found_tie)
if append_ties or not found_tie :
return ret+[x]
return ret
best_goals = []
for g in goals :
# print("g", g.cost, [x.cost for x in best_goals])
# print("g: ",g)
best_goals = append_maximal(best_goals, g)
# print("b", list(map(lambda x:x.cost, best_goals)), g.cost)
print("\n\nbest:")
for x in best_goals :
print(x.cost,"\t", x.move_seq)
# print("best", [x.cost for x in best_goals])
print("\n")
# [1 3 0 1] is missing
# best_goals = []
# for g in goals :
# for h in best_goals :
# comp = path_compare(h, g)
# if comp == -1 :
# # g is beaten by an existing goal; skip it.
# continue
# print("goals::::")
# for g in goals :
# print(g.move_seq, g.cost)
# return goals
p = Path(4)
q = Path(4)
p.cost = [3,2,2,0]
q.cost = [5,2,2,0]
# print(path_compare(p,q))
# [3 5 7 7]
# [5 7 9 9]
# print(path_compare(p,q))
path_search(10)
#search(9) takes 20-30min
# 2 best [[0, 1]]
# 3 best [[1, 1, 1]]
# 4 best [[1, 3, 0, 1], [2, 1, 1, 1]]
# 5 best [[2, 3, 1, 0, 1], [3, 1, 1, 1, 1]]
# 6 best [[2, 5, 0, 1, 0, 1], [3, 3, 1, 1, 0, 1], [4, 1, 1, 1, 1, 1]]
# 7 best [[3, 5, 1, 0, 1, 0, 1], [4, 3, 1, 1, 1, 0, 1], [5, 1, 1, 1, 1, 1, 1]]
# 8 best [[3, 7, 0, 1, 0, 1, 0, 1], [4, 5, 1, 1, 0, 1, 0, 1], [5, 3, 1, 1, 1, 1, 0, 1], [6, 1, 1, 1, 1, 1, 1, 1]]
# 9 best [[4, 7, 1, 0, 1, 0, 1, 0, 1], [5, 5, 1, 1, 1, 0, 1, 0, 1], [6, 3, 1, 1, 1, 1, 1, 0, 1], [7, 1, 1, 1, 1, 1, 1, 1, 1]]
# strategy 1: the fastest person escorts everyone else. ([n-2, 1, 1, 1, 1,...,1]
# strategy 2: 1&2 fastest go, 2 comes back, the two slowest people left go, 1 comes back, repeat ratchet. [[(n-1)/2], 2*[k/2]-1, odd,even,odd,even,...]
# strategy 3: 1&2 ratchet the slowest two, then 1 escorts the rest.
# 1 escorts two people then comes back: (1,n),(1),(1,n+1),(1) [2 0 ... 0 1 1]
# 1&2 ratchet two people: (1,2),(2),(n,n+1),(1) [1 2 ... 0 0 1]. Call this A B C D.
# We need to know whether 2A + C + D <=> A + 2B + D
# Which is whether A + C <=> 2B, as usual.
# Is there any other strategy that might ever work better?
# It's four moves that net transfer two people. that must mean 2 go, 1 comes back, 2 go, 1 comes back.
# Which means you pay max(_ _), _, max(_,_), _
# Assuming you start with no one on the other side, the people who come back must be the people you send.
# I'm sensing a proof by induction, given that each ratchet returns you to a simpler position and you can ignore the expensive people you've already brought over.
#
# [1 2 0 0]
# [0 1 1 1]
# [1 3 3 3]
# [0 1 2 3]
# [1 2 1 0]
# [2 1 1 1]
# [2 3 4 5]
# [1 3 0 1]
# [1 4 4 5]