Master of Java 2020

-

Masters of Java: De titanenstrijd waar de meest geniale programmeurs onder tijdsdruk magische code schrijven. Of nouja… eigenlijk zijn het gewoon normale mensen die het leuk vinden puzzeltjes op te lossen. In deze blog een korte beschrijving van het fenomeen Masters of java en de puzzeltjes uit editite 2020!

Sijmen deed voor het eerst mee in 2018 en won direct de titel Master of Java. Jeroen deed vorig jaar voor het eerst mee, beiden in een ander teamWe hadden direct de smaak goed te pakken en wilden vaker meedoen. 

Tijdens de wedstrijd komen een aantal programmeeropdrachten aan bod die je zo snel mogelijk moet oplossen. Je beschikt alleen over de standaard libraries en geen IDE. Pure Java dus! De enige bron van hulp was een link naar de javadoc en compiler/test feedback vanuit de wedstrijd omgeving.  

Punten scoor je door de opgave goed in te leveren (vaak krijg je maar 1 poging, soms meerdere maar dan krijg je minder punten). Voor iedere seconde die over is krijg je ook een punt en voor slagende unittests krijg je ook punten, dus ook met halve oplossingen kun je punten verdienen. 

Dijaar werd Masters of Java (MoJ) als virtueel event gehouden. Hierdoor waren de regels ook net iets anders. In tegenstelling tot voorgaande jaren mochten we alle resources gebruiken: het internet en IDE’s waren niet langer verboden. 

Het gebruiken van internet klinkt aantrekkelijk, maar is alleen interessant als je echt vast zit. Een half uur is niet lang en echt tijd om naar iets te zoeken is er niet. Het kunnen gebruiken van een IDE maakte de wedstrijd wel iets makkelijker. 

Maar goed, hoe was de wedstrijd? Lastig, spannend, leuk! De 4 opgaven waren allemaal erg verschillend en vroegen om verschillende vaardigheden. De wedstrijd ging niet helemaal soepel van start maar na een herstart van de wedstrijd omgeving konden we toch beginnen, we have all been there... Door de hoeveelheid teams had de server van de organisatie het zwaar en ging het met testen/indienen van de opgave wel eens fout. Dat was jammer maar maakte eigenlijk weinig uit (en zeker niet voor de top 3). 

Unieke karakters tellen

De eerste opgave: tel het aantal verschillende karakters in een Java String. 30 minuten de tijd, makkie!

return str.chars().distinct().count();

 

Zoiets misschien? Compile, test… Gefaalde tests. Wat blijkt? Speciale unicode karakters hebben bijzondere aandacht nodig. Een enkel karakter kan meerdere bytes innemen, bijvoorbeeld 𝄞Dit heet een surrogate pair. Een Java String is een byte array, dus zo’n speciaal karakter neemt meerdere posities in de String in beslag. Met String.codePoints() krijg je een lijst van alle karakters waarbij surrogate pairs zijn samengevoegd:

return str.codePoints().boxed().collect(Collectors.toSet()).size();

HopakeeCompile, test… rood. Een paar testen zijn groen maar de emoji-test faalt. Binnen Unicode kunnen blijkbaar meerdere emoji samengevoegd worden door middel van een zero width joiner (U+200D). Zie bijvoorbeeld deze katten: 

Door een gekleurd blokje toe te voegen verandert de kat. Het is dus zaak dat we eerste karakters samenvoegen voordat we de unieke karakters tellen.  Nu moet die werken. Compile, test… rood. Weer niet. Na debuggen blijkt dat er variant characters aanwezig zijn. Dit zijn karakters die de manier waarop een karakter wordt weergegeven aanpast. Het karakter blijft hetzelfde dus we kunnen 0xfe0f simpelweg negeren. 

 public static int countCharactersEmoji(String str) { 
        LinkedList characters = new LinkedList(); 
        int[] codePoints = str.codePoints().toArray(); 

        for (int i = 0; i < codePoints.length; i++) { 

+            if (codePoints[i] == VARIANT) { 
+                continue; 
+            } 

            if (codePoints[i] == ZWIDGE) { 
                i++; 
                characters.addLast(characters.removeLast() + "\\" + codePoints[i]); 
            } else { 
                characters.addLast("\\" + codePoints[i]); 
            } 
        } 
        return new HashSet(characters).size(); 
    } 

