Glengamoi (Forum) · AspHeute · .NET Heute (RSS-Suche) · AspxFiles (Wiki) · .NET Blogs

Tee Off - Das erste ASP Golf Turnier

Geschrieben von: Christoph Wille
Kategorie: Tee Off

This printed page brought to you by AlphaSierraPapa

Den Perl Programmierern sind Golfturniere bereits ein Begriff, und seit kurzem gehören auch die ASP Programmierer zu den begeisterten Code-Golfern: wer eine vorgegebene Aufgabe mit den wenigsten Schlägen (Zeichen in einer ASP Datei) löst, der hat das Turnier gewonnen. Unser erstes Turnier hat gleich eine ganze Zahl von Cracks auf den Platz gelockt, sehen Sie selbst...

Die Golfturniere werden in der ASP Golf Liste von AspGerman abgehalten. Die Regeln sind einfach aber effektiv:

Der Code muß lauffähiges ASP Script sein.
Die erlaubten Programmiersprachen sind: VBScript only.
Das Programm darf aus einer oder mehreren Zeilen bestehen. Gezählt wird die Anzahl der Bytes des Programmes (Zeilenumbrüche kosten somit auch Bytes). Die Anzahl der Zeilen fließt nicht in die Bewertung ein.
Verwendung externer Komponenten außer solchen die im Betriebssystem ausgeliefert werden (zB CDONTS) ist nicht erlaubt.
Lösungsvorschläge werden an den jeweiligen Turnierleiter gemailt, und nicht in die Liste gepostet.
Jeder kann so oft er will einen Lösungsvorschlag vor Turnierende einschicken. Der Turnierleiter gibt immer den aktuell besten Bytecount bekannt, man weiß also, nach welcher "Deckenhöhe" man sich strecken (oder ducken) muß.

Natürlich kann es auch vorkommen, daß eine eingeschickte Lösung nicht den Anforderungen entspricht - dann wandert die Lösung in den sprichwörtlichen Bunker (aus dem man sich jederzeit mit einer neuen Lösung wieder befreien kann). Die Turnierleiter waren Christoph Wille und Bernhard Spuida, beides Autoren von AspHeute.

Aufgabenstellung und Musterlösung

Beginnen wir mit der Aufgabenstellung: "Es ist eine Liste von allen Zahlen zu erzeugen, die in einem bestimmten Bereich liegen und einem vorgegebenen Muster/Format entsprechen. Der Bereich ist definiert durch eine untere und obere Grenze, z.B. 2345 und 36456. Das Format ist 5-stellig und besteht aus den Buchstaben a bis e, z.B. "aabbc". Die abzugebende Datei entnimmt die Aufgabenstellung aus Application("input"), das ein drei-elementiges Array mit unterer Grenze, oberer Grenze und Format enthält und schreibt die Lösung als String-Array in Application("output"). Das Ergebnis-Array muß nicht sortiert sein."

Beispiel:

Aufgabe: Application("input") = Array(89,12123,"aaabb")
Lösung: Application("output") = Array("00099","11100","11111","11122","11133", _
                                           "11144","11155","11166","11177","11188","11199")

Die Musterlösung (Musterloesung.asp) gibt neben der Erfüllung der eigentlichen Aufgabe auch noch die errechneten Zahlen aus:

<%
dim arr,start,ende,form
arr = Application("input")
start = arr(0)
ende = arr(1)
form = arr(2)
dim a,b,c,d,e,f,loes,n,loesAr
set loes = server.CreateObject("Scripting.Dictionary")
Response.Write "<br><b>"
for a=0 to 9:for b=0 to 9:for c=0 to 9:for d=0 to 9:for e=0 to 9
        n=replace(replace(replace(replace(replace(form,"a",a),"b",b),"c",c),"d",d),"e",e)
        if (clng(n)>=start) and (clng(n)<=ende) then
                if not loes.Exists(n) then
                        loes(n) = 1
                        Response.Write n&"<br>"
                end if
        end if
next:next:next:next:next
Response.Write "</b>"
loesAr = loes.Keys
Application("output") = loesAr
%>

Sehen wir uns die Lösungen der Golf-Cracks an, was sie aus 609 Bytes gemacht haben.

Die Lösungen der Turnierteilnehmer

Bevor wir zu den Lösungen kommen, möchte ich den Endstand am Leaderboard des Golfturniers präsentieren:

