Advent of Code

[ThomasL]

Teil 2 konnte man leicht in den Code von Teil 1 integrieren, da man nur anders aufsummieren musste.
Und regex kann hilfreich sein, hier reicht imho überall ein simples "split".

Code: Alles auswählen

import math

data = [line.strip().split('; ') for line in open('input.txt')]
limit = {'red': 12, 'green': 13, 'blue': 14}
sum_1 = sum_2 = 0
for id, game in enumerate(data, start=1):
    game[0] = game[0].split(': ')[1]
    valid = True
    least = {'red':0, 'green':0, 'blue':0}
    for draw in game:
        for sub in draw.split(', '):
            amount, color = sub.split()
            # condition for part 1
            if int(amount) > limit[color]:
                valid = False
            # condition for part 2
            least[color] = max([least[color], int(amount)])
    
    sum_1 += valid and id
    sum_2 += math.prod(least.values())

print(f'Part 1: {sum_1}')
print(f'Part 2: {sum_2}')

[snafu]

@ThomasL
Krass, wie kurz deine Lösungen immer sind.

Ich habe das so gemacht:

Code: Alles auswählen

from math import prod


def parse_game(string):
    game_info = {}
    for setting in string.split(": ")[1].split("; "):
        for times, color in map(str.split, setting.split(", ")):
            game_info[color] = max(int(times), game_info.get(color, 0))
    return game_info


def get_possible_game_ids(bag, games):
    return [
        game_id for game_id, game in enumerate(games, 1)
        if all(
            bag[cube_color] >= game[cube_color]
            for cube_color in game
        )
    ]


def main():
    with open("input2.txt") as stream:
        games = [parse_game(line) for line in stream]
    bag = {"red": 12, "green": 13, "blue": 14}
    print("Part 1:", sum(get_possible_game_ids(bag, games)))
    print("Part 2:", sum(prod(game.values()) for game in games))


if __name__ == "__main__":
    main()

[kbr]

Nachdem ich Tag 3 in Ruhe (und diesmal sauber) gelöst habe (in den kommenden Tagen werde ich für AoC kaum noch Zeit haben), frage ich mich wie jedes Jahr, was diejenigen, die es ins Leaderboard schaffen, wohl eingeworfen haben

[Manul]

In der Tat. Gestern wurde die erste korrekte Lösung zum 1. Teil 37 Sekunden nach Veröffentlichung eingereicht. Ich brauche schon länger, um die Aufgabenstellung überhaupt nur zu lesen.

Heute habe ich ziemlich lange gebraucht, um eine extrem ineffiziente Lösung zu programmieren. Dabei hat mich vor allem aufgehalten, daß ich eine Unterklasse einer eigenen Unterklasse von tuple bauen wollte und daran erst mal gescheitert bin. Ich hab's dann letztlich rausbekommen und viel dabei gelernt, um nach etwas Überlegung festzustellen, daß das völlig unnötig war. Schön war, daß ich meine Lösung dann recht schnell und unkompliziert auf einen deutlich effizienteren Ansatz umbauen konnte und damit die Laufzeit von über 30s auf unter 1s reduzieren konnte.

[kbr]

Diesmal bin ich es konsequent objektorientiert angegangen, was den Schritt von Teil 1 zu Teil 2 sehr einfach gemacht hat. Das ist zwar häufig der Fall, manchmal aber auch nicht. Zum Laufzeitvergleich: bei mir sind es lt. timeit 2.34 ms zur Lösung von Teil 1 und Teil 2 gemeinsam.

[kbr]

Schön war, daß ich meine Lösung dann recht schnell und unkompliziert auf einen deutlich effizienteren Ansatz umbauen konnte und damit die Laufzeit von über 30s auf unter 1s reduzieren konnte.

