-
Notifications
You must be signed in to change notification settings - Fork 0
/
11.py
67 lines (59 loc) · 2.47 KB
/
11.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
import math
import copy
import collections
def go(floor, steps, minsteps, pairs, hist):
# om vi gått för långt
if steps >= minsteps:
return hist, math.inf
# om det skiter sig
genfloors = set([x[0] for x in pairs])
for p in pairs:
if p[0]!=p[1] and p[1] in genfloors:
return hist, math.inf
# om historien upprepar sig utan att det blivit bättre
phash = frozenset({(a,b,c) for (a,b),c in collections.Counter(pairs).items()})
if phash in hist and hist[phash] <= steps:
return hist, math.inf
hist[phash] = steps
# om vi är klara
if phash == {(3,3,len(pairs))}:
return hist, steps
# annars, gå vidare
gens = [i for i,(g,m) in enumerate(pairs) if g == floor]
mics = [i for i,(g,m) in enumerate(pairs) if m == floor]
for newfloor in [x for x in range(3,-1,-1) if abs(floor-x)==1]:
#print(pairs, gens, mics, newfloor)
for i, g1 in enumerate(gens):
newps = copy.deepcopy(pairs)
newps[g1] = (newfloor,newps[g1][1])
hist, ns = go(newfloor, steps+1, minsteps, newps, hist)
minsteps = min(minsteps, ns)
if pairs[g1][1] == floor:
newps[g1] = (newfloor, newfloor)
hist, ns = go(newfloor, steps+1, minsteps, newps, hist)
minsteps = min(minsteps, ns)
for g2 in gens[i+1:]:
newps = copy.deepcopy(pairs)
newps[g1] = (newfloor,newps[g1][1])
newps[g2] = (newfloor,newps[g2][1])
hist, ns = go(newfloor, steps+1, minsteps, newps, hist)
minsteps = min(minsteps, ns)
for i, m1 in enumerate(mics):
newps = copy.deepcopy(pairs)
newps[m1] = (newps[m1][0], newfloor)
hist, ns = go(newfloor, steps+1, minsteps, newps, hist)
minsteps = min(minsteps, ns)
for m2 in mics[i+1:]:
newps = copy.deepcopy(pairs)
newps[m1] = (newps[m1][0], newfloor)
newps[m2] = (newps[m2][0], newfloor)
hist, ns = go(newfloor, steps+1, minsteps, newps, hist)
minsteps = min(minsteps, ns)
return hist, minsteps
# (genfloor, microchipfloor) order is co, po, pr, ru, th
pairs = [(0, 0), (0, 1), (0, 1), (0, 0), (0, 0)]
hist, steps = go(0,0,100,pairs,{})
print('Part 1: ',steps)
pairs = [(0, 0), (0, 1), (0, 1), (0, 0), (0, 0), (0, 0), (0, 0)]
hist, steps = go(0,0,100,pairs,{})
print('Part 2: ',steps)