Platz Wolfgang Kluge: 179
Platz Alexander Veit: 180
Platz Roman Pittroff: 181
Platz Alexander Schoeppl: 185
Platz Gerhard Buchner: 209
Platz Heiko Richler: 215
Platz Claudius Ceteras: 216
Platz Andreas Roth: 220
Platz Nils Kochan: 239

Präsentiert werden die Lösungen in umgekehrter Reihenfolge, basierend auf den Post Mortem Einsendungen (ohne Erklärung wäre der Sourcecode nicht verständlich) der Teilnehmer. Und nun auf zum Abschlag!

9 - Nils Kochan, 239 Schläge

Die Lösung von Nils sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist NilsKochan.asp)

<%b=Application("input")
for i=b(0)to b(1)
  e=string(5-len(i),48)&i
  d=0
  for j=1to 5
    for k=1to j
      if mid(b(2),j,1)=mid(b(2),k,1)and mid(e,j,1)<>mid(e,k,1)then d=1
    next
  next
  if d=0then c=c&","&e
next
Application("output")=split(mid(c,2),",")%>

Der Gedanke war, die Zahlen aus dem Bereich mit dem Muster zu vergleichen. Dabei wurde in dem JoJo in der Mitte der For...Next Schleifen einfach nach doppelten Zeichen im Muster gesucht. Waren dort welche vorhanden, müßen an den gleichen Positionen die Ziffern in der Zahl (schon zum String gewandelt) auch gleich sein. War das nicht der Fall wurde d auf 1 gesetzt und die Zahl war rausgefallen.

Mein Dozent in Software Engineering hat großen Wert darauf gelegt, nicht trickreich zu programmieren. Er wäre heute stolz auf mich ;-). Damit kann man aber beim Golfen nicht im Mittelfeld oder gar auf den vorderen Plätzen landen. Deshalb werde ich heimlich von eurem Code etwas in meine Trickkiste stecken (für das nächste Turnier).

In dem Bunker war ich gelandet, weil ich beim letzten Split nicht an das führende Komma gedacht hatte. (Kommentar der Spielleitung: tja, so eine kleine Unachtsamkeit und schon liegt man im Bunker...) Seit heute morgen weiß ich aber, wie man soetwas viiieeel eleganter macht.

8 - Andreas Roth, 220 Schläge

Die Lösung von Andreas sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist AndreasRoth.asp)

<%Set V=Application
A=V("input")
For B=A(0)To A(1)
Y=right("0000"&B,5)
O=1
For C=1To 5
D=mid(A(2),C,1)
G=mid(Y,C,1)
I=I&D&G
O=O And Mid(I,InStr(I,D)+1,1)=G
Next
I=0
If O Then T=T&" "&Y
Next
V("output")=split(mid(T,2))%>

Mein Ansatz ist es, alle Zahlen durchzugehen, und alle Zahlen auf die Gültigkeit mit dem Muster zu vergleichen.

<%Set V=Application
Zeile 1: Ich eröffne ASP Code (<%) und, um später Platz zu sparen, setze ich erst einen Zeiger auf das Application-Objekt,

A=V("input")
Zeile 2: Und referenziere das Input Array in eine weitere Variable

For B=A(0)To A(1)
Zeile 3: Eine Schleife die alle Zahlen zwischen Start und Ende einmal (in B) zurückgibt

Y=right("0000"&B,5)
Jetzt lasse ich mir die Zahl im erforderlichen Format (5 Stellig mit führenden Nullen als String) geben

O=1
Zeile 5: Indem ich der Variablen O den Wert 1 zuweise ist sie aus VB Boolean Sicht: "nicht false "(0), also True, mit dieser Variablen wird später die Gültigkeit gegengerechnet.

For C=1To 5
Zeile 6: Jetzt eröffne ich eine 2. Schleife, die die 5 Stellen der Zahl der Reihe nach durchgeht

D=mid(A(2),C,1)
Zeile 7: Der aktuelle Buchstabe aus dem Muster wird geholt

G=mid(Y,C,1)
Zeile 8: Die aktuelle Ziffer aus der aktuellen Zahl wird geholt.

I=I&D&G
Zeile 9: Beides wird hintereinander an eine Variable angefügt die für jede Zahl in Zeile 12 wieder zurückgesetzt wird

