Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Viel Spaß bei Tag 7!

Bei mir sieht es wieder wie Kraut und Rüben aus. Das Refactoring wird intensiv werden.
Bild
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Bei mir ging's. Habe den ersten Teil über ne Queue gelöst, wo immer die neuen "Super Bags" rein kamen und parallel dazu ein Set für die Ergebnisse. Darüber lief eine while-Schleife, die fertig ist, sobald die Queue vollständig geleert wurde - eben das Prinzip einer Warteschlange. Als Datenstruktur hab ich dafür ebenfalls ein Set genommen, um doppelte Einträge zu vermeiden.

Und Teil zwei konnte man rekursiv lösen, wenn man sich vorher eine geeignete Datenstruktur (Bags <-> Anzahl) angelegt hat. Aufpassen musste man, weil halt neben den enthaltenen Bags ja auch die Tasche an sich (quasi das jeweilige Super Bag) mitgezählt werden musste - außer auf der obersten Ebene.

Wer schon fertig ist oder sich gerne selbst betrügen möchte, kann ja mal hier in meine Lösung schauen... :)

https://gist.github.com/seblin/52b63d94 ... 245902ed0b
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Hier nochmal deutlich kompakter, wobei ich mir den rekursiven Ansatz für Schritt 1 ehrlich gesagt abgeguckt hab und nur leicht angepasst habe.

Trigger-Warnung: Nicht PEP8-konform, da Code auf Modulebene steht. Mache ich normalerweise nicht, tat ich für diese Version aber dennoch. :)

Code: Alles auswählen

import re

parse_bag = re.compile("[a-z]+ [a-z]+").match
parse_contents = re.compile("(\d+) ([a-z]+ [a-z]+)").findall
with open("day7/input.txt") as stream:
    rules = {
        parse_bag(line).group(): {
            name: int(amount) for amount, name in parse_contents(line)
        } for line in stream
    }

def count_super_bags(needle):
    return needle == "shiny gold" or any(map(count_super_bags, rules[needle]))

def count(needle):
    return 1 + sum(amount * count(bag) for bag, amount in rules[needle].items())

print(sum(map(count_super_bags, rules)) - 1)
print(count("shiny gold") - 1)
Zuletzt geändert von snafu am Montag 7. Dezember 2020, 20:47, insgesamt 1-mal geändert.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@snafu: Ich habe es mir im ersten Teil einfacher gemacht. Auch per rekursiven Aufrufen und die haben auch eiskalt Knoten mehrfach geliefert und am Ende erst alles ein ein `set` gekippt. Laufzeit ist auf dem Desktoprechner nicht merkbar.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Gibt es auch schon eine C64-Lösung in BASIC oder ist die Aufgabe zu komplex dafür?
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@snafu: BASIC habe ich gar nicht erst versucht. Ich hatte da nicht wirklich Zeit für heute, aber ich denke ich versuche mit das noch in C. Ein Problem ist sicher der Speicher, denn das ist eine ziemliche Datenmenge. Meine Eingabedatei ist etwas über 42 KiB gross, zur Verfügung stehen ca. 50 KiB freier RAM. Das heisst in den 8 KiB müsste dann das Programm, der Speicher für den Graphen, und der Stack passen — bei einer Aufgabe die davon für Rekursion sicher etwas brauchen wird.

Man kann beim einlesen schon was aus den Zeilen weglassen, dann bleibt mehr Arbeitsspeicher. Falls das nicht reicht, würde ich versuchen das mit zweimal einlesen lösen: im ersten Durchgang nur die Farbnamen einlesen, und im zweiten Durchgang dann den Graphen erstellen.

Und falls das dann immer noch nicht reicht, hätte ich da noch eine Speichererweiterung. Also machbar sollte es eigentlich sein. 🤓
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Guten Morgen und viel Freude bei Tag 8!

