[Programming Contest 5] Tuintopia

[Corniel]

Wanneer is er een update te verwachten? (en een devmeeting, ik houd het in beraad)

[Anoniem: 303530]

Daos schreef op donderdag 18 juli 2013 @ 12:55:
Misschien is het een idee om de prijsuitreiking tijdens dat evenement te doen. Dat scheelt weer een postzegel (drinken/eten moet wel zelf betaald worden)

Ik schat de kans klein in dat ik dan aanwezig ben.

[joram.agten]

Daos schreef op donderdag 18 juli 2013 @ 12:55:
Misschien is het een idee om de prijsuitreiking tijdens dat evenement te doen. Dat scheelt weer een postzegel (drinken/eten moet wel zelf betaald worden)

Ik ga daar ook niet aanwezig zijn, maar ik ga ook geen prijzen in de wacht slepen verwacht ik, dus dat is misschien niet eens zo een probleem.

[liquid_ice]

Creepy heeft de verschillende inzendingen getest met de finale-testsets.

Deze uitkomsten moet ik nog door de 'holy-validator' halen en samen met Arjan de resultaten bekijken.
Ik hoop, afhankelijk van Arjan's planning daar dit weekend mee aan de slag te kunnen.

Ook doen we dan een uitspraak over wanneer en hoe de uitslag wordt gepubliceerd.

[Anoniem: 303530]

Ik zal ook nog wat vertellen over de eerste poging die ik had gedaan

Voordat de contest bekend was had ik bedacht dat het slim was om blokken van 3x3 te combineren. Daar had ik al wat over verteld. Het idee is dat de blokken ongeacht de transformatie of rotatie op dezelfde score uitkomen.

Een blokje bestaat uit 9 kaarten, waarbij het aantal mogelijkheden 9! / 8 = 45360 is. Het algoritme wordt gevoerd door telkens 9 (gesorteerde) kaarten.

Tussen die 9 kaarten zijn 36 connecties mogelijk: kaart 0 kan een connectie hebben met kaart 1 t/m 8. Kaart 1 kan een connectie hebben met kaart 2 t/m 8. Enzovoorts. Dat wordt opgeslagen in een 64 bit int. Een geldig veld bestaat uit zo'n set van 36 connecties waarvan 20 bits geset zijn.

Het idee was om een bitscan uit te voeren om te kijken welke bit index geset is, en de waarde daarna uit een LUT te halen. Bij mijn eerste poging loopte ik over alle (pre-computed) bitsets heen. Hier waren telkens 20 bitscans en score loopups nodig. Maar het is slimmer om het verschil tussen de bitsets te bekijken. Als je score weet dat de score voor veld X weet, en je weet dat veld Y slechts 2 bits op een andere positie heeft staan, zijn 4 bitscan+score lookups genoeg. De hele array wordt gesorteerd om de 'bit difference' tussen verschillende mogelijkheden zo klein mogelijk te maken.

De kern daarvan ziet er als volgt uit:

C++:

    int setBit;

    while ( loadPtr != loadEnd )
    {
        loads = *loadPtr; // bitset van connecties die ingeladen moeten worden
        unloads = *unloadPtr; // bitset van connecties die uitgeladen moeten worden
        // 'loads' en 'unloads' bevatten altijd een identiek aantal bits >= 2

        // do score check
        blah;

        BSF( setBit, loads );
        unloadPtr++;
        currentPoints += scoreArr[ setBit ];
        loads = loads & ( loads - 1 ); // clear least significant set bit

        BSF( setBit, unloads );
        loadPtr++;
        currentPoints -= scoreArr[ setBit ];
        unloads = unloads & ( unloads - 1 ); // clear least significant set bit
        do
        {

            BSF( setBit, loads );
            currentPoints += scoreArr[ setBit ];
            loads = loads & ( loads - 1 ); // clear least significant set bit

            BSF( setBit, unloads );
            currentPoints -= scoreArr[ setBit ];
            unloads = unloads & ( unloads - 1 ); // clear least significant set bit
        }
        while ( unloads );
    }

