Advent of Code

Renão · Dec 18th 2020

Quote from __blackjack__
Manul Ich hatte die Berechnung der relativen Positionen der Nachbarn so verallgemeinert:
Display Spoiler
Python
from itertools import product

...

def calculate_neighbour_deltas(dimension_count):
    return [
        Point(*coordinates)
        for coordinates in product([-1, 0, 1], repeat=dimension_count)
        if not all(component == 0 for component in coordinates)
    ]
`Point` ist nicht allgemein, sondern einfach 4D mit 0 als Defaultwert für alle Komponenten.

Das mit der Zeichenkettenverarbeitung kann ich auch nicht finden. Ich bin bis jetzt eigentlich immer hauptsächlich mit `strip()`, `split()`, und `partition()` in Python ausgekommen + `more_itertools.split_at()` wenn eine Eingabe aus mehreren durch Leerzeilen getrennten Blöcken bestand. Wobei ich das parsen in der Regel auf mehrere Funktionen/Methoden aufteile. Vielleicht wird das tatsächlich etwas unübersichtlich und nervig wenn man alles komplett in einer Funktion/Methode parst.

Vielleicht hab ich schlecht ausgedrückt, wenn ich meine Anmerkungen von heute morgen nochmal lese.

Es sind nicht unbedingt die String-Operationen, die mich jetzt nerven, sondern dass meist der eigentliche Algorithmus darauf basiert, dass man einfach beim Parsen der Datei mal hier drauf und mal da drauf achten muss. Eigentlich sind das alles so Aufgaben, bei denen ich lerne ein effektives Parsen anzuwenden aber nicht mal wirklich zu knobeln.

Aber vielleicht kommt da ja mehr nach Tag 7 ... mal sehen

Manul · Dec 19th 2020

Ich bin mir nicht ganz sicher, ob ich verstehe, was Du meinst. Der Kniff beim Parsen ist doch, die Eingabe hinterher in einer Form repräsentiert zu haben, die einem eben das Bearbeiten der gestellten Aufgabe möglichst leicht macht. Ich finde, das beinhaltet durchaus ein bißchen Knobeln. Zumal ja immer noch das Raten dazu kommt, was wohl in Teil gefragt wird, und der Versuch, beim Parsen gleich dafür vorzusorgen. Das finde ich teilweise das witzigste.

Die heutige (Tag 19) Aufgabe fand ich so na ja. Aufgabenstellungen

Display Spoiler

wie in Teil 2 machen mir beim Nachdenken immer Knoten ins Hirn und ich brauche dementsprechend viele Versuche mit relativ viel trial & error, bis ich sie gelöst habe. Das ist zwar nicht unlehrreich, aber auch nicht durchgehend übertrieben spaßig. Mit meiner Lösung bin ich mittelzufrieden: Ich hätte sie gerne etwas allgemeiner und etwas übersichtlicher gehabt.

dll-live · Dec 19th 2020

Hallo zusammen

