Advertisement
Guest User

AOC2022_Day16

a guest
Dec 17th, 2022
534
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.75 KB | Source Code | 0 0
  1. import numpy as np
  2. import re
  3. from queue import PriorityQueue
  4.  
  5. def heuristic(node, time_remaining, visited, flow_rates, closest_distance):
  6. max_score = 0
  7. scores = []
  8. nodes = []
  9. for node, distance in closest_distance[node].items():
  10. if node in visited:
  11. continue
  12. if distance < time_remaining:
  13. score = (time_remaining - distance - 1) * flow_rates[node]
  14. if score > 0:
  15. scores.append(score)
  16. nodes.append(node)
  17. max_score += score
  18. sort_args = np.argsort(scores)[::-1]
  19. scores = [scores[x] for x in sort_args]
  20. ordered_nodes = [nodes[x] for x in sort_args]
  21. return max_score, scores, ordered_nodes
  22.  
  23. def best_score(min_score, time_remaining, node, visited, neighbors, flow_rates, closest_distance):
  24. max_score, ordered_weights, ordered_nodes = heuristic(node, time_remaining, visited, flow_rates, closest_distance)
  25. if max_score <= min_score:
  26. return 0
  27. actual_max_score = min_score
  28. for weight, n in zip(ordered_weights, ordered_nodes):
  29. visited.add(n)
  30. score = weight + best_score(
  31. max(actual_max_score - weight, 0),
  32. time_remaining - closest_distance[node][n] - 1,
  33. n,
  34. visited,
  35. neighbors,
  36. flow_rates,
  37. closest_distance
  38. )
  39. actual_max_score = max(actual_max_score, score)
  40. visited.remove(n)
  41. return actual_max_score
  42.  
  43. def distance(start, end, neighbors):
  44. queue = PriorityQueue()
  45. queue.put((0, start))
  46.  
  47. visited = set()
  48. visited.add(start)
  49.  
  50. while not queue.empty():
  51. distance, location = queue.get()
  52. if location == end:
  53. return distance
  54. for neighbor in neighbors[location]:
  55. if neighbor not in visited:
  56. visited.add(neighbor)
  57. queue.put((distance + 1, neighbor))
  58. return 0
  59.  
  60.  
  61.  
  62. ## Code execution
  63.  
  64. pattern = r"Valve ([A-Z]+) has flow rate=(\d+); tunnels? leads? to valves? (.*)"
  65.  
  66. neighbors = {}
  67. flow_rates = {}
  68.  
  69. input_lines = input_string.split('\n')
  70.  
  71. for i in range(len(input_lines)):
  72. line = input_lines[i]
  73.  
  74. matched = re.findall(pattern, line)
  75. flow_rate = int(matched[0][1])
  76. valve = matched[0][0]
  77. to = matched[0][2].split(', ')
  78. neighbors[valve] = neighbors.get(valve, set(to))
  79. flow_rates[valve] = flow_rate
  80.  
  81. nodes = list(neighbors.keys())
  82.  
  83. closest_distance = {}
  84. for m in nodes:
  85. for n in nodes:
  86. if m == n:
  87. continue
  88. closest_distance[m] = closest_distance.get(m, {})
  89. closest_distance[m][n] = distance(m, n, neighbors)
  90.  
  91. answer = best_score(0, 30, 'AA', set(), neighbors, flow_rates, closest_distance)
  92. print(answer)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement