staging.inyokaproject.org

Eric Wastl hat auch dieses Jahr wieder einen Advent of Code vorbereitet. Vom 1. bis zum 25. Dezember wird jeden Tag ein kleines Rätsel, das aus zwei Teilen zu einem Thema besteht, freigeschaltet. Zum zweiten Teil des jeweiligen Rätsels kommt man erst, nach dem man den ersten gelöst hat. Es ist sozusagen ein Adventskalender mit Futter für's Programmiererhirn statt Schokolade. ☺

Die Rätsel selbst sind in sich geschlossen, man kann sie also in beliebiger Reihenfolge lösen (sofern die ”Türchen” schon offen sind) und auch welche auslassen die man nicht mag oder nicht schafft.

Die Schwierigkeitsgrade der Rätsel sind unterschiedlich, es sollte für jeden etwas dabei sein. Der zweite Teil der Rätsel ist oft etwas kniffliger oder rechenaufwändiger als der erste Teil.

Programmiersprache ist egal da man nur das Ergebnis zu einer gegebenen Eingabe abgeben muss. Dadurch kann man sich selbst auch den Schwierigkeitsgrad ein wenig erhöhen wenn das Rätsel sonst zu einfach ist. Ich habe beispielsweise öfter mal versucht ein Rätsel auf dem C64 zu lösen, also mit sehr wenig Rechenleistung und Speicher in BASIC, C, oder Assembler, oder wenn das wirklich nicht ausreichte, unter DOS in Pascal und/oder Assembler. ☺

Klingt interessant. Sind das dann so Formen ausgeben lassen, etc? Also sowas wie

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void reverseNumberTriangle(int max=5) {
    for (int r = 1; r <= max; r++)
    {
        for (int sp = 1; sp < r; sp++)
        {
            std::cout << " ";
        }
        for (int c = r; c <= max; c++)
        {
            std::cout << c << " ";
        }
        std::cout << std::endl;
    }
}
int main(int argc, char **argv) {
    for(int i=12; i>1; i-=3) {
        reverseNumberTriangle(i);
    }
    return 0;
}

@ChickenLipsRfun2eat: Meistens ist das Ergebnis nur eine Zahl oder eine einzeilige Zeichenkette und es geht meistens um ein Konzept um das eine schräge weihnachtliche Geschichte gestrickt wurde. Letztes Jahr ging es in der ersten Aufgabe beispielsweise um die Manhatten-Metrik (a.k.a. Taxi- oder Cityblock-Metrik). Also die Strecke zwischen zwei Kreuzungen in einem Stadtplan der in quadratische Blöcke aufgeteilt ist, wie in Manhatten (und vielen anderen amerikanischen Grosstädten).

Die Eingabe war eine Folge von Anweisungen in der Form R5, L5, R5, R3 denen man folgen muss um den Weihnachtsmann von seinem Landeplatz zum Osterhasenhauptquartier zu bringen, und die Frage war wie weit das dann vom Startpunkt entfernt ist. Die Anweisungen stehen für Links und Rechts, gefolgt von der Anzahl der Strassenblocks die man dann geradeaus gehen soll.

Der zweite Teil war dann, dass das Osterhasenhauptquartier nicht am Ende der gegebenen Anweisungen liegt, sondern an der ersten Stelle, an der eine Kreuzung das zweite mal besucht wird.