Gestern und heute hatte ich das Gefühl, dass ich die Aufgabe nicht optimal gelöst habe. Leider hatte ich bisher keine Zeit neben der Lösung an einer Optimierung zu arbeiten oder mir andere Lösungen anzusehen.

Bild
gerryontour
User
Beiträge: 23
Registriert: Dienstag 30. Juni 2020, 15:50

WIe lange braucht ihr denn für die Aufgaben?
Ich komme teilweise leider auf gar keinen Ansatz, dafür fehlt mir wohl noch die Erfahrung.

Habt ihr trotzdem Tipps wie ich daraus lerne und das "Rätsel" selbständig löse?
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Heute habe ich circa 30 Minuten gebraucht. Ich mache das dann Schritt für Schritt. Erst lese ich den Input ein, dann zerlege ich ihn in die nötigen Bestandteile und dann arbeite ich die Bedingungen ab. Das ist dir grobe Vorgehensweise. Hast du denn die ersten Aufgaben erledigen können? Zu ein paar Tagen gibt es hier ja auch schon Ansätze und Lösungen. Poste gerne, was du versuchst. Du wirst Hilft finden.
gerryontour
User
Beiträge: 23
Registriert: Dienstag 30. Juni 2020, 15:50

Ja mir fehlt einfach die Übung. Und ich habe auch keine Zeit mich mit einem Code 3h zu beschäfitgen momentan leider.

Die einfachen würde ich gerne lösen. Welche sind das denn? Wird das sukzessive schwerer?
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Tag 8 in BASIC für den C64:

Code: Alles auswählen

   10 TI$="000000":DIM I$(700),O(700),X(700):PL=0
   50 PRINT"LOAD BOOT PROGRAM...":OPEN 2,8,2,"INPUT08,S,R"
   60 IF ST<>0 THEN CLOSE 2:GOTO 100
   70 GET#2,C1$:GET#2,C2$:GET#2,C3$:I$(PL)=C1$+C2$+C3$:INPUT#2,O(PL):PL=PL+1
   80 PRINT PL:PRINT"{UP}";:GOTO 60
  100 PRINT"TIME AFTER READING: "TI$:PRINT"EXECUTE PROGRAM..."
  110 GOSUB 1000:PRINT"PART 1:";A:PRINT"TIME SO FAR: "TI$
  120 PRINT"FIX PROGRAM..."
  130 FOR J=0 TO PL-1:I$=I$(J)
  140 IF I$="JMP" THEN NI$="NOP":GOTO 170
  150 IF I$="NOP" THEN NI$="JMP":GOTO 170
  160 GOTO 190
  170 PRINT J:PRINT"{UP}";:I$(J)=NI$:GOSUB 1000:I$(J)=I$
  180 IF IP=PL THEN PRINT"PART 2:"A:J=PL
  190 NEXT
  900 PRINT"TOTAL TIME: "TI$:END
 1000 REM EXECUTE PROGRAM UNTIL END OR ENDLESS LOOP DETECTED
 1010 A=0:IP=0:FOR I=0 TO PL:X(I)=0:NEXT
 1020 IF IP=PL OR X(IP) THEN RETURN
 1030 IF I$(IP)="ACC" THEN A=A+O(IP):GOTO 1060
 1040 IF I$(IP)="JMP" THEN IP=IP+O(IP)-1:GOTO 1060
 1050 IF I$(IP)<>"NOP" THEN PRINT"UNKNOWN INSTRUCTION "I$(IP)" @"IP:END
 1060 X(IP)=-1:IP=IP+1:GOTO 1020
@gerryontour: Übung bekommt man in dem man übt. Man muss da einfach dran bleiben. Üben kostet Zeit. Du musst das ja nicht in ”Echtzeit” machen, also nicht jeden Tag eine Aufgabe lösen. Wenn Du eine Woche für eine Aufgabe brauchst, ist das ja auch nicht weiter schlimm. Die Aufgaben sind nach Weihnachten weiter zugänglich, und auch Antworten werden von der Website das ganze Jahr geprüft. Du kannst auch die Aufgaben der vorhergehenden Jahre noch lösen.