Eigentlich hatte ich schreiben wollen, dass das doch ein richtig schönes Erlebnis ist, den eigenen Code aus eigener Kraft um einen solchen Faktor beschleunigen zu können. Tatsächlich spielt auch die Geschwindigkeit, mit der die Lösungen erstellt werden, überhaupt keine Rolle. Viel wertvoller ist es, genau wie du geschrieben hast, etwas dabei zu lernen. In dem Sinne sehe ich AoC auch als Bereicherung an und freue mich, dass es von dem Betreiber jedes Jahr wieder neu aufgelegt wird – denn diese Übungen zu erstellen ist Arbeit.
Das die Lösung noch schneller geht, soll dich in keiner Weise demotivieren. Im Gegenteil! Gewiss können es andere noch schneller, als es bei meiner Variante der Fall ist. Also bleib am Ball und viel Spaß mit den noch kommenden Aufgaben!

[Dennis89]

Der Tag neigt sich dem Ende, ich komme mal wieder nicht voran.
Ich habe im ersten Schritt die Position aller Zahlen rausgesucht und das sieht mit den Beispieldaten so aus:

Code: Alles auswählen

{0: [(0, 3), (5, 8)], 1: [], 2: [(2, 4), (6, 9)], 3: [], 4: [(0, 3)], 5: [(7, 9)], 6: [(2, 5)], 7: [(6, 9)], 8: [], 9: [(1, 4), (5, 8)]}

Schlüssel ist die Zeilennummer und die Tupel gibt an, bei welchem Index die Zahl(enfolge) anfängt und aufhört.

Mein Gedanke war, das ich mit den Indexwerten auf die Input-Daten losgehe und wenn +1 neben der gefunden Zahl oder unter der gefunden Zahl bzw. diagonal kein Punkt und keine Zahl ist, dann schreibe ich die Zahl in eine Liste.
Mit den Beispieldaten funktionierte das auch, aber mit den "richtigen" Daten leider nicht.

Hm da muss ich heute wohl aufgeben. Ich wäre, auch wenn ich unter der Woche immer wenig Zeit habe, trotzdem sehr interessiert, wie denn eine saubere Python-Lösung aussieht. Das muss ich echt aufarbeiten, bei einer ähnlichen Aufgabe bin ich in dem letzten oder vorletzten Jahr auch ausgeschieden.

Das ist mein experimentier-Code, der zumindest für die Beispieldaten funktioniert.

Code: Alles auswählen

import re
from pathlib import Path


INPUT = Path('/home/dennis/AoC/2023/Day3/input.txt')

EXAMPLE_LINES = """\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..""".splitlines()


def main():
    engine_parts = INPUT.read_text(encoding='UTF-8').splitlines()
    line_to_parts = {number: [] for number in range(len(engine_parts))}
    for line_number, line in enumerate(engine_parts):
        for match in re.finditer(r"\d+", line):
            line_to_parts[line_number].append(match.span())
    found_part = set()
    for line_number, parts in line_to_parts.items():
        for part in parts:
            start, end = part
            try:
                item = engine_parts[line_number][end]
            except IndexError:
                item = '.'
            if item != '.' and not item.isdigit():
                found_part.add(int(engine_parts[line_number][start:end]))
            else:
                try:
                    for item in engine_parts[line_number + 1][start:end + 1]:
                        if item != '.' and not item.isdigit():
                            found_part.add(int(engine_parts[line_number][start:end]))
                except IndexError:
                    pass
                try:
                    for item in engine_parts[line_number - 1][start:end + 1]:
                        if item != '.' and not item.isdigit():
                            found_part.add(int(engine_parts[line_number][start:end]))
                except IndexError:
                    pass
                try:
                    for item in engine_parts[line_number + 1][start - 1:end]:
                        if item != '.' and not item.isdigit():
                            found_part.add(int(engine_parts[line_number][start:end]))
                except IndexError:
                    pass
                try:
                    for item in engine_parts[line_number - 1][start - 1:end]:
                        if item != '.' and not item.isdigit():
                            found_part.add(int(engine_parts[line_number][start:end]))
                except IndexError:
                    pass
    print(sum(found_part))


if __name__ == "__main__":
    main()

Danke und viele Grüße
Dennis

[grubenfox]

In dem Sinne sehe ich AoC auch als Bereicherung an und freue mich, dass es von dem Betreiber jedes Jahr wieder neu aufgelegt wird – denn diese Übungen zu erstellen ist Arbeit.

Dem schliesse ich mich voll und ganz an... da hat wer viel Energie und Phantasie.