Compile, test… groen! Hiermee had je punten gehaald bij Masters of Java. Weet wel dat dit bij lange na niet alle Unicode strings correct telt. Zo zal deze oplossing onder andere skin tone modifiers en vlaggen niet correct tellen.  

Opdracht no-offence

De tweede opdracht kwam voornamelijk neer op heel goed lezen en je niet op het verkeerde been laten zetten. Het doel was om op een kaart rond een dorp een zo kort mogelijk hek te plaatsen. Hiervoor was al veel code gegeven en moesten een aantal gaten in het programma nog gevuld worden. Dit is niet ons favoriete opdracht, maar zeker belangrijk voor een ‘Master of Java’. 

Opdracht Bit Streaming

  De derde opdracht ging over het decoderen van een radiosignaal (een stream bits) en berichten te verzamelen uit een stream. Een moeilijkheid hierbij was dat het signaal in Bi-Phase wordt gestuurd, wat wil zeggen dat er dubbel zoveel bits nodig zijn voor de data. Als extra moeilijkheid moet er ook ruis uitgefilterd. Dit is een typische Masters of Java opdracht, ga hem vooral zelf hier uitproberen.   

Opdracht HiggsBugson: Oplossen van een quantum bug

  De vierde en laatste opdracht was een grote hoeveelheid code met daarin een enkele bug die soms optreedt bij een unit test maar niet altijd. Als extra twist werden er punten afgetrokken voor iedere keer dat de tests gedraaid werden.  Bij het draaien van de test gingen ongeveer 80% van de tijd een aantal tests fout. De code is zacht gezegd toe aan een grondige opschoonbeurt. Zo zijn er tests die willekeurige data genereren: 

@Test 
    public void testClassify() { 
        ParticleAccelerator pa = new ParticleAccelerator(TestUtil.allKnownParticles()); 

        for (int i = 0; i < 100; i++) { 
            Particle p = TestUtil.randomParticle(); 
            Particle measurement = TestUtil.addError(p); 
            ClassifiedParticle classified = pa.classify(measurement); 

            assertEquals(p.getName(), classified.getName()); 
            assertEquals(p.getType(), classified.getType()); 
        } 
    } 

En worden integers door elkaar gedeeld om een float waarde te krijgen…

public Electron() { 

    super("Up", 0.511f,-1, 1 / 2, Type.LEPTON); 
} 

Gelukkig is er wel een beetje documentatie om ons op weg te helpenLaten we hopen dat de 17 regels documentatie (op 214 regels code) de belangrijkste informatie bevatten. Zo lees je onder andere:    A particle is identified by its name, two particles are equal if their name is equal.  Dat is nuttig! We weten dat equality van objecten in Java wordt geïmplementeerd door equals en hashCode, dus laten we die controleren:

@Override 

    public int hashCode() { 
        final int prime = 31; 
        int result = 1; 

        result += prime * result + ((id == null) ? 0 : id.hashCode()); 

        return result; 
    } 

    @Override 
    public boolean equals(Object obj) { 
        if (this == obj) 
            return true; 
        if (obj == null) 
            return false; 

        Particle other = (Particle) obj; 

        if (name == null) { 
            if (other.name != null) 
                return false; 
        } 

        return name.equals(other.name); 
    } 

Kun jij de fout vinden?  De hashCode blijkt zich niet aan het equality contract te houden. Vervang die methode door de volgende:

@Override 
    public int hashCode() { 
        return Objects.hash(name); 
    } 

En we hebben weer punten binnen! 

Conclusie

  We hebben er weer een hoop lol bij gehad en volgend jaar doen we zeker weer mee aan wat een van de leukste programmeermiddagen van het jaar is. Kun je niet wachten? Kijk in de Masters of Java GitHub repo om de opdrachten van voorgaande edities uit te proberen. Hopelijk tot ziens bij de volgende editie van Masters of Java!