101 lines
3.4 KiB
Python
Executable File
101 lines
3.4 KiB
Python
Executable File
#!/usr/bin/env python3
|
|
|
|
from useful import *
|
|
|
|
dirind = {(-1, 0): 0,
|
|
(1, 0): 1,
|
|
(0, -1): 2,
|
|
(0, 1): 3,}
|
|
|
|
def plus(a, b):
|
|
return (a[0] + b[0], a[1] + b[1])
|
|
|
|
def diff(a, b):
|
|
return (a[0] - b[0], a[1] - b[1])
|
|
|
|
def mul(a, b):
|
|
return (a * b[0], a * b[1])
|
|
|
|
def oob(y, x):
|
|
return not (0 <= y < h and 0 <= x < w)
|
|
|
|
def wouldbe4th(step, prev, sec, third):
|
|
return all(step == p for p in (prev, sec, third))
|
|
|
|
def planvisit(step, origin, prev, sec, third):
|
|
global tovisit
|
|
nexttile = plus(origin, step)
|
|
if oob(*nexttile):
|
|
return
|
|
if wouldbe4th(step, prev, sec, third):
|
|
return
|
|
tovisit += [(nexttile, step, prev, sec, third)]
|
|
|
|
def plan2ndvisit(step, times, origin, heat):
|
|
global tovisit
|
|
nexttile = plus(origin, mul(times, step))
|
|
if oob(*nexttile):
|
|
return
|
|
acc, off = 0, origin
|
|
for i in range(times):
|
|
off = plus(off, step)
|
|
acc += heatmap[off]
|
|
tovisit += [(nexttile, step, acc, heat)]
|
|
|
|
heatmap = np.array([[int(c) for c in l] for l in lines(open(0))])
|
|
h, w = heatmap.shape
|
|
shortest = np.ones((4, 4, 4, h, w), dtype=int) * 666666
|
|
|
|
tovisit=deque() # of current position + history
|
|
shortest[:,:,:,0,0] = 0 # start here
|
|
tovisit += [((1, 0), (1, 0), (-1, 0), (-1, 0), (-1, 0)), ((0, 1), (0, 1), (0, -1), (0, -1), (0, -1))]
|
|
|
|
while tovisit:
|
|
visit, prev, second, third, fourth = tovisit.popleft()
|
|
prevsquare = diff(visit, prev)
|
|
p1 = dirind[prev]
|
|
p2 = dirind[second]
|
|
p3 = dirind[third]
|
|
p4 = dirind[fourth]
|
|
curheat, prevheat, curshort, prevshort = (heatmap[visit], heatmap[prevsquare],
|
|
shortest[(p1, p2, p3) + visit],
|
|
shortest[(p2, p3, p4) + prevsquare])
|
|
if curheat + prevshort < curshort: # new minimum, visit new places
|
|
shortest[(p1, p2, p3) + visit] = curheat + prevshort
|
|
#ic(curheat + prevshort)
|
|
for direction in dirind.keys():
|
|
if not plus(direction, prev) == (0, 0):
|
|
planvisit(direction, visit, prev, second, third)
|
|
print(min(collapse(shortest[:,:,:,-1,-1])))
|
|
|
|
shortest = np.ones((4, h, w), dtype=int) * 666666
|
|
shortest[:,0,0] = 0 # start here
|
|
tovisit += [
|
|
((4, 0), (1, 0), sum(heatmap[1:5,0]), 0),
|
|
((0, 4), (0, 1), sum(heatmap[0,1:5]), 0),
|
|
((5, 0), (1, 0), sum(heatmap[1:6,0]), 0),
|
|
((0, 5), (0, 1), sum(heatmap[0,1:6]), 0),
|
|
((6, 0), (1, 0), sum(heatmap[1:7,0]), 0),
|
|
((0, 6), (0, 1), sum(heatmap[0,1:7]), 0),
|
|
((7, 0), (1, 0), sum(heatmap[1:8,0]), 0),
|
|
((0, 7), (0, 1), sum(heatmap[0,1:8]), 0),
|
|
((8, 0), (1, 0), sum(heatmap[1:9,0]), 0),
|
|
((0, 8), (0, 1), sum(heatmap[0,1:9]), 0),
|
|
((9, 0), (1, 0), sum(heatmap[1:10,0]), 0),
|
|
((0, 9), (0, 1), sum(heatmap[0,1:10]), 0),
|
|
((10, 0), (1, 0), sum(heatmap[1:11,0]), 0),
|
|
((0, 10), (0, 1), sum(heatmap[0,1:11]), 0),
|
|
]
|
|
while tovisit:
|
|
#ic(tovisit)
|
|
visit, how, penalty, prevheat = tovisit.popleft()
|
|
curshort = shortest[dirind[how], visit[0], visit[1]]
|
|
newheat = prevheat + penalty
|
|
if newheat < curshort: # new minimum, visit new places
|
|
shortest[dirind[how], visit[0], visit[1]] = newheat
|
|
for direction in dirind.keys():
|
|
if not (plus(direction, how) == (0, 0) or diff(direction, how) == (0, 0)):
|
|
for i in range(4, 11):
|
|
plan2ndvisit(direction, i, visit, newheat)
|
|
print(min(collapse(shortest[:,-1,-1])))
|