MASTERS OF JAVA - Walkthrough

Masters of Java -- de eerste Java wedstrijd die ook leuk is om te doen! Deze beschrijving leidt u door een van de cases -- de Hanoi case -- van het prille begin tot het inleveren van de opdracht en het verkrijgen van de score.

OPSTARTEN VAN DE OMGEVING

De omgeving kan opgestart worden via de browser. De wedstrijdorganisatie zal op de dag zelf de URL bekendmaken. Zodra de omgeving opgestart is wordt het inlogscherm getoond. Met behulp van het door de organisatie uitgedeelde username/password kan worden ingelogd - als u thuis aan het oefenen bent geslagen dan is het wachtwoord 'Welkom'.  

Nadat het systeem de inloggegevens heeft geakkoordeerd wordt het wachtscherm getoond. Dit scherm geeft aan dat de wedstrijdklok voor de opdracht nog niet is gestart. Zorg dat u goed in de startblokken staat, want de wedstrijd kan ieder moment beginnen...

HET SPEL BEGINT

De klok loopt! U heeft nog een half uur om de opdracht uit te voeren en in te leveren. Laten we snel door de opdracht heen gaan en onze tijd nuttig benutten.

Eerst maar een beschrijving van de interface. Hier op het linker tabblad ziet u de opdrachtomschrijving. Iedere opdracht omschrijving bestaat uit 4 delen:  de Inleiding waarin vaak op humoristische wijze de achtergrond van de opgave geschetst wordt. Gevolgd door een concrete opdracht omschrijving - hier staat precies vermeld wat de bedoeling is. Daarna komt een voorbeeld, meestal is dit een van de test-sets uitgewerkt. Als laatste volgen er een aantal hints. Sommige zijn cryptisch, andere heel duidelijk. Het succesvol oplossen van de opgave begint met het goed lezen van de opdracht !

Op het tweede tab blad staat een bijzonder handig hulpmiddel -- de testsets. Hier kan gezien worden welke testsets er door de server losgelaten worden op de ingediende klasse. Voor deze opgave zijn er 3 test sets. Ze kunnen allemaal tegelijkertijd of individueel worden afgevuurd op de klasse.

Op de volgende tab tabbladen worden de Java klassen getoond die gebruikt worden om de opgave tot een goed einde te brengen. Voor deze opgave worden 2 interfaces, een exception en een class gegeven. De class is te bewerken en moet uiteindelijk de oplossing gaan bevatten. Vooralsnog staat er het volgende in:

/**
 * TowersOfHanoiImpl bevat een algorithme welke de klassieke 
 * 'Torens van Hanoi' puzzel oplost. 
 */
public class TowersOfHanoiImpl {
 public void solve(HanoiPuzzle hp) {
   //
   // Implement Here
   //
   System.out.println(hp); // Useful for debugging
   //
 }
}

Listing I: de klasse die geimplementeerd moet worden.

In bovenstaande listing vallen twee dingen op: we krijgen een object van het type HanoiPuzzle die we moeten oplossen en de HanoiPuzzle kan geprint worden naar de console wat handig kan zijn bij het debuggen. Maar wat kan die HanoiPuzzle nu eigenlijk ? Door naar de volgende listing:

/**
 * HanoiPuzzle representeert de bekende 'Torens van Hanoi' puzzel waarin
 * een aantal schijven van toenemende grootte 1 voor een van de linker naar
 * de rechter toren verplaatst moet worden, dusdanig dat er nooit een
 * grotere schijf boven op een kleinere terecht komt.
 */ 
public interface HanoiPuzzle {
 /** geeft de eerste toren terug welke initieel alle schijven bevat. */
 public Tower getSourceTower();
 /** de middelste toren (de hulp toren) terug */
 public Tower getMiddleTower();
 /** de toren waarop de schijven uiteindelijk terecht moeten komen */
 public Tower getTargetTower();
 /**
 * verplaatst de bovenste schijf van de ene toren naar de andere toren
 * @param source de toren waarvan de bovenste schijf verwijderd wordt.
 * @param target de toren waarop de schijf geplaatst moet worden
 * @throws RuntimeException wanneer de schijf niet past of als het
 * maximaal aantal zetten is overschreden
 */
 public void moveDisk(Tower source,Tower target) throws InvalidMoveException;
 /**
 * @return true als de puzzel correct is opgelost - alle schrijven zitten
 * op de laatste toren.
 */
 public boolean isSolved();
}

Listing II: de interface waar je tegenaan programmeert

Een HanoiPuzzle bestaat klaarblijkelijk uit 3 torens waarbij we schijven van de ene naar de andere toren kunnen verplaatsen. Dit kan niet altijd aangezien er een InvalidMoveException gegooit kan worden, volgens de java doc mag alleen schijven stapelen die kleiner zijn dan de onderliggende schijf. Rest nog de vraag van wat kunnen we met een Tower object ? Gelukkig hebben we daar ook de source van:

/**
 * Tower representeert een toren in de Torens van Hanoi puzzel. 
 * Op een toren zitten 0 of meerdere schijven welke in grootte afnemen want
 * er mag nooit een grotere schijf boven een kleinere zitten. 
 */
public interface Tower {
 /** @return de hoogte van de schijven op de toren */
 public int getHeight();
 /**
  * @return de grootte van de meest boven gelegen schijf.
  * Wanneer de toren leeg is (height==0) dan geeft deze 
  * methode Integer.MAX_VALUE terug. 
  */
 public int getTopDiskSize();
}

Listing III: De Tower interface.

Nu dat alle source code bekeken is (de InvalidMoveException is nogal triviaal en laten we achterwege :-) is het tijd om te bedenken hoe dit probleem het beste valt op te lossen.

HET PROGRAMMEREN BEGINT

