Uitslag Code Challenge Splash Paint

Voor de derde Java Magazine code challenge van dit jaar moesten de deelnemers op een 12×12 canvas de kleinste verfspetter vinden. Maar, er was een twist: de oplossing moet uit zo min mogelijk tekens bestaan. Er zijn tien inzendingen binnengekomen. Een overzicht van de inzendingen, gesorteerd van kleinste tot grootste inzending:

NaamOmvangLink
Raymond Cuenen515https://github.com/rmcuenen/verfspetters
Jos van Bakel609https://github.com/c0deaddict/verfspetters
Oscar van den Bosch612https://github.com/oscarvdbosch/splashpaint
Aldo Eisma691https://github.com/aeisma/jmcs.git
Roy van Rijn753https://gist.github.com/royvanrijn/1ea400f32d0f2e9f0422
https://gist.github.com/royvanrijn/33e780c1f270691cd326
Jonne Zutt788https://github.com/jonnez/SplashPaint 
Adriaan Koster953https://bitbucket.org/adriaan_koster/splashpaint.git
Sander Kooijmans1264https://github.com/gogognome/splashpaint
Maarten Oortwijn1430https://github.com/maartenoortwijn/splashpaint 
Stefan Boeser2335https://github.com/boess/verfspetters/

Uiteraard geldt dat de oplossing niet alleen klein, maar ook correct moet zijn. En daar wringt meteen de schoen bij de meeste inzendingen. Op één oplossing na geven alle inzendingen het correcte antwoord voor de in JM gegeven input. Maar geeft de oplossing ook in andere situaties het goede antwoord? De oplossing van Maarten Oortwijn draait bijvoorbeeld alle X en Y coordinaten om in de output en voldoet daarom niet aan de specificatie.

Op zoek naar correctheid

Het zoeken is dus naar oplossingen die wel correct zijn. Om het beoordelen overzichtelijk te houden (er waren een aantal creatieve aanpassingen op het input-formaat gedaan door sommige inzenders) heb ik een viertal testcases op iedere oplossing losgelaten. Er zijn uiteraard nog talloze andere testcases te bedenken. Deze set was echter genoeg om veel oplossingen al te kunnen falsifiëren. Je kunt de input en verwachte output van de testcases hier vinden. Wanneer de output qua formattering iets afwijkt op whitespace e.d. heb ik dit niet fout gerekend, aangezien dit niet als echt harde eis in de opdracht opgenomen was. Zie hier het resultaat van de oplossing met de test inputs:

Naamin1in2in3in4
Jos van BakelYNNY
Roy van RijnYYYY
Adriaan KosterYYYN
Jonne ZuttYNYY
Maarten OortwijnNNNN
Raymond CuenenYNNN

Sander Kooijmans

YYYY
Aldo EismaYYNY
Oscar van den BoschYYYN
Stefan BoeserYNNN

Al met al blijven er twee oplossingen over die voor alle vier de testcases het juiste antwoord opleveren: die van Roy van Rijn en Sander Kooijmans. De oplossingen van Oscar van den Bosch en Adriaan de Koster gaven wel de juiste coordinaten voor de vierde testcase, maar niet in de juiste volgorde. Dit was overigens een vaker voorkomend probleem. De gevraagde volgorde is van links naar rechts, van boven naar beneden.

Verder is het interessant om te zien dat het aantal passes over de input bij de verschillende inzendingen nogal uiteenloopt. De oplossing van Roy van Rijn gebruikt bijvoorbeeld een interessante aanpak om na het doorlopen van de input groepen te kunnen samenvoegen en de kleinste te vinden.

Op zoek naar compactheid

Het tweede aspect van deze challenge ging om het zo klein mogelijk maken van de oplossing. Alles is geoorloofd, zo lang het maar compiled. Favoriete tactieken waren:

  • alle code op één regel te zetten;
  • de class in de default package te laten leven;
  • wildcard imports te gebruiken;
  • en uiteraard gebruik te maken van één-letterige identifiers.

De meest creatieve aanpak was die van Jonne Zutt. Lees in zijn readme hoe hij met behulp van compressie en on-the-fly decompressie tot de kleinste oplossing probeerde te komen. De afloop zal ik niet verklappen 🙂

De winnaar

Het kiezen van de winnaar voor deze challenge is met de voorgaande data niet moeilijk meer. Het moge inmiddels duidelijk zijn dat de kleinste oplossingen niet per definitie de beste oplossingen waren. Er zijn twee correcte oplossingen over: die van Roy van Rijn en Sander Kooijmans. Aangezien Roy met zijn 753 tekens een aanzienlijke kleinere oplossing heeft dan Sander met 1264 tekens, is Roy de winnaar van deze editie. Gefeliciteerd.

Hopelijk tot de volgende challenge!