Mikaël Capelle
ce315b8778
Co-authored-by: Mikael CAPELLE <mikael.capelle@thalesaleniaspace.com> Co-authored-by: Mikaël Capelle <capelle.mikael@gmail.com> Reviewed-on: #3
29 lines
901 B
Python
29 lines
901 B
Python
import itertools
|
|
from collections import defaultdict
|
|
from typing import Any, Iterator, cast
|
|
|
|
import parse # type: ignore
|
|
|
|
from ..base import BaseSolver
|
|
|
|
|
|
class Solver(BaseSolver):
|
|
def solve(self, input: str) -> Iterator[Any]:
|
|
lines = input.splitlines()
|
|
|
|
distances: dict[str, dict[str, int]] = defaultdict(dict)
|
|
for line in lines:
|
|
origin, destination, length = cast(
|
|
tuple[str, str, int],
|
|
parse.parse("{} to {} = {:d}", line), # type: ignore
|
|
)
|
|
distances[origin][destination] = distances[destination][origin] = length
|
|
|
|
distance_of_routes = {
|
|
route: sum(distances[o][d] for o, d in zip(route[:-1], route[1:]))
|
|
for route in map(tuple, itertools.permutations(distances))
|
|
}
|
|
|
|
yield min(distance_of_routes.values())
|
|
yield max(distance_of_routes.values())
|