Advent of Code

Gute Links und Tutorials könnt ihr hier posten.
BlackJack

Unter http://adventofcode.com/ gibt's einen Adventskalender mit einem Rätsel/Puzzle für Programmierer für jeden Tag bis Weihnachten. :-)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Interessant, danke für den Tipp :)
Mich würden ja insb. verschiedene Lösungsansätze in Python interessieren. Können die hier diskutiert werden, oder lieber erst später?
BlackJack

@nezzcarth: Ich habe bis jetzt alles bis Tag 17 ausser Tag 15 gelöst. Eigentlich immer ziemlich plump, wenn ich ehrlich bin. Also eher „brute force“ als nachdenken, wenn's die Wahl gab. :-)

Wenn Du über irgendeinen Tag diskutieren möchtest, dann mach am besten im „Allgemeine Fragen“-Unterforum einen Beitrag auf mit einem entsprechenden Betreff „AoC - Tag X“ mit X = dem Tag/der Nummer des Puzzles. Es gibt ja offiziell eine Diskussion auf Reddit. Da sind auch mindestens zwei Github-Repositories verlinkt die Lösungen sammeln. Gegen eine öffentliche Diskussion hier sollte also eigentlich nichts sprechen.

Es bekommt übrigens nicht jeder bei jedem Puzzle die gleichen Daten! :-)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

BlackJack hat geschrieben:@nezzcarth: Ich habe bis jetzt alles bis Tag 17 ausser Tag 15 gelöst. Eigentlich immer ziemlich plump, wenn ich ehrlich bin. Also eher „brute force“ als nachdenken, wenn's die Wahl gab. :-)
Okay, das klingt so, als würde es mit der Zeit etwas langweilig? Bin erst bei 4b und bisher macht es Spaß :) Hatte das bisher meist etwas umfangreicher programmiert, als es sein müsste, zu Übungszwecken. Aufgabe 4 (Zahl finden, die gemeinsam mit einem festen String einen md5 Hash nach einem bestimmten Muster hat) ist die erste, die ich tatsächlich mit Brute Force löse. Ginge das eigentlich auch anders?
Wenn Du über irgendeinen Tag diskutieren möchtest, dann mach am besten im „Allgemeine Fragen“-Unterforum einen Beitrag auf mit einem entsprechenden Betreff „AoC - Tag X“ mit X = dem Tag/der Nummer des Puzzles. Es gibt ja offiziell eine Diskussion auf Reddit. Da sind auch mindestens zwei Github-Repositories verlinkt die Lösungen sammeln. Gegen eine öffentliche Diskussion hier sollte also eigentlich nichts sprechen.
Konkreter Diskussionsbedarf besteht nicht; mich würde einfach nur interessieren, wie man es noch lösen kann. Aber dann schaue ich einfach mal, was sich bei Reddit/Github so findet.
Es bekommt übrigens nicht jeder bei jedem Puzzle die gleichen Daten! :-)
Danke für den Hinweis.
BlackJack

@nezzcarth: Die Tage 1 bis 3 haben ja auch noch nichts was man mit roher Gewalt durchprobieren müsste. Da kann man ja einfach nach den vorgegebenen Regeln das Ergebnis ausrechnen.

Tag 4 muss man durchprobieren. Es sei denn wir haben auf magische Weise passende „rainbow tables“ vorliegen. Aber die müsste ja auch vorher jemand mal berechnet haben. :-)

Auch wenn Du Alternativen zu Deinen Lösungen oder Anmerkungen zu bekommen, kannst Du ja ein Thema dafür starten.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Ist bei Tag 7 Rekursion auch für Python die eleganteste Lösung, oder gibt es da eine äquivalente Alternative?
BlackJack

@nezzcarth: Man könnte wiederholt alle Ausdrücke auswerten bei denen die beteiligten Operanden aus Zahlen/bereits ausgewerten Variablen bestehen, solange bis alles ausgewertet ist. Was jetzt nicht wirklich elegant ist, aber simpel ist und mit wenig Stapelspeicher auskommt. Oder man sortiert die Ausdrücke topologisch nach Variablenabhängigkeiten und wertet dann einfach der Reihe nach aus. Eleganter, aber durch den Sortieralgorithmus etwas aufwändiger als einfach rekursiv auszuwerten.

Kleiner Tipp zum rekursiv auswerten (habe ich gemacht, war das naheliegendste): Die Ergebnisse der Variablen cachen sobald sie berechnet sind, sonst dauert das eeeewig. :-)