Bei den Aufgaben ist in der Regel ein oder mehrere kleine Beispiele dabei die ”vorgerechnet” werden. Es macht Sinn damit die eigene Lösung zu testen. Also tatsächlich in Code.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

ja, der Schwierigkeitsgrad steigt an. Grundsätzlich jedenfalls:
AdventOfCode hat geschrieben: Why was this puzzle so easy / hard? The difficulty and subject matter varies throughout each event. Very generally, the puzzles get more difficult over time, but your specific skillset will make each puzzle significantly easier or harder for you than someone else. Making puzzles is tricky.
aus https://adventofcode.com/2020/about
Bolitho
User
Beiträge: 219
Registriert: Donnerstag 21. Juli 2011, 07:01
Wohnort: Stade / Hamburg
Kontaktdaten:

Guten Morgen und viel Spaß bei Tag 9!

Heute empfand ich es wieder leichter als die Tage zuvor.

Bild
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Mein Code für Tag 8 und Tag 9. Wie immer sind weitere Optimierungsmöglichkeiten sehr gerne erwünscht.

Tag 8:

Code: Alles auswählen

with open('input.txt') as file:
    code = [[cmd, int(val)] for cmd, val in [line.strip().split() for line in file]]

def run():
    seen = set()
    acc = pointer = terminated = 0
    while not terminated and not pointer in seen:
        seen.add(pointer)
        cmd, val = code[pointer]
        if cmd == 'acc':
            acc += val
        elif cmd == 'jmp':
            pointer += (val - 1)
        pointer += 1
        terminated = pointer >= len(code)
    return terminated, acc

        
# Part 1
print(run()[1])

# Part 2
complement = {'nop':'jmp', 'jmp':'nop'}
        
for idx, (cmd, val) in enumerate(code):
    if cmd != 'acc':
        code[idx][0] = complement[cmd]
        terminated, accu = run()
        if terminated:
            print(accu)
            break
        code[idx][0] = cmd
        
Tag 9:

Code: Alles auswählen

from itertools import combinations

with open('input.txt') as file:
    data = [int(line.strip()) for line in file]

# Part 1
for i in range(25, len(data)):
    comb = set(sum(x) for x in combinations(data[i - 25: i], 2))
    if not data[i] in comb:
        target = data[i]
print(target)

# Part 2
summ = start = end = 0
while summ != target:
    if summ < target:
        end += 1
    else:
        start += 1
        end = start + 1
    summ = sum(data[start:end])

print(min(data[start:end]) + max(data[start:end]))
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
gerryontour
User
Beiträge: 23
Registriert: Dienstag 30. Juni 2020, 15:50

Code: Alles auswählen

print("------------" +"\n\n")
with open("pe.txt", "r") as f:
    file = f.readlines()
    file = [i.replace("\n", "") for i in file]

    for key, value in enumerate(file):
        twfive = file[key:key + 25]
        final = []
        for i in twfive:
            for e in twfive:
                ap = int(i) + int(e)
                final.append(ap)
        if value in final:
            continue
        else:
          print(value)
          break
Mein Ansatz hätte heute so in der Art ausgesehen. Leider funktionierts nicht so wie es sollte. Ich glaube das hängt mit der

Code: Alles auswählen

if value in final
Abfrage zusammen?
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

@ThomasL: Ohne auf deinen anderen Code einzugehen, aber ein split() ohne Argumente braucht kein strip() davor, da es ja jeglichen Whitespace herausfiltert. Insofern tut etwas wie "spam ham eggs\n".split() bereits das, was du wahrscheinlich durch die Kombination aus strip() und split() erreichen willst. split() funktioniert halt so, dass der leere String als Teil der Rückgabe ignoriert wird. Kann man auch ganz einfach ausprobieren mit " spam ".split().

