Das Solitaire Encryption Golfturnier war eine Challenge unter den Ägiden von Microsoft Österreich, unser Codefairway diente als bewährter Austragungsort für diesen MSDN Contest. Die Regeln und das finale Leaderboard sind ebendort nachzulesen - hier in diesem Blogpost sind die Post Mortems der Winning Entries zusammengetragen.
Die Post Mortems sind wie immer von den Golfern selbst verfasst, und werden hier ungekürzt und ungeschminkt nachgedruckt. Den optimierten Code kann man als angemeldeter Golfer im Leaderboard nachlesen (auch wenn's ohne diese Erklärungen nicht viel helfen wird <g />).
Platz 3, Claudia Krolopp
Spät, aber doch ...
Im Gegensatz zu Franz bin ich absolut nicht der Meinung, dass das was hier verbrochen wurde selbsterklärend sein soll. Ich hab schon Probleme meine eigene Code-Zeile zu durchblicken.
Aber ich versuchs mal:
Bei mir muss als Kartenstapel kein string sondern ein int array herhalten.
Der Stapel wird mit 1 beginnend initialisiert, die beiden Joker erhalten beide den Wert 53 (an irgendeiner Stelle im Algorithmus muss für beide der gleiche Wert verwendet werden).
Heisst allerdings auch, dass die Position der Joker immer bekannt sein muss, deshalb werden bei jeder Veränderung im Stapel die Indices beider Joker (x und y) mitgezogen.
Sämtliche Verschiebungen werden in einer einzigen Funktion M( int j, int k ) durchgeführt, wobei immer die ersten j Karten k mal um 1 nach hinten geschoben werden. k wird returniert und wiederverwertet.
Sieht dann z.B. beim Verschieben einer Karte um 1 nach hinten so aus:
x=4;
1234x5678y90
M(x,x);
x12345678y90
M(1,k%53+1);
12345x678y90
Mit k%53+1 funktioniert auch das Verschieben der letzten Karte reibungslos.
using S=System.String;
public class Tee
{
// In "r" landet der verschlüsselte string, in "s" der key und
// "o" wird mit dem Alphabet in Grossbuchstaben initialisiert.
S r,s,o;
// Jede Menge Hilfsvariablen und das Kartendeck "a".
int i,t,v,x,y,l,p,q;
int[]a=new int[54];
// Hier werden j Karten k mal verschoben
// in "x" und "y" werden die Positionen der Joker aktualisiert
int M(int j,int k)
{
for(;j-->0;y+=y<1?k:y>k?0:-1,x+=x<1?k:x>k?0:-1)
for(t=a[i=0];i<k;a[i]=t)
a[i++]=a[i];
return ++v>5?k:v%2>0?M(1,k%53+1):M(y,y);
}
// GenerateKeyStream generiert nicht nur den KeyStream sondern
// auch gleich die verschlüsselte Nachricht
public S GenerateKeyStream(S P,S m)
{
// Bei der Initialisierung wird gleichzeitig "P" mit Ziffern angefüllt.
// Damit ist es möglich beide Teile des Algorithmus, also über den ganzen
// string "P" und bis die benötigte KeyStream-Länge erreicht ist, in
// einer einzigen Schleife abzuarbeiten.
for(y=l=p=0;y<53;P+=a[x=y]=a[++y]=y)
o+=(char)(y%26+65);
// Und hier wird nun endlich der ganze Algorithmus aufgerufen.
// Der momentane Buchstabe in "P" wird auf Kartendeckwert runter-
// gerechnet und in "q" gespeichert.
// War es ein Grossbuchstabe, dann ist q > 0 und die strings werden
// nicht verändert.
// War es eine der angehängten Ziffern, dann sind wird durch "P"
// durch und können anfangen die strings zu basteln.
// Wenn die Nachricht vieeeel länger als das passwort ist, kann es
// allerdings sein, dass die angehängten Ziffern mengenmässig nicht
// reichen (war bei mir anfangs der Fall) - dann kann "P" auch direkt
// im if verlängert werden - kostet allerdings noch ein Byte extra
// und wenns dem Tester so genügt ...
for(r=s="";l<m.Length;)
if(M(q=P[p++]-64,M(a[M(M(x<M(x,x)?x:y,x>y?x:y)+1,53)],52))>(i=a[a[v=0]]-1)&q<1)
{
s+=o[i];
r+=o[m[l++]-64+i%26];
}
// Ab jetzt isses wirklich selbsterklärend.
r
eturn s;
}
public S EncryptData(S m,S k)
{
return r;
}
}
Platz 2, Franz Polzer
Eigentlich ist der Code sowieso selbsterklaerend :)
c Kartendeck
d Keystream
e Encrypted Message
f lookup Table um (char) typecast und Offset von 'A' zu sparen
i Startposition des zu verschiebenden Bereichs
z Zielposition des zu verschiebenden Bereichs
using S=System.String;
public class Tee
{
S c,d,e,f;
int i,z;
char j,u,l='A',a,b='5';
public S GenerateKeyStream(S p,S m)
{
// Initialisieren des Kartendecks und der Lookup-Table
for(;a<54;c+=++a)f+=l++;
// Solange bis die Message encrypted ist
for(;u<m.Length;)
{
// Move der beiden Joker
for(l=b;l<=a;M(1))
z=((i=c.IndexOf(l))+l++)%b+1;
// Triple Cut
S[]k=c.Split(b,a);
c=k[2]+c.Trim((k[0]+k[2]).ToCharArray())+k[i=0];
// Countcut mit letztem Zeichen
z=52;
M(c[b]);
try
{
// Countcut mit Passphrase solange noch
// ein Zeichen da ist.
// Sonst -> Exception
M(p[j++]%64);
}
catch
{
// Auslesen des Zeichens fuer Keystream
// und erzeugen der encrypted Message
if(b>(i=c[c[0]>b?b:c[0]]))
e+=f[(m[u]+(d+=f[--i%26])[u++]+1)%26];
}
}
// Keystream zurueckgeben
return d;
}
public S EncryptData(S m,S p)
{
// Einfach die vorher berechnete Message zurueckgeben
return e;
}
void M(int y)
{
// verschieben von y Zeichen von i nach z
c=c.Remove(i,y).Insert(z<i?z:z-y+1,c.Substring(i,y));
}
}
So, das war's eigentlich schon!
Platz 1, Thomas Gatterweh
/*
Die Idee.
Alle Veränderungen im Kartenstapel können durch eine Funktion ausgedrückt werden: Das Verschieben einer oder mehrerer Karten an eine andere Position im Stapel. Es müssen nur mehr die jeweiligen Start-, End- und Zielpositionen berechnet werden. J
Die Joker.
Um ein Zeichen (";") zu sparen, wird die erste Jokerverschiebung nicht als erstes in der Schleife gemacht, sondern als letztes (im "for"). Das ist insofern möglich, da diese erste Jokerverschiebung im allerersten Durchlauf lediglich die beiden Joker vertauscht. (Der Stapel ist ja frisch aufgebaut.) Damit kann ich diese Vertauschung weglassen, und muss jetzt nur die Bedeutung von Joker #1 und #2 vertauschen. Deshalb hat Joker #1 den Wert 54 ("6") und Joker #2 den Wert 53 ("5").
Das Green.
Es lässt sich folgendes herausfinden:
a) Die Klasse "Tee" wird jeweils nur zum Verschlüsseln einer einzigen Nachricht benutzt. ==> Ich verwende soweit wie möglich die Defaultinitialisierung von Klassenelementen, z.B. int wird als 0 initialisiert.
b) "GenerateKeyStream" und "EncryptData" wird immer 'korrekt' paarweise benutzt. ==> Die Nachricht kann schon in "GenerateKeyStream" verschlüsselt werden. Die Parameter von "EncryptData" setzte ich einfach als korrekt voraus.
*/
using S = System.String;
public class Tee
{
/*
"a" enthält in den ersten 54 Zeichen den Kartenstapel; der Rest bis Zeichen 90="Z" wird zum Wandeln einer Zahl in ein Zeichen verwendet.
"k" ist der KeyStream.
"e" ist die verschlüsselte Nachricht.
*/
S a, k, e;
/*
"i" ist die Position des Jokers #1, "j" die des Jokers #2. "j" wird gleich am Anfang gebraucht und muss initialisiert werden.
*/
int h, i, j = 52, l, n;
/*
"x" enthält a) das Zeichen des Jokers #2 (siehe oben) und auch b) 53, d.h., 1-Anzahl der Karten.
"y" enthält in der Hauptschleife a) das Zeichen des Jokers #1 und auch b) 54, d.h., die Anzahl der Karten.
Zuerst wird "y" allerdings zum Initialisieren von "a" verwendet. Der Defaultwert von 0 passt dafür hervorragend.
*/
char x = '5', y;
/*
"EncryptData" liefert nur mehr die bereits generierte verschlüsselt Nachricht zurück. */
public S EncryptData( S m, S k )
{
return e;
}
/*
"C" verschiebt einen Kartenstapel, gegeben durch die Position "s" der ersten Karte und "e" der letzten Karte (exklusiv), an die Position "z".
Ist "s" größer oder gleich "e", wird nichts verschoben.
"i" und "j" wird mit der neuen Position des 1. und 2. Jokers aktualisiert.
*/
void C( int s, int e, int z )
{
a = a.Remove( s, e -= s < e ? s : e ).Insert( z, a.Substring( s, e ));
i = a.IndexOf( y );
j = a.IndexOf( x );
}
/*
"GenerateKeyStream" verschlüsselt auch noch gleich die Nachricht und hebt sich das Ergebnis für "EncryptData" auf.
*/
public S GenerateKeyStream( S p, S m )
{
// Ein Kartenstapel muss her...
for( ; y < 90; )
a += ++y;
// Jetzt noch schnell "y" initialisiert, und dann kann es losgehen bis alle Zeichen da sind...
for( y = '6'; n < m.Length; C( i, 1 + i, i % x + 1 ))
{
// Jokerverschiebung (am Ende des "for" für Joker #1, bzw hier für Joker #2)
// Von alter Jokerposition eine Karte an die neue Position verschieben.
C( j, ++j, j % x + 1 );
// TripleCut in zwei Schritten...
// Wo ist der vordere Joker?
h = i < j ? i : j;
// 1. Schritt: Die Karten von der Karte nach dem hinteren Joker (wenn "h" der vordere ist, dann ist "i+j-h" der hintere!) bis zum Ende an die Position vor dem vorderen Joker verschieben.
C( i + j - h + 1, y, h );
// 2. Schritt: Die Karten vom Anfang bis zum (ursprünglichen) vorderen Joker ans Ende verschieben.
C( 0, h, y - h );
// CountCut gemäßder letzten Karte
// Invers zur Beschreibung: Ich verschiebe nicht die N ersten Karten unmittelbar vor die letzte Karte, sondern verschiebe die Karten von der N-ten bis zur vorletzten an den Anfang.
C( a[ x ], x, 0 );
try
{
// CountCut nach dem nächsten Zeichen in der PassPhrase. Gibt's dort keines (mehr), geht's per Ausnahme zur Ausgabe...
C( p[ l++ ] - 64, x, 0 );
}
catch
{
// Ausgabekarte holen, und wenn kein Joker...
h = a[ a[ 0 ] < x ? a[ 0 ] : x ];
if( h < x )
{
// ...dann Message verschlüsseln...
e += a[( h + 13 + m[ n++ ]) % 26 + 64 ];
// ...und KeyStream erzeugen.
k += a[ --h % 26 + 64 ];
// Beide Male wird der unverändert bleibende Teil des Kartenstapels (alles außer den ersten 54 Zeichen) zum Umwandeln des Kartenwertes in ein Zeichen verwendet.
}
}
}
return k;
}
}