Advertisement
philRG

aoc day 15 (implé. algo pardouin)

Dec 16th, 2021 (edited)
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """ --- Day 15: Chiton ---"""
  2. import heapq
  3.  
  4. import math
  5. from collections import deque
  6.  
  7. import numpy as np
  8.  
  9.  
  10. def bfs():
  11.     """ Y a pas bon le bfs philRG ici """
  12.     queue = deque([(0, [(0, 0)])])
  13.     min_risk = math.inf
  14.     best_path = []
  15.     visited = [(0, 0)]
  16.     while queue:
  17.         risk, path = queue.popleft()
  18.         x, y = path[-1]
  19.         if (x, y) == (9, 9) and risk < min_risk:
  20.             best_path = path
  21.             min_risk = risk
  22.         for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
  23.             n_x, n_y = x + dx, y + dy
  24.             if not in_grid(n_x, n_y) or (n_x, n_y) in path:
  25.                 continue
  26.             queue.append((risk + chitons[n_x, n_y], path + [(n_x, n_y)]))
  27.             # visited.append((n_x, n_y))
  28.     return best_path, min_risk
  29.  
  30.  
  31. def dijkstra():
  32.     """ tentative d'implémenter le pseudo-code de pardouin """
  33.     start, end = (0, 0), (99, 99)
  34.     pqueue = [(0, start)]
  35.     dist_dans_pqueue = {start: 0}
  36.     deja_fait = set()
  37.  
  38.     while pqueue:
  39.         dist, sommet = heapq.heappop(pqueue)
  40.         if sommet in deja_fait:
  41.             continue
  42.         deja_fait.add(sommet)
  43.         x, y = sommet
  44.         voisins = []
  45.         for s in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
  46.             if in_grid(*s):
  47.                 d = dist_dans_pqueue[s] if s in dist_dans_pqueue else chitons[x, y]
  48.                 voisins.append((s, d))
  49.         for s, d in voisins:
  50.             nouv_d = dist + d
  51.             if s in deja_fait:
  52.                 continue
  53.             if s == end:
  54.                 return nouv_d
  55.             if s not in dist_dans_pqueue or dist_dans_pqueue[s] > nouv_d:
  56.                 heapq.heappush(pqueue, (nouv_d, s))
  57.                 dist_dans_pqueue[s] = nouv_d
  58.  
  59.  
  60. chitons = np.zeros(shape=(100, 100), dtype=int)
  61. y = 0
  62. while True:
  63.     try:
  64.         for x, value in enumerate(map(int, input())):
  65.             chitons[x, y] = value
  66.         y += 1
  67.     except EOFError:
  68.         break
  69.  
  70. in_grid = lambda x, y: 0 <= x < 100 and 0 <= y < 100
  71.  
  72. # chitons.transpose()
  73.  
  74. risk = dijkstra()
  75.  
  76. print(f'risk = {risk}')
  77.  
Advertisement
RAW Paste Data Copied
Advertisement