1from __future__ import annotations
2
3import typing
4import dataclasses
5import re
6import heapq
7
8@dataclasses.dataclass(order=True)
9class Vector:
10 x: int
11 y: int
12
13 def __add__(self, b: typing.Self):
14 return Vector(self.x + b.x, self.y + b.y)
15
16
17@dataclasses.dataclass
18class Problem:
19 a: Vector
20 b: Vector
21 solution: Vector
22
23def get_data(path):
24 with open(path) as f:
25 data = f.read()
26
27 problem_data = data.split("\n\n")
28 for problem_datum in problem_data:
29 problem_components = []
30 for line in problem_datum.splitlines():
31 x, y = re.findall(r"(\d+)", line)
32 problem_components.append(Vector(int(x), int(y)))
33 yield Problem(*problem_components)
34
35
36def find_problem_cost(problem: Problem) -> int:
37 pqueue = [(0, 0, 0, Vector(0, 0))]
38
39 visited = set()
40 while pqueue:
41 cost, a_presses, b_presses, pos = heapq.heappop(pqueue)
42
43 key = (a_presses, b_presses)
44 if key in visited:
45 continue
46 visited.add(key)
47
48 if pos == problem.solution:
49 return cost
50
51 if pos.x > problem.solution.x or pos.y > problem.solution.y:
52 continue
53
54 if a_presses > 100 or b_presses > 100:
55 continue
56
57 heapq.heappush(pqueue, (cost + 3, a_presses + 1, b_presses, problem.a + pos))
58 heapq.heappush(pqueue, (cost + 1, a_presses, b_presses + 1, problem.b + pos))
59 return 0
60
61def main(problems):
62 output = 0
63 for problem in problems:
64 cost = find_problem_cost(problem)
65 output += cost
66 return output
67
68if __name__ == "__main__":
69 print(main(get_data("day_13_input_test.txt")))
70 print(main(get_data("day_13_input.txt")))
1from __future__ import annotations
2
3import typing
4import dataclasses
5import re
6
7@dataclasses.dataclass(order=True)
8class Vector:
9 x: int
10 y: int
11
12 def __add__(self, b):
13 if isinstance(b, Vector):
14 return Vector(self.x + b.x, self.y + b.y)
15 elif isinstance(b, int):
16 return Vector(self.x + b, self.y + b)
17 raise Exception(f"Cannot handle {b=}")
18
19 def __sub__(self, b: typing.Self):
20 return Vector(self.x - b.x, self.y - b.y)
21
22
23@dataclasses.dataclass
24class Problem:
25 a: Vector
26 b: Vector
27 solution: Vector
28
29def get_data(path):
30 with open(path) as f:
31 data = f.read()
32
33 problem_data = data.split("\n\n")
34 for problem_datum in problem_data:
35 problem_components = []
36 for line in problem_datum.splitlines():
37 x, y = re.findall(r"(\d+)", line)
38 problem_components.append(Vector(int(x), int(y)))
39 yield Problem(problem_components[0], problem_components[1], problem_components[2] + 10000000000000)
40 # yield Problem(problem_components[0], problem_components[1], problem_components[2])
41
42
43def find_problem_cost(problem: Problem) -> int:
44 numerator = problem.solution.x * problem.a.y - problem.a.x * problem.solution.y
45 denominator = problem.b.x * problem.a.y - problem.b.y * problem.a.x
46 b_presses = numerator / denominator
47 a_presses = (problem.solution.y - b_presses * problem.b.y) / problem.a.y
48 if b_presses != int(b_presses):
49 return 0
50 elif a_presses != int(a_presses):
51 return 0
52 else:
53 return int(a_presses * 3 + b_presses)
54
55def main(problems):
56 output = 0
57 for problem in problems:
58 cost = find_problem_cost(problem)
59 output += cost
60 return output
61
62if __name__ == "__main__":
63 # print(main(get_data("day_13_input_test.txt")))
64 print(main(get_data("day_13_input.txt")))