(BSF is een macro welke naar verschillende compiler implementaties van BitScanForward expand)

Hij doet ongeveer 10 clock cycles per veld. De meeste tijd wordt verspild door de cache mis bij het inladen van 'loads' en 'unloads' (op regel 12 en 17). Het lijkt mij dat de CPU de simpele sequentiële access wel zou herkennen, maar dat viel dus tegen. De instructies staan in een bepaalde volgorde. Ik dacht altijd dat de compiler wel instruction reordering toe past. En anders de GPU wel. Het verwisselen van een paar regeltjes code bleek soms voor een procent of 10 snelheidswinst te zorgen.

Door de opzet kunnen we wat leuke pruning uithalen. We weten dat we 20 scores uit de mogelijke 36 moeten kiezen. Als we alle velden in 9 segmenten opdelen, en elk segment heeft een andere kaart in het midden van het veld, wordt het mogelijk om zeer efficiënt te prunen. Ik geloof dat de pruning rate ver boven de 99% uit kwam.

Verder heb ik nog een soort van hash ontwikkeld om collecties van unieke kaarten te mappen naar een unieke value zonder 'gaten' er in. Dat werd gebruikt om de score tabel en score van die set kaarten te cachen.

Wat dit algoritme de doodsteek gaf was de zon en wind, en het feit dat de grootte van het veld niet van tevoren vast staat. Ik had nog geprobeerd de zon en wind als een soort post processing stap toe te voegen, maar dat was niet snel te krijgen.

[Daos]

liquid_ice schreef op woensdag 07 augustus 2013 @ 09:27:
Creepy heeft de verschillende inzendingen getest met de finale-testsets.

Deze uitkomsten moet ik nog door de 'holy-validator' halen en samen met Arjan de resultaten bekijken.
Ik hoop, afhankelijk van Arjan's planning daar dit weekend mee aan de slag te kunnen.

Ook doen we dan een uitspraak over wanneer en hoe de uitslag wordt gepubliceerd.

Lang weekend

Kan je die 'holy-validator' niet aan Creepy geven en het zijn probleem maken?

[liquid_ice]

DAOS, de validator staat online, daar kan iedereen bij.

maar je hebt helemaal gelijk DAOS, het was een lang weekend

nee, ik ben er niet aan toegekomen om het met Arjan af te werken en een beslissing te maken.
Ook willen we de resultaten nog een keer met Creepy spiegelen.

Zodra ik Arjan zie zal ik op z'n minst afspreken wanneer en hoe we de bekentmaking doen.
Opzich zijn we wel gecharmeerd van het plan om het op de Devschuur meeting W *26 oktober* te doen, maar dat is nog niet besloten.

[Daos]

liquid_ice schreef op woensdag 14 augustus 2013 @ 15:07:
Opzich zijn we wel gecharmeerd van het plan om het op de Devschuur meeting W *26 oktober* te doen, maar dat is nog niet besloten.

Ik ben de enige van de inzenders die naar de Devschuur meeting gaat. Darkstone en joram.agten hebben in dit topic al aangegeven (vrijwel zeker) niet te komen:

Anoniem: 303530 schreef op maandag 05 augustus 2013 @ 14:35:
[...]

Ik schat de kans klein in dat ik dan aanwezig ben.

joram.agten schreef op dinsdag 06 augustus 2013 @ 14:27:
[...]

Ik ga daar ook niet aanwezig zijn, maar ik ga ook geen prijzen in de wacht slepen verwacht ik, dus dat is misschien niet eens zo een probleem.

[liquid_ice]

We hebben besloten om een paar van de inzendingen een extra test set te laten doen.

Dit besluit is genomen omdat hun resultaten wel erg dicht bij elkaar liggen.

[Corniel]

Spannend, wanneer komt de uitslag naar verwachting?

[Malthus]

