Guest User

Untitled

a guest
Dec 21st, 2024
518
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.82 KB | None | 0 0
  1. from pathlib import Path
  2. from collections import deque
  3. from functools import lru_cache
  4.  
  5.  
  6. @lru_cache(maxsize=None)
  7. def get_Paths(start, end, gridname):
  8.     KEYPAD = [["7", "8", "9"], ["4", "5", "6"], ["1", "2", "3"], [" ", "0", "A"]]
  9.     DPAD = [[" ", "^", "A"], ["<", "v", ">"]]
  10.     grid = KEYPAD if gridname == "KEYPAD" else DPAD
  11.     """Compute distances using optimized BFS."""
  12.     height, width = len(grid), len(grid[0])
  13.     DIRECTIONS = {(0, 1): "v", (0, -1): "^", (1, 0): ">", (-1, 0): "<"}
  14.  
  15.     def find_index_2d(lst, value):
  16.         for i, row in enumerate(lst):
  17.             if value in row:
  18.                 return (row.index(value), i)
  19.         return None
  20.  
  21.     start_point = find_index_2d(grid, start)
  22.     end_point = find_index_2d(grid, end)
  23.     blank = find_index_2d(grid, " ")
  24.     seen = {start_point, blank}
  25.     queue = deque([(start_point, [])])
  26.     paths = []
  27.  
  28.     min_distance = float("inf")
  29.     distance = 0
  30.     while queue and distance <= min_distance:
  31.         (x, y), path = queue.popleft()
  32.         distance = len(path)
  33.         if (x, y) == end_point:
  34.             min_distance = distance
  35.             paths.append("".join(path) + "A")
  36.             continue
  37.         for dx, dy in DIRECTIONS:
  38.             new_x, new_y = x + dx, y + dy
  39.             if 0 <= new_x < width and 0 <= new_y < height:
  40.                 neighbor = (new_x, new_y)
  41.                 if neighbor not in seen:
  42.                     queue.append((neighbor, path + [DIRECTIONS[(dx, dy)]]))
  43.         seen.add((x, y))
  44.  
  45.     return paths
  46.  
  47.  
  48. def parse_data(file_name):
  49.     """Read and process the grid data from the file."""
  50.  
  51.     file_path = Path(__file__).resolve().parent / f"{file_name}.txt"
  52.     with open(file_path) as f:
  53.         data = f.read().splitlines()
  54.  
  55.     return data
  56.  
  57.  
  58. @lru_cache(maxsize=None)
  59. def min_length_DPAD(sequence: str, depth: int) -> int:
  60.     if depth == 0:
  61.         return len(sequence)
  62.     b = 0
  63.     prev = "A"
  64.     for character in sequence:
  65.         c1 = get_Paths(prev, character, "DPAD")
  66.         a = [min_length_DPAD(sub_sequence, depth - 1) for sub_sequence in c1]
  67.         b += min(a)
  68.         prev = character
  69.     return b
  70.  
  71.  
  72. def find_complexity(sequence: str, depth: int) -> int:
  73.     prev = "A"
  74.     b = 0
  75.     for character in sequence:
  76.         c1 = get_Paths(prev, character, "KEYPAD")
  77.         a = [min_length_DPAD(sub_sequence, depth) for sub_sequence in c1]
  78.         prev = character
  79.         b += min(a)
  80.     return b * int(sequence[:-1])
  81.  
  82.  
  83. def find_total_complexity(data, depth=2):
  84.     return sum(find_complexity(sequence, depth) for sequence in data)
  85.  
  86.  
  87. def main():
  88.     data = parse_data("data")
  89.     print(f"Total complexity with depth=2: {find_total_complexity(data, 2)}")
  90.     print(f"Total complexity with depth=25: {find_total_complexity(data, 25)}")
  91.  
  92.  
  93. if __name__ == "__main__":
  94.     main()
  95.  
Advertisement
Add Comment
Please, Sign In to add comment