Ich bin heute (Blick auf die Uhr) äh, gestern endlich mit allen Tagen von 1 bis 21 fertig geworden. Momentan sitze ich an Tag 6 in C mit der Einschränkung, dass das am Ende auf einem C64 laufen soll. Also mit unter 64 KiB Speicher für Programm und Daten. Da bekommt man nicht einmal die eine Million Lampen aus Aufgabenteil A gleichzeitig im Arbeitsspeicher abgebildet wenn man nur ein Bit pro Lampe verwendet. Habe dafür aber schon einen Lösungsansatz. :-)
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

nezzcarth hat geschrieben:Ist bei Tag 7 Rekursion auch für Python die eleganteste Lösung, oder gibt es da eine äquivalente Alternative?
Es gibt Alternativen die vielleicht eleganter sind. Rekursion ist aber meiner Meinung nach am einfachsten zu Verstehen und mit Memoization so schnell, dass du mit anderen Ansätzen wohl kaum spürbar schneller wird.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

Okay, ich denke, dann werde ich einfach mal beide Ansätze versuchen :) Danke für die Tipps. Dass ich bis zum 25. fertig werde, ist ohnehin nicht mehr aufhole.

(Möglicherweise reicht aber auch ein Fortran-Compiler?

Code: Alles auswählen

$ file day7.txt 
day7.txt: FORTRAN program, ASCII text
;)
)

@BlackJack: So aus Neugier, wie verwendet man mehr Speicher, als man hat? Zwischenspeichern, irgendwie in Blöcke aufteilen?
BlackJack

@nezzcarth: Nette Idee mit dem FORTRAN-Compiler, aber leider:

Code: Alles auswählen

$ gfortran input.txt 
/usr/bin/ld:input.txt: file format not recognized; treating as linker script
/usr/bin/ld:input.txt:1: syntax error
:-)

Zwischenspeichern ist bei der üblichen Massenspeicherlösung, einem 1541-Laufwerk, für 1 Million Bitwerte zwar möglich — eine Diskettenseite fasst ca. 170 KiB und man braucht nur 122 KiB für eine entsprechende Bitmap — aber spätestens beim Aufgabenteil B reicht das nicht mehr. Da könnte man dann höchstens die ausgelagerten Teile komprimieren und hoffen dass der Platz dann ausreicht. Die ”Geschwindigkeit” des Laufwerks wäre aber auch für Teil A schon ein KO-Kriterium.

Teil A könnte ich noch mit der 2 MiB „RAM Extension Unit“ (REU) lösen die heute in meinem C64 steckt, aber bei Teil B würde auch das nicht reichen. Eine 16 MiB REU könnte ich gerade noch so im Emulator verwenden, aber AFAIK gab es die damals nie in echt, das ist nur die Obergrenze die man mit der Technik hätte adressieren können. Das wäre wohl auch ein ziemlich grosser Kasten geworden der extra Strom benötigt hätte. Die originalen 512 KiB REUs von Commodore hatten am C64 teilweise schon Probleme mit dessen normaler Stromversorgung (die waren eigentlich für den C128 gedacht). Das 2 MiB-Modul ist ein Nachbau einer anderen Firma, das kleiner ist (normale Steckmodulform) und anscheinend weniger Strom verbraucht.

Also meine Idee war die Instruktionen zu parsen und dann jede Zeile einzeln zu berechnen in dem ich schaue welche Instruktionen sich auf die jeweils aktuell berechnete Zeile beziehen. Im Grunde recht einfach und naheliegend.
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

BlackJack hat geschrieben:Unter http://adventofcode.com/ gibt's einen Adventskalender mit einem Rätsel/Puzzle für Programmierer für jeden Tag bis Weihnachten. :-)
Gibt's übrigens dieses Jahr wieder -- falls wer Interesse an Rätseln hat. Fand ich letztes Jahr ganz nett.
BlackJack

Verdammt, der erste Tag dieses Jahr bei dem ich die Lösung nicht für den C64 programmiert habe. :-)
nezzcarth
User
Beiträge: 1631
Registriert: Samstag 16. April 2011, 12:47

BlackJack hat geschrieben:Verdammt, der erste Tag dieses Jahr bei dem ich die Lösung nicht für den C64 programmiert habe. :-)
Auf Reddit wurde für die heutige Aufgabe (insb. Teil 2) ja recht schnell die B-Note "möglichst Hacker-Film-artigen Output erzeugen" eingeführt. Ich glaube, da würde der C64 eine gute Figur machen ;)
BlackJack

