Plagiate in (Java) Quellcode finden

fadingLeider scheint bis jetzt niemand eine wirklich freie, gute und lokale Code-Plagiats-Applikation entwickelt zu haben. Ich wäre sehr gespannt, was AST-Vergleiche bringen würden. Nundenn, ein erster und unaufwändiger Vergleich von Quellcode (und bei Programmierprüfungen eventuell mit alten Lösungen) kann schon vieles zeigen. Die einfachste Variante, die ich bis jetzt gefunden habe, ist der CPD copy-paste-detector, der Teil des PMD-Packages ist.

Der CPD braucht nicht installiert zu werden: Herunterladen, entpacken und den Pfad bei den Einstellungen in Control Panel\System and Security\System\Advanced system SettingsAdvancedEnvironmentVariables setzen.

Pfad Setzen in Windows

Pfad Setzen in Windows

Danach eine Kommandozeile öffnen den Computer um Folgendes bitten:

cpd --encoding utf8 --minimum-tokens 200 --files E:\Pruefungen\IB13a\VMKN-226\files > similarities.txt

Das kann auch auf eine Sprache eigegrenzt werden:

cpd --language java --encoding utf8 --minimum-tokens 200 --files E:\Pruefungen\IB13a\VMKN-226\files > similarities.txt

Nun stehen in der Datei similarities.txt die Teile der Dateien, die gleich sind. Weitere Optionen können auf der CPD-Page gefunden werden.

Website mit Java-Programmieraufgaben, die automatisch korrigiert werden

batUnd es gibt sie: Die Perlen im Web. Man surft sich einfach so die Zeit weg, weil die Arbeit lauert und nur darauf wartet zuzupacken und versucht verzweifelt das schlechte Gewissen wegzusurfen und dann trifft einem der Hammer und eine Rechtfertigung für das Prokastrinieren: JavaBat. JavaBat ist undesigned, sehr technisch, aber einfach genial um Java zu lernen.

Auf JavaBat gibt es Programmieraufgaben zu verschiedenen Themen. Die Lösung wird als Java-Quellcode eingereicht, auf dem Server compiliert, ausgeführt und mittels Unit-Tests korrigiert. Eine geniale Idee: Schlicht und ergreifend und mit dem Potential süchtig zu machen. Zusätzlich besteht die Möglichkeit, einen „Teacher“ anzugeben, dieser kann dann die Fortschritte beobachten.

Diese Aufgabe wurde gelöst

Diese Aufgabe wurde gelöst

Aber wie machen die denn das? Wie bewahren sie sich davor, dass ich ihnen mit den Dateioperationen den Server überschreibe? Es wäre doch wunderbar, wenn man dieses Prinzip auch für andere Programmiersprachen anwenden könnte… Es scheint so, dass es bei Java sehr einfach ist: JavaBat verbietet Import-Statements, oder es kann über die JVM-Security-Policies gelöst werden (sagen sie bei Stackoverflow). Eine generellere Herangensweise zeigt Geordi: Hier werden die System-Calls geblockt. Mal sehen, wie sich das zum Nutzen Aller verwenden lässt…

Der Avaloqix Spielagent

Juhuu! Mein Spieler hat sich anscheinend gut geschlagen und ich wurde an den Battleday von Avaloq eingeladen! An diesem Datum werden die programmierten Spieler in einem spassigen Turniermodus gegeneinander antreten. Noch mehr freue ich mich auf die Präsentationen der anderen Mannschaften und auf die Leute. Ich kann mir da sehr spannende Begegnungen, Gespräche und Kontakte vorstellen. Ich werde mit Photoapparat bewaffnet davon berichten.

Nun kann ich auch kurz die Taktik meines Spielagenten vorstellen, da er sich ja anscheinend nicht ganz überschlecht angestellt hat. Wenn für Sie als Leser bis hier alles nur nach Bahnhof geklungen hat, dann möchte ich Sie ermuntern, die restlichen Beiträge dieser Serie durchzulesen.

Grundsätzlicher Ablauf

