Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Ah, da liegt der Hund begraben! Jetzt verstehe ich es. Grober Verständnis-Schnitzer auf meiner Seite :-). Das Kapitel "tiefes vs. flaches Kopieren" sollte ich wohl noch einmal lesen. Krass, dass es dennoch solange bei mir zu den gewünschten Ergebnissen geführt hat.

Vielen Dank!
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Ok, jetzt hab ich die korrekt Lösung. Besten Dank, Lektion gelernt. Melde mich beim nächsten Problem :-)
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@steveO_O: Allgemeine Anmerkungen zum gezeigten Quelltext:

Wenn man Schlüssel *und* Wert aus einem Wörterbuch in einer Schleife braucht, dann sollte man gleich über diese Paare iterieren und nicht nur über den Schlüssel:

Code: Alles auswählen

def is_in_values(dictionary_one):
    bags = []
    for key, value in dictionary_one.items():
        if SEARCH_WORD in value:
            bags.append(key)
    return bags
Und bei diesem Code drängt sich eine „list comprehension“ geradezu auf:

Code: Alles auswählen

def is_in_values(dictionary_one):
    return [
        key for key, value in dictionary_one.items() if SEARCH_WORD in value
    ]
Gilt auch für `bag_check()`:

Code: Alles auswählen

def bag_check(item, dictionary_one):
    bags_output = [
        key for key, value in dictionary_one.items() if item in value
    ]
    print("bags_ouput", bags_output)
    return bags_output
Wobei die Funktionen nahezu das gleiche machen, nur mit anderen Werten. Das könnte man also zu einer Funktion zusammenfassen.

In der `main()`-Funktion begehst Du neben dem schon genannten Fehler noch einen weiteren: Man darf Datenstrukturen über die man gerade iteriert im allgemeinen nicht verändern. Und im besonderen ist das entfernen von Elementen aus Listen vor oder genau an dem Punkt, an dem sich der Iterator gerade befindet ein Problem, weil dann Elemente übersprungen werden in der Schleife. Beispiel:

Code: Alles auswählen

In [334]: items = list(range(10))                                               

In [335]: for item in items: 
     ...:     print(item) 
     ...:     if item == 5 or item == 6: 
     ...:         items.remove(item) 
     ...:                                                                       
0
1
2
3
4
5
7
8
9

In [336]: items                                                                 
Out[336]: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Die 6 ist immer noch da, weil die nie geprüft wurde.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

__blackjack__ hat geschrieben: Mittwoch 27. Januar 2021, 09:16 ....

In der `main()`-Funktion begehst Du neben dem schon genannten Fehler noch einen weiteren: Man darf Datenstrukturen über die man gerade iteriert im allgemeinen nicht verändern. Und im besonderen ist das entfernen von Elementen aus Listen vor oder genau an dem Punkt, an dem sich der Iterator gerade befindet ein Problem, weil dann Elemente übersprungen werden in der Schleife. Beispiel:

Code: Alles auswählen

In [334]: items = list(range(10))                                               

In [335]: for item in items: 
     ...:     print(item) 
     ...:     if item == 5 or item == 6: 
     ...:         items.remove(item) 
     ...:                                                                       
0
1
2
3
4
5
7
8
9

In [336]: items                                                                 
Out[336]: [0, 1, 2, 3, 4, 6, 7, 8, 9]
Die 6 ist immer noch da, weil die nie geprüft wurde.
Danke für die Tipps!

Wie machts man das dann in dem Beispiel wenn man die Liste beim Iterieren nicht ändern darf?
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

steveO_O hat geschrieben: Mittwoch 27. Januar 2021, 17:27 Wie machts man das dann in dem Beispiel wenn man die Liste beim Iterieren nicht ändern darf?
Man erzeugt dann eine neue Liste. Das geht besonders elegant mit List-Comprehensions:

Code: Alles auswählen

In [1]: items = list(range(10))

In [2]: items = [item for item in items if item not in {5, 6}]

In [3]: items
Out[3]: [0, 1, 2, 3, 4, 7, 8, 9]
Mit einer Schleife wie im Originalbespiel ist das natürlich auch möglich, nur eben deutlich unhandlicher.
steveO_O
User
Beiträge: 22
Registriert: Montag 23. März 2020, 20:08

Das ist ziemlich cool. Danke!
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Und auch dieses Jahr gibt es wieder einen Advent of Code: :)
https://adventofcode.com/2021
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

