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

Tee Off! Zahlen, Wörter, Zahlwörter

Geschrieben von: Bernhard Spuida
Kategorie: Tee Off

This printed page brought to you by AlphaSierraPapa

Die Zeit der Entzugserscheinungen ist vorbei! Wieder wurde ein spannendes Turnier ausgetragen. Es gab immerhin 79 Einsendungen mit einer Spannweite von 1578 bis zu 271 Schlägen. Wie man dem Leaderboard und dem Archiv der Golfliste entnehmen kann war der Kampf an der Spitze recht hart und spannend. Besonders freuen wir uns mit Yvonne Eichner die erste ASP-Golferin begrüssen zu dürfen! Es ist also an der Zeit endlich das vierte Turnier und seine überaus interessanten Lösungen vorzustellen.

Die Aufgabenstellung

Wie man von Schecks her kennt (nicht daß ich täglich Unmengen davon kriege) muß der Betrag in Zahlen und Worten darauf stehen. Das gehört natürlich kontrolliert!

Eine Zahl kleiner einer (deutschen) Billion (1.000.000.000.000) wird in englischen Zahlworten (um es leichter zu machen) angegeben und ist in Ziffern mit Tausendergruppierung umzuwandeln.

Zahlworte sind:

Billion 1.000.000.000
Million 1.000.000
Thousand 1.000
Hundred 100

und die Zahlen 1 - 99 auf Englisch. Das Wort 'and' kann vorkommen.

Beispiele

two hundred and fifteen -> 215
ninety billion two hundred thousand -> 90.000.200.000
three hundred twenty eight thousand five hundred and sixty seven -> 328.567

Die Zahl in Worten wird als String an Application("input") übergeben, die umgewandelte Zahl wird ebenfalls als String in Application("output") zurückgegeben. Ungültiger Input kommt nicht vor.

Das Leaderboard

1. Johann Engbers 271
1. Mischa Landwehr 271
3. Alexander Veit 276
4. Yvonne Eichner 307
5. Michael Schmidt 315
6. Stefan Mayer 321
7. Christian Rudig 353
8. Christian Marin 360
9. Claudius Ceteras 388
10. Michele Marsching 462
11. Ingo Höller 540

Im Bunker landeten diesmal Mansur Esmann und Stephan Weikert. Bis zum Turnierende fanden die beiden leider ihre Schäufelchen nicht.

Genug der Vorrede, auf zur Vorstellung einiger interessanter Lösungen.

Claudius Ceteras

Eine Lösung von Claudius, dem wir unseren Golftester zu verdanken haben. Wie man an dieser Lösung sieht, muß gutes Golf nicht viel Zeit kosten... Schade nur daß er die zweite vorgestellte Lösung nicht mehr einreichen konnte.

Mein Posting entstand eine Stunde bevor ich zur Uni musste unter Stress... Nur so ist es zu erklären, daß ich die FormatNumber-Funktion vergessen und selbst implementiert habe... *doh* :-)

Hier der Code....

<%Set a=application
b="Å¡OÂ§+ÃŽÃi`Â¾Ã¸Ã]LÃ€Â£Ã–ÂªqS Â¡ Â·Ãª@Ã†Â¨ l a"
for each w in split(a("input"))
y=0
for i=1to len(w):y=(y+(i+16)*asc(mid(w,i,1)))mod 256:next
p=instr(b,chr(y))
if p<20then
q=q+p
elseif p<28then
q=q+(p-18)*10
elseif p=28then
q=q*100
else
q=q*10^(3*(p-28))
x=x+q
q=0
end if
next
x=x+q
for i=0to 3
r=right(x,3)
x=int(x/1000)
s="."&r&s
if x=0then exit for
next
a("output")=mid(s,2)
%>