[__blackjack__]

Ich habe Teil 1 von Tag 3 in Python schon mit dem Hintergedanken gelöst, dass ich das auf einer speicherbeschränkten Plattform in BASIC machen muss/will. Was dann dazu geführt hat, das ich für den zweiten Teil noch mal von vorne angefangen habe, das in Python zu lösen als wenn es Python wäre.

Ich habe im ersten Schritt jedes Zeichen zu einem `Item` gemacht, mit dem Zeichen als Wert und den Koordinaten wo es im Bauplan steht. Dann die zusammenhängenden Ziffern in jeder Zeile zusammengefasst und die Leerfelder ausgefiltert, und zwei Abbildung angelegt: Koordinaten zu Zahlen und Koordinaten zu Symbolen. Das ganze in einem `Schematic`-Objekt zusammengefasst:

Code: Alles auswählen

#!/usr/bin/env python3
import sys
from itertools import groupby

from attr import attrib, attrs

EXAMPLE_LINES = """\
467..114..
...*......
..35..633.
......#...
617*......
.....+.58.
..592.....
......755.
...$.*....
.664.598..
""".splitlines()


@attrs(frozen=True)
class Item:
    value = attrib()
    coordinate = attrib()

    def __len__(self):
        return len(self.value)

    def __int__(self):
        return int(self.value)

    @property
    def x(self):
        return self.coordinate[0]

    @property
    def y(self):
        return self.coordinate[1]

    @property
    def coordinates(self):
        return ((self.x + i, self.y) for i in range(len(self)))

    @property
    def surrounding_coordinates(self):
        yield from (
            (self.x + d_x, self.y + d_y)
            for d_y in [-1, 1]
            for d_x in range(-1, len(self) + 1)
        )
        yield (self.x - 1, self.y)
        yield (self.x + len(self), self.y)

    def is_empty(self):
        return self.value == "."

    def is_number(self):
        return self.value.isdigit()

    def is_symbol(self):
        return not (self.is_empty() or self.is_number())

    def extended(self, items):
        return Item(
            self.value + "".join(item.value for item in items), self.coordinate
        )


@attrs(frozen=True)
class Schematic:
    items = attrib()
    coordinate_to_number = attrib()
    coordinate_to_symbol = attrib()

    def has_adjacent_symbol(self, item):
        return any(
            map(self.coordinate_to_symbol.get, item.surrounding_coordinates)
        )

    def get_adjacent_numbers(self, item):
        return set(
            map(self.coordinate_to_number.get, item.surrounding_coordinates)
        ) - {None}

    @classmethod
    def from_items(cls, items):
        items = list(items)
        coordinate_to_number = {}
        coordinate_to_symbol = {}
        for item in items:
            for coordinate in item.coordinates:
                if item.is_number():
                    coordinate_to_number[coordinate] = item
                elif item.is_symbol():
                    coordinate_to_symbol[coordinate] = item
                else:
                    assert item.is_empty(), repr(Item)

        return cls(items, coordinate_to_number, coordinate_to_symbol)


def parse_items(lines):
    return (
        Item(character, (x, y))
        for y, line in enumerate(lines)
        for x, character in enumerate(line.rstrip())
    )


def group_and_filter_items(items):
    for (_, is_number), group in groupby(
        items, lambda item: (item.y, item.is_number())
    ):
        if is_number:
            yield next(group, None).extended(group)
        else:
            yield from (item for item in group if not item.is_empty())


def parse_lines(lines):
    return Schematic.from_items(group_and_filter_items(parse_items(lines)))


def sum_part_numbers(schematic):
    """
    >>> sum_part_numbers(parse_lines(EXAMPLE_LINES))
    4361
    """
    return sum(
        int(item)
        for item in schematic.items
        if item.is_number() and schematic.has_adjacent_symbol(item)
    )


def sum_gear_ratios(schematic):
    """
    >>> sum_gear_ratios(parse_lines(EXAMPLE_LINES))
    467835
    """
    candidates = (
        list(schematic.get_adjacent_numbers(item))
        for item in schematic.items
        if item.value == "*"
    )
    return sum(
        int(candidate[0]) * int(candidate[1])
        for candidate in candidates
        if len(candidate) == 2
    )