Teil 1 ging in BASIC auf dem C64 relativ schnell, jeweils ca. 8½ Sekunden für das Parsen der Eingabedaten und für das Folgen der Anweisungen. Mit Teil 2 war das Programm dann etwas mehr als eine halbe Stunde beschäftigt. Hauptsächlich weil es keine Datenstrukturen wie Hashtabellen gibt, mit denen man einen schnellen Test auf eine bereits besuchte Koordinate machen kann. Das habe ich linear in zwei Arrays (VX und VY) für die jeweils schon besuchten Kreuzungen gemacht (Zeile 400-430):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

   10 TI$="000000":MI=200:DIM IT(MI),ID(MI),DX(3),DY(3),VX(1000),VY(1000)
   20 DX(1)=1:DX(3)=-1:DY(0)=1:DY(2)=-1
  100 T1=TI:PRINT"PARSING INSTRUCTIONS...":IC=0:PL=0
  110 READ I$:IF I$="" THEN PRINT"PATH LENGTH";PL:IC=IC-1:GOTO 160
  120 A=0:A$=LEFT$(I$,1):IF A$="L" THEN A=-1
  130 IF A$="R" THEN A=1
  140 IF A=0 THEN PRINT"UNKNOWN TURN: ";A$:END
  150 IT(IC)=A:ID(IC)=VAL(MID$(I$,2)):PL=PL+ID(IC):IC=IC+1:GOTO 110
  160 T2=TI:PRINT(T2-T1)/60;"S"
  200 FOR PT=1 TO 2:T1=TI:PRINT:PRINT"PART";PT
  210 PRINT"FOLLOWING";IC;"INSTRUCTIONS..."
  220 SD=0:SX=0:SY=0:VC=0:VX(0)=SX:VY(0)=SX
  230 FOR I=0 TO IC:PRINT I;"{UP}":SD=(SD+IT(I)) AND 3
  240 ON PT GOSUB 300,400:NEXT
  250 PRINT:PRINT"DISTANCE TO HQ:";ABS(SX)+ABS(SY):T2=TI:PRINT(T2-T1)/60;"S"
  260 NEXT:END
  300 SX=SX+DX(SD)*ID(I):SY=SY+DY(SD)*ID(I):RETURN
  400 F=0:FOR J=1 TO ID(I):SX=SX+DX(SD):SY=SY+DY(SD)
  410 FOR K=0 TO VC:F=VX(K)=SX AND VY(K)=SY:IF F THEN K=VC:J=ID(I):I=IC
  420 NEXT:IF NOT F THEN VC=VC+1:VX(VC)=SX:VY(VC)=SY
  430 NEXT:RETURN
50000 DATA L2,L3,L3,L4,R1,R2,L3,R3,R3,L1,L3,R2,R3,L3,R4,R3,R3,L1,L4,R4,L2
50010 DATA R5,R1,L5,R1,R3,L5,R2,L2,R2,R1,L1,L3,L3,R4,R5,R4,L1,L189,L2,R2
50020 DATA L5,R5,R45,L3,R4,R77,L1,R1,R194,R2,L5,L3,L2,L1,R5,L3,L3,L5,L5
50030 DATA L5,R2,L1,L2,L3,R2,R5,R4,L2,R3,R5,L2,L2,R3,L3,L2,L1,L3,R5,R4,R3
50040 DATA R2,L1,R2,L5,R4,L5,L4,R4,L2,R5,L3,L2,R4,L1,L2,R2,R3,L2,L5,R1,R1
50050 DATA R3,R4,R1,R2,R4,R5,L3,L5,L3,L3,R5,R4,R1,L3,R1,L3,R3,R3,R3,L1,R3
50060 DATA R4,L5,L3,L1,L5,L4,R4,R1,L4,R3,R3,R5,R4,R3,R3,L1,L2,R1,L4,L4,L3
50070 DATA L4,L3,L5,R2,R4,L2,""

Programmausgaben:

PARSING INSTRUCTIONS...
PATH LENGTH 939
 8.43333334 S

PART 1
FOLLOWING 149 INSTRUCTIONS...
 149
DISTANCE TO HQ: 301
 8.55 S

PART 2
FOLLOWING 149 INSTRUCTIONS...
 49
DISTANCE TO HQ: 130
 2018.05 S

Falls jetzt jemand versucht ist die Aufgabe mit diesen Werten zu ”lösen”: Jeder Benutzer bekommt übrigens seine eigenen Eingabedaten, die konkreten Ergebnisse hier nützen also keinem etwas. 😉

Ah. Sehr interessant, danke. Ich denke, ich werde mir das am 01.12. direkt mal angucken. Wenigstens die einfacheren Aufgaben, die könnte ich hinbekommen ☺

btw: Weißt du wie lange ich kein c64-Basic mehr gesehen habe? Hatte direkt die Erinnerung an Die Dunkle Dimension ☺ Damals haben wir uns durch die Bugs mit dem Vampirgewölbe den fehlenden Dolch reingecheatet, damit es weiterging.

Und, macht da jmd. mit?