O=O And Mid(I,InStr(I,D)+1,1)=G
Zeile 10: der eigentliche Trick bei der Sache. Von innen nach außen: Instr() gibt immer das erste Vorhandensein eines Teilstrings. Hier überprüfe ich das erste Auftreten des aktuell getesten Buchstabens. Direkt daneben steht ja die Ziffer, die diesem Buchstaben als erstes zugewiesen wurde. Also lasse ich mir den mit Mid() Buchstaben aus dem in Zeile 9 zusammengesetzten String geben, und teste, ob er der aktuellen Ziffer entspricht. Ein Vergleich gibt einen Boolean zurück, und um diese nicht mit If nutzen zu müssen, was viel Platz kostet, weise ich der boolschen Variable aus Zeile 5 das Ergebnis der logischen Operation und das Ergebnis des Vergleichs zu (zB:O=O AND true). Dies ist nur dann Wahr, wenn beide Variablen Wahr sind. Ist O also aus einem früheren Vergleich falsch, oder der aktuelle Vergleich ist nicht wahr. Trifft der Vergleich also einmal nicht zu, ist O falsch.

Next
Zeile 11: Die nächste Ziffer wird kontrolliert

Zeile 12: I=0
I, das die Buchstaben / Zahlen Kombinationen für den Vergleich enthält, wird wieder zurückgesetzt. Um zu sparen nicht mit einem Leersting ("") sondern mit einer Ziffer. Es wird ja nach dem ersten Auftreten eines Buchstabens gesucht, sodaß eine Ziffer am Anfang nicht weiter stört.

Zeile 13: If O Then T=T&" "&Y
Wenn O nach dem ganzen Prozedere noch immer Wahr ist, entsprach der Vergleich dem Muster der Buchstaben, und die Zahl wird zusammen mit einem anführenden Lehrzeichen an ein String angehängt, der die Ergebnisse enthält

Zeile 14: Next
Die nächste Zahl wird untersucht

Zeile 15: V("output")=split(mid(T,2))%>
Nachdem nun alle Zahlen ausortiert und in den String T geschrieben wurden, wird der erste Buchstabe ignoriert (mid(T,2) => alles von Tab dem 2. Zeichen) und anhand des Leerzeichens (Der Defaultwert, wenn kein anderer Buchstabe angegeben wurde) mit Split ein Array generiert, das dem Zeiger auf das Application Object, Variable("output") übergeben wird.

Kommentar der Spielleitung: bravurös - ein gekonnter Slice um den Bunker herum. Weiter so!

7 - Claudius Cetera, 216 Schläge

Die Lösung von Claudius sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist ClaudiusCeteras.asp)

<%set x=Application
y=x("input")
for k=10^5to 10^6
n=right(k,5)
m=y(2)
for i=1to 5
m=replace(m,mid(y(2),i,1),mid(n,i,1))
next
if m+0>=y(0)and m+0<=y(1)and instr(z,m)=0then z=z&" "&m
next
x("output")=split(mid(z,2))%>

Der Algorithmus basiert darauf alle im Formatstring vorkommenden Buchstaben durch alle möglichen Kombinationen von 0 bis 9 zu ersetzen. Da dies mit Replace geschieht, wird automatisch dem Format gehorcht. Tricks:

1 Zeilenumbrüche = CR

2 Folgender Block: for k=10^5to 10^6 und n=right(k,5) ist ein Ersatz für: for k=0 to 99999 und n=right("0000"&k,5). Letzteres ist einfacher zu lesen, aber auch länger. Der Block dient dazu alle 5stelligen Kombinationen von 0-9 zu erzeugen. Daß die Kombinationen mehrfach erzeugt werden macht nichts, da doppelte Lösungen später rausgefiltert werden.

3 m+0 ist eine kurze Möglichkeit Strings in Zahlen umzuwandeln. Normalerweise: CInt(m) oder ähnliches.

4 Wenn man Space (Leerzeichen) als Trenner benutzt, muß man bei Split den Trenner nicht angeben.

Kommentar der Spielleitung: ein harter Drive, fürwahr!

6 - Heiko Richler, 215 Schläge

Die Lösung von Heiko sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist HeikoRichler.asp)

<%i=application("input"):

for z=i(0)to i(1):
        m=i(2):
        for y=1to 5:
                c=chr(y+96):
                p=instr(m,c):
                if p then m=replace(m,c,mid(right(1e6&z,5),p,1))
        Next
        if m-z=0 then o=o&","&m
