Geschrieben von: Christoph Wille
Kategorie: Tee Off
This printed page brought to you by AlphaSierraPapa
Die Entzugserscheinungen in den Golf-losen Tagen scheinen mit jedem Turnier immer schlimmer zu werden, was sich während des Golfens dann etwa so manifestiert: "Neulich bei Vera am Mittag - Thema: Hilf mir, Vera, mein Mann spielt ASP Golf...". Aber zurück zum Turnier des Monats November: es galt den zentralen Teil einer erfolgreichen Weltuntergangsmaschine - den Countdownzähler - einer rigiden Qualitätskontrolle zu unterziehen!
Insgesamt wurden 137 Lösungsvorschläge eingereicht, was dazu führte, daß die Golflehrer sich des öfteren im dichten Ballhagel ducken mußten um von den tieffliegenden Bällen nicht getroffen zu werden. Bevor wir auf die Aufgabenstellung und einige (sehr interessante) Lösungen näher eingehen, hier das Leaderboard nach Beendigung des Turniers:
Erfreulicherweise ist der Bunker trotz hoher Beteiligung am Ende leer gewesen, allerdings werden wir durch starke Benützung von Roman etwas Sand nachfüllen müssen. Der Tortoise Award (Preis für die langsamste eingereichte Lösung) geht an Alexander Veit.
Die Firma Villainsupply ist der weltgrößte Lieferant für Weltuntergangsmaschinen ('doomsday devices' im Shop). An die Qualität derartiger Geräte werden extreme Anforderungen gestellt, schließlich müßen sie zuverlässig funktionieren damit sie der Held zwei Sekunden vor Ablauf des Countdowns entschärfen kann. Ein zentraler Teil einer erfolgreichen Weltuntergangsmaschine ist daher der Countdownzähler! Unsere Aufgabe hat daher mit der Kontrolle von Zählerdisplays zu tun - nichts ist ärgerlicher als ein defektes Display wenn es um den Weltuntergang geht.
Die zu testenden Displays sind zweistellige 7-Segment LEDs, die wie folgt adressiert werden:
A H === === D| B |F K| I |M === === E| C |G L| J |N === ===
Der Countdown läuft hexadezimal von FF bis 00. Die Zustände der Segmente werden am Teststand von einem Bilderkennungssystem mit 0 und 1 wie folgt codiert:
Segment: A B C D E F G H I J K L M N
Display 00 1 0 1 1 1 1 1 1 0 1 1 1 1 1
01 1 0 1 1 1 1 1 0 0 0 0 0 1 1
...
FF 1 1 0 1 1 0 0 1 1 0 1 1 0 0
Alle einzelnen Ziffern im Überblick:
0: 1011111 1: 0000011 2: 1110110 3: 1110011 4: 0101011 5: 1111001 6: 1111101 7: 1000011 8: 1111111 9: 1111011 A: 1110111 B: 0111101 C: 1011100 D: 0110111 E: 1111100 F: 1101100
Unser Programm bekommt eine Sequenz aus fünf Zahlen übergeben, die einer Sequenz aus dem Countdown entsprechen müssen. Z.B. FF, FE, FD, FC, FB oder 23, 22, 21, 20, 19. Trifft dies nicht zu weil eine Zahl fehlt, oder Anzeigesegmente ungültige Zustände aufweisen, muß das Display ausgesondert werden - wir wollen ja einen erfolgreichen Weltuntergang! Beispiel:
11110111111011 11110111111111 11110111000011 11110111111101 11110111111001 ergibt OK 10000110000011 10000111011111 11111011111011 11111010111111 11111011000011 ergibt FAIL
Die Sequenzen werden wie üblich als Array aus Strings übergeben:
Application("input")=Array("10000110000011","10000111011111"....)
Das Ergebnis wird als String an Application("output") zurückgegeben der entweder "OK" oder "FAIL" beinhaltet.
Beginnen wir mit der Lösung von Mischa, der siegreich aus dem Turnier hervorgegangen ist. Die Beschreibungen sind wie immer O-Ton der Golfer vom Post Mortem an der Bar im Clubhaus:
<%Set a=Application
For b=0To 3583
u=Asc(Mid("_.vs+y}C{w=\7|l",b\14\16^(b\7Mod 2)Mod 16+1))\2^(b Mod 7)Mod
2&u
Next
o="FAIL"
If InStr(u,Join(a("input"),""))Mod 14=1Then o="OK"
a("output")=o%>
Die Kernidee ist einigen anderen Lösungen recht ähnlich: Zuerst generiere ich den gesamten Countdown als Binärzahlen im String u und überprüfe, ob der übergebene Countdownausschnitt in diesem - an einer korrekten Position - zu finden ist. Zwar hätte es bei der vorgegeben Test-Umgebung gereicht, daß man nur auf Existenz prüft (und noch acht Bytes gespart). Da es durchaus Werte geben kann, die zwar vorkommen, aber nicht korrekt sind, ist die gewählte Lösung sauberer.
Aus Platzgründen wurde eine einzige Schleife über die Anzahl aller Bits gewählt - also b=0 To 3583. Die 16 gültigen Zeichen wurden als Zeichenkette abgelegt und müssen somit erst in Binärzahlen umgewandelt werden: Asc(..)\2^(b Mod 7)Mod 2
Da die Anzeige zweistellig ist, müssen für jeden dargestellten Wert zwei Zeichen umgewandelt werden, also ein höherwertiges und ein niederwertiges Zeichen: b\224+1 bzw. b\14 Mod 16+1. Das ließe sich aber auch elegant und kurz zusammenfassen: b\14\16^(b\7Mod 2)Mod 16+1.
Das Script wurde im Mac-Format abgespeichert. Dieses verwendet ähnlich Unix nur ein Zeichen am Zeilenende.
Set a=Application
x="OK"
for z=0To 4
for p=0To 1
j=0
For i=1To 7
j=j+Mid(a("input")(z),i+p*7,1)*2^i
Next
y=InStr("úÀnÎÔz¾ÂþÞî¼:ì>6",Chr(j))+y*16*p
next
if z*(y-l+1)then x="FAIL"
l=y
Next
a("output")=x
Set a=Application, was sonst ;)
for p=0To 1
p gibt den Durchgang an. Wenn p 0 ist, werden die ersten 7 Ziffern ausgewertet, danach die 2.
For i=1To 7
j=j+Mid(a("input")(z),i+p*7,1)*2^i
Next
Hier wird die ASCII-Zahl ausgerechnet, die die Bytefolge darstellt. p ist einmal 0 und dann 1, um aus den 14 Stellen zwei Teilstrings mit je 7 Zeichen zu machen, wobei die Umrechnung selbst in umgekehrter Richtung und mit vorangestellter 0 vonstatten geht. (aus 1100000 wird [praktisch] 01100000 und ist damit 6). j liegt damit im Bereich von 0 bis 255 (And Not 1 *g*).
y=InStr("úÀnÎÔz¾ÂþÞî¼:ì>6",Chr(j))+y*16*p
"úÀnÎÔz¾ÂþÞî¼:ì>6" kennt man nun ja auch schon fast. Das sind die Zahlen in ASCII-Format. Die Reihenfolge in der die Ziffern vorkommen ist von der darzustellenden 0 bis zu F aufgeführt. Nun wird die Position des ASCII-Zeichens j innerhalb meiner Prüfzeichenfolge abgefragt. Beim ersten Durchgang (p=0) wird das, was zuletzt in y Stand *0 genommen und dazugezählt (erspart y=0). Wenn p=1, dann wird die zuletzt berechnete Position *16 genommen und die aktuelle dazugezählt (damit die beiden sich nicht stören*g*). Die maximale Zahl liegt also bei 16+16^2.
if z*(y-l+1)then x="FAIL" l=y
Nachdem nun beide Positionen zusammengezählt wurden, muß noch überprüft werden, ob diese auch hintereinander liegen. l wird erst ab dem 2 Eintrag im Array gesetzt. Daher (und weil's auch gar nichts bringen würde) kann die erste Zahl nicht so geprüft werden. Ab dem 2. Durchgang muß y-l+1 0 sein, ansonsten liegt's außerhalb der Reihe. z ist beim ersten Eintrag 0. Daher ist am Anfang jede Zahl gültig. (Wenn diese eigentlich ungültig wäre, wird dies bei den weiteren Durchläufen ersichtlich)
Es tut mir leid, daß ich dieser super Aufgabe nicht die Zeit widmen konnte wie ich wollte und sollte :-). Deswegen mehr eine Notlösung....
<%Set a=application
o="FAIL"
d="6>ì:¼îÞþ¾žÃ”ÃŽnÀú"
for i=1to 16
for k=1to 16
for j=1to 14
x=x&sgn(asc(mid(d,i,1))+asc(mid(d,k,1))*128 and 2^j)
next
x=x&" "
next
next
if instr(x,join(a("input")))>0then o="OK"
a("output")=o%>
Alle 255 Werte der richtigen Reihenfolge aufbauen und am Schluß schauen ob sich die Sequence auch in dem String befindet - wenn ja, dann ist alles oki ;-)
Besonderheiten
6>ì:¼îÞþ¾žÃ”ÃŽnÀú
Das sind die Werte der Anzeige in Kurzfassung für 054 062 236 058 188 238 222 254 194 190 158 212 206 110 192 250 1101100 ... also immer erste Stelle 2 4 8 16 32 64 ... aber das kennt ihr ja fast außer daß es normalerweise mit 1 anfängt ...
Diese Zeile gefällt mir noch:
for j=1to 14 sgn(asc(mid(d,i,1))+asc(mid(d,k,1))*128 and 2^j) next
Damit wird die Integerzahl in die Binärzahl konvertiert.
<%set a=Application
b=split("1101100 1111100 0110111 1011100 0111101 1110111 1111011 1111111
1000011 1111101 1111001 0101011 1110011 1110110 0000011 1011111")
for i=0to 15:for j=0to 15
c=c&b(i)&b(j)
next:next
if instr(c,join(a("input"),x))then o="OK"else o="FAIL"
a("output")=o%>
Relativ straight-forward...
Danke für das spannende Golf. Wir freuen uns schon auf das nächste Loch. Happy Golfing und bis am nächsten Abschlag!
This printed page brought to you by AlphaSierraPapa
Tee Off - Das erste ASP Golf Turnier
http:/www.aspheute.com/artikel/20020930.htm
Tee Off! Die Zweite
http:/www.aspheute.com/artikel/20021104.htm
Tee Off! Wolpertinger Genome Project
http:/www.aspheute.com/artikel/20031222.htm
Tee Off! Zahlen, Wörter, Zahlwörter
http:/www.aspheute.com/artikel/20030115.htm
ASP Golfplatz
http://www.aspgerman.com/golf/
©2000-2006 AspHeute.com
Alle Rechte vorbehalten. Der Inhalt dieser Seiten ist urheberrechtlich geschützt.
Eine Übernahme von Texten (auch nur auszugsweise) oder Graphiken bedarf unserer schriftlichen Zustimmung.