Hab es vergessen, aber schon in nem zweiten Tab offen. Gucke gleich mal rein ☺

Ja, aber ich hänge reichlich nach, weil ich gesundheitlich in den letzten Tagen etwas angeschlagen war. Bin gerade bei Tag 4 und finde die Aufgaben bis dahin verhältnismässig einfach.

Für den ersten Teil von Tag 3 habe ich das erste mal das BASIC-Programm auf dem C64 kompiliert weil es unkompiliert fast zwei Stunden gelaufen wäre. Und den zweiten Teil habe ich auf dem aktuellen PC unter Linux gelöst. Aufgaben wo man so etwas wie Hashmaps gebrauchen kann, sind auf dem C64 nicht so gut/effizient umsetzbar. ☺

Die Geschichte hat diesmal so einen „Textadventure-Retro-Touch“ finde ich. Der Held wird aus seiner normalen Umwelt gerissen und befindet sich plötzlich an einem Ort wo andere Regeln gelten und er sich da Aufgaben lösend durcharbeiten muss.

Was ich auch immer spannend finde, aus Sicht der Softwareentwicklung, ist die Überlegung beim ersten Puzzleteil wie generisch man das programmiert. Wenn man alles zu generisch macht, ist das viel unnötige Arbeit. Wenn man dagegen wirklich so spezifisch wie möglich die Aufgabe löst und jede mögliche Abkürzung verwendet, kann es sein das man im schlimmsten Fall beim zweiten Puzzleteil nichts von der ersten Lösung wiederverwenden kann, und dadurch dann am Ende insgesamt mehr Arbeit hat.

Beispiel dafür war bei mir Tag 1 wo ich den Umstand, dass die Folgeziffer der letzten Ziffer wieder die erste Ziffer in der Eingabe ist, einfach als Sonderfall mit einer zusätzlichen IF-Abfrage nach der Schleife über die Ziffern gelöst hatte. Wenn ich das gleich generisch gelöst hätte, wäre die Lösung für den zweiten Teil nur das ersetzen einer Konstanten 1 durch eine Variable gewesen, und man hätte den Code einfach mit zwei verschiedenen Werten für diese Variable durchlaufen lassen. In moderne(re)n Programmiersprachen also ein Parameter für eine Funktion die für beide Aufgabenteile identisch ist. In C hätte ich das gleich gemacht, aber das CBM BASIC V2 ist da etwas arm an mathematischen Operatoren, so das es in BASIC vom Code her keinen Unterschied macht — man braucht eine IF-Abfrage. Aber die wäre dann in der Schleife, schlägt dort also linear auf die Laufzeit, statt einmal nach der Schleife.

Bis auf 9b habe ich alles, inklusive 9a und der Testfälle für 9b. Allerdings fehlen mir Nerv und Zeit, das zu lösen - womöglich später. ☺

Bei 10b habe ich mich sehr schwer getan die Aufgabe richtig zu verstehen.

Marc_BlackJack_Rintsch schrieb:

Für den ersten Teil von Tag 3 habe ich das erste mal das BASIC-Programm auf dem C64 kompiliert weil es unkompiliert fast zwei Stunden gelaufen wäre.

Hast du da versucht die komplette Spirale zu berechnen? Ich habe mir das hier überlegt:

1
2
3
4
5
6
7
8
9

10 T=277678:  REM TARGET CELL VALUE
20 R=1:       REM RADIUS OF MANHATTAN SQUARE
30 C=R*R:     REM VALUE OF SPIRAL'S BOTTOM RIGHT CORNER
40 IF T>C THEN R=R+2:GOTO 30
50 E=R-1: REM STEPS BETWEEN CORNERS (AND FROM CONER TO CENTER)
60 M=E/2: REM STEPS FROM CORNER TO MIDDLE OF SPIRAL EDGE
70 IF T<C THEN C=C-E: GOTO 70
80 G=E - (M - ABS(C + M - T))
90 PRINT "STEPS TO CENTRE:";G

Marc_BlackJack_Rintsch schrieb:

Was ich auch immer spannend finde, aus Sicht der Softwareentwicklung, ist die Überlegung beim ersten Puzzleteil wie generisch man das programmiert. Wenn man alles zu generisch macht, ist das viel unnötige Arbeit. Wenn man dagegen wirklich so spezifisch wie möglich die Aufgabe löst und jede mögliche Abkürzung verwendet, kann es sein das man im schlimmsten Fall beim zweiten Puzzleteil nichts von der ersten Lösung wiederverwenden kann, und dadurch dann am Ende insgesamt mehr Arbeit hat.

Ich habe mich bislang nur bis Tag 6 durchgearbeitet, aber in Python habe ich noch nicht mehr als 80 Zeilen pro Tag benötigt. Mit gezielter Deduplizierung von Code für die beiden Teile könnte man vermutlich noch Zeilen einsparen.

@seahawk1986: Ich habe in der Tat die Variante ohne viel nachzudenken genommen und bin der Spirale Schritt für Schritt gefolgt. Wenn das zu lange gedauert hätte, wäre mein nächster Schritt wahrscheinlich zwischen meiner und Deiner Variante gewesen: nicht jeden Schritt einzeln, sondern immer die komplette Länge einer Seite.

1
2
3
4
5
6
7
8
9

    0 REM@ £PROTOCOL:£FASTFOR:£FASTARRAY:£SHORTIF
    1 REM@ £BOOLEAN IL:£BYTE DI:£INTEGER DX(,DY(,X=FAST,Y=FAST:£WORD I,L
    2 REM@ £REAL A:£CONSTANT Z
   10 TI$="000000":DIM DX(3),DY(3):DX(0)=1:DX(2)=-1:DY(1)=-1:DY(3)=1
   20 Z=368078:A=1:L=1:X=0:Y=0:IL=0:DI=0
   30 FOR I=1 TO L:IF A=Z THEN 100
   40 A=A+1:X=X+DX(DI):Y=Y+DY(DI):NEXT:IF IL THEN L=L+1:PRINT A;"{UP}"
   50 IL=NOT IL:DI=(DI+1) AND 3:GOTO 30
  100 PRINT:PRINT ABS(X)+ABS(Y);"IN";TI/60;"S"

Z ist mein Zielwert, in DX()/DY() sind die relativen Werte um einen Schritt eine der vier Richtungen zu gehen. A ist der aktuelle Schritt. L die Länge der aktuellen Seite. X/Y sollten selbsterklärend sein. IL ein Flag ob die Länge L beim Richtungswechsel erhöht werden soll oder nicht. DI ist der Index für die aktuelle Richtung in DX()/DY().

Die Zeilen unter 10 sind Anweisungen und Deklarationen für den BASIC-Compiler (BasicBoss), der kann ein paar mehr Datentypen als CBM BASIC V2. Wo man eigentlich immer Gleitkommazahlen verwendet und so gut wie nie Ganzzahlen. Die sind wegen der leicht dusseligen Implementierung langsamer und verbrauchen ausser bei Arrays den gleichen Speicherplatz im Vergleich zu Gleitkommazahlen.

@ChickenLipsRfun2eat: Ah, Erinnerungen! Ich hatte die Golden Disk-Version von der Dunklen Dimension. Der Autor hatte das ganze mal etwas aufpoliert und als Mobil-App rausgebracht, wo man auch die klassische Version inklusive Kartenmaterial herunterladen konnte. Auf der Website gibt es aber nur noch Online-Casino-Müll.

1
2
3
4
5

17  16  15  14  13
18   5   4   3  12  …
19   6   1   2  11  ^
20   7   8   9  10  |
21  22  23  24  25 26

Ich habe überlegt, ob ich es berechnen soll, oder beim ablaufen mitzählen soll, und dann doch abgezählt, weil es so rasch ging.

Zum Berechnen ist es hilfreich zu wissen, dass auf der Diagonalen, die vom Mittelpunkt nach rechts unten läuft, die Zahlen 1, 9, 25, … also (2n-1)² liegen, mit n als Zeile vom Mittelpunkt, zählend ab 1, liegen.

Damit kann man zwar leicht errechnen, auf welcher Schale der Wert liegt, aber von da aus ist es ja noch ein Stück bis zur Lösung, und dann schien die Chance hoch, dass man bei Aufgabe b doch durchlaufen muss.