Daos schreef op woensdag 14 augustus 2013 @ 18:53:
Ik ben de enige van de inzenders die naar de Devschuur meeting gaat. Darkstone en joram.agten hebben in dit topic al aangegeven (vrijwel zeker) niet te komen:

Ik heb 26 oktober ook al iets anders op het programma staan, dus ik zal ook niet bij de Devschuur meeting aanwezig zijn. En ik zou het ook niet erg vinden als de uitslag al voor 26 oktober bekend gemaakt wordt.

[liquid_ice]

Ik moet jullie NOG heel even in spanning houden jongens...

[Anoniem: 510923]

Inzendingen en uitslagen : Tuintopia

^

Inzendingen

Bij de inzendingen die een ongeldig resultaat hebben geleverd op 1 van de testsets, hebben we ons best gedaan met wat aanpassingen om toch een validatie voor de output file te krijgen. Bij het kopje 'beoordeling' staat hoe we deze validaties hebben meegenomen in de eindbeoordeling.

Een Zip bestand met de originele inzendingen en de bijbehorende output files (ook de aangepaste versies) kun je hier downloaden. Tevens vind je er de validatie raporten.
http://www.tuintopia.nl/prog_wedstr/uitslag.rar

^

Beoordeling

De beoordeling van de inzendingen hebben we gedaan op basis van de volgende regels:

• Diegene met de hoogste score krijgt 1 punt, de volgende 2 en zo verder.
• Indien er meerdere entries zijn met dezelfde score dan wordt de plaats bepaald aan de hand van de looptijd van het programma. Het programma dat als eerste uit zichzelf is gestopt krijgt dan 1 punt, de volgende 2, enz.
• Een geldig resultaat is altijd beter dan een ongeldig resultaat, ongeacht de score.
• Een ongeldig resultaat is altijd beter dan een crash
• Het geven van ongeldig resultaat betekent niet meteen dat je "af" bent, maar elke foute kaart wordt als lege kaartlocatie beschouwd
• De enige foutieve punten bepaling is gevonden in gecorrigeerde outputs. Tevens hebben we gezien dat de regel: “Het berekenen van een foutieve eindscore kost je de punten die het huis zou hebben opgeleverd” geen enkele invloed zou hebben op de eindpositie, dus hebben we besloten om dit niet mee te nemen in de uiteindelijk behaalde punten.

^

Uitslagen

Alleen bij testset 1 hebben 3 deelnemers dezelfde score behaald. Om de volgorde te bepalen hebben we naar de looptijd van het programma gekeken. Deze was volgt: Daos 0m04, Soultaker 4m57, Maltus 4m58.

Na het draaien van de eerste 3 testsets ontstond er een gedeelde eerste plaats. Om te bepalen wie de winnaar was hebben we met deze 2 inzendingen een vierde testset gedraaid.

^

Bijzonderheden Testset 1(TS1)

Pete: Bleef draaien en moest gestopt worden
Darkstone: Is bij de scoreregel de ‘:’ en hoofdletter vergeten
Corniel: Heeft de dierenweide te vaak gebruikt

^

Bijzonderheden Testset 2(TS2)

Pete & Bas Nieuwehuizen: Bleven draaien en moesten gestopt worden
Darkstone: Is bij de scoreregel de ‘:’ en hoofdletter vergeten
Corniel: Heeft de dierenweide te vaak gebruikt
joram.agten:
Crash bij SET 2: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 28 at programmingcontest5.BoardReader.read(BoardReader.java:35)
at programmingcontest5.Main.main(Main.java:18)

^

Bijzonderheden Testset 3(TS3)