EDIT: Technisch gesehen gibt es natürlich keinen ignorierten Teil, da einfach der Whitespace am Anfang und am Ende durchlaufen wird, ohne dass etwas hinzugefügt wird. Ich meinte das quasi aus der semantischen Sicht, wo manch einer von einem Split (= linker und rechter Teil) im Ergebnis ausgeben würde.
Benutzeravatar
snafu
User
Beiträge: 6731
Registriert: Donnerstag 21. Februar 2008, 17:31
Wohnort: Gelsenkirchen

Hier ein Nachbau von split() ohne Argumente in Python-Code:

Code: Alles auswählen

def get_part(iterable):
    result = []
    for char in iterable:
        if not char.isspace():
            result.append(char)
        elif result:
            break
    return "".join(result)

def split(string):
    parts = []
    it = iter(string)
    while (part := get_part(it)):
        parts.append(part)
    return parts
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@gerryontour: Anmerkungen zum Quelltext:

Warum verbindest Du zwei literale Zeichenketten mit ``+``? Da kann man doch einfach gleich nur *eine* Zeichenkette schreiben.

An den Namen musst Du arbeiten. Was soll `f` bedeuten? `file`? Gibt es ja auch, aber das ist dann gar keine Datei, sondern eine Liste mit Zeichenketten. `i` ist ein ganz schlechter Name für eine Zeichenkette. Leser erwarten unter `i`, `j`, und `k` ganze Zahlen die als Index verwendet werden können. `line` wäre beispielsweise ein passender Name für eine Zeile.

Der `readlines()`-Aufruf ist Überflüssig. Dateiobjekte sind iterierbar und liefert die Zeilen aus der Datei.

Zeilenendezeichen entfernt man am Ende und sicht nicht in der gesamten Zeile danach. Also `rstrip()` statt `replace()`. Wobei das nicht wirklich notwendig ist, denn `int()` stört sich nicht an ”whitespace” vor und nach der Zahldarstellung.

Nach dem Einlesen sollte man bereits eine Liste mit Zahlen haben und nicht eine Liste mit Zeichenketten wo *jedesmal* zum addieren die Zeichenketten erneut in Zahlen umgewandelt werden.

Im ``with``-Block braucht nur der Code stehen, der die Daten einliest. Nachdem das passiert ist, braucht man die Datei ja nicht mehr.

`key` und `value` ist hier auch unpassend weil `key` gar kein Schlüssel ist.

`twfive` ist auch kein guter Name. Er ist kryptisch abgekürzt und sagt überhaupt aus was der Wert bedeutet, nur das es irgendwas mit „twenty five“ ist, wenn man den Namen mit der literalen Zahl in der Zeile in Verbindung bringen kann.

Und auch `final` ist nicht wirklich verständlich.

`i` ist wie gesagt ein Name für Indexwerte, also auch wieder schlecht, weil es zwar ganze Zahlen sind, aber keine Indexwerte. Bei `e` und `ap` kann ich nicht mal ansatzweise erraten was die bedeuten sollen. Man muss auch nicht jeden Zwischenwert an einen Namen binden.

``continue`` sollte man meiden. Das ist hier auch überhaupt nicht nötit, denn nach dem ``if``/``else`` wird ja ganz regulär ein neuer Schleifendurchlauf begonnen. Man kann also einfach die Bedingung beim ``if`` umkehren und den Code aus dem ``else``-Zweig in den ``if``-Zweig verschieben.

Zwischenstand mit besseren Namen, aber Code der immer noch das gleiche macht wie Deiner, also noch fehlerhaft ist:

Code: Alles auswählen

#!/usr/bin/env python3


def main():
    print("------------\n\n")
    with open("pe.txt", "r") as file:
        numbers = [int(line) for line in file]

    for i, number in enumerate(numbers):
        previous_numbers = numbers[i : i + 25]
        sums = []
        for number_a in previous_numbers:
            for number_b in previous_numbers:
                sums.append(number_a + number_b)

        if number not in sums:
            print(number)
            break


