Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from pathlib import Path
- from collections import deque
- from functools import lru_cache
- @lru_cache(maxsize=None)
- def get_Paths(start, end, gridname):
- KEYPAD = [["7", "8", "9"], ["4", "5", "6"], ["1", "2", "3"], [" ", "0", "A"]]
- DPAD = [[" ", "^", "A"], ["<", "v", ">"]]
- grid = KEYPAD if gridname == "KEYPAD" else DPAD
- """Compute distances using optimized BFS."""
- height, width = len(grid), len(grid[0])
- DIRECTIONS = {(0, 1): "v", (0, -1): "^", (1, 0): ">", (-1, 0): "<"}
- def find_index_2d(lst, value):
- for i, row in enumerate(lst):
- if value in row:
- return (row.index(value), i)
- return None
- start_point = find_index_2d(grid, start)
- end_point = find_index_2d(grid, end)
- blank = find_index_2d(grid, " ")
- seen = {start_point, blank}
- queue = deque([(start_point, [])])
- paths = []
- min_distance = float("inf")
- distance = 0
- while queue and distance <= min_distance:
- (x, y), path = queue.popleft()
- distance = len(path)
- if (x, y) == end_point:
- min_distance = distance
- paths.append("".join(path) + "A")
- continue
- for dx, dy in DIRECTIONS:
- new_x, new_y = x + dx, y + dy
- if 0 <= new_x < width and 0 <= new_y < height:
- neighbor = (new_x, new_y)
- if neighbor not in seen:
- queue.append((neighbor, path + [DIRECTIONS[(dx, dy)]]))
- seen.add((x, y))
- return paths
- def parse_data(file_name):
- """Read and process the grid data from the file."""
- file_path = Path(__file__).resolve().parent / f"{file_name}.txt"
- with open(file_path) as f:
- data = f.read().splitlines()
- return data
- @lru_cache(maxsize=None)
- def min_length_DPAD(sequence: str, depth: int) -> int:
- if depth == 0:
- return len(sequence)
- b = 0
- prev = "A"
- for character in sequence:
- c1 = get_Paths(prev, character, "DPAD")
- a = [min_length_DPAD(sub_sequence, depth - 1) for sub_sequence in c1]
- b += min(a)
- prev = character
- return b
- def find_complexity(sequence: str, depth: int) -> int:
- prev = "A"
- b = 0
- for character in sequence:
- c1 = get_Paths(prev, character, "KEYPAD")
- a = [min_length_DPAD(sub_sequence, depth) for sub_sequence in c1]
- prev = character
- b += min(a)
- return b * int(sequence[:-1])
- def find_total_complexity(data, depth=2):
- return sum(find_complexity(sequence, depth) for sequence in data)
- def main():
- data = parse_data("data")
- print(f"Total complexity with depth=2: {find_total_complexity(data, 2)}")
- print(f"Total complexity with depth=25: {find_total_complexity(data, 25)}")
- if __name__ == "__main__":
- main()
Advertisement
Add Comment
Please, Sign In to add comment