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.
109 lines
2.9 KiB
109 lines
2.9 KiB
#!/usr/bin/env python3
|
|
|
|
import sys
|
|
from functools import cache
|
|
|
|
@cache
|
|
def path(f1,f2):
|
|
path = []
|
|
y, x = f1
|
|
while y != 0:
|
|
y -= 1
|
|
path.append((y,x))
|
|
while x != f2[1]:
|
|
x += 1 if f2[1] > x else -1
|
|
path.append((y,x))
|
|
while y != f2[0]:
|
|
y += 1
|
|
path.append((y,x))
|
|
assert path[-1] == f2
|
|
return path
|
|
|
|
def pathvalid(path,board):
|
|
for p in path:
|
|
if p in board: return False
|
|
return True
|
|
|
|
def cost(a,w):
|
|
if a == 'A': return len(w) * 1
|
|
if a == 'B': return len(w) * 10
|
|
if a == 'C': return len(w) * 100
|
|
if a == 'D': return len(w) * 1000
|
|
|
|
def endstate(board):
|
|
for f,a in board.items():
|
|
if f[1] != target[a]: return False
|
|
return True
|
|
|
|
def target_position(f,b,lowest):
|
|
a = b[f]
|
|
if f[1] != target[a]: return False
|
|
for y in range(f[0],lowest+1):
|
|
if (y,target[a]) not in b: return False
|
|
if b[(y,target[a])] != a: return False
|
|
return True
|
|
|
|
def totarget(board,lowest):
|
|
change = False
|
|
costs = 0
|
|
nb = {k: v for k,v in board.items()}
|
|
for f,a in board.items():
|
|
if target_position(f,nb,lowest): continue
|
|
t = (lowest,target[a])
|
|
while t in nb and nb[t] == a:
|
|
t = (t[0]-1,target[a])
|
|
if t == (0,target[a]): continue
|
|
p = path(f,t)
|
|
if pathvalid(p,nb):
|
|
change = True
|
|
nb.pop(f)
|
|
nb[t] = a
|
|
costs += cost(a,p)
|
|
return nb,costs,change
|
|
|
|
def dfs(board,lowest,costs=0,curmin=sys.maxsize):
|
|
ch = True
|
|
nb = {k: v for k,v in board.items()}
|
|
while ch:
|
|
nb,co,ch = totarget(nb,lowest)
|
|
costs += co
|
|
if endstate(nb):
|
|
return costs
|
|
if costs > curmin: return None
|
|
board = {k: v for k,v in nb.items()}
|
|
for f,a in board.items():
|
|
if f[0] != 0 and not(target_position(f,board,lowest)):
|
|
for f2 in hallway:
|
|
p = path(f,f2)
|
|
if pathvalid(p, board):
|
|
cb = {k: v for k,v in board.items()}
|
|
cb.pop(f)
|
|
cb[f2] = a
|
|
nc = dfs(cb,lowest,costs+cost(a,p),curmin)
|
|
if nc is not None and nc < curmin: curmin = nc
|
|
if curmin < sys.maxsize: return curmin
|
|
|
|
if __name__ == '__main__':
|
|
# challenge 1
|
|
lines = open(sys.argv[1]).readlines()
|
|
start = {}
|
|
for y,l in enumerate(lines[1:]):
|
|
for x,f in enumerate(l[1:]):
|
|
if f in 'ABCD': start[(y,x)] = f
|
|
|
|
hallway = [(0,0), (0,1), (0,3), (0,5), (0,7), (0,9), (0,10)]
|
|
target = {'A': 2, 'B': 4, 'C': 6, 'D': 8}
|
|
|
|
res1 = str(dfs(start,2))
|
|
print("challenge 1:" + "\n" + res1 + "\n")
|
|
|
|
# challenge 2
|
|
lines = open(sys.argv[2]).readlines()
|
|
start = {}
|
|
for y,l in enumerate(lines[1:]):
|
|
for x,f in enumerate(l[1:]):
|
|
if f in 'ABCD': start[(y,x)] = f
|
|
|
|
res2 = str(dfs(start,4))
|
|
print("challenge 2:" + "\n" + res2 + "\n")
|
|
|
|
|