Golf.NET - Maya Zahlen
Eines vorweg:
Do not do this at home - or at all!
Bei .NET Golf geht es darum, eine bestimmte Aufgabe mit der geringsten Anzahl an Schlägen - in dem Fall Zeichen zu lösen.
In diesem Fall bestand die Aufgabe daraus, die Zahlen des uralten Mayavolkes in unser heutiges Dezimalsystem zu überführen.
Auszug aus der Aufgabenstellung:
Das Zahlensystem der Mayas und Azteken beruht auf einer Zwanzigerbasis - offensichtlich wurde mit Fingern und Zehen gezählt. Die Zahlzeichen sind:
- . steht für 1 Stein
- : steht für 2 Steine
- | steht für 5 Steine (oder einen Stock, da streiten die Archäologen noch)
- - steht für eine Muschel, die Null symbolisiert.
.:| .:||| ::| ::|| . ergibt die 1427881, folgendermassen berechnet:
20**4*(3+5) + 20**3*(3+15) + 20**2*(4+5) + 20**1*(4+10) + 20**0*(1)
= 1280000 + 144000 + 3600 + 280 + 1
= 1427881
Dafür galt es dann, eben diese Konvertierung mittels C# oder VB.NET zu lösen und dazu wie oben beschrieben möglichst wenig Zeichen zu verbrauchen.
Herausgekommen sind dann in chronologischer Reihenfolge und nach (zu) vielen Stunden die folgenden Lösungen:
1 // Z = mayazahl
2 // r = result
3 // p = power
4 // t = temp
5 // i = iterator
6
7 public class Tee
8 {
9 public int Off(string Z)
10 {
11 int r,p,t,i;
12 r=t=0;
13 p=1;
14 for(i=Z.Length-1;i>=0;i--)
15 {
16 t+=Z[i]=='.'?1:0;
17 t+=Z[i]==':'?2:0;
18 t+=Z[i]=='|'?5:0;
19 t=Z[i]=='-'?0:t;
20 if (Z[i]==' ')
21 {
22 r+=t*p;
23 p*=20;
24 t=0;
25 }
26 }
27 r+=t*p;
28
29 return r;
30 }
31 }
Es gab eine Klasse Tee und die Methode Off die die Maya Zahl als String empfängt. Der Rückgabewert der Methode ist eben die Konvertierte Dezimalzahl.
Diese Lösung ging in einer Schleife alle Zeichen der Maya Zahl durch und addierte die entsprechende Zahl. Diese Lösung hatte jedoch bis auf kurze Variablenbezeichnungen noch wenig Optimierung erfahren.
Die nächste Lösung war dann schon etwas ausgereifter:
1 public class Tee
2 {
3 public int Off(string Z)
4 {
5 int r,p,i;
6 r=0;
7 p=1;
8 for(i=Z.Length;i>0;)
9 {
10 r+=Z[--i]=='.'?1*p:Z[i]==':'?2*p:Z[i]=='|'?5*p:0;
11 if(Z[i]==' ')p*=20;
12 }
13 return r;
14 }
15 }
Sie nutzte geschickter die Möglichkeit des Zugriffs über den Index und addierte in Zeile 10 die korrekte Zahl bereits in nur einer Zeile.
In Zeile 11 wurde dann nur noch die Zahl mit 20 Multipliziert und so eine Stelle in der Maya Zahl weiter nach links gerückt. In der Dezimalen Denkweise würde dies bei der Zahl 154 nach der Zahl Vier den gedachten Punkt auf die Zahl 5 weiterrücken (dann natürlich durch eine Multiplikation mit 10).
Aber auch hier ist noch jede Menge zu optimieren:
1 public class Tee
2 {
3 public int Off(string Z)
4 {
5 int p,i,z,r=0;
6 p=z=1;
7 for(i=Z.Length;i>0;r+=((z=Z[--i])>99?5:z>57?2:z>45?1:z<33?(p*=20)-p:0)*p);
8 return r;
9 }
10 }
Ab diesem Beispiel fängt es dann an richtig "pervers" zu werden. Jetzt befindet sich die komplette for - Schleife hmm... es ist eigentlich keine Schleife mehr - es befindet sich die komplette Logik der Addition und der Abfragen direkt im Kopf der nicht-for-Schleife.
Der Größte Speicherspareffekt trat aber durch folgenden Trick auf:
Man kann mittels for bzw. foreach Schleife einen String durchlaufen. Dabei wird - wie zu erwarten - jeder Buchstabe als ein Characterzeichen zurückgeliefert. Und genau das wird hier überprüft. Zugewiesen wird der Charcter mit z=Z[--i]. Der dahinterliegende Bereich prüft jetzt durch geschicktes größer/kleiner Testen, was genau addiert werden soll.
Aber auch das ist noch nicht das Ende der Fahnenstange:
1 public class Tee
2 {
3 public int Off(string Z)
4 {
5 int i=Z.Length,p=1,r=0;
6 for(;i>0;r+=(Z[--i]>33?(Z[i]^56)%7:(p*=20)-p)*p);
7 return r;
8 }
9 }
Jetzt galt es noch diese doch noch zu vielen größer/kleiner Abfragen zu eleminieren. Dazu habe ich mir dann ein seperates Testprogramm zur Findung eines Algorythmus geschrieben. Also ein Programm, welches einen Eingangswert mit möglichst kurzen C# Konstrukten in beliebige Ausgabewerte konvertiert. Wenn dabei mehr als 2 Werte gute Ergebnisse geliefert haben (das kam insgesammt bei zweien vor) habe ich diesen Algorythmus gewählt.
Heraus kam dann das obige Konstrukt, welches mir dann auch prompt den Ersten Platz brachte (okok - da waren noch 7!!! andere die sich den Platz mit mir teilten).
Hat jedenfalls jede Menge Spaß gemacht, auch wenn ich nicht an allen Turnieren teilgenommen habe (meist mangels Zeit...):
http://codefairway.net/de/solvedholes.aspx?action=leaderboard&hole=15
P.S. An dieser Stelle dann auch noch herzlichen Dank für das Ausrichten des Turniers und an alle die mitgemacht haben!