Der Algorithmus basiert wie Mischas Lösung auf einer Hash-Funktion, die alle vorkommenden Worte (and, one, two, ..., nineteen, twenty, thirty, ..., ninety, hundred, thousand, million, billion) auf eine unterschiedliche Zahl umrechnet... In der Variable b sind dann alle diese Zahlen (außer die fürs "and") als Zeichen mit entsprechendem ASCII-Wert gespeichert...

Dann kommt das wichtigste:

 if p<20then
  q=q+p
 elseif p<28then
  q=q+(p-18)*10
 elseif p=28then
  q=q*100
 else
  q=q*10^(3*(p-28))
  x=x+q
  q=0
 end if

Für die Positionen 1 bis 19 kann man die Zahl direkt übernehmen... Die nächsten Zahlen sind twenty, thirty, ..., ninety, also müssen sie nach Abzug von 18 mit 10 malgenommen werden... An Position 28 liegt "hundred"..., also wird alles vorher mit 100 multipliziert... Die restlichen Positionen beinhalten thousand, million, billion... Deshalb wird entsprechend multipliziert, aufsummiert in der Variable x und q auf null gesetzt für den nächsten Dreierblock... Die letzte For-Schleife tut die Arbeit von FormatNumber...

In der langweiligen Vorlesung dann... Ganz ohne Stress fiel mir natürlich sehr schnell eine kürzere Lösung mit nur 311 Bytes ein... *g*

<%Set a=application
for each w in split(a("input"))
y=0:for i=1to len(w):y=(y+(i+16)*asc(mid(w,i,1)))mod 256:next
p=instr("Å¡OÂ§+ÃŽÃi`Â¾Ã¸Ã]LÃ€Â£Ã–ÂªqS Â¡ Â·Ãª@Ã†Â¨ l a",chr(y))
if p<20then
q=q+p
elseif p<28then
q=q+(p-18)*10
elseif p=28then
q=q*100
else
q=q*1e3^(p-28)
x=x+q
q=0
end if
next
a("output")=FormatNumber(x+q,0)%>

Anmerkungen: was es nicht alles ausmacht, den Sprachumfang von ASP zu kennen... Andererseits sieht man mal wieder daß Unis zu was gut sind :-)

Stefan Mayer:

Was seine Beschreibung so interessant macht, ist daß er uns den gesamten Weg bis zu seiner respektablen Lösung zeigt:

Grundsätzlich vorweg - hier ein paar Worte zu meiner Lösung - bis zum Schluß entwickelte sie sich in 11 Versionen, wobei als neue Version von mir eine gröbere Änderung angenommen wurde.

Mein erster Ansatz war: www.google.at - suche nach "VB Text Zahl Umwandeln" - naja, vielleicht gibt's ja einen Befehl, der aus einem Zahlenwort eine Zahl macht. Tja - keine Treffer.

Ansatz 2 ging hin und hat aus dem Input ein Array gemacht; blank als Trennzeichen, wo jeder bekannte Text durch die Zahl ersetzt wurde. Anschließend habe ich überall wo "100" gestanden ist, den vorigen Arraywert mit 100 multipliziert und scheiterte an den Millionen, Billionen & co.

