You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
75 lines
1.9 KiB
75 lines
1.9 KiB
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
|
|
def memo(f):
|
|
memo = {}
|
|
|
|
def f2(a,x,y,c,e):
|
|
if (x,y) not in memo: memo[(x,y)] = f(a,x,y,c,e)
|
|
return memo[(x,y)]
|
|
return f2
|
|
|
|
def nb(sx, sy):
|
|
n = [(0,1), (1,0), (0,-1), (-1,0)]
|
|
return [(max(0,sx+x), max(0,sy+y)) for x,y in n]
|
|
|
|
def dijkstra(graph, s):
|
|
a = {}
|
|
v = {}
|
|
Q = initG(graph, s, a, v)
|
|
lq = len(Q)
|
|
while len(Q) > 0:
|
|
u = min([u for u in Q], key=lambda x: a[x])
|
|
Q.remove(u)
|
|
for vo in nb(*u):
|
|
if vo in Q:
|
|
distance_update(graph, u,vo,a,v)
|
|
if (len(Q)/lq * 100 % 1) == 0:
|
|
print("|", end='', flush=True)
|
|
print("\n")
|
|
return v
|
|
|
|
def initG(graph, s, a, v):
|
|
for vo in graph.keys():
|
|
a[vo] = 9999999999999999
|
|
v[vo] = 'null'
|
|
a[s] = 0
|
|
Q = [n for n in graph.keys()]
|
|
return Q
|
|
|
|
def distance_update(g, u,vo,a,v):
|
|
alt = a[u] + g[u]
|
|
if alt < a[vo]:
|
|
a[vo] = alt
|
|
v[vo] = u
|
|
|
|
def shortest_path(g, d, v):
|
|
w = [d]
|
|
u = d
|
|
r = 0
|
|
while v[u] != 'null':
|
|
r += g[u]
|
|
u = v[u]
|
|
w.append(u)
|
|
return w.reverse(), r
|
|
|
|
if __name__ == '__main__':
|
|
nums = [[int(i) for i in list(line.strip('\n'))] for line in open(sys.argv[1])]
|
|
|
|
# challenge 1
|
|
g1 = {(x,y) : nums[y][x] for x in range(len(nums[0])) for y in range(len(nums))}
|
|
v = dijkstra(g1, (0,0))
|
|
w, r = shortest_path(g1, (len(nums)-1, len(nums[0])-1), v)
|
|
|
|
res1 = str(r)
|
|
print("challenge 1:" +"\n" + res1 + "\n")
|
|
|
|
# challenge 2 - inefficient
|
|
g2 = {(x+i*len(nums[0]),y+j*len(nums)) : (nums[y][x] + i + j if nums[y][x] + i + j < 10 else (nums[y][x] + i + j) % 10 + 1) for x in range(len(nums[0])) for y in range(len(nums)) for i in range(5) for j in range(5)}
|
|
v = dijkstra(g2, (0,0))
|
|
w, r = shortest_path(g2, (len(nums[0])*5-1, len(nums)*5-1), v)
|
|
|
|
res2 = str(r)
|
|
print("challenge 2:" +"\n" + res2 + "\n")
|
|
|
|
|