From a7a6b86002b595bc167af72606b14c67ed1bdf8f Mon Sep 17 00:00:00 2001 From: Tomasz Kramkowski Date: Wed, 24 Nov 2021 22:25:42 +0000 Subject: init commit --- 13/input | 56 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 13/solution.py | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 107 insertions(+) create mode 100644 13/input create mode 100644 13/solution.py (limited to '13') diff --git a/13/input b/13/input new file mode 100644 index 0000000..35be357 --- /dev/null +++ b/13/input @@ -0,0 +1,56 @@ +Alice would gain 54 happiness units by sitting next to Bob. +Alice would lose 81 happiness units by sitting next to Carol. +Alice would lose 42 happiness units by sitting next to David. +Alice would gain 89 happiness units by sitting next to Eric. +Alice would lose 89 happiness units by sitting next to Frank. +Alice would gain 97 happiness units by sitting next to George. +Alice would lose 94 happiness units by sitting next to Mallory. +Bob would gain 3 happiness units by sitting next to Alice. +Bob would lose 70 happiness units by sitting next to Carol. +Bob would lose 31 happiness units by sitting next to David. +Bob would gain 72 happiness units by sitting next to Eric. +Bob would lose 25 happiness units by sitting next to Frank. +Bob would lose 95 happiness units by sitting next to George. +Bob would gain 11 happiness units by sitting next to Mallory. +Carol would lose 83 happiness units by sitting next to Alice. +Carol would gain 8 happiness units by sitting next to Bob. +Carol would gain 35 happiness units by sitting next to David. +Carol would gain 10 happiness units by sitting next to Eric. +Carol would gain 61 happiness units by sitting next to Frank. +Carol would gain 10 happiness units by sitting next to George. +Carol would gain 29 happiness units by sitting next to Mallory. +David would gain 67 happiness units by sitting next to Alice. +David would gain 25 happiness units by sitting next to Bob. +David would gain 48 happiness units by sitting next to Carol. +David would lose 65 happiness units by sitting next to Eric. +David would gain 8 happiness units by sitting next to Frank. +David would gain 84 happiness units by sitting next to George. +David would gain 9 happiness units by sitting next to Mallory. +Eric would lose 51 happiness units by sitting next to Alice. +Eric would lose 39 happiness units by sitting next to Bob. +Eric would gain 84 happiness units by sitting next to Carol. +Eric would lose 98 happiness units by sitting next to David. +Eric would lose 20 happiness units by sitting next to Frank. +Eric would lose 6 happiness units by sitting next to George. +Eric would gain 60 happiness units by sitting next to Mallory. +Frank would gain 51 happiness units by sitting next to Alice. +Frank would gain 79 happiness units by sitting next to Bob. +Frank would gain 88 happiness units by sitting next to Carol. +Frank would gain 33 happiness units by sitting next to David. +Frank would gain 43 happiness units by sitting next to Eric. +Frank would gain 77 happiness units by sitting next to George. +Frank would lose 3 happiness units by sitting next to Mallory. +George would lose 14 happiness units by sitting next to Alice. +George would lose 12 happiness units by sitting next to Bob. +George would lose 52 happiness units by sitting next to Carol. +George would gain 14 happiness units by sitting next to David. +George would lose 62 happiness units by sitting next to Eric. +George would lose 18 happiness units by sitting next to Frank. +George would lose 17 happiness units by sitting next to Mallory. +Mallory would lose 36 happiness units by sitting next to Alice. +Mallory would gain 76 happiness units by sitting next to Bob. +Mallory would lose 34 happiness units by sitting next to Carol. +Mallory would gain 37 happiness units by sitting next to David. +Mallory would gain 40 happiness units by sitting next to Eric. +Mallory would gain 18 happiness units by sitting next to Frank. +Mallory would gain 7 happiness units by sitting next to George. diff --git a/13/solution.py b/13/solution.py new file mode 100644 index 0000000..af0362b --- /dev/null +++ b/13/solution.py @@ -0,0 +1,51 @@ +"""Advent of Code 2015, day 15""" + +from collections import defaultdict +from itertools import combinations +from functools import cache +from typing import TypeVar, Generic + +T = TypeVar('T') +class WeightedGraph(Generic[T]): + nodes: set[T] + weights: defaultdict[tuple[T, T], int] + def __init__(self): + self.nodes = set() + self.weights = defaultdict(int) + def add_edge(self, a, b, weight): + self.nodes.add(a) + self.nodes.add(b) + self.weights[tuple(sorted((a, b)))] = weight + def get_edge(self, a, b): + return self.weights[tuple(sorted((a, b)))] + +def part1(graph: WeightedGraph[str]) -> int: + @cache + def max_happiness(first_guest: str, guest: str, remaining: frozenset[str]) -> int: + remaining = remaining - {guest} + if len(remaining) == 0: + return graph.get_edge(first_guest, guest) + return max(graph.get_edge(guest, other) + max_happiness(first_guest, other, remaining) for other in remaining) + return max(max_happiness(guest, guest, frozenset(graph.nodes)) for guest in graph.nodes) + +def part2(graph: WeightedGraph[str]) -> int: + for guest in graph.nodes.copy(): + graph.add_edge(guest, 'Me', 0) + return part1(graph) + +if __name__ == '__main__': + guests = set() + edges = dict() + with open('input') as f: + for l in f: + a, _, what, how_much, _, _, _, _, _, _, b = l.rstrip()[:-1].split() + guests.add(a) + guests.add(b) + if what == 'lose': + how_much = -int(how_much) + edges[(a, b)] = int(how_much) + g = WeightedGraph() + for a, b in combinations(guests, 2): + g.add_edge(a, b, edges[(a, b)] + edges[(b, a)]) + print(part1(g)) + print(part2(g)) -- cgit v1.2.3-54-g00ecf