@nezzcarth: So eine Ausgabe ist kein Problem, aber das berechnen von mehreren Millionen MD5-Hashwerten könnte auf dem C64 länger dauern als der Adventskalender läuft. ;-)
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Sollte man nicht eigentlich jede Challenge in einer anderen Sprache lösen?
BlackJack

@DasIch: Das wären dann ja insgesamt 25 Sprachen. :-) Ich weiss gar nicht ob es so viele verschiedene für den C64 gibt. ;-)

Der Kalender selber will ja nur das Ergebnis haben. Quelltext wie beispielsweise bei Spoj ist nicht erforderlich.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

BlackJack hat geschrieben:das berechnen von mehreren Millionen MD5-Hashwerten könnte auf dem C64 länger dauern als der Adventskalender läuft. ;-)
Ich hatte auch erst die Befürchtung meinen Laptop möglicherweise für längere Zeit lahmzulegen ... aber die Laufzeit betrug dann - trotz Python - doch nur wenige Sekunden. Der Fortschritt seit C64 Zeiten ist schon enorm :)
BlackJack

@kbr: Bei der Aufgabe gestern (4. Tag) war mir schon beim entwickeln des Programms klar, dass ich das BASIC-Programm kompilieren muss, damit da eine halbwegs annehmbare Laufzeit bei herum kommt. Als ich es dann gelöst hatte, habe ich den C64 vorm schlafen gehen noch mal das unkompilierte Programm laufen lassen und dann heute morgen nachgeschaut wie lange es beschäftigt war: 6 Stunden und 48 Minuten. Kompiliert waren es nur 8½ Minuten. Wobei davon ein beträchtlicher Teil für das lesen der Daten von Diskette drauf gegangen sein wird.

Die 49 DM die ich damals für den BASIC-Boss-Compiler ausgegeben hatte, waren/sind wirklich gut angelegt. :-D In C wäre es wahrscheinlich auch nicht viel schneller — höchstens lesbarer als das BASIC-Programm.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

BlackJack hat geschrieben:In C wäre es wahrscheinlich auch nicht viel schneller — höchstens lesbarer als das Basic-Programm.
So viel zu Basic als Anfängersprache — meine frühen Basic Programme wären heute wahrscheinlich auch ziemlich unlesbar, aber nicht wegen der Optimierungen :)

AoC gefällt mir bisher gut, da sich bislang bei jeder Aufgabe erkennen lässt, wie gut Python mit den builtin-Datentypen und der Standard-Library aufgestellt ist und wie sauber sich die Lösungen erstellen lassen.
Falls es an brute-force mit wirklich langen Laufzeiten geht, werde ich wohl die Lust verlieren. Oder schaue mir mal Lua oder Rust an, falls es gerade regnet ... :)
BlackJack

@kbr: Naja, das liegt ja eher nicht an der Sprache BASIC an sich, sondern an den Implementierungen für die 8-Bit-Rechner damals. Die Beschränkung auf maximal zwei signifikante Zeichen bei Variablennamen, kein ELSE, kein BREAK, kein WHILE oder UNTIL, alles ein globales Programm ohne Funktionen oder benannte Unterprogramme, der langsame Interpreter und nur 40×25 Zeichen auf dem Bildschirm, …. In QBasic, das beim ersten DOS-Rechner dabei war, den wir zuhause hatten, ist das dann schon lesbarer umsetzbar. Und da hat man dann auch schon ein bisschen mehr kommentiert, weil es nicht mehr so auf den Speicherplatz ankam und das Programm dadurch auch nicht ausgebremst wurde.

Selbst wenn man meine Lösung für Tag vier…