Corniel:
Crash bij SET 3:
Unhandled Exception: System.ArgumentException: Must specify valid information for parsing in the string.
at System.Enum.TryParseEnum(Type enumType, String value, Boolean ignoreCase,
EnumResult& parseResult)
at System.Enum.Parse(Type enumType, String value, Boolean ignoreCase)
at GentleWare.DessertStorm.TuinInstructie.Create(String line)
at System.Linq.Enumerable.WhereSelectListIterator`2.MoveNext()
at System.Linq.Buffer`1..ctor(IEnumerable`1 source)
at System.Linq.Enumerable.ToArray[TSource](IEnumerable`1 source)
at GentleWare.DessertStorm.Program.Main(String[] args)

Daos: Lijkt te hangen met SET 3. Geen output

Bas Nieuwehuizen:
Crash bij SET 3.
9 10
Aborted (core dumped)

Pete:
Crash bij SET 3:
Starting Running queue with width 100
Watchdog is watching over you
8 threads
terminate called after throwing an instance of 'std::length_error'
what(): vector::reserve
Aborted (core dumped)

Maltus: Heeft het datacenter te vaak gebruikt & 10 kaarten op eilanden
Darkstone: Is bij de scoreregel de ‘:’, hoofdletter vergeten & 4 kaarten op eilanden
Joram.agten: Heeft lege plekken gevuld met: “null” & 6 kaarten op eilanden

^

Meegezonden programmabeschrijvingen

Enkele van de inzendingen hebben mooie programma beschrijvingen mee geleverd, dit waarderen wij zeer en willen we graag delen met iedereen.

Bas Nieuwenhuizen:
http://www.tuintopia.nl/prog_wedstr/bnieuw_beschrijving.txt

Malthus:
http://www.tuintopia.nl/prog_wedstr/malthus_beschrijving.pdf

Darkstone:
http://gathering.tweakers...message/40679021#40679021

Soultaker:
http://gathering.tweakers...message/40422059#40422059

^

Afsluiting

Het begon een paar maanden geleden met een schijnbaar eenvoudige vraag, namelijk: wat is de topscore van een nieuw kaartspel met maar een paar spelregels? Na wat uitproberen bleek het toch een behoorlijk uitdagende vraag te zijn. Gelukkig hebben we een grote groep enthousiaste programmeurs gevonden die deze uitdaging aan durfden te gaan.

Het organiseren van een wedstrijd als deze was ook een uitdaging op zich, keer op keer de teksten over lezen in de hoop alle mogelijke vragen uit te sluiten en geen dubbelzinnige bewoordingen achter te laten, maar het is wel erg leuk om te doen.

We willen iedereen bedanken voor de resultaten, het elkaar helpen, ondersteunen (zo ver als een wedstrijd dit toe liet natuurlijk) en de mooie inzendingen.

Als laatste zijn felicitaties op z’n plaats, sowieso aan jullie allemaal, maar in het bijzonder aan onze 3 winnaren.

Daos, Ondanks het hangen bij testset 3 heeft jouw applicatie keer op keer uitstekende scores in bijzonder krappe tijden. Hierdoor win jij de Raspberry Pie B met accessoires en het kaartspel Tuintopia in het echt.

Soultaker, De enigste inzending die elke testset volledig goed heeft kunnen uitvoeren. Dit op zichzelf is al een prijs waard. Ook jij ontvangt van ons het kaartspel.

Malthus, Jammer van de fouten in testset 3, anders was jouw inzending een serieuze kandidaat om er met de hoofdprijs van door te gaan. Als nummer 3 ontvang jij ook het kaartspel.

[Anoniem: 303530]

Anoniem: 510923 schreef op maandag 26 augustus 2013 @ 22:55:
Darkstone: Is bij de scoreregel de ‘:’ en hoofdletter vergeten

Wel opvallend dat ik zo laag ben geëindigd. Ik kreeg op alle bijna alle testsets de optimale score. Misschien heb ik toch nog iets verprutst op de laatste dag.

[Pete]

Gefeliciteerd Daos, Soultaker en Malthus!

Niet helemaal onverwacht dit keer geen topscore voor mij De crash op testset3 had niet moeten gebeuren, maar het niet uit zichzelf eindigen is soort van correct.