Struktogramm meines Spielers

Struktogramm meines Spielers

Nach der Initialisierung und der Aktualisierung verschiedener Attribute wird zuerst der maximale Fluss nach Edmonds-Karp (Ford-Fulkerson mit BFS) berechnet.
Danach werden möglichst viele „minimale Schnitte“ gesucht. Minimale Schnitte in diesem Kontext sind Kombi­natio­nen von Kanten, die alle bei einer maximalen Flusskonstellation durchflossen sind – in der Summe mit den maxi­ma­len Fluss – und die den Graphen teilen.

Weiterlesen

Lokale Turniere für CodeRuler

coderulerCodeRuler ist ein geniales Programmierspiel von IBM. Es eignet sich sehr für eine spielerische Beschäftigung mit der Programmiersprache Java.

Für Turniere hat das Spiel eine eingebaute Serverfunktion. Rulers werden ganz bequem von Eclipse aus eingereicht und stehen dann auf dem Server zur Verfügung. Wenn man allerdings eigene Rulers gegeneinander antreten lassen möchte, oder wenn das Netz securitymässig so abgeriegelt ist dass Peer to Peer Verbindungen nicht möglich sind, muss man etwas tricksen. Hier die einfachste Möglichkeit unter Linux (eventuell portierbar), die ich gefunden habe. Kompliziertere Möglichkeiten gibt es natürlich auch.

  1. Die MyRuler.java Dateien müssen irgendwie auf den Servercomputer kommen. Ev. mit E-Mail, USB-Stick oder Flaschenpost.
  2. Den Server in Eclipse starten mittels: Window → Preferences → Games → Start. Eventuell sollte vor dem Start der Port angepasst werden (9999 ist gut).
  3. Für jeden Ruler muss ein eigenes „Game“ Projekt in Eclipse erstellt werden. Die MyRuler.java dorthin kopieren.
  4. Für jeden Ruler Folgendes erledigen:
    1. Projekt öffnen und Games.xml anklicken.
    2. Mit dem Pfeil den Bereich Game Server erweitern und die korrekten Daten ausfüllen.
    3. Identification ausfüllen.
    4. Ruler submitten.
    5. Im Workspace Verzeichnis (Ersichtlich unter File → Switch Workspace) in .metadata/.plugins/com.ibm.games/players wechseln
    6. Das Verzeichnis localhost in irgendetwas Anderes umbenennen

Turniere können nun an Zwei Orten durchgeführt werden:

  • Entweder Direkt von einem games.xml aus.
  • Im Turniermodus: Window → Preferences → Games → Tournaments.

Der Turniermodus ist ein Sensibelschen. Turniere scheinen nur mit neu submitteten Rulern möglich zu sein. Ausserdem: Im Hintergrund wird sofort mit dem Turnier begonnen! Das GUI zeigt keine direkte Reaktion, nicht mal ein Eintrag des neuen Turniers ist ersichtlich, aber im Hintergrund kämpfen die armen Gesellen. Das Spiel kann dann mit dem Button Play angesehen werden. Hier hat erst ein Klick auf den schwarzen Bereich das Spielfeld zum Vorschein gebracht.

Profiling des Spielagenten mit Eclipse TPTP

Die FAQ zu Avaloqix geben ganz klar die Kriterien bekannt:

Für den Wettbewerb werden Graphen mit 20-60 Knoten genutzt. Pro Knoten gibt es max. 9 Kanten. Zusätzlich gibt es eine Timelimite von 5 sec pro Spielzug.

Leider fehlen die Angaben über die Leistungsfähigkeit der Wettbewerbsmaschine. Ich gehe mal ganz willkürlich davon aus, dass sie nicht langsamer ist oder weniger Speicher hat als mein Laptop und die Resultate nur besser sein können. Eine Geschwindigkeitsoptimierung dürfte also nicht ganz sinnlos sein. Ausserdem wird mein Agent in den ersten paar Zügen nie fertig mit Rechnen und muss abbrechen. Eine Optimierung die hier mehr Spielzüge erlaubt, würden die Gewinnchancen signifikant steigern.