Nächster Versuch - bzw. die Idee: "Thousand" ist doch der Zahlenblock mal 1000. Also *10^3 plus dem nächsten Zahlenblock. Million selbiges ^6. Ich ersetzte also die Zahlen durch )*10^p+( wobei p wahlweise 3,6 oder 9 war.

In weiteren Versuchen wurde der Algorithmus zur Umwandlung in Zahlen immer mehr ausgefeilt - im Schnitt reichten mir 2 Buchstaben zur Ziffernerkennung.

Um das Ergebnis zu erhalten, verwendete ich die Eval-Funktion - sowie ein Join um das Array wieder zusammenzubauen und ein paar Replaces.

Das ist meine endgültige Lösung (mit Zeilenumbrüchen):

1: <%Set z=Application
2: u=z("Input")
3: for s=0to 10
4: u=replace(u,split("tho~wel~tee~ty~hu~m~b~ ~+*~#~$","~")(s),split("#3$
12 +10 *10 *100 #6$ #9$ + * +0)*10^ +(0")(s))
5: u=replace(u,split("one tw th fo fi x se ei ni ten el")(s),s+1)
6: next
7: for p=97to122:u=replace(u,chr(p),g):next
8: z("Output")=FormatNumber(eval("("&u&")"),0,,-1)%>

Und so funktioniert sie:
1: sollte schon aus früheren Wettkämpfen bekannt sein.
2: Ich arbeite mit dem kompletten String - kein Array mehr. Wozu auch!
3: 11 (0 to 10) ist das Ergebnis der Optimierungen und zwar werden in dieser Schleife zuerst "Sonderfälle", die leider etwas länger sind, ersetzt und in Zeile 5 die einfachen Fälle von 1 bis 11.
4: m --> Million --> #6$ wobei # später durch +0)*10^ ersetzt wird und $ durch +(0. tee ist der kürzeste String zur Erkennung von "-teen" - wo ich einfach ein "+10" hineinschreibe. ty ist zur Erkennung von "-ty" nicht viel kürzer, jedoch ein einfaches "*10". hu(ndred) multipliziert die vorangegangene Zahl mit 100. (t)wel(ve) war leider etwas kompliziert, weil twoteen leider nicht existiert oder oneteen
7: Ach ja, nun wird alles rausgeworfen, was man nicht mehr braucht. Sprich alle verbliebenen Buchstaben, ersetzt durch die Variable g weil g ist kürzer als "" - und solange g "" ist....
8: Und hier wird das, was von dem Ersetzten übergeblieben ist, mit () versehen und ausgerechnet. Anschließend mit FormatNumber mit Punkten versehen. 0 steht für keine Nachkommastellen, -1 für Tausendertrennpunkt.

Thats it.

Anmerkungen dazu: Schön gegolft! Weiter so, wir sind schon auf Deine Lösungen beim nächsten Turnier gespannt.

Mischa Landwehr

Nun zur ersten der beiden Lösungen die sich den ersten Platz mit 271 teilen:

<%Set a=Application
i=a("input")
For z=0To 26
i=Replace(i,Split("
1e1t1i1h1v1an1on1wo1wn1four1ff1f1sx1sn1g1nn1ln1wl1y1+un1o1m1b1n1+#1r",1)
(z ),Split("+       1 2 2 4 5 5 6 7 8 9 11 12 0 00+ #3+( #6+( #9+( +10
)*1e 3")(z)) Next a("output")=FormatNumber(Eval("("&i&")"),0)%>

Um das Problem zu lösen, habe ich die übergebenen Wörter in einen mathematischen Ausdruck umgewandelt. "one hundred and thirty seven thousand ninety one" kann man z. B. durch "(1*100+3*10+7)*1e3+(9*10+1)" ausdrücken. Das muss man nur mit der Funktion Eval ausführen lassen und anschließend formatieren.

Dazu habe ich zwei Arrays erzeugt, in denen festgelegt wurde, was ersetzt werden muss. Anfangs sah das so aus:

"one two three four five six seven eight nine ten eleven twelve thir
teen een fif twen ty y hundred thousand million billion and"
"+1 +2 +3 +4 +5 +6 +7 +8 +9 +10 +11 +12 +3 +10 +10 +5 +2 0 0 *100
)*1e3+( )*1e6+( )*1e9+( +0"

Nun ging es ja darum, es möglichst klein zu bekommen und so habe ich erst einmal alle unnötigen Zeichen (e, t, i, h und v) gelöscht bzw. durch ein "" ersetzt - und das " " noch durch ein "+".

Wenn man sich die Sache genauer anschaut, so merkt man, daß man außerdem nicht alle Buchstaben ersetzen muß. Z.b. könnte man "housand" stehen lassen. Im obrigen Beispiel wäre damit "(1*100+3*10+7)*1e3+(housand+9*10+1)" raus gekommen. Das geht, da "housand" als Variable aufgefasst wird, und so lange es diese nicht gibt, gibt es auch keinen Fehler.

Mit beiden Optimierungen - häufige Zeichen löschen und unnötige stehen lassen - wurde daraus folgendes:

" 1e1t1i1h1v1an1on1wo1wn1four1ff1f1sx1sn1g1nn1ln1wl1y1+un1o1m1b1n1+#1r" "+
      1 2 2 4 5 5 6 7 8 9 11 12 0 00+ #3+( #6+( #9+( +10 )*1e 3"

Da ich auch das " " ersetzen wollte, musste ich beim ersten String ein Trennzeichen wählen. Die 1 schien mir dafür ideal, da ich sie als Integer an die Split-Funktion übergeben konnte. "1" wären zwei Zeichen mehr gewesen. Anmerken möchte ich noch, daß die 1 als Trennzeichen im Nachhinein eine dumme Idee war, da man sie zu leicht mit einem l verwechselt. Eine 0 wäre deutlich besser gewesen.

Anmerkung: Der Ansatz ist ähnlich dem oben gezeigten von Stefan, aber diese Eleganz, diese Reduktion auf das wesentliche! Sehr schön.

Johann Engbers

Komplett anders als die Lösung von Mischa, aber trotzdem gleich lang bzw. kurz:

1: set b=application
2: for each k in split(b("input"))
3: o=0:for i=1to 9:o=o+asc(right(k,i))*i:next
4: j=instr(".z~nW.HE(o.—.‡2[SwM..Ojq1B#;m“*.",chr(o mod 153))-4
5: if j>21then j=10*j-190
6: if j<0then h=h+1e3^-j*l:j=-l
7: if j=21then j=l*99
8: l=l+j
9: next
10: b("output")=formatnumber(h+l,0)

1: bekannt
2: jedes Zahlwort der Liste wird einzeln verarbeitet
3: damit berechne ich einen Hashwert, jedes Zahlwort wurde vorher mit dieser Funktion kodiert, da ja nur korrekte Lösungen vorkommen ist das möglich.
4: der Platz im String gibt den Wert des Zahlwortes wieder. Die -4 verkürzt noch mal die späteren Abfragen
5: die Plätze 22..28 sind für die 10er-Zahlen thirty, fourty, ... ninety reserviert. Z.B. 22 bedeutet 10*22-190=30 die addiert werden sollen. Daß dieser Wert in j wieder gespeichert wird spart ein paar Bytes in Zusammenhang mit Zeile 8, eigentlich müsste es heißen: l=l+10*j-190
6: -3,-2,-1 bedeuten billion, million, thousand. Z.b. -3 ergibt 1e3^3 also eine Milliarde. In l ist die Anzahl der Milliarden gespeichert, die schon vorher berechet werden musste. j=-l ist eine umständliche Schreibweise für l=0
7: an 21er Stelle steht die Hundert, daher müsste ich jetzt l=l*100 berechnen, aber mit j=l*99 und der 8.Zeile lässt sich noch ein Byte sparen
8: wenn kein Sonderfall aufgetreten ist, entspricht die Position des Zahlwortes seinem Wert (1..20) und kann einfach addiert werden, 'and' hat den Wert 0
10: zum Schluß noch die Ausgabe mit FormatNumber.

Anmerkungen dazu: Ebenfalls sehr schön - ein Beweis dafür daß auch im ASP-Golf verschiedene Weg zum Green führen. Interessant sind bei diesem Turnier vor allem die vielen alternativen Ansätze zum Sparen von Zeichen in der Kodierung der Zahlwörter.

Schlußbemerkung

So, liebe Golffreunde, das war's wieder einmal vom Golfplatz. Schalten sie sich wieder ein wenn sie das nächste Mal 'Fore!' hören.