next:

application("output")=split(mid(o,2),",")%>

Der Algorithmus überprüft die aktuelle Zahl (z) indem er im Formatstring (m=i(2)) die Buchstaben 'a' bis 'e' (c) der Reihe nach durch die Ziffer ersetzt die in der Zahl (z, bzw. right(1e6&zamp;,5))am ersten Vorkommen (p) des Buchstaben steht (mid(right(1e6&z,5),p,1)). Um die Zahl auf fünf Stellen zu erweitern brauchte ich mindestens vier Nullen am Ende einer Zeichenkette. Die bekomme ich mit 1e6 =1.0*10^6 = 1000000 (1e4 würde reichen). Ich erhalte dadurch in m eine gültige Zahl. Sind nun m und z noch immer gültig (m-z=0) dann hänge ich die Zahl an mein Ergebnis an. Nach dem then-Teil der bedingten Ausdrücke hatte ich einen Zeilenumbruch (nur CR), ansonsten nur den Doppelpunkt.

Kommentar der Spielleitung: Nach der Beispiellösung für den Test mit 609 ist das ein wahrer Quantensprung. Wir sind alle schon auf die nächsten Turniere gespannt.

5 - Gerhard Buchner, 209 Schläge

Die Lösung von Gerhard sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist GerhardBuchner.asp)

<%set a=Application
e=a("input")
f=e(2)
for t=e(0) to e(1)
z=right("0000"&t,5)
for i=0 to 3
if mid(z,5-i,1)<>mid(z,instr(f,mid(f,5-i,1)),1) then i=4
if i=3 then r=r&z&" "
next
next
a("output")=split(trim(r))%>

Instanz a der Application erzeugen da öfter benötigt.
Instanz e des Application("Input") erzeugen da öfter benötigt.
Format der Variablen f zuweisen.
Schleife durch alle Zahlen laufen. t hat die aktuelle Zahl.
5-stellige Zahl generieren.
Schleife mit 4 Durchläufen 0-3
mid(z,5-i,1) entspricht der Zahl an der aktuellen Stelle (es wird von hinten begonnen 5-i). Ich nehme den Buchstaben an der aktuellen Stelle mid(f,5-i,1), nehme das erste Vorkommen desselben Buchstabens instr(f,mid(f,5-i,1)) und von der Position des Treffers wieder die Zahl mid(z,instr(f,mid(f,5-i,1)),1) und vergleiche die beiden. Sind die Zahlen unterschiedlich, ist dies eine Zahl welche nicht dem Format entspricht und beende die Überprüfung mit i=4. Dies geschieht mit den Positionen 5-2.
Ist die Überprüfung OK und der Durchlauf bei 3 (letzte Position des Formats) dann diese Zahl r hinzufügen. Das Leerzeichen wird für den späteren Split benötigt, da dies das Standardtrennzeichen ist.
Nächste Position im Format.
Nächste Zahl.
Zuweisung an das Application-Array mit Trim um das letzte (überflüssige) Leerzeichen abzuschneiden.

Kommentar der Spielleitung: Golf mit mehreren Bällen (Instanzen) im Spiel, sozusagen...

3 - Roman Pittroff, 181 Schläge

Die Lösung von Roman sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist RomanPittroff.asp)

set a = Application
i = a("input")
for c = i(0)to i(1)
        w = right(10^9&c,5)
        v=i(2)
        for h=1to 5
                v = replace(v,mid(v,h,1),mid(w,h,1))
        next
        if v=w then s=s&x&v:x=" "
next
a("output")=split(s)

Die Lösung ähnelt denen der ersten Plätze. Der lustige Punkt dieser Lösung war:

        for h=1to 5
                v = replace(v,mid(v,h,1),mid(w,h,1))
        next

Kommentar der Spielleitung: wie im echten Leben, die asiatischen Golfer holen stark auf.

1 - Wolfgang Kluge, 179 Schläge

Die Lösung von Wolfgang sieht so aus (zur leichteren Lesbarkeit in mehrere Zeilen aufgegliedert, Originalfile ist WolfgangKluge.asp)

<%set f=application
t=f("input")
for i=t(0)to t(1)
x=t(2)
for a=1to 5
x=replace(x,mid(x,a,1),int(0&mid(i/1e5,a+2,1)))
next
if i=x*1then o=o&x&" "
next
f("output")=split(trim(o))%>