Ausserdem gilt wie überall im Leben: Machs schön und richtig und erst danach schnell.

Benchmarking

Bei einer Geschwindigkeitsoptimierung sollte man immer benchmarken. Das heisst: Die Geschwindigkeit vor und nach der Optimierung nachmessen, so dass man sicher sein kann, dass man in die richtige Richtung optimiert hat. Ebenfalls empfehlenswert ist gezieltes optimieren: Wenn man eine Funktion nur ein bisschen verschnellert, die sehr oft aufgerufen wird, bringt das unter Umständen mehr wie wenn man eine Funktion mit viel Aufwand drastisch verkürzt die nur wenige Male zum Zuge kommt. Man braucht also Daten.

Als Benchmark habe ich – mangels anderer Gegner – ein Spiel gegen den OptimalOneAgent gewählt. Für den Benchmark sollten immer die gleichen Einstellungen gelten, die komfortable Avaloqix Oberfläche erlaubt zum Glück das Festlegen des Spielfeldes mit dem Random Seed.

Es empfiehlt sich auch, Turn Pause zu deaktivieren und End when winner is ovious zu aktivieren.

Profiling

Doch woher die Daten nehmen und nicht stehlen? Dafür zuständig sind sogenannte Profiler. Für Eclipse gibt es einen (einer der versteckten Diamanten) im TPTP-Projekt.
Weiterlesen

Maximaler Fluss (maxflow) eines Netzwerkes in Java