def main():
    schematic = parse_lines(sys.stdin)
    print(sum_part_numbers(schematic))
    print(sum_gear_ratios(schematic))


if __name__ == "__main__":
    main()

[kbr]

Ich werfe auch mal meine Lösung von Tag 3 hier rein.

Code: Alles auswählen

import collections
import re

from itertools import chain
from math import prod


NUM_PATTERN = re.compile(r"(\d+)")
SYM_PATTERN = re.compile(r"([^0-9.\n])")
GEAR_SYMBOL = "*"
FNAME = "input.txt"


class Area:

    def __init__(self, value, start):
        # area includes the positions before and after the value
        self.value = int(value)
        self.left = start - 1
        self.right = self.left + len(value) + 1

    def __add__(self, other_area):
        return self.value + other_area.value

    def __radd__(self, other):
        return other + self.value

    def __mul__(self, other_area):
        return self.value * other_area.value

    def __rmul__(self, other):
        return other * self.value

    def __contains__(self, symbol):
        return self.left <= symbol.position <= self.right

    def __repr__(self):
        return f"Area({self.value}, {self.left + 1}, {self.right - 1})"


class Symbol:

    def __init__(self, symbol, position):
        self.symbol = symbol
        self.position = position
        self.adjacent_areas = []

    @property
    def is_gear(self):
        return self.symbol == GEAR_SYMBOL and len(self.adjacent_areas) >= 2

    @property
    def ratio(self):
        return prod(self.adjacent_areas)

    def __repr__(self):
        return f"Symbol({self.symbol}, {self.position})"

    def add_adjacent_area(self, area):
        self.adjacent_areas.append(area)


class Engine:

    def __init__(self):
        self.areas = collections.defaultdict(list)
        self.symbols = collections.defaultdict(list)

    def __repr__(self):
        return f"Engine:\nAreas:\n{self.areas}\nSymbols:\n{self.symbols}"

    def _is_active_area(self, area, line):
        for i in range(line-1, line+2):
            try:
                symbols = self.symbols[i]
            except KeyError:
                continue
            for symbol in symbols:
                if symbol in area:
                    symbol.add_adjacent_area(area)
                    return True
        return False

    def collect_active_areas(self):
        active_areas = []
        for line, areas in self.areas.items():
            active_areas.extend(
                [area for area in areas if self._is_active_area(area, line)]
            )
        return active_areas

    def get_gear_ratios(self):
        return sum(
            symbol.ratio for symbol in chain.from_iterable(self.symbols.values())
            if symbol.is_gear
        )

    @staticmethod
    def _scan_collection(line, schema, pattern, collection, cls):
        hits = pattern.findall(schema)
        pos = 0
        for hit in hits:
            start = schema.find(hit, pos)
            pos = start + len(hit)
            collection[line].append(cls(hit, start))

    def parse(self, fname):
        with open(fname) as fobj:
            for line, schema in enumerate(fobj):
                self._scan_collection(line, schema, NUM_PATTERN, self.areas, Area)
                self._scan_collection(line, schema, SYM_PATTERN, self.symbols, Symbol)


engine = Engine()
engine.parse(FNAME)
active_areas = engine.collect_active_areas()
print(sum(active_areas))
print(engine.get_gear_ratios())

[grubenfox]

Mit den Beispieldaten funktionierte das auch, aber mit den "richtigen" Daten leider nicht.

Hm da muss ich heute wohl aufgeben. Ich wäre, auch wenn ich unter der Woche immer wenig Zeit habe, trotzdem sehr interessiert, wie denn eine saubere Python-Lösung aussieht. Das muss ich echt aufarbeiten, bei einer ähnlichen Aufgabe bin ich in dem letzten oder vorletzten Jahr auch ausgeschieden.

Dachte ich auch in der Nacht: Teil 1: im ersten Durchlauf die Positionen der Markierungen merken. Gibt dann für jede Zeile eine schöne Menge an Positionen. im zweiten Durchlauf die Anfangs- und Endpositionen der Zahlen ermitteln und im Umfeld schauen ob es eine nicht leere Schnittmenge mit den Positionen der Markierungen gibt: fertig.