Grundsätzliches

1 Die Datei wurde im Unix-Format gespeichert. Dies hat zur Folge, daß ein Zeilenumbruch aus nur einem statt 2 Zeichen besteht. Letztendlich spart man damit in diesem Beispiel aber nur ein einziges Byte ein, da man in VBScript Anweisungen auch mit ":" trennen kann. Das eine Byte kommt in der If-Zeile zustande. Next darf hier nicht in derselben Zeile stehen, da es sonst nur ausgeführt werden würde, wenn i=x*1 ist. (Dies geht nicht da Syntaxfehler).

2 Das Application-Objekt (bzw. eine Referenz darauf) wurde in einer Variable gespeichert. Dies spart in diesem Code exakt 2 Bytes ;)

3 Alle unnötigen Leerzeichen wurden entfernt. Da eine Variable in VBScript niemals mit einer Zahl oder einem Sonderzeichen beginnen darf, ist es möglich auf eine Zahl oder einer Klammer folgend eine Anweisung anzugeben. zB. For a=1To. Hier 3 Bytes geholt.

Etwas Spezifischer

4 i/1e5 Das war das letzte Byte und hat die längste Zeit gekostet. 1e5 ist eine Kurzschreibweise von 1.e+5 und dies ist wiederum die Expotentialschreibweise einer Zahl gleichbedeutend mit 10^5. Heraus kommt 100000.

5 int(0&mid(i/1e5,a+2,1)) Der Sinn des Ganzen ist, die vorangestellten 0-en der Zahl i zurückgeben zu können. Durch das Teilen durch 100000, ergibt sich eine Zahl von 0.00000 und 0.99999 (durch den Wertebereich). Da 0-en nach der letzten Wertziffer auch automatisch "abgeschnitten" werden, würde Mid() alleine eine Leerstring zurückgeben. Deswegen mußte eine nochmalige Umwandlung mittels Int() erfolgen. Int("") ist allerdings auch ein Fehler - daher muß wieder eine 0 vorangestellt werden. 0.00012 ist jetzt natürlich 2 Zeichen länger, und man muß die Position mit +2 angeben.

6 i=x*1 Da i in diesem Beispiel eine Zahl und x ein String ist, können diese beiden nicht direkt verglichen werden (geht schon, ist aber nicht das erwünschte Ergebnis). In der Variable x steht definitiv kein Buchstabe mehr, daher gibt es mindestems 3 Möglichkeiten - eine Umwandlung mit CInt(), ein voranstellen von &H (an beide Variablen) oder eben das Multiplizieren mit 1. Letzteres ist natürlich kürzer und wird dadurch bevorzugt.

7 o=o&x&" " In der Variablen o wird das Ausgabearray (bis dahin noch einfacher String) gespeichert. Die Trennung der einzelnen Werte erfolgt mit einem Leerzeichen, da dies das Standardtrennzeichen für die Split-Funktion ist.

8 f("output")=split(trim(o)) Mittels Trim wird noch das letzte Leerzeichen abgeschnitten, damit das Ausgabearray nicht ein Feld zuviel hat. Split() braucht keine weiteren Parameter, da " " wie geschrieben Standard ist.

Der ganze Algorithmus basiert auf der Tatsache, daß die Replace-Funktion immer alle gefundenen Zeichen ersetzt, die sie findet. Da gleichzeitig immer alle 5 "Zeichen" der Zahl ersetzt werden, kommt es zu wirren/falschen Ergebnissen, wenn die Zahl nicht "in" das Format passt.

Zum Beispiel wird bei einem Format-String "aaabb" und der Zahl 00089 erst a durch 0 ersetzt(000bb), danach noch 2x 0 durch 0, dann wird b durch 8 ersetzt (00088) und danach nochmal 8 durch 9 (00099). Die Eingangszahl war 89 ergo falsch. Daher reicht zum Schluß auch das Testen des neu erstellten Strings x gegen die Zahl i aus um festzustellen, daß es sich eine gültige Zahl handelt - oder auch nicht.

Kommentar der Spielleitung: ein mächtiger Drive - ist Wolfgang der Tiger Woods des ASP Golf?

Schlußbemerkung

Das erste Golfturnier war bereits ein großer Erfolg unter den Teilnehmern, das nächste Turnier kommt bestimmt!