[codebox=locobasic file=Unbenannt.txt] 0 REM@ £PROTOCOL:£FASTARRAY:£FASTFOR:£SHORTIF
1 REM@ £CONSTANT A:£BYTE LC(,LP(,I,CI,X,Y,T
2 REM@ £WORD RI,R,SI:£INTEGER C:£BOOLEAN F
10 TI$="000000":DIM LC(25),LP(25):A=65:PRINT"{CLEAR}"
20 POKE53280,2:POKE53281,5:POKE646,6
30 OPEN 2,8,2,"INPUT04.TXT,S,R":RI=0:SS=0:R=-1
40 INPUT#2,L$:IF ST THEN 60
50 RI=RI+1:GOSUB 100:GOTO 40
60 CLOSE 2:PRINT"SUM:{WHITE}";SS;"{BLUE}NP ROOM:{WHITE}";R;"{BLUE}TIME: {WHITE}";TI$:END
100 PRINT"{WHITE}";RI;"{BLUE}";L$;" ";
110 REM CALCULATE CHECKSUM
120 REM -COUNT LETTERS
130 FOR I=0 TO 25:LC(I)=0:LP(I)=I:NEXT:CI=1
140 C$=MID$(L$,CI,1):IF C$="-" THEN 170
150 C=ASC(C$)-A:IF C<0 THEN 200
160 LC(C)=LC(C)+1
170 CI=CI+1:GOTO 140
200 REM -SORT LETTERS
210 F=0:FOR I=0 TO 24:X=LC(LP(I)):Y=LC(LP(I+1)):IF X>Y THEN 240
220 IF X=Y AND LP(I)<LP(I+1) THEN 240
230 T=LP(I):LP(I)=LP(I+1):LP(I+1)=T:F=1
240 NEXT:IF F THEN 210
300 REM CHECK CHECKSUM
310 CK$="":FOR I=0 TO 4:CK$=CK$+CHR$(LP(I)+A):NEXT:PRINT CK$;" ";
320 IF CK$<>MID$(L$,LEN(L$)-5,5) THEN PRINT"{RED}FAKE{BLUE}":RETURN
330 PRINT"{LIGHT GREEN}REAL{BLUE}"
340 REM PARSE SECTOR ID
350 SI=VAL(MID$(L$,CI,5)):SS=SS+SI
400 REM DECODE ROOM NAME
410 N$="":FOR I=1 TO CI-1:C$=MID$(L$,I,1):IF C$="-" THEN N$=N$+" ":GOTO 430
420 C=ASC(C$)-A+SI:N$=N$+CHR$(C-INT(C/26)*26+A)
430 NEXT:PRINT"{YELLOW}";N$;"{BLUE}":IF LEFT$(N$,5)="NORTH" THEN R=SI
440 RETURN
5000 REM DUMP HISTOGRAM
5010 PRINT:FOR I=0 TO 24:PRINT CHR$(LP(I)+A);LC(LP(I)),:NEXT:PRINT:RETURN[/code]

…mehr oder weniger 1:1 in QBasic implementiert…

[codebox=qbasic file=Unbenannt.txt]CONST AscA=ASC("a")
DIM letterCount(25) AS INTEGER,letterPosition(25) AS INTEGER

sum=0
northPoleSectorId=-1

inFile=FreeFile
OPEN "input.txt" FOR INPUT AS #inFile
WHILE NOT EOF(inFile)
LINE INPUT #inFile,line$
GOSUB processLine
WEND
CLOSE #inFile

PRINT sum,"North Pole stuff is in sector:";northPoleSectorId
END

processLine:
' Initialize histogram.
FOR i=0 TO 25
letterCount(i)=0
letterPosition(i)=i
NEXT

' Count letters.
' After this loop ci contains the index of the first non-letter or
' dash character, i.e. the first digit of the sector number!
FOR ci=1 TO Len(line$)
c$=MID$(line$,ci,1)
IF c$<>"-" THEN
IF c$<"a" OR c$>"z" THEN EXIT FOR
j=ASC(c$)-AscA
letterCount(j)=letterCount(j)+1
END IF
NEXT

' Bubble sort the letter positions by letter count and letter value.
DO
swapHappend=0
FOR i=0 TO 24
x=letterCount(letterPosition(i))
y=letterCount(letterPosition(i+1))
IF x<y OR (x=y AND letterPosition(i)>letterPosition(i+1)) THEN
t=letterPosition(i)
letterPosition(i)=letterPosition(i+1)
letterPosition(i+1)=t
swapHappend=1
END IF
NEXT
LOOP WHILE swapHappend

checksum$=""
FOR i=0 TO 4
checksum$=checksum$+CHR$(letterPosition(i)+AscA)
NEXT

' If it is a real room then add the sector id to the result and
' decode the name and check if it is the room with the
' north pole stuff.
IF checksum$=MID$(line$,LEN(line$)-5,5) THEN
' ci is the index of the first digit of the sector id from counting
' the letters above.
sectorID=VAL(MID$(line$,ci))
sum=sum+sectorID

' Decode name.
name$=""
FOR i=1 TO ci-2
c$=MID$(line$,i,1)
IF c$="-" THEN
c$=" "
ELSE
c$=CHR$((ASC(c$)-AscA+sectorID) MOD 26+AscA)
END IF
name$=name$+c$
NEXT

IF InStr(name$,"north") THEN northPoleSectorId=sectorID
END IF

RETURN[/code]

…hat man es IMHO schon deutlich lesbarer.
Antworten