Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
FAQ
What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
Where do I participate?: https://adventofcode.com/
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
Python
Also on Github
749 line-seconds
import collections import dataclasses import heapq import numpy as np from .solver import Solver @dataclasses.dataclass(order=True) class QueueEntry: price: int x: int y: int momentum_x: int momentum_y: int deleted: bool class Day17(Solver): lines: list[str] sx: int sy: int lower_bounds: np.ndarray def __init__(self): super().__init__(17) def presolve(self, input: str): self.lines = input.splitlines() self.sx = len(self.lines[0]) self.sy = len(self.lines) start = (self.sx - 1, self.sy - 1) self.lower_bounds = np.zeros((self.sx, self.sy)) + np.inf self.lower_bounds[start] = 0 queue: list[QueueEntry] = [QueueEntry(0, self.sx - 1, self.sy - 1, 0, 0, False)] queue_entries: dict[tuple[int, int], QueueEntry] = {start: queue[0]} while queue: cur_price, x, y, _, _, deleted = dataclasses.astuple(heapq.heappop(queue)) if deleted: continue del queue_entries[(x, y)] self.lower_bounds[x, y] = cur_price price = cur_price + int(self.lines[y][x]) for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)): nx, ny = x + dx, y + dy if not (0 <= nx < self.sx) or not (0 <= ny < self.sy): continue if price < self.lower_bounds[nx, ny]: self.lower_bounds[nx, ny] = price if (nx, ny) in queue_entries: queue_entries[(nx, ny)].deleted = True queue_entries[(nx, ny)] = QueueEntry(price, nx, ny, 0, 0, False) heapq.heappush(queue, queue_entries[(nx, ny)]) def _solve(self, maximum_run: int, minimum_run_to_turn: int): came_from: dict[tuple[int, int, int, int], tuple[int, int, int, int]] = {} start = (0, 0, 0, 0) queue: list[QueueEntry] = [QueueEntry(self.lower_bounds[0, 0], *start, False)] queue_entries: dict[tuple[int, int, int, int], QueueEntry] = {start: queue[0]} route: list[tuple[int, int]] = [] prices: dict[tuple[int, int, int, int], float] = collections.defaultdict(lambda: np.inf) prices[start] = 0 while queue: _, current_x, current_y, momentum_x, momentum_y, deleted = dataclasses.astuple(heapq.heappop(queue)) cur_price = prices[(current_x, current_y, momentum_x, momentum_y)] if deleted: continue if ((current_x, current_y) == (self.sx - 1, self.sy - 1) and (momentum_x >= minimum_run_to_turn or momentum_y >= minimum_run_to_turn)): previous = came_from.get((current_x, current_y, momentum_x, momentum_y)) route.append((current_x, current_y)) while previous: x, y, *_ = previous if x != 0 or y != 0: route.append((x, y)) previous = came_from.get(previous) break for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)): dot_product = dx * momentum_x + dy * momentum_y if dot_product < 0 or dot_product >= maximum_run: continue if ((momentum_x or momentum_y) and dot_product == 0 and abs(momentum_x) < minimum_run_to_turn and abs(momentum_y) < minimum_run_to_turn): continue new_x, new_y = current_x + dx, current_y + dy if not (0 <= new_x < self.sx) or not (0 <= new_y < self.sy): continue new_momentum_x, new_momentum_y = (dx, dy) if dot_product == 0 else (momentum_x + dx, momentum_y + dy) new_position = (new_x, new_y, new_momentum_x, new_momentum_y) potential_new_price = cur_price + int(self.lines[new_y][new_x]) if potential_new_price < prices[new_position]: queue_entry = queue_entries.get(new_position) if queue_entry: queue_entry.deleted = True queue_entries[new_position] = QueueEntry(potential_new_price + self.lower_bounds[new_x, new_y], *new_position, False) came_from[new_position] = (current_x, current_y, momentum_x, momentum_y) prices[new_position] = potential_new_price heapq.heappush(queue, queue_entries[new_position]) return sum(int(self.lines[y][x]) for x, y in route) def solve_first_star(self) -> int: return self._solve(3, 0) def solve_second_star(self) -> int: return self._solve(10, 4)