De laatste avond had ik nog grote veranderingen aangebracht die misschien niet helemaal ten goede waren. Op de eerdere testsets werkte het ietsje beter, maar ik denk dat mijn originele code het hier beter zou hebben gedaan.

[DaCoTa]

Ik mis Eskimootje en mijzelf in de resultaten. En is de versie van Daos de 1e of 2e inzending? Zie Creepy in "[Programming Contest 5] Tuintopia" voor de deelnemerslijst zoals die na de sluitingsdatum is gegeven. (Ja, ik weet dat ik te laat was, maar ik had de verwachting dat mijn inzending wel mee zou draaien.)

[ Voor 17% gewijzigd door DaCoTa op 26-08-2013 23:09 ]

[Creepy]

De inzendingen die die te laat waren, en dus ook de tweede inzending van Daos, ga ik nog draaien. Maar dat wilde ik pas doen nadat de uitslag bekend is. En dat is nu

De inzending van Eskimootje was een fout van mij. Mijn zoekacties in mijn eigen mailbox leverde 1 resultaat teveel op: de inzending van Eskimootje op de tetris competitie van flink wat tijd terug

En gefeliciteerd aan de winnaars. Nog een leuk detail: Soultakers entry is singlethreaded. En malthus draaide verschillende type solvers tegelijk om zo meerdere threads te gebruiken.

[ Voor 19% gewijzigd door Creepy op 26-08-2013 23:22 ]

[Anoniem: 303530]

Er staat in mijn output wel een :. Is dat een foutje? De hoofdletter ontbreekt inderdaad.

Ik snap wel waarom ik een lage score haal. De testsets, zelfs de minst complexe, zijn significant complexer dan mijn eigen testsets. Zelfs mijn worst-case testset is minder zwaar.

Ter vergelijking, ik heb een complexiteitsberekening om de moeilijkheid van het veld in te schatten. Onder de 30 pakt hij standaard een optimaal codepad. Boven de 100 kapt hij na de eerste iteratie af omdat het anders te lang duurt.

De complexiteit van daos' mijn testvelden ligt tussen de 47 en 50. Uit de set van daos ia alles onder 010x010 van 'lage' complexiteit. De complexiteit van het eerste testveld uit de officiële set is 95, die van het 2e testset 175, bij de 3e overflowt de berekening en is het resultaat -inf waardoor hij het <30 codepad neemt. Oeps

Waarom hebben jullie zulke lastige velden gegenereerd? . Daar kan mijn algoritme niet goed mee om gaan.

[ Voor 7% gewijzigd door Anoniem: 303530 op 27-08-2013 02:19 ]

[BNieuwenhuizen]

Ik heb de wedstrijd dus verloren op afhandeling van whitespace aan het eind van de regel. Mijn code negeert die niet en krijgt dus problemen met strings als levert\t.Als ik de whitespace negeer krijg ik voor TS3 en TS4 in luttele seconden 1022 en 2974.

Waarom is TS4 eigenlijk maar getest voor 2 spelers?

Overigens heet ik Bas, niet Bart.

[Creepy]

TS4 is gedraaid omdat na TS3 er een gelijke eindstand was (zie laatste kolom in de tabel)

[Anoniem: 510923]

@BNieuwenhuizen

Hoi Bas! Wat Creepy zegt klopt. Ik heb de post aangepast, ik hoop dat het nu duidelijk is!

Ik heb ook je naam aangepast. Die resultaten die je thuis krijgt klinken trouwens wel vet!

[Vaan Banaan]

Ik begrijp testset 3 niet, die vreet mijn programma (nooit afgemaakt) niet vanwege de input/output regel:

De volgende key is "input", hierachter staan de inputs voor deze kaart. Hierna
komt de key "output". Er zijn maximaal 4 inputs en 4 outputs per kaart en ....

code:

