b-recursive-slow.py (1432B)
1 import fileinput 2 from functools import cache 3 4 def readline(line): 5 b = [] 6 j = line.index(']') 7 while '(' in line[j:]: 8 i = line[j:].index('(') + j + 1 9 j = line[i:].index(')') + i 10 x = 0 11 for y in line[i:j].split(','): 12 x |= 1 << int(y) 13 b.append(x) 14 15 begin = line.index('{')+1 16 end = line.index('}') 17 j = tuple(int(x) for x in line[begin:end].split(',')) 18 19 return tuple(b), j 20 21 def newj(j, b, n): 22 return tuple(j[i]-n if b & (1<<i) else j[i] for i in range(len(j))) 23 24 def can(b, i): 25 return b & (1 << i) != 0 26 27 inf = 99999999999 28 @cache 29 def sol(b, j, best): 30 print(f"{b} {j} {best}") 31 if all(x == 0 for x in j): 32 return 0 33 if any(x < 0 for x in j): 34 return inf 35 if len(b) == 0: 36 return inf 37 for i in range(len(j)): 38 if j[i] > 0 and not any(can(bb, i) for bb in b): 39 return inf 40 41 # Optimization: if any of the buttons is the last one available that 42 # toggles a certain jolt, we press it as much as needed. 43 for i in range(len(j)): 44 for k in range(len(b)): 45 bb = b[:k] + b[k+1:] 46 if can(b[k], i) and not any(can(x, i) for x in bb): 47 return j[i] + sol(bb, newj(j, b[k], j[i]), best) 48 49 c = 0 50 while all(x >= 0 for x in j) and c <= best: 51 best = min(best, c + sol(b[1:], j, best)) 52 j = newj(j, b[0], 1) 53 c += 1 54 55 return best 56 57 with fileinput.input() as lines: 58 sols = [] 59 c = 1 60 for line in lines: 61 print(f"doing line {c}: {line}") 62 c += 1 63 sols.append(sol(*readline(line), inf)) 64 print(sols) 65 print(sum(sols)) 66