Dieser Beitrag ist Teil 1 von 2 in der Serie Avaloqix Programmierwettbewerb

    MaxFlowUm im Avaloqix Wettbewerb einen einigermassen sinnvollen Agenten zustande zu kriegen, braucht es sehr wahrscheinlich eine Funktion, die den maximalen Fluss eines gegebenen Netzwerkes berechnet. Dafür gibt es eine Vielzahl von Algorithmen mit verschiedenen Aufwänden und in verschiedenen Komplexitätsstufen.

    Der erste, älteste und einfachste Algorithmus ist wohl derjenige von Ford und Fulkerson. Er ist aber relativ aufwändig in der Berechnung (O(#Kanten*#Knoten*Grösste-Kapazität)), da der maximale Fluss in den Aufwand hineinspielt. Etwas besser ist der Algorithmus von Tarjan und Goldberg. Er wird von der Uni Karlsruhe anschaulich erklärt und bei Google Code findet man auch eine Implementation davon.

    Für Graphen mit kleiner Kantendichte ist allerdings der Edmonds-Karp-Algorithmus schneller (laut Wikipedia).

    Wenn man die von der Avaloqix-Oberfläche unter Wettbewerbsbedingungen erzeugten Graphen anschaut, ergibt sich folgendes Bild:

    • Bei 20 Knoten werden 40-50 Kanten generiert, das ergibt eine Dichte von ungefähr 0,263
    • Bei 60 Knoten werden 160 Kanten generiert, das ergibt eine Dichte von ungefähr 0,090

    Das darf wohl mit Fug und Recht als undicht, ääh, geringe Dichte bezeichnet werden, also machen wir uns doch an Edmonds Karp!

    Implementation

    Bei der Implementation habe ich mich sehr nahe an die Beispielimplementation von Wikipedia gehalten. Die einzelnen Teile sind etwas aufgeräumter und kommentierter:

    /**
     * Edmonds-Karp algorithm with O(V³E) complexity
     *
     * This implementation is a slightliy modified source from Wikipedia. See
     * http://en.wikipedia.org/wiki/Edmonds_karp
     */

    class MaxFlow {

        public static final int UNVISITED = 0, VISITED = 1;

        private int[][] res_capacity; // Residual capacity
        private int[] parent; // Parent node in Breadth First Search (BFS)
        private int[] mark; // BFS: Already visited?
        private int[] min_capacity; // Minimal flow
        private int size; // Number of nodes
        private int sink;

        public MaxFlow() {
        }

        public int getMaxflow(int[][] graphMatrix, int source, int sink) {
            this.sink = sink;
            this.size = graphMatrix.length;

            int max_flow = 0; // THE max flow for which we are doing this
            // circus

            int[][] flow = new int[size][size]; // Our flow
            res_capacity = new int[size][size]; // Remaining capacity

            parent = new int[size];
            min_capacity = new int[size];
            mark = new int[size];

            // Before we start, all capacities are residual
            // System.arraycopy may be faster: see http://www.javaspecialists.eu/archive/Issue124.html
           
            // The following is wrong, as Feri in the comments has found out.
            // clone() is one-dimensional! *pats-head*
            // res_capacity=graphMatrix.clone();
            //
            //Faster:
            for (int i = 0; i < size; i++) {
                System.arraycopy(graphMatrix[i], 0, res_capacity[i], 0, size);
            }

            // Search in BFS manner through the graph, Path by Path
            while (BFS(source)) {
                max_flow += min_capacity[sink];
                int v = sink, u;
                while (v != source) {
                    u = parent[v];
                    flow[u][v] += min_capacity[sink];
                    flow[v][u] -= min_capacity[sink];
                    res_capacity[u][v] -= min_capacity[sink];
                    res_capacity[v][u] += min_capacity[sink];
                    v = u;
                }
            }
            return max_flow;
        }

        /**
         * Breadth First Search in O(V²)
         *
         * @param source
         *            The source node
         */

        private boolean BFS(int source) {
            int first, last; // Queue pointers
            int[] queue; // Queue pointers

            queue = new int[size];
            for (int i = 0; i < size; i++) {
                mark[i] = UNVISITED;
                min_capacity[i] = Integer.MAX_VALUE;
            }

            first = last = 0;
            queue[last++] = source;
            mark[source] = VISITED;

            while (first != last) { // While "queue" not empty.
                int v = queue[first++];
                for (int u = 0; u < size; u++)
                    if (mark[u] == UNVISITED && res_capacity[v][u] > 0) {
                        min_capacity[u] = Math.min(min_capacity[v],
                                res_capacity[v][u]);
                        parent[u] = v;
                        mark[u] = VISITED;
                        if (u == sink)
                            return true;
                        queue[last++] = u;
                    }
            }
            return false;
        }
    }

    Resultat

    Als innere Klasse angelegt, arbeitet diese Implementation wunderbar in einem Avaloqix-Agenten. Tests haben gezeigt, dass das Resultat nicht nur stimmt, sondern auch mit den Ausgaben der Spieloberfläche korrespondiert. Auch bei sehr grossen Netzwerken braucht sie auf meinem Schlaftop nur ein paar wenige Millisekunden.

    Avaloqix: Unterhaltsamer Java-Programmierwettbewerb

    Flow im HirnIch liebe Wettbewerbe und ich liebe das Spielen. Meine inneres, urmännliches Ich springt voll auf das kompetitive Element solcher Veranstaltungen an. Zum Erlegen von Höhlenbären oder für Sportwettkämpfe eigne ich mich definitiv nicht, darum bin ich froh, wenn ab und zu ein Kräftemessen auf meinem – eher wetwarelastigen – Gebiet stattfindet.

    Leider hat es jetzt seit längerer Zeit kein Codeduel (ein spassiger, von Microsoft Schweiz gesponserter/organisierter Event in welchem SOAP-Services gegeneinander angetreten sind, für den es aber leider keine offizielle Website mehr gibt) mehr gegeben und für die kommerzielle Version solcher Wettbewerbe habe ich im Moment wirklich keine Zeit.

    Über die Seite des Schweizerischen Jahres der Informatik bin ich auf Avaloqix gestossen und war sofort begeistert. Am Tag der Informatik am 29. August 2008 in Zürich wird es ein Event speziell zu diesem Wettbewerb geben.

    Das Spiel

    Es geht darum, einen Spieler für eine abgewandelte Version des Shannon Switching Games zu programmieren. Kurz erklärt: Es gibt eine Quelle und ein Senke, die über ganz viele Röhren und Sammelpunkte miteinander verbunden sind. Im ersten Durchgang versucht der eine Spieler einen möglichst grossen Durchfluss zu erzielen indem er Röhren freischaltet, während der andere Spieler ebendies durch das Ausbauen von Röhren zu verhindern versucht. In einer zweiten Runde werden die Rollen der Spieler in demselben Röhrengeflecht getauscht. Gewonnen hat, wer als Durchflussmaximierer den grösseren Durchfluss erzielen konnte.
    Weiterlesen

    Automatisches und mehrfaches submitten von Formularen

    Wirre Gedanken

    FormularDieser Beitrag ist dem Titz gewidmet. Dem Titz, der sich aufgeregt hat :pirate-grumble: , obwohl es gar nicht nötig gewesen wäre und der sich nun mit einer gewissen Teilnehmerredundanz anfreunden muss. Hauptsache ist doch, das PHP fliesst und die Variablen bleiben sauber… Und ein Bierchen würde ich auch noch springen lassen :bier: …

    Eine wichtige Frage zu Beginn: Wieso sollten wir denn automatisch und mehrfach Formulare submitten wollen? Hmm, um den Titz zu ärgern? Weil wir es können? Weil man manchmal tun muss, was man tun muss? Weil man seine 84 Kinder an einem elektronischen Fussballturnier anmelden will :laola: (hat eigentlich schon jemand bemerkt, dass ich neue Smilies und unglaublich Freude daran habe?)? Oder weil man über einen Wettbewerb gestolpert ist, der ebendies nicht verbietet (also das Mehrfachsubmitten, nicht das Kinderanmelden oder die neuen Smilies) und der kein Captcha hat (vielleicht, weil es der Titz vergessen hat)?

    Nachtrag 31.07.2008: Schenken mir doch so unglaublich nette Mitarbeiter einer Versicherung heute morgen am Bahnhof einen Müsliriegel. Und auf diesem eher gesunden Teil hat es, ja rate, oh wissbegieriges Volk, einen Wettbewerb. Ob der Titz wohl am Abend für eine andere Firma weitercoded? Ich werde mich auf jeden Fall während der Zugfahrt mal damit befassen :computer: .

    Vorgehen

    Erster Schritt: Selenium IDE

    Man könnte nun wie wild losprogrammieren, oder aber einen einfacheren Weg wählen. Ein guter Startpunkt für automatisiertes Browsen generell ist die Selenium IDE. Dieses geniale Teil für den Firefox zeichnet wie ein Macrorecorder alles auf, was im Browser gemacht wird. Hat man die Teilnahme beim Wettbewerb einmal so aufgezeichnet, so müssen nur noch die click’s, die das Form absenden, durch clickAndWait’s ersetzt werden, damit vor dem Weiterausfüllen (bei mehrseitigen Formularen) auf die neue Seite gewartet wird. Es empfiehlt sich, eine Abschlussüberprüfung als letzten Schritt hinzuzufügen, um um kontrollieren zu können, ob die Kinder erfolgreich angemeldet wurden (markieren des „Dankeblabla“, dann rechte Maustaste und assertTextPresent).

    Ein Wettbewerb über 2 Seiten. Aufgezeichnet und bearbeitet mit der Selenium IDE.

    Ein Wettbewerb über 2 Seiten. Aufgezeichnet und bearbeitet mit der Selenium IDE.

    Diesen Testcase kann man nun abspeichern und eigentlich immer wieder ausführen. Ein Klick reicht und Firefox rasselt alles schön durch. Den Namen leicht verändern kann man durch Editieren des Skripts…

    Für den zweiten Schritt sollte man das Testscript als PHP exportieren.

    Zweiter Schritt: Selenium RC

    Die Selenium RC Komponente kann den Browser fernsteuern und so ferngesteuert am Wettbewerb teilnehmen. Um sie unter Linux Debian zum Laufen zu kriegen, war ein Bisschen Gemurkse notwendig.

    Weiterlesen