|
|
|
|
|
Tee Off! Wolpertinger Genome Project
Geschrieben von: Bernhard Spuida Nach langer Pause gab es wieder ein Golfturnier mit spannender Aufgabe und heroischen Mitspielern. Dieses Mal stammt die Aufgabenstellung von Alexander Veit. Die Aufgabe erscheint auf den ersten Blick kompliziert - weshalb auch eine Dauer von einem Monat für das Turnier festgesetzt wurde - ist aber mit erstaunlich wenig Schlägen zu bewätigen. Sehen wir sie uns an. Die AufgabenstellungBösewicht Venter möchte aus der DNA verschiedener alpenländischer Tierarten den Wolpertinger wieder erschaffen. Hans Blond, Topspion der Staatspolizei, soll ihm zuvor kommen und die Welt vor der Tyrannei, die Venter mit Hilfe des Wolpertingers zu errichten gedenkt (Wie soll das gehen?, der Autor) bewahren. Da Blond keinen Plan von Molekulargenetik hat, bittet er seine Golffreunde um Mithilfe.Regeln:
Diese Aufgabenstellung h&oumL;rt sich wirklich kompliziert und nahezu unlösbar an. Ist sie aber nicht, außerdem wurde ein Testprogramm zur Verfügung gestellt. Ein Beispiel für Rohdaten in der richtigen Sequenz:
ALLEK
KUEHE
HETR
ETRINK
NKENG
GERNEM
MILCH
Ist doch nicht so schlimm wie man nach dem ersten Durchlesen der Aufgabenstellung meinen könnte, oder? Nach einigen Diskussionen auf der Mailingliste war allen klar was zu tun war und ein spannendes Turnier nahm seinen Lauf. Leaderboard
Zwar recht wenige Teilnehmer, aber in Anbetracht der Aufgabe beachtlich. Und kein einziger Golfer lag zum Turnierende im Bunker. Die ersten beiden Plätze bekamen einen Intrexx Portal Manager respektive ein United Planet Zippo. Gratulation! Bedenkt man daß die längste gültige Einreichung bei 712 Schlägen (Stefan Mayer, auf 311 herunter gegolft) liegt, ist der Spizenplatz wirklich eindrucksvoll. Wir waren alle überrascht daß so etwas möglich ist. Und nun wenden wir uns einigen Lösungen zu: Stefan MayerStefan hat eine wahrhaft heroische Verbesserung seines Scores erreicht. Von anfänglich 712 um 401 Schläge verbessert, alle Achtung. Na dann - mein Code samt Erklärung:
<%Set V=Application
A=V("input")
u=ubound(a)
for g=0 to u
m=0
for i=0 to u
for j=0 to u
c=len(a(i)):d=len(a(j))
if d<c then c=d
p=0
for e=1 to c
if i<>j and right(a(i),e)=left(a(j),e) then p=e
next
if m<p then m=p:k=j:f=i
next
next
a(f)=a(f)&mid(a(k),m+1)
a(k)=""
next
v("output")=join(a,q)%>
Mein Problem ist aber, daß ich nicht mehr so genau weiß, wie ich darauf gekommen bin...... Auf jeden Fall funktioniert es so: Die einzelnen Fragmente werden jeder mit jedem auf Überschneidungen verglichen und da, wo sie am größten ist, wird Vorderteil und Hinterteil im Feld des Vorderteils gespeichert. Der Hinterteil wird auf "" gesetzt. Das ganze wiederholt er so oft es Felder im Array gibt. Zum Schluß wird das Array zusammengebaut mit dem Trennzeichen LEER. That's it Michael SchmidtDie beste Lösung ist ablauftechnisch ähnlich der von Stefan Mayer, aber doch um einiges kürzer. Außerdem erklärt uns Michael noch einen alternativen Ansatz den er aus Zeitgründen leider nicht einreichen konnte. Man muß nicht immer 'for'-Schleifen nehmen... Platz da und Weg frei für meine Lösung:
<%set a=Application:i=a("input"):u=ubound(i)
for e=0to u
t=0
for m=0to u:for n=0to u
if m<>n then
for j=1to len(i(m))
if right(i(m),j)=left(i(n),j) and j>t then t=j:b=m:c=n
next
end if
next:next
i(b)=i(b)&mid(i(c),t+1)
i(c)=r
next
a("output")=i(b)%>
Also: Von der Technik ebenso wie bei Stefan, ich durchlaufe eine Schleife sooft wie Elemente übergeben wurden. Die Variable t wird bei jedem Schleifendurchlauf auf 0 gesetzt, in ihr wird später in der Schleife die maximale Überlappung gespeichert. Jetzt wird jedes Element im Input-Array mit jedem anderen verglichen, wobei mit einer Schleife, geschaut wird, wie hoch jeweils die Überlappung zum nächsten Element ist (right(i(m),j)=left(i(n),j)). Ist bei diesem Schleifendurchlauf noch keine höhere Überlappung gefunden worden (j>t), merke ich mir die Überlappung in t und die entsprechenden Elementnummern in b und c (t=j:b=m:c=n). Danach füge ich direkt im Input-Array den nicht überlappenden Rest des c-Elements (rechter Teil der Überlappung, mid(i(c),t+1)) an das b-Element (linker Teil der Überlappung, i(b)) und leere das Feld i(c). Am Ende von dat Janze steht nur noch im letzten i(b)-Feld etwas, was dann auch direkt an a("output") übergeben werden kann. Übrigens: Zweite Lösung mit 237 Zeichen:
<%set a=Application:i=a("input"):u=ubound(i)
do
t=0
for m=0to u
for n=0to u
for j=1to len(i(m))
if right(i(m),j)=left(i(n),j) and j>t and m<>n then t=j:b=m:c=n
next
next
next
i(b)=i(b)&mid(i(c),t+1)
i(c)=r
loop while t
a("output")=i(b)%>
Funktionsweise wie oben, jedoch mit
do ... loop while t statt der äußeren for/next-Schleife. Es läuft halt so lange, wie es Überlappungen gibt. m<>n innerhalb von if right(i(m),j)=left(i(n),j) and j>t and m<>n, dadurch spare ich mir ein weiteres "if", "then" und "end if". So wird man nebenher noch diese lästigen Abfragen los... Markus OestreicherDiese Lösung ist anders und zeigt uns Golf wie es sich gehört - knapp, originell und funktional. Die vorbildliche Erklärung folgt den in den Code eingefügten Ziffern.
So... Platz 3 meldet sich auch zu Wort.
<%
(1)
set b=application
a=b("input")
c=ubound(a)
(2)
p=9
while p
m=1
(3) for i=0to c
for j=0to c
s=a(j)
(4) if right(a(i),p)=left(s,p)<(i=j)<(s=x)then
a(i)=a(i)&mid(s,p+1)
a(j)=x
(5) m=0
end if
next
next
(6) p=p-m
wend
b("output")=join(a,x)
%>
(1) Das traditionelle "must have" (Siehe dazu frühere Tee Off! Artikel) Kopf hoch - beim nächsten Turnier wirds wieder! Michele MarschingDie Lösungen werden zwar kürzer je mehr wir uns der Spitze nähern, die Erklärungen aber nicht. Auch hier sind die wichtigsten Schritte nummeriert. Michele hat auch eine sehenswerte Lösung gefunden, die der des Siegers ähnelt, aber doch unterschiedlich ist. Jeder Golfer hat seinen persönlichen Stil. Seht selbst: Dann wollen wir mal
<%SET a=Application
b=a("input")
FOR L=99TO 1STEP-1 #1
c=UBOUND(b)
FOR z=0TO c #2
FOR y=0TO c
e=b(y)
f=b(z)
IF LEFT(f,L)=RIGHT(e,L)THEN
b(z)=w:b(y)=e&MID(f,L+1):a("output")=join(b,w)END IF #3
NEXT
NEXT
NEXT%>
Nachdem ich zuerst die Übereinstimmung in einem zweidimensionalen Array
gespeichert hatte, kam mir irgendwann die Idee, wie bei Johann wohl
auch... Mit dem FOR L=-99TO-1 von Johann wäre ich auf 197/196 (wenn 9 statt 99) Bytes gekommen. Beim nächsten Mal fällt mir da auch wieder was vom Auge,... ;) P.S.: Nachdem ich mit Markus auf einer Stufe war, glaube ich, daß er das selbe hatte wie ich, aber die Zeile 8 bei ihm noch IF e<>""AND z<>y AND LEFT(b(z),L)=RIGHT(e,L)THEN b(y)=e&MID(b(z),L+1):b(z)=w:a("output")=b(y)END IF heißt... fragt mich nicht, wie ich darauf gekommen bin, das eine andere Art, sich den Wert zu merken die Abfragen nicht mehr braucht ;) P.S.2: Endlich mal Silber *smile* Bewundernswert. Und nun auf zum Sieger mit seinen unglaublichen 192 Schlägen. Johann EngbersDie bisherigen Lösungen waren ja alle mehr oder weniger 'gierig' - d.h. sie suchten nach den größten Überlappungen. Johann ging einen anderen Weg, ähnlich wie Michele und doch anders: Hallo Golfer, hier dann mein Code:
<%set b=application
h=b("input")
p=ubound(h)
for c=-9to-1
for l=0to p
for i=0to p
if l<>i and right(h(l),-c)=left(h(i),-c)then
h(i)=h(l)&mid(h(i),1-c):h(l)=l:b("output")=h(i)
next:next:next%>
Meine Schleifen funktionieren ein wenig anders, ich suche nicht die größte Überlappung, sondern teste von 9 nach 1 runter (bißchen gepfuscht, 99 wäre besser gewesen) ob es eine solche Überlappung gibt. Dann werden diese Elemente verschmolzen. for c=-9to-1 statt for c=9 to 1 step -1 l<>i brauche ich, damit kein Element mit sich selbst verglichen wird. Ich habe zuerst das verschmolzene Element im Array auf "" gesetzt, brauchte dann aber eine zusätzliche Abfrage. Daher habe ich zum löschen einfach in das i-te Arrayfeld die Zahl i geschrieben (h(l)=l), so stören die gelöschten Werte nicht mehr. Da das Genom zum Schluß ein Ganzes ist, muß es in dem Feld mit der letzten Verschmelzung stehen, daher b("output")=h(i). Spart das Join. Bravo, die Handhabung der gelöschten Felder ist genial. Ein verdienter erster Platz! SchlußbemerkungBei ASP Golf lernt man immer wieder dazu. Selbst nach all den Turnieren die ich schon als Schiedsrichter betreut habe finde ich doch jedesmal wieder Code der mich staunen macht oder mir Tränen in die Augen treibt. Was wäre das Leben ohne Golf... 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 |