Lief mit den Testdaten... nur mit den Testdaten.

Vorhin hatte ich dann gesehen:

Code: Alles auswählen

SYM_PATTERN = re.compile(r"([^0-9.\n])")

... und bei mir das fehlende \n hinzugefügt. Nun geht's! Aber für den zweiten Teil muss ich noch überlegen. In drei schleifen durch die Daten laufen (Markierung, erste Zahl, Zweite Zahl), erscheint mir spontan nicht sinnführend.

[Dennis89]

Danke für eure Lösungen. Die Art wie ihr denkt und was euer Code macht habe ich verstanden. (Natürlich nicht alles sofort, aber ich bilde mir ein, das ich es nach testen, printen, lesen und printen und lesen, verstanden habe)

Ihr habt echt "coole" Sachen eingebaut und wenigstens hat es dadurch Spass gemacht, zu entdecken wie eure Codes funktionieren.
Eventuell kann ich mich an der Aufgabe am Wochenende noch ein mal versuchen.

Grüße
Dennis

[__blackjack__]

Heute ist ja wieder eine einfache Aufgabe. Frage mich ob die auch in Betracht ziehen was Wochentag und was Wochenende ist, bei der Aufgabenstellung.

[Dennis89]

Habe heute noch gar nicht reingeschaut, aber sag bitte nicht sowas. Da ist die Enttäuschung größer, wenn man es nicht schafft.

Vielleicht kannst du die Aufgabe noch mal genau anschauen und du merkst dann, dass sie extrem schwer ist, oder?

Ich kann den Zeitaufwand von euch nicht einschätzen, aber bei mir gehen da gut mal Stunden vorbei. Aber Leute wie ich, sind auch sicherlich nicht die primäre Zielgruppe.

[__blackjack__]

@Dennis89: Okay, ich habe mir die Aufgabe noch mal ganz genau angeschaut, und Teil 1 ist *wirklich* einfach. Wenn man die Daten aus der Eingabezeile gekratzt hat, dann ist das ausrechnen der Zahl für eine Eingabezeile im Grunde ein Einzeiler mit Grunddatentypen. Und das Gesamtergebnis ist dann diese Zahlen pro Eingabezeile aufsummieren. Piece of .

Teil 2 ist dann extrem schwer. Sprich, da muss man ein bisschen Nachdenken. (Aber auch nicht wirklich viel. Ich denke heute Abend wird da von mir noch eine BASIC-Lösung kommen.)

[nezzcarth]

Dachte ich auch in der Nacht: Teil 1: im ersten Durchlauf die Positionen der Markierungen merken. Gibt dann für jede Zeile eine schöne Menge an Positionen. im zweiten Durchlauf die Anfangs- und Endpositionen der Zahlen ermitteln und im Umfeld schauen ob es eine nicht leere Schnittmenge mit den Positionen der Markierungen gibt: fertig.

Da meine gestrige Lösung ganz ähnlich aussah, kann ich aus erster Hand bestätigen, dass das so ähnlich grundsätzlich klappt

[snafu]

Meine Lösung für Tag 3 sieht so aus:

Code: Alles auswählen

import re
from collections import namedtuple

NUMBER_RE = re.compile(r"\d+")
SYMBOL_RE = re.compile(r"[^\d.\n]")

Position = namedtuple("Position", "x y")


class NumberArea(
    namedtuple("NumberArea", "value start end")
):
    def __contains__(self, position):
        return (
            self.start.x <= position.x <= self.end.x
            and self.start.y <= position.y <= self.end.y
        )

    @classmethod
    def from_match(cls, match, lineno):
        return cls(
            int(match.group()),
            Position(max(0, lineno - 1), max(0, match.start() - 1)),
            Position(lineno + 1, match.end())
        )


class Symbol(
    namedtuple("Symbol", "value position")
):
    @classmethod
    def from_match(cls, match, lineno):
        return cls(match.group(), Position(lineno, match.start()))


