Advent of Code

[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.

[kbr]

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. In C wäre es wahrscheinlich auch nicht viel schneller — höchstens lesbarer als das BASIC-Programm.

[kbr]

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.

[kbr]

@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, …

... und zudem jede Menge GOTOs. Im Kontext bezog ich mich auch auf das C64 Basic, jedenfalls was meine Programme anging. Nach dem C64 habe ich Basic dann nicht mehr verwendet. Im Sinne von Jack Reacher: "Never go back" ...

[BlackJack]

@kbr: Die vielen GOTOs (und GOSUBs) sind ja eine direkte Folge der Einschränkungen von: kein ELSE, BREAK, WHILE, UNTIL, und keine benannten Funktionen. Es gab ja auch BASIC-Erweiterungen die so etwas zur Verfügung gestellt haben. Simons BASIC zum Beispiel hatte so einiges davon. Leider sind die Programme dadurch eher langsamer geworden.

So sieht das dann in QBasic aus wenn man noch eigene Datentypen und benannte Unterprogramme und Funktionen dazu nimmt:
[codebox=qbasic file=Unbenannt.txt]CONST AscA=ASC("a")

TYPE RoomType
name AS STRING
sectorID AS INTEGER
checksum AS STRING*5
END TYPE

TYPE HistogramType
count(25) AS INTEGER
letter(25) AS INTEGER
END TYPE


SUB ParseRoom(room AS RoomType, s AS STRING)
i=INSTR(s, ANY "0123456789")
room.name=MID$(s,1,i-2)
room.sectorID=VAL(MID$(s,i))
room.checksum=MID$(s,LEN(s)-5,5)
END SUB


SUB InitHistogram(histogram AS HistogramType)
FOR i=0 TO 25
histogram.count(i)=0
histogram.letter(i)=i
NEXT
END SUB


SUB CountLetters(histogram AS HistogramType, s AS STRING)
FOR i=1 TO LEN(s)
c$=MID$(s,i,1)
IF c$<>"-" THEN
c=ASC(c$)-AscA
histogram.count(c)=histogram.count(c)+1
END IF
NEXT
END SUB


SUB SortHistogram(histogram AS HistogramType)
DO
swapHappend=0
FOR i=0 TO 24
x=histogram.count(histogram.letter(i))
y=histogram.count(histogram.letter(i+1))
IF x<y OR (x=y AND histogram.letter(i)>histogram.letter(i+1)) THEN
t=histogram.letter(i)
histogram.letter(i)=histogram.letter(i+1)
histogram.letter(i+1)=t
swapHappend=1
END IF
NEXT
LOOP WHILE swapHappend
END SUB


FUNCTION IsValid(room AS RoomType)
DIM histogram AS HistogramType

InitHistogram histogram
CountLetters histogram,room.name
SortHistogram histogram

checksum$=""
FOR i=0 TO 4
checksum$=checksum$+CHR$(histogram.letter(i)+AscA)
NEXT

IsValid=checksum$=room.checksum
END FUNCTION


FUNCTION DecodeName$(room AS RoomType)
name$=""
FOR i=1 TO LEN(room.name)
c$=MID$(room.name,i,1)
IF c$="-" THEN
c$=" "
ELSE
c$=CHR$((ASC(c$)-AscA+room.sectorID) MOD 26+AscA)
END IF
name$=name$+c$
NEXT
DecodeName$=name$
END FUNCTION


DIM room AS RoomType, northPoleRoom AS RoomType
sum=0
northPoleRoom.sectorID=-1

inFile=FreeFile
OPEN "input.txt" FOR INPUT AS #inFile
WHILE NOT EOF(inFile)
LINE INPUT #inFile,line$
ParseRoom room,line$
IF IsValid(room) THEN
sum=sum+room.sectorID
IF INSTR(DecodeName(room),"north") THEN northPoleRoom=room
END IF
WEND
CLOSE #inFile

PRINT sum,"North Pole stuff is in sector:";northPoleRoom.sectorID[/code]
Das könnte man dann schon fast als lesbar bezeichnen. Da hat sich ein Microsoft so ein bisschen in Richtung Pascal bewegt. Was dann auch meine nächste Programmiersprache auf dem PC war.

[kbr]

@kbr: Die vielen GOTOs (und GOSUBs) sind ja eine direkte Folge der Einschränkungen von: kein ELSE, BREAK, WHILE, UNTIL, und keine benannten Funktionen.

Ja klar, ich wollte auch nichts anderes behaupten.

Da hat sich ein Microsoft so ein bisschen in Richtung Pascal bewegt. Was dann auch meine nächste Programmiersprache auf dem PC war.

Bei mir ebenso, Turbo Pascal 2 oder 3; das weiß ich gar nicht mehr so genau

[nezzcarth]

Für die heutige Aufgabe will mir noch kein passender Lösungsansatz einfallen. Meine Ausgangsidee war, dass die Aufgabenstellung Ähnlichkeiten mit den Türmen von Hanoi hat und man Algorithmen dafür adaptieren könnte. Allerdings hat diese Variante ja deutlich mehr Zusatzbedingungen, die das Ganze komplexer machen. Bin ich grundsätzlich auf dem richtigen Weg? Gibt es vielleicht etwas anderes, was man sich zur Inspiration ansehen könnte?

[BlackJack]

@nezzcarth: Alte Informatikerweisheit: Man kann fast jedes Problem als Graphenproblem ausdrücken. Ich musste spontan an das Ziege, Kohlkopf, Wolf-Rätsel denken. Ich denke das hat dazu mehr Ähnlichkeit als zu den Türmen von Hanoi.

[nezzcarth]

@nezzcarth: Alte Informatikerweisheit: Man kann fast jedes Problem als Graphenproblem ausdrücken. Ich musste spontan an das Ziege, Kohlkopf, Wolf-Rätsel denken. Ich denke das hat dazu mehr Ähnlichkeit als zu den Türmen von Hanoi.

Stimmt, diese Rätsel hatte ich ganz vergessen; die sind natürlich noch näher dran, als die Türme von Hanoi. Tatsächlich nennt der Autor der Rätsel ein vergleichbares als Referenz und der deutschsprachige Wikipedia-Artikel zu diesem Rätseltyp schlägt eine graphen-basierte Lösung vor. Mal sehen…

[nezzcarth]

Wie ist eure Zwischenbilanz bislang so? Ich war anfangs ganz gut dabei, nach Tag Zehn fehlen mir inzwischen 5½ Tage; mal sehen, was ich noch aufholen kann. Sagen euch die Aufgaben zu? Es sind gefühlt immer dieselben paar Aufgaben-Typen (Maximum/Minmum von etwas bestimmen, Eingaben nach Mustern durchsuchen, einen Interpreter für eine Mini-DSL schreiben) aber sind für mich ausreichend interessant. Was mich tatsächlich ein bisschen stört, ist dass die Lösungen, die man im Netz findet sehr auf schnellen und trickreichen Einsatz der verwendeten Programmiersprache ausgelegt sind, was unmittelbar mit der Leaderboard-Mechanik zusammenhängt; insb. die Pythonlösungen sind für meinen Geschmack oftmals eher unschön.

[BlackJack]

@nezzcarth: Die Ranglisten sind für'n A****. Ich denke was da hauptsächlich zählt ist in welcher Zeitzone man lebt, oder zumindest an welche man seinen Tages-/Nachtrhythmus angepasst hat. Wobei wir es hier in Mitteleuropa ja gar nicht so schlecht getroffen haben. Ich glaube das neue Rätsel kommt so gegen 6 Uhr morgens raus. Und die ersten 1000 richtigen Lösungen bekommen Punkte beziehungsweise in der Reihenfolge der Lösungsabgabe in die Rangliste.

Am 11. und heute fehlt mir noch der zweite Stern und 14, 15, und 19 habe ich noch nicht gelöst. Ich schaue mich eigentlich nicht woanders um, also die Diskussionen und Lösungen bei Reddit gehen an mir vorbei. Aus Zeitgründen kommt hier mittlerweile Python zum Einsatz, also nicht mehr der C64 mit BASIC und Compiler dafür. Ob die Python-Lösungen schön sind, die ich dafür ”verbreche” weiss ich nicht. Es geht ja primär um die Lösung der Probleme und nicht saubere Programme zu schreiben die lange im Einsatz sind. Wobei es sich doch manchmal lohnt gleich für die erste Aufgabe eine abstraktere Lösung zu schreiben, weil man ab und zu vom zweiten Aufgabenteil dazu gezwungen wird, die Lösung für den ersten Teil etwas generischer zu gestalten. Für den 21. hatte ich beispielsweise je eine Funktion pro Operation, die ich dann für den zweiten Teil für die Umkehrfunktionen dann doch zu Klassen gemacht habe. Und da bin ich dann heute morgen vor der Arbeit bei Umkehrung irgendwo falsch abgebogen und musste abbrechen. Und abends war dann Firmenweihnachtsfeier, deshalb habe ich da nicht mehr weiter gemacht.

Ich habe übrigens gerade festgestellt das ich mal besser auf die ASCII-Grafik auf der Indexseite geachtet hätte. Da unten wo jetzt die Tanne steht war am Anfang noch ein leerer Parkplatz. Wer weiss was ich da zwischenzeitlich verpasst habe.

[nezzcarth]

@BlackJack:
Ja, die Ranglisten sind auch nicht mein Fall -- für viele andere aber scheinbar ein großer Teil des Spaßes. Und ich finde, sie führen teilweise zu "unschönem" Code. Zwar müssen es keine solide durchgeplanten Programme mit Tests usw. sein, aber ich finde, auch bei solchen Aufgaben kann es sinnvoll sein, sich an gängige Konventionen der verwendeten Programmiersprache zu handeln (bei Python also z. B. PEP 8 inkl. Vermeidung von *-Importen, Verzicht auf globale Variablen usw.). Ich schaue mir nachdem ich eine Lösung gefunden habe gerne an, wie andere das gelöst haben. Und zumindest auf Reddit sehen die Lösungen nicht selten eher nach Quick and Dirty und/oder Code-Golf aus.

Mir fehlen noch Tag 11, 13, 17, 19, 21.2, 22-25. Mal sehen, was ich bis Ende des Jahres noch schaffe Bei 21.2 -- was du ja gerade angesprochen hast -- überlege ich noch, wie ich die Umkehrung gut realisieren kann; "reverse positions X through Y" ist, glaube ich, doch nicht umkehrbar...
Die Änderungen an der ASCII-Grafik waren mir gar nicht aufgefallen, danke für den Hinweis

[BlackJack]

Mir fehlen noch 11.2, 14, 15, 19, 21.2, 22.2, 24, und 25.

Bei „reverse X through Y“ ist das doch selbst schon die Umkehrfunktion. Wenn man das zwei mal anwendet, hat man wieder den Ausgangszustand. Das schwierigste ist IMHO das Rotieren mit gegebenen Buchstaben, weil da die Anzahl der Stellen vom Index des Buchstabens vor dem Rotieren abhängt.

[nezzcarth]

Wenn man das zwei mal anwendet, hat man wieder den Ausgangszustand. Das schwierigste ist IMHO das Rotieren mit gegebenen Buchstaben, weil da die Anzahl der Stellen vom Index des Buchstabens vor dem Rotieren abhängt.

Das war auch, was ich meinte; copy&paste Fehler. Wie soll man rückwirkend analytisch bestimmen, welche Position der Buchstabe vorher hatte? Das geht vermutlich doch wieder besser per (semi-)brute-force.
Naja, mal sehen, was mir dazu einfällt

[kbr]

Wie soll man rückwirkend analytisch bestimmen, welche Position der Buchstabe vorher hatte? Das geht vermutlich doch wieder besser per (semi-)brute-force.

Nein, das ist sogar ganz einfach, da die Verschiebung des Buchstabens aus der ersten Teilaufgabe eindeutig ist. Ich hatte mir eine Tabelle angelegt um dies zu testen, da ich auf brute-force keine Lust hatte. Und siehe da: auch dieser Schritt ist eindeutig umkehrbar

[nezzcarth]

Auch dieses Jahr gibt es wieder eine Neuauflage:
http://adventofcode.com/2017
Vielleicht kennen es machen noch nicht und haben ja einige Lust, mit zu rätseln.

[nezzcarth]

Wie habt ihr Tag 3 gelöst? Ich muss zugeben, dass ich mir für Teil 1 per oeis passende Formeln zusammengesucht habe, um die X und Y Koordinaten zu bestimmen. Zählt das schon als Schummeln? Jedenfalls ging es mit einem Iterator, der die Koordinaten ausspuckt dann ganz einfach...

[__blackjack__]

Und auch dieses Jahr gibt's den Adventskalender für Programmierer wieder. *<:-)