Coverage for src\aoc2022\days\day11.py: 100%
84 statements
« prev ^ index » next coverage.py v7.0.0, created at 2022-12-23 05:19 +0000
1from __future__ import annotations
3import math
4from typing import Callable, Dict, List, NamedTuple
6from src.aoc2022 import utils
9class Monkey(NamedTuple):
10 """
11 Data class representing the monkey configuration
13 :param items: list of items the monkey is currently holding
14 :type items: List[int]
16 :param operation: lambda function for updating the item priority
17 :type operation: Callable[[int], int]
19 :param divisible: number used for divisible check when throwing items
20 :type divisible: int
22 :param false_throw: id of monkey to throw to on item % divisible != 0
23 :type false_throw: int
25 :param true_throw: id of monkey to throw to on item % divisible == 0
26 :type true_throw: int
27 """
29 items: List[int]
30 operation: Callable[[int], int]
31 divisible: int
32 false_throw: int
33 true_throw: int
35 def add_items(self, items: List[int]):
36 """
37 Add a list of items to the items held by the monkey
39 :param items: List of items to add to the monkey's held items
40 :type items: List[int]
42 """
43 self.items.extend(items)
45 def pop_items(self) -> List[int]:
46 """
47 Pop all the items from the monkey and return the list
49 :return: items held by monkey
50 :rtype: List[int]
51 """
52 n = len(self.items)
53 return [self.items.pop() for _ in range(n)]
55 def copy(self) -> Monkey:
56 """
57 Create a new copy of this monkey
59 :return: Monkey copy
60 :rtype: Monkey
61 """
62 return Monkey(
63 items=[e for e in self.items],
64 operation=self.operation,
65 divisible=self.divisible,
66 false_throw=self.false_throw,
67 true_throw=self.true_throw,
68 )
71def parse_data_to_dict(raw_data: str) -> Dict[int, Monkey]:
72 """
73 Parse the raw data intoa dict of monkeys
75 :param raw_data: Raw data containing numerical data
76 :type raw_data: str
78 :return: parsed dict of Monkey id, Monkey
79 :rtype: Dict[int, Monkey]
80 """
82 parsed_monkeys = {}
83 for idx, block in enumerate(raw_data.split("\n\n")):
84 monkey = parse_block(block)
85 parsed_monkeys[idx] = monkey
87 return parsed_monkeys
90def parse_block(raw_data_block: str) -> Monkey:
91 """
92 Parse block of raw data to a single monkey monkey
94 :param raw_data_block: Raw data containing data for single monkey
95 :type raw_data_block: str
97 :return: parsed Monkey instance
98 :rtype: Monkey
99 """
100 lines = raw_data_block.split("\n")
102 starting_items_string = lines[1].strip().split(": ")[1]
103 starting_items = [int(e) for e in starting_items_string.split(", ")]
105 operation_string = lines[2].strip().split(" = ")[-1]
106 match operation_string.split(" "): # noqa
107 case ["old", "*", "old"]: # noqa: E211
108 operation = lambda x: x**2 # noqa: E731
109 case ["old", "+", "old"]: # noqa: E211
110 operation = lambda x: x + x # noqa: E731
111 case ["old", "*", val]: # noqa: E211
112 value = int(val) # noqa: F821
113 operation = lambda x: x * value # noqa: E731
114 case ["old", "+", val]: # noqa: E211
115 value = int(val) # noqa: F821
116 operation = lambda x: x + value # noqa: E731
118 divisible = int(lines[3].strip().split(" ")[-1])
119 true_throw = int(lines[4].strip().split(" ")[-1])
120 false_throw = int(lines[5].strip().split(" ")[-1])
122 return Monkey(
123 items=starting_items,
124 operation=operation,
125 divisible=divisible,
126 false_throw=false_throw,
127 true_throw=true_throw,
128 )
131def compute_number_of_counted_items(
132 num_rounds: int, monkeys: Dict[int, Monkey]
133) -> Dict[int, int]:
134 """
135 Compute the number of items each monkey has examined during a game
137 :param num_rounds: Number of rounds to simulate
138 :type num_rounds: int
140 :param monkeys: Monkeys instances to simulate playing the game
141 :type monkeys: Dict[int, Monkey]
143 :return: Examined items counts for each monkey id
144 :rtype: Dict[int, int]
145 """
147 monkeys = {k: v.copy() for k, v in monkeys.items()}
149 n = len(monkeys.keys())
151 checked_items = {k: 0 for k in range(n)}
153 for i in range(num_rounds):
154 for j in range(n):
155 monkey = monkeys[j]
156 checked_items[j] += len(monkey.items)
158 true_throws = []
159 false_throws = []
161 items = monkey.pop_items()
163 for item in items:
164 updated_item = monkey.operation(item) // 3
166 throw_check = updated_item % monkey.divisible == 0
168 if throw_check:
169 true_throws.append(updated_item)
170 else:
171 false_throws.append(updated_item)
173 monkeys[monkey.false_throw].add_items(false_throws)
174 monkeys[monkey.true_throw].add_items(true_throws)
176 return checked_items
179def compute_number_of_counted_items_no_div(
180 num_rounds: int, monkeys: Dict[int, Monkey]
181) -> Dict[int, int]:
182 """
183 Compute the number of items each monkey has examined
184 during a game with no division rule
186 :param num_rounds: Number of rounds to simulate
187 :type num_rounds: int
189 :param monkeys: Monkeys instances to simulate playing the game
190 :type monkeys: Dict[int, Monkey]
192 :return: Examined items counts for each monkey id
193 :rtype: Dict[int, int]
194 """
196 monkeys = {k: v.copy() for k, v in monkeys.items()}
198 common_modulo = math.lcm(*[m.divisible for m in monkeys.values()])
200 n = len(monkeys.keys())
201 checked_items = {k: 0 for k in range(n)}
203 for i in range(num_rounds):
204 for j in range(n):
205 monkey = monkeys[j]
206 checked_items[j] += len(monkey.items)
208 true_throws = []
209 false_throws = []
211 items = monkey.pop_items()
213 for item in items:
214 updated_item = monkey.operation(item) % common_modulo
216 throw_check = updated_item % monkey.divisible == 0
218 if throw_check:
219 true_throws.append(updated_item)
220 else:
221 false_throws.append(updated_item)
223 monkeys[monkey.false_throw].add_items(false_throws)
224 monkeys[monkey.true_throw].add_items(true_throws)
226 return checked_items
229if __name__ == "__main__": # pragma: no cover
231 num_rounds = 20
233 raw_data = utils.get_raw_data("./src/aoc2022/data/day11.txt")
234 parsed_data = parse_data_to_dict(raw_data)
236 counted_items = compute_number_of_counted_items(num_rounds, parsed_data)
237 sorted_values = sorted(counted_items.values())
238 max_mul = sorted_values[-1] * sorted_values[-2]
239 print(f"The max priorities multiplied are : {max_mul}")
241 num_rounds = 10_000
243 res = compute_number_of_counted_items_no_div(num_rounds, parsed_data)
244 sorted_values = sorted(res.values())
245 max_mul = sorted_values[-1] * sorted_values[-2]
246 print(f"The max priorities multiplied are : {max_mul}")