[deeeuwigestudent]
wind=
windbeschutting=
schaduw=
input=water,nectar,voedsel,stro,stroom,afdak,plaagbestrijders,afvalwater,bevruchting,plantenresten
aantal=6
zon=nodig
output=mest

[dehoorndesovervloeds]
aantal=4
input=
output=voedsel,stro,water,nectar,stroom,afdak,plaagbestrijders,mest,afvalwater,bevruchting,plantenresten
zon=nodig
schaduw=
wind=
windbeschutting=

Hoe moet ik dat interpreteren? Die kaarten ongeldig maken en volledig negeren?

[Malthus]

Anoniem: 510923 schreef op maandag 26 augustus 2013 @ 22:55:

Bijzonderheden Testset 3(TS3)

Maltus: Heeft het datacenter te vaak gebruikt & 10 kaarten op eilanden

datacenter te vaak gebruikt: Een dag voor de deadline kwam ik er opeens achter dat sommige oplossingen van mijn programma niet correct waren. Bij foute oplossingen werd meestal een kaart teveel gebruikt (en waarschijnlijk verdween ergens anders een kaart zodat het aantal kaarten gelijk bleef). Helaas trad deze fout niet altijd op en was daarom moeilijk te vinden. Ik heb nog eens extra naar de cross-over gekeken omdat ik daar het probleem verwachte, maar ook daar kon ik het niet snel genoeg vinden. En uiteindelijk had ik te weinig tijd om het probleem op te lossen...

10 kaarten op eilanden: Hier heb ik de regels niet goed genoeg gelezen of niet lang genoeg over nagedacht. Ik had in ieder geval helemaal niet over eilanden nagedacht totdat iemand het (na de deadline) noemde.

Ondanks beide problemen toch nog derde geworden, en bovendien nog wat geleerd. Allemaal bedankt voor deze leuke wedstrijd!

En ik ben klaar voor Programming Contest 6.

[Soultaker]

Gefeliciteerd Daos! Een terechte winnaar, lijkt me, zeker als je naar de gebruikte processortijd kijkt.

[joram.agten]

Proficiat Daos Soultaker en Maltus.
Mijn oplossing had duidelijk nog last van bugs. Maar zelfs als die eruit zijn dan haal ik nog niet de snelheid van de winnaars.

Ik vond het een leuke opgave en houd me zeker klaar voor Programming Contest 6.

[liquid_ice]

@Vaan Banaan, Je hebt gelijk dat dit op z'n minst een onduidelijkheid was in de OP en de regel set, erg knap dat je deze gespot hebt.

Verderop in de regels staat namelijk ook:

code:

Om te voorkomen dat jullie een clustertje huren en de uitkomst hardcoded implementeren
houden we een aantal variabelen open:
- De aantallen van de kaarten
- De eigenschappen van de kaarten (welke inputs en outputs)
- De grootte van het speelveld
- Waar het huis staat.

De uiteindelijke Validator die ik geschreven heb heeft de insteek gehad om zowel het speelveld, de kaarten als OOK het resultaat te valideren.

Deze validator heeft online gestaan en voor meerdere weken was er ruimte voor en heb ik gevraagd naar input, bugs en onvolkomenheden. Tevens is er afgesproken dat de validator heilig verklaard zou worden en dat deze daarmee dus onbetwistbaar is.

De Validator kijkt niet naar het aantal inputs en outputs van de kaarten, en dat is nu dus ook officieel zo.
Natuurlijk hoop ik dat deze onduidelijkheid niemand punten heeft gekost, het zou erg jammer zijn als dit wel zo is.

Ik wil niet bot overkomen, maar neem hierin wel het volgende standpunt in:
De Validator heeft gesproken

[ Voor 4% gewijzigd door liquid_ice op 30-08-2013 10:31 ]

[Corniel]

Gek dat er kennelijk een bug in mijn uiteindelijke versie is geslopen. Alle door mij verzonnen proefsets leverden volgens mij gelijksoortige oplossingen. Maar goed. het was leuk, en niet mijn beste deelname ooit.