Leider teile ich euch heute mit, dass ich aus Zeitgründen (Arbeit und "normales Leben und dann noch hier probieren eine Lösung finden) nun "mehrheitlich" aufgebe.

Finde die Idee super, und durch das hier einige Ihre Lösungen präsentieren kann ich von denen lernen. Dafür nochmals und auch noch im voraus an alle

Freundliche Grüsse

Dani

__blackjack__ · Dec 20th 2020

Manul Ich habe die Regeln einfach in einen regulären Ausdruck übersetzt. Mit einer Sonderbehandlung in Teil 2 für die betroffenen Regeln. Zur Hälfte ging das noch ganz regulär (Knallerwortspiel 🤓), für die andere Hälfte muss man eine Regex-Engine verwenden, die das kann was in Deinem Spoiler versteckt ist. Damit ist das dann recht einfach. Also in Python ist das ein Grund sich das externe `regex`-Modul mal anzuschauen. Hat die gleiche API wie das `re`-Modul aus der Standardbibliothek, kann aber ein bisschen mehr.

Für Teil 1 ist in Python 3.9 das neu hinzugekommene `graphlib`-Modul nützlich. Vorsicht Spoiler: Nicht in das Modul schauen wenn man keinen deutlichen Hinweis haben möchte. Wer noch kein Python 3.9 einsetzt: Das Modul gibt es als `graphlib-backport` aus dem Python Package Index für Versionen von 3.6 bis 3.8.

Manul · Dec 20th 2020

__blackjack__ Danke! Allerdings sind mir sowohl der Ansatz mit regulären Ausdrücken als auch die Funktionsweise der graphlib nicht wirklich klar. Magst Du Deine entsprechenden Lösungen teilen? Ich verstehe sowas manchmal besser anhand von Beispielen als anhand der Dokumentation.

Manul · Dec 20th 2020

Die heutige (Tag 20) Aufgabe fiel für mich – auch wenn mein Spoiler von gestern heute nicht gilt – doch wieder in die gleiche Kategorie: Knoten ins Hirn, viel trial & error und damit letztlich Fleißarbeit mit mäßigem Spaßfaktor.

Vermutlich ist mein Ansatz wieder zu kompliziert und ich habe diverse Räder neu erfunden, die ich in Form von Pythonbibliotheken gratis frei Haus hätte bekommen können.

Wenn die verbleibenden Aufgaben ähnlich sind, muß ich schauen, ob ich dabeibleibe.

__blackjack__ · Dec 20th 2020

Manul Teil 1 von Tag 19 lässt sich sehr einfach, weil direkt, auf reguläre Ausdrücke abbilden. Die erste Modifikation von Teil 2 ist auch noch ganz einfach auf reguläre Ausdrücke übertragbar, also noch mit dem `re`-Modul realisierbar. Nur die zweite Modifikation verlangt etwas was reguläre Ausdrücke wie sie Sinne von formalen Sprachen definiert sind, nicht leisten können, wo man dann auf die nächste Stufe, kontextfreie Sprachen, gehen muss. Aber es gibt Regex-Engines die ”aufgebohrt” sind und man auch die zweite Modifikation von Aufgabenteil zwei als ”regulären” Ausdruck beschreiben kann. Perl und Ruby können das von Haus aus. Für Python kann man das `regex`-Modul installieren.

Hier meine Lösung für Tag 19:

Display Spoiler

Das Programm wandelt die Regeln erst in ein Wörterbuch das Regelnummer auf eine Liste von Listen umwandelt, wobei die äussere Liste die Alternativen enthält, und die inneren Listen die Verkettungen von Regeln. Oder es wird die Regelnummer auf den Buchstaben abgebildet.

Und dann habe ich eine Funktion die diese Datenstruktur in reguläre Ausdrücke umwandelt. Da kommt erst `graphlib` ins Spiel um die Regeln so zu sortieren dass man immer nur Regeln betrachten kann für die man vorher schon alle benötigten Regeln die von der Regel verwendet werden verarbeitet hat. Beim ersten Beispiel kann man die Regeln einfach von der letzten bis zur ersten Abarbeiten, aber die tatsächlichen Eingabedaten sind unsortiert.

Umwandlung in einen regulären Ausdruck am ersten Beispiel, wo man nichts sortieren muss, sondern einfach von Regel 5 bis Regel 0 gehen kann:

Code

0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

4 und 5 sind einfach der Buchstabe selbst. Und dann muss man die eigentlich einfach nur noch in die Regeln davor einsetzen und Klammern um einen passenden regulären Ausdruck aufzubauen:

3: "(ab|ba)"

2: "(aa|bb)"

1: "((aa|bb)(ab|ba)|(ab|ba)(aa|bb))"

0: "(a((aa|bb)(ab|ba)|(ab|ba)(aa|bb))b)"

Python

#!/usr/bin/env python3
import sys
from graphlib import TopologicalSorter

import pytest
import regex as re
from more_itertools import flatten, split_at

PART_1_EXAMPLE_LINES = """\
0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"

ababbb
bababa
abbbab
aaabbb
aaaabbb
""".splitlines()

PART_2_EXAMPLE_LINES = """\
42: 9 14 | 10 1
9: 14 27 | 1 26
10: 23 14 | 28 1
1: "a"
11: 42 31
5: 1 14 | 15 1
19: 14 1 | 14 14
12: 24 14 | 19 1
16: 15 1 | 14 14
31: 14 17 | 1 13
6: 14 14 | 1 14
2: 1 24 | 14 4
0: 8 11
13: 14 3 | 1 12
15: 1 | 14
17: 14 2 | 1 7
23: 25 1 | 22 14
28: 16 1
4: 1 1
20: 14 14 | 1 15
3: 5 14 | 16 1
27: 1 6 | 14 18
14: "b"
21: 14 1 | 1 14
25: 1 1 | 1 14
22: 14 14
8: 42
26: 14 22 | 1 20
18: 15 15
7: 14 5 | 1 21
24: 14 1

abbbbbabbbaaaababbaabbbbabababbbabbbbbbabaaaa
bbabbbbaabaabba
babbbbaabbbbbabbbbbbaabaaabaaa
aaabbbbbbaaaabaababaabababbabaaabbababababaaa
bbbbbbbaaaabbbbaaabbabaaa
bbbababbbbaaaaaaaabbababaaababaabab
ababaaaaaabaaab
ababaaaaabbbaba
baabbaaaabbaaaababbaababb
abbbbabbbbaaaababbbbbbaaaababb
aaaaabbaabaaaaababaa
aaaabbaaaabbaaa
aaaabbaabbaaaaaaabbbabbbaaabbaabaaa
babaaabbbaaabaababbaabababaaab
aabbbbbaabbbaaaaaabbbbbababaaaaabbaaabba
""".splitlines()


def is_empty_line(line):
    return line.strip() == ""


def parse_rules(lines):
    rule_number_to_rule_data = {}
    for line in lines:
        rule_number_text, _, rule_text = line.strip().partition(":")
        rule_text = rule_text.strip()
        if rule_text.startswith('"'):
            rule = rule_text.strip('"')
        else:
            rule = [
                list(map(int, altenative.split()))
                for altenative in rule_text.split("|")
            ]
        rule_number_to_rule_data[int(rule_number_text)] = rule
    return rule_number_to_rule_data


def parse_lines(lines):
    rules_lines, messages = split_at(lines, is_empty_line)
    return parse_rules(rules_lines), [message.strip() for message in messages]


def compile_regex_check(rule_number_to_rule_data, patch=False):
    sorter = TopologicalSorter()
    for rule_number, rule_data in rule_number_to_rule_data.items():
        if not isinstance(rule_data, str):
            sorter.add(rule_number, *flatten(rule_data))

    rule_number_to_pattern = {}
    for rule_number in sorter.static_order():
        rule_data = rule_number_to_rule_data[rule_number]
        if isinstance(rule_data, str):
            rule_number_to_pattern[rule_number] = re.escape(rule_data)
        else:
            pattern = "(?:{})".format(
                "|".join(
                    "".join(
                        rule_number_to_pattern[sub_rule_number]
                        for sub_rule_number in alternative
                    )
                    for alternative in rule_data
                )
            )
            if patch:
                assert rule_number_to_rule_data[8] == [[42]]
                assert rule_number_to_rule_data[11] == [[42, 31]]

                if rule_number == 8:
                    pattern = "(?:{0})+".format(rule_number_to_pattern[42])
                elif rule_number == 11:
                    pattern = "(?P<R11>{0}(|(?&R11)){1})".format(
                        rule_number_to_pattern[42], rule_number_to_pattern[31]
                    )

            rule_number_to_pattern[rule_number] = pattern

    regex = re.compile(rule_number_to_pattern[0])
    return lambda message: regex.fullmatch(message) is not None


def count_matching_messages(check_function, messages):
    return sum(map(check_function, messages))


def main():
    rule_number_to_rule_data, messages = parse_lines(sys.stdin)
    for patch in [False, True]:
        print(
            count_matching_messages(
                compile_regex_check(rule_number_to_rule_data, patch), messages
            )
        )


@pytest.mark.parametrize(
    "lines,expected", [(PART_1_EXAMPLE_LINES, 2), (PART_2_EXAMPLE_LINES, 3)]
)
def test_regex_check_example(lines, expected):
    rule_number_to_rule_data, messages = parse_lines(lines)
    assert (
        count_matching_messages(
            compile_regex_check(rule_number_to_rule_data), messages
        )
        == expected
    )


def test_modified_rules():
    rule_number_to_rule_data, messages = parse_lines(PART_2_EXAMPLE_LINES)
    assert (
        count_matching_messages(
            compile_regex_check(rule_number_to_rule_data, True), messages
        )
        == 12
    )


if __name__ == "__main__":
    main()

Display More

Teil zwei ist bei mir auch nicht allgemein gelöst, sondern wirklich sehr eng an der Aufgabe in die Lösung von Teil eins rein gepatcht. Ich denke man kann mit `regex` eine allgemeinere Lösung umsetzen. Also wo man nicht ”manuell” über die Bedeutung der beiden Modifikationen nachdenkt, sondern die einfach an den Regeln ändert und die geänderten Regeln durch die gleiche, unveränderte Funktion jagt, die auch für Teil eins funktioniert. Wäre ein TODO. 🙂

Die heutige Aufgabe habe ich gelesen, und ein paar Zeichnungen auf einem gebrauchten Briefumschlag gemacht, und dann beschlossen das heute Sonntag ist.

Renão · Dec 20th 2020

Quote from Manul

Ich bin mir nicht ganz sicher, ob ich verstehe, was Du meinst. Der Kniff beim Parsen ist doch, die Eingabe hinterher in einer Form repräsentiert zu haben, die einem eben das Bearbeiten der gestellten Aufgabe möglichst leicht macht. Ich finde, das beinhaltet durchaus ein bißchen Knobeln. Zumal ja immer noch das Raten dazu kommt, was wohl in Teil gefragt wird, und der Versuch, beim Parsen gleich dafür vorzusorgen. Das finde ich teilweise das witzigste.
...

Hm ich habe ehrlicherweise meist direkt beim Parsen versucht auf die Lösung der Aufgabe einzugehen, ohne mir bspw. irgendwelche Hilfsobjekte zu bauen - möglichst keine Zyklen verschwenden, wenn es offensichtlich klappt

Na ja, so oder so lese ich hier noch ein wenig quer, aber der Rückstand mindert meine Motivation noch umso mehr ... viel Spaß und Erfolg euch noch

Manul · Dec 21st 2020

__blackjack__ Danke! Den TopologicalSorter muss ich mir nochmal genauer anschauen – was er in Deiner Lösung macht, ist mir jetzt klar, warum er das macht noch nicht endgültig.

Meine umständliche Lösung ist in gewisser Weise dann sogar allgemeiner als Deine, macht aber eben sehr spezifische Annahmen über die Eigenschaften der Regeln

Display Spoiler

.

Renão Na ja, was heißt Hilfsobjekte? Ich versuche halt jeweils schon, die eingelesenen Daten auch gleich in geeigneter Form zu speichern, weil ich ja weiß, daß ich sie nochmal brauchen werde.

Die heutige (Tag 21) Aufgabe fand ich wieder etwas überschaubarer und dementsprechend auch in deutlich kürzerer Zeit zu lösen. Vielleicht motiviert das ja den einen oder anderen der mittlerweile passiven Mitleser, sich an der doch noch mal zu versuchen.

Manul · Dec 23rd 2020

Spielt außer mir eigentlich noch jemand mit?

Die heutige Aufgabe (Tag 23) ist eigentlich relativ trivial, mein naiver Ansatz stößt im Teil 2 aber an Ressourcengrenzen. Geht das noch jemandem ähnlich? Ich habe ein, zwei Ideen, wo ich ansetzen könnte, bin mir aber unsicher, ob die erfolgversprechend sind.

Manul · Dec 24th 2020

Ich setze mal mein Selbstgespräch fort: Tag 24 war wieder relativ straightforward, Teil 2 war dann noch mal

Display Spoiler

, mehr davon braucht's jetzt nicht mehr.

Nach nochmaligem Nachdenken habe ich meinen Teil 2 von Tag 23 jetzt auch auf knapp eine Minute Laufzeit bekommen. Anderswo habe ich von 8 Sekunden Laufzeit (wenn ich mich richtig erinnere ebenfalls in Python) gelesen, da würde mich schon interessieren, mit welchem Ansatz das erreicht wurde.

Jetzt noch das morgige Finale...

dll-live · Dec 24th 2020

Salü Manul

Finde es tool, das du bis am Schluss zeit hattest (gehe jetzt einfach davon aus, das morgen auch noch gemacht wird).

bei mir hat es leider nicht mehr gereicht, und aktuell stehen wieder andere "wichtigere / interessantere " oder anders ausgedrückt "nützlichere " Projekt an. (z.B.: erste Schritte mit Grafana (geht "nur" noch um die Darstellung - Die Datenaufzeichnung ist in mysql und influxdb vorhanden - da geht es erst mal um Temperaturaufzeichnung von 5 Messpunkten über ca 40 Stunden mit jede MInute ein Messwert. Was mich vorallem INteressiert ist die Dynamische ansicht - also "zoomen, falls ich ein Bereich genauer anschauen möchte....).

Gruss Dani

Manul · Dec 25th 2020

Quote from dll-live

Finde es tool

Aha? Neue Wortschöpfung aus "toll" und "cool"? Freut mich auf jeden Fall!

Quote from dll-live

gehe jetzt einfach davon aus, das morgen auch noch gemacht wird

Na klar. Ist erledigt und wie alle anderen Lösungen auf Github.

Hofei · Nov 24th 2021

Nicht zu glauben, aber bald ist wieder ein Jahr um und somit steht das Advent of Code Event so langsam vor der Türe.

https://www.heise.de/news/Adve…sel-Tuerchen-6269129.html

Habe leider bisher noch nichtmal die restlichen Rätsel von 2020 nachgemacht, bin gespannt wie weit ich es dieses Jahr wieder schaffe.

Wer wird dieses Jahr sonst noch wieder mit dabei sein?

Dennis89 · Nov 24th 2021

Ich werde es auch versuchen 👍🏼

schlizbäda · Nov 24th 2021

an sich eine coole Sache! Aber das werde ich mir persönlich nicht auch noch antun. Es stehen eh schon so viele Dinge auf meiner TODO-Liste

A so a Woch, då kánnst so vui z'reissn, aber mit da Arwat is komplett versaut!

("Ja, so eine Woche, da könnte man so viel schaffen, aber mit der Arbeit ist sie komplett versaut!")

Steinardo · Nov 24th 2021

Ich bin auch wieder dabei. Ich finde den Lerneffekt super wenn ich am Ende des Tages meinen Code mit eurem Code vergleiche. Das brachte mich wirklich weiter.

framp · Nov 24th 2021

Quote from Steinardo

meinen Code mit eurem Code vergleiche.

Welche Sprache nimmst Du denn?

Steinardo · Nov 24th 2021

Python, das haben die meisten benutzt.

__blackjack__ · Nov 24th 2021

Ich bin wohl auch wieder dabei. Diesmal vielleicht mit BBC-Basic als erste Waffe, statt CBM BASIC V2 wie letztes mal. Und ansonsten natürlich auch wieder Python.

Advent of Code

Similar Threads

Was der Opa noch wusste...

Tags