class Scheme:
    def __init__(self, areas, symbols):
        self.areas = areas
        self.symbols = symbols

    def get_part_numbers(self):
        return [
            area.value for area in self.areas
            if any(
                symbol.position in area
                for symbol in self.symbols
            )
        ]

    def get_star_areas(self):
        return [
            [
                area for area in self.areas
                if symbol.position in area
            ]
            for symbol in self.symbols
            if symbol.value == "*"
        ]

    def get_gears(self):
        return [
            (areas[0].value, areas[1].value)
            for areas in self.get_star_areas()
            if len(areas) == 2
        ]

    @classmethod
    def from_lines(cls, lines):
        areas, symbols = [], []
        for lineno, line in enumerate(lines):
            for match in NUMBER_RE.finditer(line):
                areas.append(NumberArea.from_match(match, lineno))
            for match in SYMBOL_RE.finditer(line):
                symbols.append(Symbol.from_match(match, lineno))
        return cls(areas, symbols)


def main():
    with open("input3.txt") as stream:
        scheme = Scheme.from_lines(stream)
    print("Part 1:", sum(scheme.get_part_numbers()))
    print("Part 2:", sum(a * b for a, b in scheme.get_gears()))


if __name__ == "__main__":
    main()

Kann man sicherlich effizienter machen, aber ich wollte am Ende fertig werden.

[snafu]

Tag 4 nun auch gelöst, aber mit extrem übler Laufzeit bei Part 2. Das muss ich mir nochmal genauer angucken.

[Dennis89]

[...]dann ist das ausrechnen der Zahl für eine Eingabezeile im Grunde ein Einzeiler

Ich hatte tatsächlich ein grinsen im Gesicht als ich

Code: Alles auswählen

def calculate_points(winnings):
    return 2 ** (winnings - 1) if winnings >= 1 else 0

schrieb

Teil 2 ist dann extrem schwer. Sprich, da muss man ein bisschen Nachdenken. (Aber auch nicht wirklich viel. Ich denke heute Abend wird da von mir noch eine BASIC-Lösung kommen.)

Ob ich das heute noch schaffe. Wie ich das umsetzen soll überlege ich noch.

Daher mal erst die vollständige Lösung vom ersten Teil:

Code: Alles auswählen

#!/usr/bin/env python3
from pathlib import Path
import re


INPUT = Path("/home/dennis/AoC/2023/Day4/input.txt")

EXAMPLE_LINES = """\
Card 1: 41 48 83 86 17 | 83 86  6 31 17  9 48 53
Card 2: 13 32 20 16 61 | 61 30 68 82 17 32 24 19
Card 3:  1 21 53 59 44 | 69 82 63 72 16 21 14  1
Card 4: 41 92 73 84 69 | 59 84 76 51 58  5 54 83
Card 5: 87 83 26 28 32 | 88 30 70 12 93 22 82 36
Card 6: 31 18 13 56 72 | 74 77 10 23 35 67 36 11""".splitlines()


def parse_cards(input_lines):
    cards = []
    for card in input_lines:
        card_number, numbers = card.split(":")
        my_numbers, winning_numbers = numbers.strip().split("|")
        my_numbers = set(map(int, re.findall(r"\d+", my_numbers)))
        winning_numbers = set(map(int, re.findall(r"\d+", winning_numbers)))
        cards.append({card_number.replace("Card ", ""): my_numbers & winning_numbers})
    return cards


def calculate_points(winnings):
    return 2 ** (winnings - 1) if winnings >= 1 else 0


def main():
    cards = parse_cards(INPUT.read_text(encoding="UTF-8").splitlines())
    print(
        sum(
            calculate_points(len(*card_to_winning.values()))
            for card_to_winning in cards
        )
    )


if __name__ == "__main__":
    main()

[__blackjack__]

Hm, eine Liste mit Wörterbücher wo jedes Wörterbuch genau *ein* Schlüssel/Wert-Paar enthält, erscheint mir nicht so wirklich sinnvoll. Der jeweilige Schlüssel wird auch nirgends verwendet. Das kann man also einfach vereinfachen.

Edit: Ich sitze nebenbei an Teil 2 in BASIC. Da ist irgendwo der Wurm drin in der Endlosschleife, die ich da offenbar gebastelt habe.