Het voorbeeld in de opgave geeft de oplossing van de puzzel voor 2 schrijven. De testset zelf bestaat uit de varianten voor 2, 3, 4 en 5 schijven. Nu is altijd goed om eenvoudig te beginnen, dus laten we eerst eens een hard coded oplossing voor het voorbeeld (en de eerste test) maken:

    |  | |     |  |  |   | |  |     |  |  |
    #  | |     |  |  |   | |  |     |  |  # 
   ### | |    ### #  |   | # ###    |  | ###
  ---------- ---------- ---------- ----------

public void solve(HanoiPuzzle hp) {
 hp.moveDisk(hp.getSourceTower(),hp.getMiddleTower());
 hp.moveDisk(hp.getSourceTower(),hp.getTargetTower());
 hp.moveDisk(hp.getMiddleTower(),hp.getTargetTower());
}

Listing IV: Oplossing voor 2 schijven

Bovenstaande code kan worden gesaved, gecompileerd en getest worden door op de Test knop te drukken. Het is dus niet nodig om eerst te saven, dan te compileren en dan te testen. Dat scheelt weer de nodige seconden ! Als alles goed is geeft de eerste test case nu groen en kan je rechts onderin kijken naar een animatie van de zetten die het programma gemaakt heeft. Wel jammer dat de andere testen (nog) rood geven.

Kijkend naar het voorbeeld valt iets vreemds op, de linker kant is het spiegelbeeld van de rechter kant. Het zelfde gebeurt in de code, de eerste en de laatste regel zijn elkaars spiegelbeelden. Hoe vreemd..

De oplossing voor een puzzel met 3 schijven is ook nog goed te doen op een stukje papier, er zijn exact 7 zetten voor nodig. Probeer het eens en maak gelijk een notitie dat je een kladblok mee neemt naar de wedstrijd :) Weer ontstaat diezelfde symmetrie in de oplossing en in de code.

public void solve(HanoiPuzzle hp) { 
 hp.moveDisk(hp.getSourceTower(),hp.getTargetTower());
 hp.moveDisk(hp.getSourceTower(),hp.getMiddleTower()); 
 hp.moveDisk(hp.getTargetTower(),hp.getMiddleTower()); 
 hp.moveDisk(hp.getSourceTower(),hp.getTargetTower()); 
 hp.moveDisk(hp.getMiddleTower(),hp.getSourceTower()); 
 hp.moveDisk(hp.getMiddleTower(),hp.getTargetTower()); 
 hp.moveDisk(hp.getSourceTower(),hp.getTargetTower()); 
}

Listing IV: Oplossing voor 3 schijven

Als je 1000 letters per minuut typt kan je er nu voor kiezen om op dezelfde manier de oplossing voor 4 schijven uit te werken. Dat kan net binnen de tijd, alleen een geweldige score zul je er niet mee halen. Beter is het nog even na te denken hoe deze puzzel op een algemene manier is te omschrijven en dan in 1 keer klaar te zijn voor alle mogelijke aantallen schijven.

In zijn eenvoudigste vorm heeft puzzel slechts 1 schijf en kan deze met 1 beweging worden opgelost. Deze beweging zien we bij iedere oplossing excact in het midden terug komen. Het aantal zetten er voor en er na zijn gelijk wat een recursieve oplossing doet vermoeden (en uiteraard, wat de torens van hanoi is een schoolvoorbeeld van recursie :-)

De variant met twee schrijven kan worden opgelost met dezelfde zet in het midden en twee gespiegelde zetten er voor en er na. Voor de variant met 3 schijven is het eigenlijk het zelfde, alleen dat de eerste 3 en laatste 3 zetten gespiegeld zijn en dat ze intern ook weer gespiegeld zijn (de bovenste 3 zetten zijn identiek aan de oplossing voor 2 zetten, alleen is de Target tower nu de Middle tower en vice versa..) kortom..

 // Bij 0 schrijven zijn we klaar.
 if (n==0) return; 
 // Heen.. (doet niets bij n==1)
 solve(hp,n-1, src, dst, aux); 
 // De winnende zet :-)
 hp.moveDisk(src,dst); 
 // en Terug..
 solve(hp,n-1, aux, src, dst);

Nu moeten er alleen nog een vertaling gemaakt worden van het aangeboden object naar de recursieve implementatie:

public void solve(HanoiPuzzle hp) {
 //
 try {
  solve(hp,
        hp.getSourceTower().getHeight(),
        hp.getSourceTower(),
        hp.getMiddleTower(),
        hp.getTargetTower());
 } catch (InvalidMoveException ex) {
  System.out.println(ex);
 }
 //
}
private void solve(HanoiPuzzle hp,
                   int n,
                   Tower src,
                   Tower aux,
                   Tower dst) throws InvalidMoveException{ 
 if (n==0) return;
 solve(hp,n-1, src, dst, aux);
 hp.moveDisk(src,dst);
 solve(hp,n-1, aux, src, dst);
}

Opnieuw draaien van de testset geeft een welkom resultaat -- alle tests zijn geslaagd. We zijn nu klaar om de opdracht in te dienen en de scoring te ondergaan.

HET INDIENEN VAN DE OPDRACHT

Na het drukken op de "submit" knop en het bevestigen van de indiening, wordt de server gevraagd om een score toe te kennen. De indiener zal allereerst alle testsets met succes moeten afronden. Als dat niet lukt worden 0 punten toegekend. Als dat wel is gelukt wordt daarna gekeken naar de verstreken tijd. Afhankelijk hiervan worden de punten toegekend.

En op het grote server board wordt de score van het team getoond naast de voortgang van de andere partijen.

Hoera ! De opgave is klaar, nu kan het echte werk beginnen - de inschrijving opent binnenkort !