|
|
|
|
|
Tee Off - Das erste ASP Golf Turnier
Geschrieben von: Christoph Wille 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:
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ösungBeginnen 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 TurnierteilnehmerBevor wir zu den Lösungen kommen, möchte ich den Endstand am Leaderboard des Golfturniers präsentieren:
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ägeDie 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ägeDie 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
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
Zeile 12: I=0
Zeile 13: If O Then T=T&" "&Y
Zeile 14: Next
Zeile 15: V("output")=split(mid(T,2))%> Kommentar der Spielleitung: bravurös - ein gekonnter Slice um den Bunker herum. Weiter so! 7 - Claudius Cetera, 216 SchlägeDie 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ägeDie 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ägeDie 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))%>
Kommentar der Spielleitung: Golf mit mehreren Bällen (Instanzen) im Spiel, sozusagen... 3 - Roman Pittroff, 181 SchlägeDie 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ägeDie 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ätzliches1 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 Spezifischer4 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ßbemerkungDas erste Golfturnier war bereits ein großer Erfolg unter den Teilnehmern, das nächste Turnier kommt bestimmt! Download des CodesKlicken Sie hier, um den Download zu starten. Verwandte Artikel
3. Loch - Dr. Evils Qualitätskontrolle Links zu anderen SitesWenn Sie jetzt Fragen haben...Wenn Sie Fragen rund um die in diesem Artikel vorgestellte Technologie haben, dann schauen Sie einfach bei uns in den Community Foren der deutschen .NET Community vorbei. Die Teilnehmer helfen Ihnen gerne, wenn Sie sich zur im Artikel vorgestellten Technologie weiterbilden möchten.
Haben Sie Fragen die sich direkt auf den Inhalt des Artikels beziehen, dann schreiben Sie dem Autor! Unsere Autoren freuen sich über Feedback zu ihren Artikeln. Ein einfacher Klick auf die Autor kontaktieren Schaltfläche (weiter unten) und schon haben Sie ein für diesen Artikel personalisiertes Anfrageformular.
Und zu guter Letzt möchten wir Sie bitten, den Artikel zu bewerten. Damit helfen Sie uns, die Qualität der Artikel zu verbessern - und anderen Lesern bei der Auswahl der Artikel, die sie lesen sollten.
©2000-2006 AspHeute.com |