Ich hatte mir dieses Jahr vorgenommen, AoC zu nutzen um Bash-Scripting zu lernen. Ich glaube ich verwerfe das Vorhaben schnell wieder.

Part 1:

Code: Alles auswählen

#!/usr/bin/env bash

MEASUREMENTS=()
INCREASED=0

while read line
  do
    MEASUREMENTS+=($line)
  done < day1-input.txt

for (( i=2; i<=${#MEASUREMENTS[@]}; i++ ));
  do
    if [[ $MEASUREMENTS[$i] -gt $MEASUREMENTS[$i-1] ]]; then
      INCREASED=$((INCREASED + 1))
    fi
  done

echo $INCREASED
When we say computer, we mean the electronic computer.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Jo, Tag 1 ist ja wie immer ziemlich einfach. Das liess sich problemlos mit BASIC auf dem C64 lösen. Wobei Teil 2 Potential hat optimiert zu werden:

Code: Alles auswählen

10 TI$="000000":PRINT"READING INPUT...":DIM A(2000):OPEN 1,8,0,"INPUT01,S":N=0
20 INPUT#1,A(N):N=N+1:IF ST=0 THEN 20
30 CLOSE 1:PRINT N;"VALUES IN ";TI$:PRINT"PART 1..."
40 C=0:FOR I=0 TO N-2:IF A(I)<A(I+1) THEN C=C+1
50 NEXT:PRINT C;TI$
60 PRINT"PART 2...":C=0:FOR I=0 TO N-4
70 X=0:Y=0:FOR J=0 TO 2:K=I+J:X=X+A(K):Y=Y+A(K+1):NEXT:IF X<Y THEN C=C+1
80 NEXT:PRINT C;TI$
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

@sls: Das läuft bei mir nicht solange ich die Indexzugriffe auf MEASUREMENTS nicht in geschweifte Klammern setze: ``${MEASUREMENTS[$i]}``. Meine Bash sagt da sonst Syntaxfehler.

Und dann kommt bei mir das falsche Ergebnis, weil die Schleife bei 2 statt bei 1 anfängt. Indizes fangen bei Bash-Arrays bei 0 an.

Dann hat die Bash den praktischen ``readarray``-Befehl.

Um 1 erhöhen geht ohne Zuweisung, mit ``++``.

Und Lesbarkeit wird IMHO überbewertet — weg mit dem ``if``, her mit dem ``&&``. 😜

Code: Alles auswählen

#!/usr/bin/env bash

readarray MEASUREMENTS < input.txt

INCREASED=0
for (( i=1; i<=${#MEASUREMENTS[@]}; i++ )); do
    [[ ${MEASUREMENTS[i]} -gt ${MEASUREMENTS[i-1]} ]] && (( INCREASED++ ))
done

echo $INCREASED
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

__blackjack__ hat geschrieben: Mittwoch 1. Dezember 2021, 17:56 @sls: Das läuft bei mir nicht solange ich die Indexzugriffe auf MEASUREMENTS nicht in geschweifte Klammern setze: ``${MEASUREMENTS[$i]}``. Meine Bash sagt da sonst Syntaxfehler.

Und dann kommt bei mir das falsche Ergebnis, weil die Schleife bei 2 statt bei 1 anfängt. Indizes fangen bei Bash-Arrays bei 0 an.
Oh man, ich hatte das Bash-Skript in PyCharm geschrieben und ausgeführt, dabei hat er das auf meiner Kiste mit zsh ausgeführt. Komischerweise zählt er dort noch das newline mit und das `INCREASED` ist dann um eins zu hoch, selbst wenn ich beim korrekten Index 1 starte. Der Rest ist mega praktisch, danke dir!

Update: readarray wird von zsh nicht mal gefunden... Ein grund mehr wieder bash zu verwenden.
Update2: Newline wurde ebenfalls von Pycharm hinzugefügt. Trotzdem will ich zsh nicht mehr verwenden.
Zuletzt geändert von sls am Mittwoch 1. Dezember 2021, 18:51, insgesamt 1-mal geändert.
When we say computer, we mean the electronic computer.
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Iiihk, ja das ``<=`` als Schleifenbedingung ist natürlich falsch, dass müsste nur ``<`` heissen. Sorry, das habe ich übersehen.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

@sls:
Zu deinem Shell-Skript hier noch meine "One-Liner" (spätestens beim zweiten wird es etwas absurd, aber nun gut … :) ):

Code: Alles auswählen

#!/bin/bash
FILE="day01.txt"
paste <(head -n -1 "$FILE") <(tail -n +2 "$FILE" ) | awk '$2>$1{print}' | wc -l
paste -d + <(head -n -2 "$FILE") <(tail -n +2 "$FILE" | head -n -1) <(tail -n +3 "$FILE") | bc >_day01.tmp && paste <(head -n -1 _day01.tmp) <(tail -n +2 _day01.tmp) | awk '$2>$1{print}' | wc -l && rm -f _day01.tmp 
(AWK wollte ich so minimal wie möglich verwenden; ansonsten könnte man natürlich auch da viel mehr direkt machen)
Benutzeravatar
sls
User
Beiträge: 480
Registriert: Mittwoch 13. Mai 2015, 23:52
Wohnort: Country country = new Zealand();

__blackjack__ hat geschrieben: Mittwoch 1. Dezember 2021, 18:48 Iiihk, ja das ``<=`` als Schleifenbedingung ist natürlich falsch, dass müsste nur ``<`` heissen. Sorry, das habe ich übersehen.
Alles gut, das war ja ein Fehler von mir :-D

@nezzcarth:

Das beste was ich für Tag auf die Schnelle hinbekommen habe ist das (Part 2):

Code: Alles auswählen

#!/usr/bin/env bash

readarray MEASUREMENTS < day1.txt

for (( i=0; i+3<${#MEASUREMENTS[@]}; i++ )); do
  WINDOW1=$((${MEASUREMENTS[i]} + ${MEASUREMENTS[i+1]} + ${MEASUREMENTS[i+2]}))
  WINDOW2=$((${MEASUREMENTS[i+1]} + ${MEASUREMENTS[i+2]} + ${MEASUREMENTS[i+3]}))
  [[ ${WINDOW1} -lt ${WINDOW2} ]] && (( INCREASED++ ))
  done


echo $INCREASED
When we say computer, we mean the electronic computer.
Benutzeravatar
Kebap
User
Beiträge: 686
Registriert: Dienstag 15. November 2011, 14:20
Wohnort: Dortmund

Ich versuche mich derzeit auch am AoC 2021, weil ich das schöne Rätsel und Übung und Inspiration finde.
Zwar erwarte ich nicht, da innerhalb eines Monats fertig zu werden, aber darum geht es mir auch gar nicht.

Nur weiß ich noch nicht, wie ich dann hier Feedback zu meinen stümperhaften Ergebnissen erfragen kann.
Soll ich neue Threads pro Tag öffnen oder alles hier in den riesigen Thread einfügen, wo es ggf. untergeht?
Bis dato stelle ich alles bei Github online, weil ich die Versionierung mag und Zugriff von mehreren Orten:

https://github.com/Kebap/aoc2021
MorgenGrauen: 1 Welt, 8 Rassen, 13 Gilden, >250 Abenteuer, >5000 Waffen & Rüstungen,
>7000 NPC, >16000 Räume, >200 freiwillige Programmierer, nur Text, viel Spaß, seit 1992.
Benutzeravatar
Kebap
User
Beiträge: 686
Registriert: Dienstag 15. November 2011, 14:20
Wohnort: Dortmund

Tag 6 brachte exponentielles Wachstum mit sich.
Meine naive Lösung für die erste Teilaufgabe ließ sich nicht ohne weiteres für größere Listen fortsetzen, da die Berechnungen exponentiell immer länger dauerten.
Stattdessen habe ich (weil es nicht gefragt war) einen Teil der Informationen fallen gelassen, und die Gegenstände in Masse bearbeitet, statt jedes einzeln in Reihenfolge.
MorgenGrauen: 1 Welt, 8 Rassen, 13 Gilden, >250 Abenteuer, >5000 Waffen & Rüstungen,
>7000 NPC, >16000 Räume, >200 freiwillige Programmierer, nur Text, viel Spaß, seit 1992.
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

Bei den Aufgaben kommt es manchmal auf einzelne Worte in der Aufgabenstellung an, die einen Hinweis auf die Art und Weise einer Lösung geben.

Bei dieser Aufgabe war es die erste Zeile im gegebenen Beispiel: "Initial state: 3,4,3,1,2" und zwar das Wort state.

Danach wurde man zwar durch die Art und Weise der Erklärung des Beispiels auf eine falsche Fährte geschickt (erstellen einer immer längeren Liste).

Anstatt für jeden einzelnen Fisch den Status nachzuhalten, reicht es die Anzahl der Fische pro State (Lebenstage) nachzuhalten. Wenn man das mal mit Pen & Paper macht, kommt das heraus. Und dann erkennt man,
dass dies einfachst durch eine Verschiebung der Werte nach links zu erreichen ist.

Code: Alles auswählen

   0 1 2 3 4 5 6 7 8
0:   1 1 2 1
1: 1 1 2 1
2: 1 2 1       1   1
3: 2 1       1 1 1 1
Hatte die Verschiebung zuerst selbst gecodet und mich dann an collections deque erinnert. Das ist auch mit eine der wichtigen Helferbibliotheken bei AoC jedes Jahr. Meine Lösung:

Code: Alles auswählen

from collections import deque

data = list(map(int, open('input.txt').read().split(',')))

def life(n):
    counts = deque([data.count(i) for i in range(9)])
    for _ in range(n):
        counts.rotate(-1)
        counts[6] += counts[8]
    return sum(counts)

print('Part1:', life(80))
print('Part2:', life(256))
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
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Ich hatte gleich Abstand von der länger werdenden Liste genommen, weil ich ja immer als erstes CBM BASIC V2 im Kopf habe, und da wäre das selbst ohne exponentielles Wachstum ja keine gute Idee gewesen. Hier der erste Lösungsansatz von mir:

Code: Alles auswählen

   10 TI$="000000":SF=7:DIM P(SF+1)
   20 OPEN 1,8,0,"INPUT06,S":PRINT"READING FISH..."
   30 GET#1,A$:IF ST<>0 THEN PRINT"READ ERROR":CLOSE 1:END
   40 I=VAL(A$):P(I)=P(I)+1:GET#1,A$:REM SKIP ","
   50 IF ST=0 THEN 30
   60 CLOSE 1:PRINT "READING TIME ";TI$:PRINT
   70 FOR D=1 TO 256:PRINT"{UP}DAY";D
   80 C=P(0):FOR I=0 TO SF:P(I)=P(I+1):NEXT:P(SF+1)=C:P(SF-1)=P(SF-1)+C
   90 IF D=80 THEN GOSUB 200
  100 NEXT:GOSUB 200:PRINT"TOTAL TIME ";TI$:END
  200 S=0:FOR I=0 TO SF+1:S=S+P(I):NEXT:PRINT S:PRINT:RETURN
Funktioniert eigentlich auch, wenn der begrenzte Wertebereich der Gleitkommazahlen nicht wäre, denn die 80 Tage-Marke gibt das noch exakt aus, aber nach 256 Tagen fallen 36 Fische ”hinten runter”:

Code: Alles auswählen

RUN
READING FISH...
READING TIME 000008
DAY 80
 353079
DAY 256
 1.60540013E+12

TOTAL TIME 000037
37 Sekunden Laufzeit inklusive einlesen der Daten von Diskette ist aber okay für den alten Rechner.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Benutzeravatar
ThomasL
User
Beiträge: 1366
Registriert: Montag 14. Mai 2018, 14:44
Wohnort: Kreis Unna NRW

ist aber okay für den alten Rechner.
Was ist denn das für eine Hardware?
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
Benutzeravatar
__blackjack__
User
Beiträge: 12984
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Commodore 64, interpretiertes BASIC auf einer etwas unter 1 Mhz getakteten 8-Bit-CPU. Plus grottenlangsame Disk-I/O. Einlesen der 600 einstelligen Werte hat alleine schon 8 Sekunden gedauert.

Ich habe das mal zu GW-BASIC für den PC portiert, da gibt es auch einen Gleitkommatyp mit höherer Genauigkeit:

Code: Alles auswählen

10 SPAWN.FREQ=7:REM In days.
20 DIM POPULATION#(SPAWN.FREQ+1):REM Index=days till spawn, Value=# of fish.
30 OPEN "INPUT06.TXT" FOR INPUT AS #1
40 WHILE NOT EOF(1):INPUT #1,I:POPULATION#(I)=POPULATION#(I)+1:WEND:CLOSE #1
100 FOR DAY=1 TO 256
110   N#=POPULATION#(0)
120   FOR I=0 TO SPAWN.FREQ:POPULATION#(I)=POPULATION#(I+1):NEXT
130   POPULATION#(SPAWN.FREQ+1)=N#
140   POPULATION#(SPAWN.FREQ-1)=POPULATION#(SPAWN.FREQ-1)+N#
150   IF DAY=80 THEN GOSUB 500
160 NEXT:GOSUB 500:END
500 SUM#=0:FOR I=0 TO SPAWN.FREQ+1:SUM#=SUM#+POPULATION#(I):NEXT
510 PRINT SUM#:RETURN
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten