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);
    }

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);

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];
             }

        return 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;
         }
}