66 lines
1.7 KiB
Python
66 lines
1.7 KiB
Python
from tools.aoc import AOCDay
|
|
from typing import Any
|
|
|
|
|
|
def get_max_bridge_strength(bridge_parts: list, connect_to: int) -> int:
|
|
max_strength = 0
|
|
|
|
for part in bridge_parts:
|
|
if connect_to not in part:
|
|
continue
|
|
|
|
sub_parts = bridge_parts.copy()
|
|
sub_parts.remove(part)
|
|
this_strength = sum(part) + get_max_bridge_strength(sub_parts, part[int(not part.index(connect_to))])
|
|
max_strength = max(max_strength, this_strength)
|
|
|
|
return max_strength
|
|
|
|
|
|
def get_possible_bridges(bridge_parts: list, connect_to: int) -> list:
|
|
bridges = []
|
|
for part in bridge_parts:
|
|
if connect_to not in part:
|
|
continue
|
|
|
|
sub_parts = bridge_parts.copy()
|
|
sub_parts.remove(part)
|
|
bridges.append([part])
|
|
sub_bridges = get_possible_bridges(sub_parts, part[int(not part.index(connect_to))])
|
|
for sub_bridge in sub_bridges:
|
|
bridges.append([part] + sub_bridge)
|
|
|
|
return bridges
|
|
|
|
|
|
class Day(AOCDay):
|
|
inputs = [
|
|
[
|
|
(31, "input24_test"),
|
|
(1940, "input24")
|
|
],
|
|
[
|
|
(19, "input24_test"),
|
|
(1928, "input24")
|
|
]
|
|
]
|
|
|
|
def get_bridge_parts(self) -> list:
|
|
return [
|
|
list(map(int, line.split("/")))
|
|
for line in self.getInput()
|
|
]
|
|
|
|
def part1(self) -> Any:
|
|
return get_max_bridge_strength(self.get_bridge_parts(), 0)
|
|
|
|
def part2(self) -> Any:
|
|
bridges = get_possible_bridges(self.get_bridge_parts(), 0)
|
|
max_length = max(map(len, bridges))
|
|
return max(sum(sum(x) for x in b) for b in bridges if len(b) == max_length)
|
|
|
|
|
|
if __name__ == '__main__':
|
|
day = Day(2017, 24)
|
|
day.run(verbose=True)
|