if __name__ == "__main__":
    main()
Die von Dir genannte Zeile macht in der Tat nicht das richtige. Mit den richtigen Namen fällt vielleicht sogar auf was der Fehler in der Zeile ist.

Aber auch die Schleife welche die Summen berechnet ist fehlerhaft. Einer der Beispielfälle für (un)gültige Zahlen aus der Aufgabenstellung würde damit nicht funktionieren.

Darum als Tipp diese Beispielfälle tatsächlich als Tests zu programmieren. Da gibt es bekannte Eingabedaten und dazu gehörende Ergebnisse. Wenn Dein Code die nicht reproduzieren kann, dann ist es *sehr* wahrscheinlich, dass es auch bei den Eingabedaten für die Aufgabe nicht richtig funktionieren wird.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
narpfel
User
Beiträge: 643
Registriert: Freitag 20. Oktober 2017, 16:10

@gerryontour: Ergänzend zu __blackjack__: Das Testen geht sehr einfach mit pytest:

Code: Alles auswählen

import random


def is_valid_next_number(number, last_numbers):
    # TODO
    return False


def test_is_valid_next_number():
    preamble = random.shuffle(list(range(1, 26)))
    assert is_valid_next_number(26, preamble)
    assert is_valid_next_number(49, preamble)
    assert not is_valid_next_number(100, preamble)
    assert not is_valid_next_number(50, preamble)

Code: Alles auswählen

$ pytest day09.py
============================= test session starts ==============================
platform linux -- Python 3.9.0, pytest-6.1.2, py-1.9.0, pluggy-0.13.1
rootdir: /tmp/t
collected 1 item

day09.py F                                                               [100%]

=================================== FAILURES ===================================
__________________________ test_is_valid_next_number ___________________________

    def test_is_valid_next_number():
        preamble = random.shuffle(list(range(1, 26)))
>       assert is_valid_next_number(26, preamble)
E       assert False
E        +  where False = is_valid_next_number(26, None)

day09.py:11: AssertionError
=========================== short test summary info ============================
FAILED day09.py::test_is_valid_next_number - assert False
============================== 1 failed in 0.03s ===============================
Dabei hilft es enorm, wenn man den Code auf (kleine) Funktionen aufteilt, die man leicht unabhängig voneinander testen kann.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Tag 9 in BASIC für den C64:

Code: Alles auswählen

   10 TI$="000000":N=1000:DIM N(N):OPEN 2,8,2,"INPUT09,S,R"
   20 PRINT"READING NUMBERS...":I=0
  100 IF ST<>0 THEN CLOSE 2:GOTO 200
  110 INPUT#2,N(I):I=I+1:IF (I AND 31)=0 THEN PRINT I:PRINT"{UP}";
  120 GOTO 100
  200 PRINT"READING TIME: "TI$:PRINT"SEARCHING INVALID NUMBER..."
  210 FOR I=25 TO N:PRINT I:PRINT"{UP}";:X=N(I):FOR J=I-25 TO I-2
  220 FOR K=J+1 TO I-1:F=N(J)+N(K)=X:IF F THEN J=I:K=I
  230 NEXT:NEXT:IF NOT F THEN R1=X:I=N
  240 NEXT:PRINT"PART 1:"R1:PRINT"TIME SO FAR: "TI$:
  300 PRINT"SEARCHING CONTIGEOUS SUBSET..."
  310 FOR I=0 TO N:PRINT I:PRINT"{UP}";:S=0:FOR J=I TO N:IF S>=R1 THEN B=J-1:J=N
  320 S=S+N(J):NEXT:IF S=R1 THEN A=I:I=N
  330 NEXT:MI=N(A):MA=N(A):FOR I=A TO B:X=N(I):IF X<MI THEN MI=X
  340 IF X>MA THEN MA=X
  350 NEXT:PRINT"PART 2:";MI+MA:PRINT"TOTAL TIME: "TI$
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten