Diana.Savvatina
BAN USERPython
def trace(*txt):
traceOn = False
if traceOn:
print(*txt)
class Bike:
def __init__(self,gmap):
assert len(gmap) > 0
assert len(gmap[0]) > 0
self._m = gmap
print("Got new map! %dx%d"%(len(gmap),len(gmap[0])))
def findRoute(self, *pos):
visited = {pos: None} # position -> (tuple for direction, prev y, prev x)
stack = [pos]
gm = self._m
h,w = len(gm), len(gm[0])
y, x = pos
trace("Start at ", pos)
if y < 0 or x < 0 or y >= h or x >= w:
print("You are out of map, too bad: %s\n\n"%(str(pos)))
return
while len(stack):
prevY, prevX = stack[0]
for a,y,x in [('U', prevY - 1, prevX),
('D', prevY + 1, prevX),
('L', prevY, prevX - 1),
('R', prevY, prevX + 1)]:
trace("try: %s %u,%u"%(a,y,x))
if y < 0 or x < 0 or y >= h or x >= w:
trace("out of map: %s %u,%u"%(a,y,x))
continue
if (y,x) in visited:
trace("already visited: %s %u,%u"%(a,y,x))
continue
obj = gm[y][x]
if obj == '#':
continue # skip wall
trace("new area: %s %u,%u reached from %u,%u"%(a,y,x,prevY,prevX))
visited[(y,x)] = (a, prevY, prevX)
stack.append((y,x))
if obj == 'B':
print("Bike found!")
print("Follow me: ")
path = []
# print pretty map and instructions
trace("\n".join([str(pos)+"->"+str(prev) for pos,prev in visited.items()] ))
while visited[(y,x)]:
m = visited[(y,x)]
a,y,x=m
trace("adding: ", m)
path.insert(0, m)
print("".join([a for a,_,_ in path]))
plan = [list(r) for r in gm]
trace(plan)
for a,y,x in path:
if plan[y][x] != 'B':
plan[y][x] = '*' if (y,x) != pos else "E"
for r in range(len(plan)):
print("%s\t\t%s"%(gm[r], "".join(plan[r])))
print ("\n")
return
del stack[0]
print("I can't reach the bike! My position is ", pos)
print("\n".join(gm))
print("\n")
b1 = Bike(["..#...#..",
"....#...B"])
b1.findRoute(0,0)
b1.findRoute(len(b1._m),0)
b1.findRoute(0,len(b1._m[0]))
bb = Bike(["..#...#..",
"....#.#.B"])
bb.findRoute(0,0)
b2 = Bike([".#",
".#",
"..",
"#.",
".B"])
b2.findRoute(0,0)
b3 = Bike([".....#",
".....#",
"####.#",
".B....",
".....B"])
b3.findRoute(1,3)
b4= Bike([".....#..#.....#...#",
".#####..#..#..#...#",
"...........#......#",
"..#...#..#######..#",
"..###.#......#....#",
"......#........#..#",
".##.######..#..#..#",
"..#..B.#....#......"])
b4.findRoute(0,0)
b4.findRoute(0,10)
b4.findRoute(7,18)
Output:
Got new map! 2x9
Bike found!
Follow me:
DRRRURRDRRR
..#...#.. E.#***#..
....#...B ****#***B
You are out of map, too bad: (2, 0)
You are out of map, too bad: (0, 9)
Got new map! 2x9
I can't reach the bike! My position is (0, 0)
..#...#..
....#.#.B
Got new map! 5x2
Bike found!
Follow me:
DDRDD
.# E#
.# *#
.. **
#. #*
.B .B
Got new map! 5x6
Bike found!
Follow me:
RDDDR
.....# .....#
.....# ...E*#
####.# ####*#
.B.... .B..*.
.....B ....*B
Got new map! 8x19
Bike found!
Follow me:
DDDDDRRRDDRR
.....#..#.....#...# E....#..#.....#...#
.#####..#..#..#...# *#####..#..#..#...#
...........#......# *..........#......#
..#...#..#######..# *.#...#..#######..#
..###.#......#....# *.###.#......#....#
......#........#..# ****..#........#..#
.##.######..#..#..# .##*######..#..#..#
..#..B.#....#...... ..#**B.#....#......
Bike found!
Follow me:
DDLLLLLDDDLLDDRR
.....#..#.....#...# .....#..#.E...#...#
.#####..#..#..#...# .#####..#.*#..#...#
...........#......# .....******#......#
..#...#..#######..# ..#..*#..#######..#
..###.#......#....# ..###*#......#....#
......#........#..# ...***#........#..#
.##.######..#..#..# .##*######..#..#..#
..#..B.#....#...... ..#**B.#....#......
Bike found!
Follow me:
LLLLUULLULLLLUULLLDDDLLDDRR
.....#..#.....#...# .....#..#.....#...#
.#####..#..#..#...# .#####..#..#..#...#
...........#......# .....****..#......#
..#...#..#######..# ..#..*#.*#######..#
..###.#......#....# ..###*#.*****#....#
......#........#..# ...***#.....***#..#
.##.######..#..#..# .##*######..#.*#..#
..#..B.#....#...... ..#**B.#....#.****E
Has a bug. Doesn't count the last packet
##########
# Tests
##########
#import functools
def distr_toffee(packets):
lo,arrangement = find(packets,5)
sum_per_box = list(map(sum,arrangement))
print("%s\n%s\n%s\n%s"%(packets,lo,sum_per_box,arrangement))
print("Test %s"%("PASSED\n" if sum(packets)==sum(sum_per_box) else \
"FAILED: %u packets distributed instead of %u\n"%(sum(sum_per_box), sum(packets))))
distr_toffee([1,1,1,1,1])
distr_toffee([1,2,3,4,5])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,21,41,61,81,159,160,169,170,179,180,189,190,199,200])
Result:
[1, 1, 1, 1, 1]
1
[1, 1, 1, 1, 1]
[[1], [1], [1], [1], [1]]
Test PASSED
[1, 2, 3, 4, 5]
5
[3, 3, 4, 5]
[[1, 2], [3], [4], [5]]
Test PASSED
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
9.65625
[7, 8, 6, 6, 6]
[[1, 2, 3, 1], [2, 3, 1, 2], [3, 1, 2], [3, 1, 2], [3, 1, 2]]
Test FAILED: 33 packets distributed instead of 36
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
6.9375
[3, 4, 5, 3, 4]
[[1, 2], [3, 1], [2, 3], [1, 2], [3, 1]]
Test FAILED: 19 packets distributed instead of 30
[1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200]
499.71142578125
[364, 329, 349, 369, 389]
[[1, 21, 41, 61, 81, 159], [160, 169], [170, 179], [180, 189], [190, 199]]
Test FAILED: 1800 packets distributed instead of 2000
Python
def trace(*txt):
traceOn = False
if traceOn:
print(*txt)
def getTimeForDelivery(boxes, machines):
time = 0
if len(machines) == 0 and len(boxes)> 0:
print("No machines, That will take eternity\n")
return
# work on a copy of boxes and set the weight to deliver
# to 0 when delivered
delb = boxes[:]
# while we have anything to deliver
while len([b for b in delb if b > 0]):
noofdeliveries = 0
for m in machines:
for bIx in range(len(delb)):
b = delb[bIx]
if b == 0:
continue
if m >= b:
trace("box %u goes with machine %u"%(b, m))
noofdeliveries += 1
delb[bIx] = 0
break
time += 1
trace("waiting for machines... 1 min")
if noofdeliveries == 0:
print("Something goes wrong, cannot deliver anything for boxes %s with machines %s\n"%(boxes, machines))
return
print("%u mins to move boxes %s with machines %s\n"%(time, boxes, machines))
return time
# negative tests
getTimeForDelivery([],[1])
getTimeForDelivery([1],[])
getTimeForDelivery([1],[0])
getTimeForDelivery([1,2,3],[1,1])
# positive
getTimeForDelivery([1,1,3],[1,3])
getTimeForDelivery([3,3,3],[1,3])
getTimeForDelivery([1,1],[1,3,5,6])
Output:
0 mins to move boxes [] with machines [1]
No machines, That will take an eternity
Something goes wrong, cannot deliver anything for boxes [1] with machines [0]
Something goes wrong, cannot deliver anything for boxes [1, 2, 3] with machines [1, 1]
2 mins to move boxes [1, 1, 3] with machines [1, 3]
3 mins to move boxes [3, 3, 3] with machines [1, 3]
1 mins to move boxes [1, 1] with machines [1, 3, 5, 6]
Python:
def trace(txt):
traceOn = False
if traceOn:
print(txt)
class Scheduler:
def __init__(self):
self._s = {}
def addPerson(self, name, *schedule):
self._s[name] = schedule
def getFreeTime(self, *names):
freeTime = set(range(0,24*100)) # in minutes
for name in names:
busyTime = set()
for start, end in self._s[name]:
busyTime |= set(range(int(start*100), int(end*100)))
trace("%s BUSY -> %s"%(name, busyTime))
freeTime = freeTime - busyTime
trace("%s FREE -> %s"%(name, freeTime))
startFree = None
prev = None
res = []
for min in sorted([*freeTime]):
if startFree == None:
startFree = min
continue
if prev is not None and min-prev > 1:
res.append((startFree/100,(prev+1)/100))
prev = min
startFree = min
prev = min
if prev is not None:
res.append((startFree/100,(prev+1)/100))
print("free time: %-20s \t%s"%(names,res))
s = Scheduler()
s.addPerson('Alice', (13.5, 14), (15.75, 17))
s.addPerson('Bob', (9, 12), (13, 14), (14, 16))
s.addPerson('Eve', (9, 11), (12.5, 13.5), (14, 15), (16, 18))
s.addPerson('Mallory', (0, 9), (12, 24))
s.getFreeTime('Alice')
s.getFreeTime('Alice', 'Bob')
s.getFreeTime('Bob', 'Mallory')
s.getFreeTime('Alice', 'Bob', 'Eve')
Output:
free time: ('Alice',) [(0.0, 13.5), (14.0, 15.75), (17.0, 24.0)]
free time: ('Alice', 'Bob') [(0.0, 9.0), (12.0, 13.0), (17.0, 24.0)]
free time: ('Bob', 'Mallory') []
free time: ('Alice', 'Bob', 'Eve') [(0.0, 9.0), (12.0, 12.5), (18.0, 24.0)]
def trace(*args):
traceOn = False
if traceOn:
print(*args)
def calc_deviation_for_box(distr, avg, boxId):
return (avg - sum(distr[boxId]))**2
def calc_deviation(distr, avg):
diff_from_optimal = 0
for boxId in range(1,6):
diff_from_optimal += calc_deviation_for_box(distr, avg, boxId)
diff_from_optimal = round(diff_from_optimal**(0.5),4)
trace("diff_from_optimal=", diff_from_optimal, distr)
return diff_from_optimal
def distr_toffee(packets):
distr = {}
noof_toffee = sum(packets)
noof_packets = len(packets)
assert noof_packets >= 5, "packets are not enough for 5 boxes"
avg_per_box = noof_toffee/5
packetIx = 0
print("Start: noof_toffee=", noof_toffee, "noof_packets=", noof_packets, "avg_per_box=",avg_per_box)
print(packets)
# initial distribution: put less than avg except for the last box
for box in range(1,6):
trace("=== Box", box)
distr[box] = []
toffee_in_box = 0
while packetIx != noof_packets:
trace("toffee_in_box + packets[packetIx]=", toffee_in_box + packets[packetIx])
trace("packets_left=", noof_packets - packetIx, "5-box=", 5-box)
if box != 5:
if noof_packets - packetIx <= 5-box:
trace("next box, please: leave packets for remaining boxes")
break
if toffee_in_box > 0 and toffee_in_box + packets[packetIx] > avg_per_box:
trace("next box, please: stop before avg threshold")
break
distr[box].append(packets[packetIx])
trace("put", packetIx, "to", box)
toffee_in_box += packets[packetIx]
packetIx +=1
# optimization
diff_from_optimal = calc_deviation(distr, avg_per_box)
while True:
for box in range(5,1,-1):
trace("=== Optimizing Box", box)
while True:
if len(distr[box]) == 1:
trace("Next box, this one has just one packet")
break
diff_orig = (avg_per_box - sum(distr[box]))**2 + (avg_per_box - sum(distr[box-1]))**2
diff_new = (avg_per_box - (sum(distr[box]) - distr[box][0]))**2 + (avg_per_box - (sum(distr[box-1]) + distr[box][0]))**2
diff_orig = round(diff_orig**(0.5),4)
diff_new = round(diff_new**(0.5),4)
if diff_new > diff_orig:
trace("Next box, this one is good: ", diff_new, " vs.", diff_orig)
break
trace("move packet:", diff_new, " vs.", diff_orig)
distr[box-1].append(distr[box][0])
distr[box].pop(0)
trace(distr[box-1],distr[box])
new_diff = calc_deviation(distr, avg_per_box)
if new_diff >= diff_from_optimal:
break
diff_from_optimal = new_diff
print(distr)
print(list(map(lambda box: sum(distr[box]), range(1,6))))
print("==================================================== DONE", diff_from_optimal)
##########
# Tests
##########
distr_toffee([1,1,1,1,1])
distr_toffee([1,2,3,4,5])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,2,3,1,2,3,1,2,3,1,2,3,1,2,3])
distr_toffee([1,21,41,61,81,159,160,169,170,179,180,189,190,199,200])
Output:
Start: noof_toffee= 5 noof_packets= 5 avg_per_box= 1.0
[1, 1, 1, 1, 1]
{1: [1], 2: [1], 3: [1], 4: [1], 5: [1]}
[1, 1, 1, 1, 1]
==================================================== DONE 0.0
Start: noof_toffee= 15 noof_packets= 5 avg_per_box= 3.0
[1, 2, 3, 4, 5]
{1: [1], 2: [2], 3: [3], 4: [4], 5: [5]}
[1, 2, 3, 4, 5]
==================================================== DONE 3.1623
Start: noof_toffee= 36 noof_packets= 18 avg_per_box= 7.2
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
{1: [1, 2, 3, 1], 2: [2, 3, 1, 2], 3: [3, 1, 2, 3], 4: [1, 2, 3], 5: [1, 2, 3]}
[7, 8, 9, 6, 6]
==================================================== DONE 2.6077
Start: noof_toffee= 30 noof_packets= 15 avg_per_box= 6.0
[1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3]
{1: [1, 2, 3], 2: [1, 2, 3], 3: [1, 2, 3], 4: [1, 2, 3], 5: [1, 2, 3]}
[6, 6, 6, 6, 6]
==================================================== DONE 0.0
Start: noof_toffee= 2000 noof_packets= 15 avg_per_box= 400.0
[1, 21, 41, 61, 81, 159, 160, 169, 170, 179, 180, 189, 190, 199, 200]
{1: [1, 21, 41, 61, 81, 159], 2: [160, 169, 170], 3: [179, 180], 4: [189, 190], 5: [199, 200]}
[364, 499, 359, 379, 399]
==================================================== DONE 114.9783
def validateStr(s):
braces = {'(':')', '[':']', '{':'}', '<':'>'}
closing = [v for _,v in braces.items()]
stack = []
for c in s:
if c in braces:
stack.append(braces[c])
elif c in closing:
if len(stack) and c == stack[-1]:
del stack[-1]
else:
print("%-15s\tInvalid. Unpaired %c"%(s,c))
return False
if len(stack):
print("%-15s\tInvalid. Not closed braces: %s"%(s,"".join(stack)))
return False
print("%-15s\tok"%(s))
return True
validateStr("([<>])")
validateStr("([<")
validateStr(")([<>])(")
validateStr("([)]")
validateStr("([<!#%^&>])")
Output:
([<>]) ok
([< Invalid. Not closed braces: )]>
)([<>])( Invalid. Unpaired )
([)] Invalid. Unpaired )
([<!#%^&>]) ok
def trace(*args):
traceOn = False
if traceOn:
print(*args)
class Net:
'''
Allows finding a minimal set of stores which can serve an order.
Returns these stores and the products of interest that they have.
The same product might be shown for several stores if they all
have that. Nethertheless, the list of stores will be optimal.
'''
def __init__(self):
self._s = {}
def addStore(self, name, *prods):
print("Store %10s has %s"%(name, prods))
self._s[name] = set(prods)
def getStores(self, *prods):
res = {}
matched_prods = {} # set of (product tuples)->store name
count_prods = {p:[] for p in prods}
search = set(prods)
for s,p in self._s.items():
match = p & search
# perfect match
if len(match) == len(search):
return 'prods: %16s %s'%(search, str({s:search}))
# quickly skip stores which have exactly the same products
if tuple(match) in matched_prods:
# this store is not any better than the one we already found
continue
matched_prods[tuple(match)] = s
res[s] = match
for p in match:
count_prods[p].append(s)
trace("count_prods=",count_prods)
# prepare to drop stores with less number of useful products
# 1. we will for take stores with unique products and as a result all other their products
# 2. now we need to care only about all other products when dropping excessive stores
# We will sort stores in order of remaining useful products
# and drop those which have all products covered by stores below them in the list
uniq = {p for p,stores in count_prods.items() if len(stores)==1}
trace("uniq=", uniq)
uniq_and_related = set()
for s,p in res.items():
if len(p & uniq)>0:
uniq_and_related |= p
trace("uniq_and_related=", uniq_and_related)
noof_matches_exc_uniq = {s:len(res[s]-uniq_and_related) for s,k in res.items()}
stores_sorted = sorted(noof_matches_exc_uniq.items(), key=lambda x: x[1])
trace("stores_sorted=", stores_sorted)
# drop out stores which have less of requested products
for store in stores_sorted:
s = store[0]
# drop the store if all its items are covered by other stores together
cumulative_os = set()
for os in list(res.keys()): # os is other store
if s == os:
continue
# check because we drop stores on the go
if s not in res.keys() or os not in res.keys():
continue
s_specials = res[s] - res[os]
os_specials = res[os] - res[s]
if len(os_specials) == 0:
del res[os]
elif len(s_specials) == 0:
del res[s]
else:
cumulative_os.update(res[os])
# drop if these products are covered by other stores
if s in res.keys() and len(res[s] - cumulative_os) == 0:
del res[s]
return 'prods: %16s %s'%(search, str(res))
n = Net()
n.addStore('Amazon', 1,2,3)
n.addStore('Ozon', 3, 4)
n.addStore('Wallmart1', 5)
n.addStore('Wallmart2', 5)
n.addStore('Wallmart3', 5)
n.addStore('AliExpress', 3, 6)
n.addStore('Ebay', 1,2,5)
print(n.getStores(1))
print(n.getStores(1,3))
print(n.getStores(1,5))
print(n.getStores(3,4,5))
print(n.getStores(1,3,5))
print(n.getStores(1,2,3,4,5))
print(n.getStores(3,5))
print(n.getStores(1,2,4,6))
print("===")
n2 = Net()
n2.addStore('st_1', 'x1', 'x2', 'x3', 'x4')
n2.addStore('st_2', 'x1', 'x2', 'x5')
n2.addStore('st_3', 'x3', 'x4')
print(n2.getStores('x1', 'x2', 'x3', 'x4', 'x5'))
print("===")
n3 = Net()
n3.addStore('st_1', 'x1', 'x2', 'x3')
n3.addStore('st_2', 'x1', 'x2', 'y3')
n3.addStore('st_3', 'x3', 'z1', 'z2', 'z3')
print(n3.getStores('x1', 'x2', 'x3', 'y3', 'z3'))
print("===")
n4 = Net()
n4.addStore('st_1', 1,2)
n4.addStore('st_2', 1,'a')
n4.addStore('st_3', 2,'a')
n4.addStore('st_4', 3,'a','z')
print(n4.getStores(1,2,3,'a','x','z'))
Output
Store Amazon has (1, 2, 3)
Store Ozon has (3, 4)
Store Wallmart1 has (5,)
Store Wallmart2 has (5,)
Store Wallmart3 has (5,)
Store AliExpress has (3, 6)
Store Ebay has (1, 2, 5)
prods: {1} {'Amazon': {1}}
prods: {1, 3} {'Amazon': {1, 3}}
prods: {1, 5} {'Ebay': {1, 5}}
prods: {3, 4, 5} {'Ozon': {3, 4}, 'Wallmart1': {5}}
prods: {1, 3, 5} {'Amazon': {1, 3}, 'Ebay': {1, 5}}
prods: {1, 2, 3, 4, 5} {'Ozon': {3, 4}, 'Ebay': {1, 2, 5}}
prods: {3, 5} {'Amazon': {3}, 'Wallmart1': {5}}
prods: {1, 2, 4, 6} {'Amazon': {1, 2}, 'Ozon': {4}, 'AliExpress': {6}}
===
Store st_1 has ('x1', 'x2', 'x3', 'x4')
Store st_2 has ('x1', 'x2', 'x5')
Store st_3 has ('x3', 'x4')
prods: {'x4', 'x5', 'x3', 'x2', 'x1'} {'st_1': {'x3', 'x4', 'x2', 'x1'}, 'st_2': {'x5', 'x2', 'x1'}}
===
Store st_1 has ('x1', 'x2', 'x3')
Store st_2 has ('x1', 'x2', 'y3')
Store st_3 has ('x3', 'z1', 'z2', 'z3')
prods: {'y3', 'x3', 'x2', 'z3', 'x1'} {'st_2': {'x2', 'x1', 'y3'}, 'st_3': {'z3', 'x3'}}
===
Store st_1 has (1, 2)
Store st_2 has (1, 'a')
Store st_3 has (2, 'a')
Store st_4 has (3, 'a', 'z')
prods: {1, 2, 3, 'x', 'a', 'z'} {'st_1': {1, 2}, 'st_4': {'a', 3, 'z'}}
Now your code is good. Thanks! :)
- Diana.Savvatina November 11, 2018