[Programming Contest 5] Tuintopia

[joram.agten]

damn, ik heb nog een bug, afhakelijk van de volgorde van het platsen van de kaarten kom ik een andere score uit, soms

[CodeCaster]

Van bugs heb ik niet per se last, maar ... heeft er nog iemand een boek over algoritmes te leen?

@SoulTaker grappig oneindig countdown-plaatje, maar Chrome laat de tab-spinner continu draaien.

[ Voor 34% gewijzigd door CodeCaster op 16-06-2013 08:12 ]

[Verwijderd]

CodeCaster schreef op zondag 16 juni 2013 @ 08:09:Van bugs heb ik niet per se last, maar ... heeft er nog iemand een boek over algoritmes te leen?

Ik vind https://www.edx.org/cours...tificial-intelligence/579 erg goed. Die komt om de paar maanden langs

@SoulTaker grappig oneindig countdown-plaatje, maar Chrome laat de tab-spinner continu draaien.

Streaming gif, jeweettoch . Het gif bestandsformaat heeft geen voorgedefinieerde grootte, wel een 'dit is de laatste frame' indicatie. Als je die nooit zend blijft de verbinding open, en kan je steeds nieuwe frames pushen.

Edit: zo, alles gefixt. Nu nog even de documentatie corrigeren..

[ Voor 4% gewijzigd door Verwijderd op 16-06-2013 10:00 ]

[Verwijderd]

.

[ Voor 99% gewijzigd door Verwijderd op 16-06-2013 10:14 ]

[liquid_ice]

joram.agten, heb je al een idee in welke hoek van de berekening dat het um zit?
De inputs, outputs, zon, wind of het huis misschien?

De validator begint vormen aan te nemen.
De files worden ingelezen (lekker streng) en het bord wordt gevuld.
Vandaag beginnen aan de punten berekening en verdere verificaties.

[ Voor 40% gewijzigd door liquid_ice op 16-06-2013 10:30 ]

[Daos]

CodeCaster schreef op zondag 16 juni 2013 @ 08:09:
heeft er nog iemand een boek over algoritmes te leen?

Ik vond How to Solve it: Modern Heuristics wel geinig en makkelijk te lezen. Het bevat ook leuke puzzeltjes tussendoor. Combinatorial Optimization en Introduction to Algorithms heb ik ook thuis, maar daar moet je je echt doorheen ploeteren.

[Creepy]

Kom maar op met die e-mails!

[Malthus]

Creepy schreef op zondag 16 juni 2013 @ 15:05:
Kom maar op met die e-mails!

Ik heb vandaag nog een gruwelijke bug uit mijn zoekalgoritme opgelost, en een heleboel commentaar getypt. En ik moet nog een beschrijving maken, dus ik ben bang dat ik alle beschikbare tijd tot aan de deadline nodig heb.

[Soultaker]

Same here; ik was vanmiddag pas begonnen met m'n oplossings-algoritme (wel eerder een checker geschreven, dat scheelt!)

Als ik alle bugs eruit heb ga ik zo een testrun doen terwijl ik avondeten maak, en hopelijk werkt alles dan naar behoren. (Nette code of veel commentaar hoef je van mij in ieder geval niet te verwachten )

[Daos]

Wel een middelbare-school-mentaliteit om pas op het laatst hard te werken.

Overigens heb ik daar wel een leuke herinnering aan: bij een scheikundeleraar was ook een deadline om middernacht; hij had er een feestje bij hem thuis van gemaakt met bier enzo. Misschien een ideetje voor de volgende keer...

Er was wel vandaag een feestje waar je naar toe kon: het Tuintopia-intro-feest. Iemand daar nog geweest?

[Verwijderd]

Zo. Die is verstuurd.

Voor de geïnteresseerden:

004x003_+003/   26    47 ms (maar soms ook <16ms, afhankelijk van timer precisie / print zut)
005x003_+002/   71    438 ms
005x004_+001/   62    19873 ms
005x004_+003/   68    32250 ms
005x004_+029/   93    1422 ms
005x004_-001/   59    36160 ms
010x010_+000/   545   94 ms (maximale score in dit topic: 599)
017x013_+020/   1384  297 ms (maximale score in dit topic: 1439)
topicstart/     98    60972 ms

In vergelijking met pete: verlies met ~7x marge op 005x003_+002/, winst op de rest van de velden (met 3-10x marge, behalve de eerste). Als de deadline voorbij is zal ik even de highlights van mijn algoritme benoemen.

CPU = sandy bridge quadcore 2.6 ~ 3.0 Ghz, max geheugengebruik ~600MB. Als ik hem langer door laat rekenen begint bij enorm te slurpen en raakt zelfs mijn gloednieuwe 16GB vol binnen de tijd

[Creepy]

Daos schreef op zondag 16 juni 2013 @ 20:48:
Wel een middelbare-school-mentaliteit om pas op het laatst hard te werken.

Overigens heb ik daar wel een leuke herinnering aan: bij een scheikundeleraar was ook een deadline om middernacht; hij had er een feestje bij hem thuis van gemaakt met bier enzo. Misschien een ideetje voor de volgende keer...

Er was wel vandaag een feestje waar je naar toe kon: het Tuintopia-intro-feest. Iemand daar nog geweest?

Dan leggen we deadline de volgende keer op zaterdag 23:59. Kijk ik of we een feestje kunnen regelen . Ik had even langs willen gaan bij het tuin topia feestje maar gezien vaderdag kon ik dat niet naken

[Soultaker]

Daos schreef op zondag 16 juni 2013 @ 20:48:
Wel een middelbare-school-mentaliteit om pas op het laatst hard te werken.

Niet als je niet op de middelbare school zit en juist belangrijkere dingen te doen hebt dan huiswerk maken.

Sowieso is 't ook voor de uiteindelijke winnaar wel leuk als er een redelijk aantal tegenstanders zijn (ook al zijn hun programma's last-minute in elkaar gehackt).

edit:
Zo, alle bugs zijn gefixt. Ik zal m'n programma eens op die testdata van Corniel runnen terwijl ik eten maak, dan kan ik zo ook nog posten om mensen te vermaken die hun code al ingestuurd hebben.

[ Voor 18% gewijzigd door Soultaker op 16-06-2013 21:21 ]

[DaCoTa]

Ik heb zojuist pas mijn eerste score... Wellicht wat laat, maar heeft iemand misschien een validator die mijn score kan doorrekenent? Het gaat om de standaardset.

code:

Score:87
[terras][dierenstal][huis][huis][rijbessen][terras]
[notenboom][vijver][notenboom][insectenhotel][vijver][insectenhotel]
[rijbessen][mesthoop][kas][mesthoop][groentetuin][groentetuin]

[Malthus]

DaCoTa schreef op zondag 16 juni 2013 @ 21:59:
Ik heb zojuist pas mijn eerste score... Wellicht wat laat, maar heeft iemand misschien een validator die mijn score kan doorrekenent? Het gaat om de standaardset.

code:

Score:87
[terras][dierenstal][huis][huis][rijbessen][terras]
[notenboom][vijver][notenboom][insectenhotel][vijver][insectenhotel]
[rijbessen][mesthoop][kas][mesthoop][groentetuin][groentetuin]

Volgens de puntenteller van Daos klopt jouw score.

[ Voor 6% gewijzigd door Malthus op 16-06-2013 22:04 . Reden: Linkje naar Puntenteller-bericht van Daos toegevoegd ]

[DaCoTa]

Dankdank! Er was toch een puntenteller. Ik dacht al zoiets maar kon hem in de stress niet meer vinden. Stress is funest voor google-fu.

[Malthus]

@DaCoTa: ik heb jouw output ook nog even door mijn eigen puntenteller gehaald en die komt (gelukkig) ook op dezelfde score uit.

En ik heb zojuist mijn programma ingestuurd .

Door tijdgebrek wel heel veel dingen niet geprogrammeerd (en veel te weinig unit-tests gemaakt). Ik gebruik een genetisch algoritme, dus het is lastig om scores te vergelijken (want deze zijn ieder keer anders), maar ik kom redelijk in de buurt van de scores die tot nu toe genoemd zijn. Ook met de test-set 105x184_+000 kom ik nog tot een antwoord. Maar als het om de tijd gaat, dan verlies ik flink, want ik pak altijd de volledige vijf minuten.

[Soultaker]

Mijn resultaten:

0000 Score:98
004x003_+003 Score:26
005x003_+002 Score:71
005x004_-001 Score:59
005x004_+001 Score:61
005x004_+003 Score:68
005x004_+029 Score:93
010x010_+000 Score:560
017x013_+020 Score:1424
048x039_+040 Score:15201
061x043_+172 Score:22128

(En de laatste kom ik niet uit.)

edit:
Hm, multithreading levert nogal weinig op. Jammer, maar ik heb geen tijd meer om 't te verbeteren of eruit te slopen.

[ Voor 17% gewijzigd door Soultaker op 16-06-2013 23:31 ]

[Verwijderd]

Heel mooi dat er een paar last minute acties bij zijn gekomen. Die last minute mentaliteit is mij ook niet vreemd. Anders had ik de validator al gehad, haha.

Nog een avondje de punten telling erin hangen en dan een avond testen met Arjan.

Ik denk dat de Validator komend weekend online komt ter review aan U allen.
(Mocht iemand dan nog C# gerelateerd commentaar hebben ben ik er ook geïnteresseerd in)

Dan zal ook de definitieve testsets aan Creepy zijn aangeleverd.

[ Voor 7% gewijzigd door Verwijderd op 16-06-2013 22:48 ]

[Daos]

somename == liquid_ice ??

[Creepy]

somename == liquid_ice ja. En aangezien cloontjes niet zijn toegestaan.. oh well

[Pete]

En verstuurd.

Helaas te weinig tijd gehad deze week om het goed af te maken. Ik hoop maar dat alles nu werkt...

[joram.agten]

@liquid_ice ik vermoed iets met het huis en de zon/schaduw, ofwel huis met wind/windbeschutting
Ik heb net mijn commentaar in de code getyped; en toch nog wat gerefactored en precies nog een typo of 2 opgelost in de score berekening (of nieuwe fouten bijgemaakt). Maar er is niet echt tijd meer om veel na te kijken, en unit tests schrijven en dingen met de hand berekenen...
Dat had ik beter vorige week gedaan precies.

[joram.agten]

en mijn inzending is ook verstuurd (om 11u56), tot nu toe kom ik altijd tot een oplossing voor eender welk speelveld van de TestSets.
Ik reken wel altijd 5 minuten met veel Threads. De gevonden eindscore is nogal random de hoogste ;-)

Ik heb net nog 3 uurtjes commentaar in mijn code getyped, maakt het geheel toch iets leesbaarder.
Maar mijn echte "slimme" ideeen voor algoritmes heb ik helaas niet kunnen implementeren.

Ik had al lang een initiele versie in python, maar de Global Interpreter Lock speelde me parten voor de performance. Gisterenavond dan "even" alles herschreven in Java en een nachtje doorgedaan.

Vandaag had ik andere verplichtingen, enkel nu nog een beetje tijd gevonden om het geheel wat op te schonen
met commentaar.

Ik ben benieuwd...

[DaCoTa]

Ook ingeleverd. En nog een keer... Ik ben het niet meer gewend om java van de commandline te starten dus daar ging nogal wat mis. Erg frustrerend om het laatste kwartier uit te zoeken hoe dat ook alweer zat met classpaths terwijl er ook nog een bug in de tree pruning zit. Ben bang dat het allemaal niet ok is.

[ Voor 65% gewijzigd door DaCoTa op 17-06-2013 00:29 ]

[Daos]

DaCoTa schreef op maandag 17 juni 2013 @ 00:28:
[afbeelding]

Was je nog op tijd?

[DaCoTa]

Daos schreef op maandag 17 juni 2013 @ 00:29:
[...]

Was je nog op tijd?

Ach, wat is nou een kwartier op een mensenleven ;-)

[F.West98]

DaCoTa schreef op maandag 17 juni 2013 @ 00:46:
[...]

Ach, wat is nou een kwartier op een mensenleven ;-)

Het verschil tussen leven en dood?

[CodeCaster]

Ik geef het op, ik heb door een verkeerde insteek code geschreven waar ik absoluut niet trots op ben en die ook nog eens de helft van de hier genoemde scores haalt. Weer wat geleerd, en ik zal eens een boek of twee kopen. Bedankt voor de suggesties.

[ Voor 12% gewijzigd door CodeCaster op 17-06-2013 00:51 ]

[Verwijderd]

Mijn algoritme, is gebaseerd op een vrij recht-aan A* implementatie.

Je hebt een State (repressentatie van een stap in het probleem) bestaande uit een map (1D, alles is 1-dimensionaal), een score, een heuristic, en een array met hoeveel kaarten er nog aanwezig zijn in het deck. Meer hierover later.

Verder heb je een Node, dat is een soort van abstracte representatie van het probleem. Ik denk dat ik hier de meeste winst heb gepakt ten opzichte van de moordende concurrentie . Het 'probleem' bestaat uit een linked list van Node, elke node bevat een positie, maximaal 4 buren (als in, een integere positie) en een interne score lookup array. Hiermee kan snel de score bij een bepaalde kaartzet worden berekend. Elke node bevat zijn eigen score lookup array. Wat schiet je daarmee op? Het berekenen van de score van een veld is zo simpel als:

C++:

int Node::whatIf(const CardID *map, const CardID &c) const
{
    scoreType score = 0;
    scoreArrEntry* cacheLine = &scoreArr[ amountOfCards * c ];

    switch ( amountOfNeigbours )
    {
        case 4:
            score += cacheLine[ map[ cardPositions[ 3 ] ] ][ 3 ];
        case 3:
            score += cacheLine[ map[ cardPositions[ 2 ] ] ][ 2 ];
        case 2:
            score += cacheLine[ map[ cardPositions[ 1 ] ] ][ 1 ];
        case 1:
            score += cacheLine[ map[ cardPositions[ 0 ] ] ][ 0 ];
//        case 0:
            return score;
        default:
#if defined(_MSC_VER)
            __assume( 0 );
#else
            __builtin_unreachable();
#endif
    }
}

Het ziet er ingewikkelder uit dan het is. Ik had ook een branchless versie gemaakt met wat template & virtual methods, maar die bleek ~10% trager.

En je zegt dat een Node maximaal 4 buren heeft, het zijn er toch 8? Ja en nee, ik had gemerkt dat de volgorde waarin je het probleem oplost erg belangrijk is voor runtime. Daarom wordt er bij het opbouwen van de probleem representatie een BFS gedraaid om de optimale volgorde te berekenen. Hoe vroeger in het spel de connecties worden gemaakt, hoe sneller het algoritme draait. Resulterend in maximaal 4 connecties. Een connectie wordt pas gemaakt wanneer een kaart naast een andere kaart komt te liggen.

Ten slotte bestaat er een max-heap implementatie. De naam max-heap is misleidend, intern is het een soort van hash table die dynamisch resized (vector van vectors). Nieuwe States kunnen dan altijd in O(1) worden geplaatst of opgehaald totdat de gebruikte vector reallocate waardoor de concurrency drastisch afneemt.... Wie regelmatig in de devschuur komt had opgemerkt dat ik dat op probeerde te lossen door een linked list van vectors te gebruiken zodat het resizen vermeden wordt. Maar dat vertraagde de boel nogal, met name omdat het destructen op de een of andere manier gruwelijk traag is. Om het reallocaten zo efficiënt mogelijk te maken bestaat een State gewoon uit een pointer naar een stukje memory (8 bytes per stuk @ x64)

De concurrecy was een groot probleem. Daar ga ik mettertijd nog eens een topic over openen. 8 threads op een 'lastig' probleem, oke, maar als het aantal threads verder toeneemt of het probleem simpeler wordt, brengen de threads de meeste tijd door met het knokken om mutexen. Als je algoritme met 8 threads half zo snel is als met 3 threads, dan ben je niet happy.. Bij de meeste problemen schaalt het vrij aardig en wordt iets van ~4x speedup behaald over 4 cores (met elk 2 threads).

Wat betreft de heuristics, ik heb er 2: een welke altijd een lagere of gelijke score teruggeeft, en een welke altijd een hogere of gelijke score teruggeeft. Respectievelijk werken deze door middel van een DFS (gewoon het complete probleem afhandelen op basis van best-first), en door van elk leeg veld de maximale score te bruteforcen. Waarbij de bovengenoemde score lookup array uitstekend van pas komt . Deze 2 functies nemen respectievelijk 10% en 85% van de runtime in beslag. Ik denk dat er veel winst zit in het verbeteren van de heuristics, maar dat is mij niet gelukt. Bovendien heeft heuristic1 een groot probleem: hij is namelijk erg onstabiel. Bij een bepaalde testcase kon hij een score teruggeven tussen de 28 en 42 op exact dezelfde map als ik de kaarten in een andere (uniform random) volgorde doorgaf.

Om een zeker maximum te vinden wordt het algoritme meerdere keren uitgevoerd: de eerste keer is de invloed van heuristic1 100% en de invloed van heuristic2 0%. Daarna neemt de invloed van heuristic1 elke keer af met 20% en de invloed van heuristic2 evenzoveel toe. Naarmate de invloed van heursitc2 toeneemt duurt het steeds langer om tot een oplossing te komen. Aangezien heuristic2 admissable is weten we zeker dat de gevonden score optimaal is bij heuristic2 = 100%. Overigens geraak je bij de meeste problemen uit mem als je dat probeert.

Ja maar hoe beslis je dan wanneer je stopt? Simpel maar effectief: de tijd die nodig was om het algoritme 'de vorige keer' te draaien wordt vermenigvuldigd met 10. Is dat lager dan de tijd die we nog over hebben? Dan gaan we het proberen. Ik heb veel tijd besteed aan het verzinnen van een relatie tussen het veld en de 'moeilijkheid' van het oplossen, maar dat is op niets uitgelopen, vermoedelijk omdat het berekenen van de complexiteit het zo 'lastig' (als in tijdscomplexiteit) is als het oplossen van het probleem zelf. Bovenstaande uitzonderlijk triviale oplossing stopt in geen enkel veld wat ik kon genereren te vroeg, maar toch wordt er nooit veel te lang doorgegaan met rekenen.

Dat waren de highlights uit mijn bijna 5k regels code. Wat voor truuks hebben jullie toegepast?

[Soultaker]

Eigenlijk verschilt mijn aanpak niet eens zoveel, hoewel ik niet echt aan optimaliseren toegekomen ben. In het bijzonder precompute ik ook met een BFS de volgorde waarin kaarten worden neergelegd (en de richtingen waarbij dan naar buurkaarten gekeken moet worden) en heb ik mijn queue geïmplementeerd met een vector van vectors (eigenlijk deques, maar dat hadden achteraf gezien best vectors kunnen zijn). Ook precompute ik natuurlijk hoeveel punten iedere combinatie van kaarten oplevert.

De kern van m'n algoritme bestaat uit een soort van breadth-first search over de probleemruimte, waarbij ik om tijd/ruimte te besparen bij elke iteratie in plaats van de volledige breedte van de zoekboom een maximaal aantal states bijhoudt (en wel de meest waardevolle states die ik gevonden heb).

Omdat ik ook niet weet hoeveel states ik per iteratie kan queuen binnen de tijdlimiet, begin ik gewoon met een lage limiet en verdubbel ik die steeds. Dat is verre van optimaal, maar het is een relatief simpele manier om de hoeveelheid werk die je doet een beetje aan te passen aan de tijd die je beschikbaar hebt.

Ik had graag nog iets willen doen met:
• A*-stijl heuristics,
• elimineren van equivalente states.
Eigenlijk de dingen die ik in het vorige topic juist wél had geïmplementeerd. Geen idee of dat erg veel opgeleverd had — als ik het zo zie komen mijn scores al redelijk in de buurt van de meer verfijnde implementaties (hoewel die kleine verschilen natuurlijk net wel bepalend kunnen zijn voor de uitslag van de contest).

Ik denk dat het gebrek aan heuristic mijn algoritme parten gaat spelen, maar uit uit eigenbelang hou ik m'n mond even over de details tot de jurering achter de rug is.

Re: thread support: zelf heb ik die op het laatste moment uit m'n programma gesloopt omdat 'ie niet perfect werkte en ik geen zin had om multithreading bugs te fixen een half uur voor de deadline. Ik zou denken dat zo'n algoritme redelijk goed te paralleliseren zou moeten zijn (er is nauwelijks data contention) maar in de praktijk leek het tegen te vallen — waarom weet ik nog niet precies.

Mijn code beslaat zo'n 700 regels, waarvan ~300 voor de solver, ~200 voor de checker, en de rest voor IO. Ik denk dat deze twee het interessantst zijn:
• Configuration.h, beschrijft de datastructuur die de invoer representeert.
• solver.cpp, de daadwerkelijke solver.

[DaCoTa]

Mijn aanpak verschilt wel, voornamelijk omdat ik geen aanpak had. Ik ben eigenlijk pas op de laatste dag aan de solver begonnen, ik heb daarvoor in de tijd die ik had enorme omzwermingen gehad in datamodel en opslag, maar het meeste daarvan weer overboord gegooid. Wat ik overhield was een precalculated score voor alle kaarten in alle richtingen, zodat dat deel in ieder geval snel zou zijn.

Mijn aanpak is simpel: een brute-force BFS, sorteer alle mogelijkheden op gemiddeld aantal punten per buurman (dus bij een nieuwe kaart is 3 punten over 1 connectie beter dan 2 punten over 2 connecties). Gooi deze velden weer terug in een gesorteerde set. Ga zo door tot je een oplossing heb en gooi dan alle velden weg die nooit meer boven deze score uit kunnen komen. Rinse and repeat tot de tijd op is. Dit in 3 uurtjes geschreven.

Verdere opmerkingen: ik heb alleen getest met de standaard set. Wat er met grotere velden gebeurd, geen idee, waarschijnlijk out of memory. Minder kaarten dan velden geeft waarschijnlijk een NPE of een ArrayIndex ofzo. De output gaat naar console, ipv output.ini (strafpunten!) en ben de source en documentatie vergeten.

Ik merk wel dat ik erg stroef ben in algoritmiek, voornamelijk omdat ik het in mijn werk vrijwel nooit nodig heb. Maar als afgestudeerd A.I.-er zou ik toch beter moeten weten. Ik ga weer even de literatuur aanhalen

[Daos]

Beschrijving van mijn algoritme:
Het is een 'local search' die afwisselend twee dingen doet:
- kaart op het speelveld vervangen door kaart in de hand als dat hogere punten oplevert.
- twee kaarten op het speelveld verwisselen met elkaar als dat hogere punten oplevert.

Omdat een local search kan blijven hangen in een lokaal optimum wordt er met meerdere random beginvelden gestart. In 5 minuten zijn er op mijn pc 40000 iteraties mogelijk. Een handje vol iteraties lijkt al voldoende. Om te zorgen dat het programma snel stopt is dit begrensd tot 100.

[Verwijderd]

Ik had wat spectaculairders verwacht dan 'doe wat randoms, stop na X pogingen'

[DaCoTa]

Ben toch nog even doorgegaan. Mijn ingeleverde code werkt niet met de andere testsets (hij accepteerd geen cijfers in kaartnamen). Daarnaast doet hij veel te veel. Mijn originele code haalt 88 op de testset. Als ik nog een paar kleine wijzigingen doorvoer kom ik op de volgende scores:

Met wat kleine aanpassingen kom ik op:
testset: 97
004x003_+003: 23
005x003_+002: 66
005x004_-001: 44
005x004_+001: 45
005x004_+029: 85
010x010_+000: 462
017x013_+020: 1246
048x039_+040: 13037
061x043_+172: 18312
105x184_+000: no score (teveel kaarten, gebruik byte als kaartindex)

Alle scores die er zijn worden binnen een paar seconden gehaald. Ik heb ze niet allemaal laten doorlopen maar ik denk dat er bij de grotere geen hogere scores gehaald worden.

Maargoed, dit is dus niet de code die ik ingeleverd heb Ik denk dat ik nog een dag nodig had om het wat robuuster te maken. Les geleerd.

[Creepy]

Om even het totaal beeld te geven: In totaal zijn er 9 inzendingen die meedoen voor de prijzen.
Op willekeurige volgorde:

• Corniel
• Eskimootje
• Darkstone
• BNieuwehuizen
• Malthus
• joram.agten
• <nickname>^WSoultaker
• Daos
• Pete

Dan hebben we nog twee inzendingen die we voor de eer mee laten doen maar geen kans maken op de prijzen:

• Daos (een verbeterde versie van de eerst ingezonden entry)
• Dacota (ingestuurd na de deadline)

Mocht je toch iets ingeleverd hebben maar je nick staat niet in de lijst, laat het dan even weten, dan spit ik mijn e-mails nog een keertje door

De test set wordt nog aan gesleuteld, evenals de code voor de validator. Zodra die definitief zijn zal ik de entries gaan runnen. Het systeem waar de entries op gerunt gaan worden:

• OS: Windows 7 64 bits of Linux mint 14 64 bits.
• Processor: Intel(R) Core(TM) i7-3610QM CPU @ 2.30GHz
• Geheugen: 16GB
• Mocht er een entry tussen zitten die daadwerkelijk de GPU gaat gebruiken: Radeon HD 7970M

[ Voor 7% gewijzigd door Creepy op 17-06-2013 22:18 ]

[raptorix]

Helaas geen tijd meer om het af te maken, er zat een fout in mijn berekening en kwam er maar slecht achter waar het aan lag, ook al omdat ik erg druk had op me werk waqt minder gemotiveerd, ik vond het in ieder geval een leuke opdracht, waar ik toch het nodige plezier aan heb gehad (en natuurlijk weer dingen geleerd ).

[Malthus]

Hoewel ik anderhalve maand geleden al zag dat er weer een programmeerwedstrijd was, had ik aan het einde toch wel een beetje last van tijdgebrek. Ik heb veel tijd gebruikt om verschillende dingen uit te proberen, en daar heeft mijn code toch wel veel last van. Ik ben bang dat in sommige classes bijna de helft van de methodes niet meer gebruikt wordt.

Ik heb een Java-programma gemaakt dat willekeurig kaarten neer legt, een genetisch algoritme, een 'netwerk'-programma dat op niets is uitgelopen, en uiteindeijk nog een depth-first zoekprogramma. Dit zoekprogramma heeft echter het meeste last gehad van tijdgebrek, op de laatste dag heb ik er nog een gruwelijke bug uitgehaald, en misschien was het niet de laatste.

Ook het optimaliseren is niet helemaal gelukt, want dat is eigenlijk een beetje meegegroeid. Zo heb ik een cache voor de scores die bepaalde kaarten opleveren. Deze cache bestaat uit een hashmap en wordt tijdens het evalueren van de oplossingen opgebouwd. Ik had echter veel beter van te voren een array met alle mogelijke combinaties kunnen uitrekenen, dan was de toegangstijd veel beter.

Uiteindelijk heb ik een aantal ideeën samengevoegd. Deze worden op verschillende threads uitgevoerd en zo nu en dan wisselen ze de beste resultaten uit. Hierdoor voedt het zoek-algoritme een redelijk goede oplossing aan mijn genetisch algoritme, en die kan proberen om er nog iets moois van te maken. Soms gaat dat best goed en kom ik in de buurt van de scores die in dit topic zijn gepost, en soms lijkt het helemaal nergens op.

Conclusie, ik heb weer veel te veel tijd aan de verkeerde zaken besteed...

[Daos]

Ik had veel mazzel. Mijn eerste poging was een depth-first search die niet veel opleverde:

Daos schreef op donderdag 25 april 2013 @ 20:53:
Na 10 minuten brute-force/depth-first search zit ik pas op:

code:

Score:61
[graanveld][vijver][huis][huis][notenboom][insectenhotel]
[dierenweide][graanveld][groentetuin][insectenhotel][notenboom][groentetuin]
[bijenkorf][bijenkorf][bloemenveld][boomgaard][compostvat][dierenstal]

Volgens mijn schatting kan het nog een paar dagen duren. Dit gaat hem dus niet worden...

De volgende dag als tweede poging een 'local search' gemaakt waarmee ik zo snel op het optimum zat dat ik hem maar meteen had ingeleverd (helaas met bugje en het kon nooog sneller).

[liquid_ice]

Gave nabespreking zo, ik moet de posts van Darkstone nog eens goed in me laten inwerken, want ik begrijp het nog niet helemaal.

De eerste avond dat ik zelf een eerste poging deed om dit probleem brute force op te lossen had ik de complete punten berekening en het brute force progje er omheen in 1 avondje erin zitten.
Nu ik het opnieuw in C# probeer heb ik nog alleem maar de basis IO punten in 1 avond erin zitten.

Andere avond dan maar verder met de Wind en de Zon.

[liquid_ice]

Zo, de validator 0.2 is af.

Ik heb geen unittesten, maar wel integratie testen (heb de door jullie geposte oplossingen gebruikt)

er zitten nog wel een paar fouten in die ik moet uitzoeken, maar dat komt een andere avond.

[liquid_ice]

Zijn er nog wensen mbt de output van de validator?

[Daos]

liquid_ice schreef op vrijdag 21 juni 2013 @ 17:48:
Zijn er nog wensen mbt de output van de validator?

- Punten per kaart
- Score/Totaal aantal punten (= helft van som alle punten per kaart)
- Of de score in output.ini correct is

[liquid_ice]

Ik bereken niet alle punten dubbel, maar heb gekozen om maar gewoon de helft van de punten te berekenen.

Door die keuze vallen sommige punten juist op de ene, of de andere kaart.
Dat maakt het lastig om mijn "punten per kaart" te vergelijken met de "punten per kaart" van anderen.

[Daos]

10. Het geven van foute uitvoer betekent niet meteen dat je "af" bent, maar elke foute kaart wordt als lege kaartlocatie beschouwd. Grote fouten kunnen zelfs leiden tot diskwalificatie en foltering.

Verder ivm de foltering:
- Of het veld de juiste grootte heeft,
- Of het huis op de juiste plek staat.
- Of er niet teveel kaarten van een soort zijn neergelegd.

[CodeCaster]

Of er minstens één kaart aan het huis aansluit en er geen kaarten los liggen?

quote: OP

Elke beurt leg je een kaart aansluitend aan de al bestaande kaarten aan.

[ Voor 63% gewijzigd door CodeCaster op 21-06-2013 19:17 ]

[Daos]

CodeCaster schreef op vrijdag 21 juni 2013 @ 19:15:
Of er minstens één kaart aan het huis aansluit en er geen kaarten los liggen?

Kaarten mogen toch los liggen?

Je hoeft dacht ik niet alles te vullen:

Mocht je een leeg veld innemen in je uitkomst, dan gebruik je de blokhaken zonder tekst erin, dus zo: "[]"

.

[ Voor 20% gewijzigd door Daos op 21-06-2013 19:30 ]

[liquid_ice]

CodeCaster schreef op vrijdag 21 juni 2013 @ 19:15:
Of er minstens één kaart aan het huis aansluit en er geen kaarten los liggen?


[...]

Er mogen geen 'eilandjes' van kaarten zijn.
Elke kaart moet op een of andere manier aansluiten aan de anderen en zo een verbinding met het huis hebben.

[Daos]

liquid_ice schreef op vrijdag 21 juni 2013 @ 19:34:
[...]


Er mogen geen 'eilandjes' van kaarten zijn.
Elke kaart moet op een of andere manier aansluiten aan de anderen en zo een verbinding met het huis hebben.

Is er iemand geweest die daar rekening mee houdt?

[liquid_ice]

Ik vermoed dat eilandjes slecht zijn voor je punten

[CodeCaster]

Daos schreef op vrijdag 21 juni 2013 @ 19:38:
[...]


Is er iemand geweest die daar rekening mee houdt?

Klinkt als een leuke testset: een groot bord met het huis niet op een voorspelbare positie en naast het huis slechts één kaart in de kaarten.ini.

[Verwijderd]

Mijn algoritme gaat dan in elk geval fout.. Ik had over het hoofd gezien dat een kaart niet los mocht liggen.

Er zitten sowieso nog wel meer 'suffe kaartenset' corner cases in.

[liquid_ice]

Poeh, ik ben achter de 'laatste' bug gekomen.

Dit is een mooie, daarom wil ik um ook gewoon even delen.
Mijn validator heeft een testset van 26 speelvelden (uit dit topic) en berekent ze goed.
(ook een compliment aan jullie dat jullie het ook goed hebben).

Maar nu ik op het eind de "punten per kaart" op verzoek erin wilde maken ben ik tegen een probleem aangelopen. Namelijk, mijn punten per kaart zijn hoger dan de totale punten...
(wie voelt um al aankomen?)

In de kaarten.ini staan kaarttype defenities. Om dit te emuleren heb ik 3 classes gemaakt.
1 - Kaart type
2 - Kaarten deck
3 - CardCounter

In het Deck zit voor elk type een carc counter die bij houdt hoeveel kaarten er nog zijn en als je een kaart opvraagt geeft deze een pointer naar zijn kaart uit.

Wat er dus op neerkomt dat als kaart [2,3] en kaart [4,5] dezelfde kaarttype zijn dat ze ook het zelfde object in zijn en de punten van [2,3] bij de punten van [4,5] wordt getelt en omgekeerd.

pff, even denken hoe ik dit in C# ga oplossen.
Ik denk dat ik de CardCounter nieuwe kaart objecten moet laten maken oid.

[liquid_ice]

bug gefixed.

Ik moet wachten op Arjan om de validator daar online te zetten.

[Daos]

Mijn output.ini eindigt met een lege regel. Bij anderen is dit misschien zonder. Hou je hier ook rekening mee?

Stukje code:

C#:

private static void WriteOutput(PlayCard[,] play_field)
{
    using (StreamWriter file = new StreamWriter("output.ini"))
    {
        int score = CalcScore(play_field);
        file.WriteLine("Score:{0}", score);

        for (int i = y_count; i >= 1; i--)
        {
            for (int j = 1; j <= x_count; j++)
            {
                file.Write("[{0}]", play_field[i, j] == null ? "" : play_field[i, j].name);
            }
            file.WriteLine(); // hier had dan een if(i > 1) omheen gemoeten
        }
    }
}

[Soultaker]

Daos schreef op vrijdag 21 juni 2013 @ 19:38:
Is er iemand geweest die daar rekening mee houdt?

Ik was me in ieder geval van de restrictie bewust, hoewel ik er in m'n solver ook geen rekening mee gehouden heb. In m'n checker wel, en volgens mij checkt die ook al die andere dingen (huis op de goede plaats, alleen beschikbare kaarten gebruikt, enzovoorts).

edit:
Mijn checker is hier online te gebruiken.

[ Voor 12% gewijzigd door Soultaker op 23-06-2013 22:43 ]

[liquid_ice]

Daos, die lege regel is een goede.

Ik heb um in mijn testset opgenomen en het veranderd de results niet.

[joram.agten]

lap, nog minpunten voor mijn oplossing: die laatste newline in de output.

[Daos]

Soultaker schreef op zondag 23 juni 2013 @ 17:14:
edit:
Mijn checker is hier online te gebruiken.

Hij doet het bij mij niet. Als ik op check klik, krijg ik een leeg scherm.

joram.agten schreef op maandag 24 juni 2013 @ 10:57:
lap, nog minpunten voor mijn oplossing: die laatste newline in de output.

Ik had het al gemeld en het lijkt geen probleem te zijn.

Lap moest ik even opzoeken. Heb je vroeger veel Samson gekeken?

quote: http://www.vlaamswoordenboek.be/definities/term/lap

lap (interjectie)
Uitroep van ontsteltenis, teleurstelling, pech. Vergelijkbaar met “verdorie”.

Dit woord werd populair door de kinderserie Samson, waar het veelvuldig werd gebruikt om grove woorden met dezelfde lading te voorkomen

[joram.agten]

CodeCaster schreef op zaterdag 22 juni 2013 @ 00:49:
[...]
Klinkt als een leuke testset: een groot bord met het huis niet op een voorspelbare positie en naast het huis slechts één kaart in de kaarten.ini.

En waarbij die ene kaart dan minpunten geeft bij elke positie rond het huis via de wind/windbeschutting.

INI: speelveld.ini

[speelveld]
aantalveldenxas=6
aantalveldenyas=5
eerstehuisdeel=3,3

INI: kaarten.ini

[huis]
aantal=1
input=
output=
zon=
schaduw=
wind=levert
windbeschutting=nodig

[k001]
aantal=1
input=
output=
zon=
schaduw=
wind=levert
windbeschutting=nodig

En ja hoor, mijn oplossing gaat ook de mist in Ik lever mooi een output.ini met score:0
Erger nog, ik merk nu pas op dat ik [null] schrijf in output.ini voor een leeg veld. In mijn python prototype was dat wel in orde

Nog iets om mogelijks strafpunten voor te tellen: in output.ini staat er tussen Score:<< de door jou berekende score >> geen spatie.
Dat doe ik ook niet goed. En in mijn python prototype was dat ook in orde.
Grr, dat nachtje programmeren heeft al heel wat extra bugs opgeleverd.

offtopic:
Daos schreef op maandag 24 juni 2013 @ 12:37:
[...]
Lap moest ik even opzoeken. Heb je vroeger veel Samson gekeken?
[...]

Ik ben Vlaming, en hier wordt dat wel meer gebruikt. Maar om nou met Samson geassocieerd te worden is weer minder leuk.

[joram.agten]

Daos schreef op maandag 24 juni 2013 @ 12:37:

liquid_ice: Daos, die lege regel is een goede.
[...]
joram.agten: lap, nog minpunten voor mijn oplossing: die laatste newline in de output.
[...]
Daos: Ik had het al gemeld en het lijkt geen probleem te zijn.
[...]

Ik begreep: die lege regel is een goed check om strafpunten te tellen.
Maar naar ik nu begrijp wordt er bedoeld: Een output.ini met een lege regel op het einde is ook een goede output.ini.

[Soultaker]

Daos schreef op maandag 24 juni 2013 @ 12:37:
Hij doet het bij mij niet. Als ik op check klik, krijg ik een leeg scherm.

Fixed. Nooit code wijzigen zonder daarna te testen.

Ik ben het er trouwens mee oneens dat die newline op het eind fout is. Een tekstbestand bestaat uit regels die eindigen met newline characters. Een tekstbestand dat niet eindigt op een newline character is dus vroegtijdig afgekapt (tenzij het leeg is, dan bevat het 0 regels). De newline character weglaten is juist fout.

Ik weet dat Microsoft Kladblok er anders over denkt, maar dat is een belachelijke standaard. Alle traditionale tools die met tekstbestanden werken (awk, sort, sed, et cetera) printen een newline character achter elke regel (dus ook de laatste) ongeacht of die nu in de invoer stond of niet.

[ Voor 58% gewijzigd door Soultaker op 24-06-2013 22:25 ]

[Daos]

Soultaker schreef op maandag 24 juni 2013 @ 22:15:
[...]

Fixed. Nooit code wijzigen zonder daarna te testen.

Of betekende dat lege scherm soms dat er geen fouten gevonden waren? Hij laat nu output.ini zien en geeft een warning als bv de score niet goed is.

Ik ben het er trouwens mee oneens dat die newline op het eind fout is.

Wel of geen newline wordt beiden goedgerekend als ik het goed begrijp.

[Soultaker]

Daos schreef op maandag 24 juni 2013 @ 23:05:
Of betekende dat lege scherm soms dat er geen fouten gevonden waren?

Het betekende dat het Perl script dat de checker callt een parse error gaf.

Hij laat nu output.ini zien en geeft een warning als bv de score niet goed is.

Het idee is dat 'ie een gesanitizede output.ini print, waar ongeldige kaarten uit verwijderd zijn enzo (en inderdaad warnings voor dingen die niet kloppen op stderr, al verdwijnt dat onderscheid via de webinterface).

Als je uitvoer geldig is, dan krijg je geen warnings en inderdaad precies dezelfde uitvoer als je erin gestopt hebt. (Ik ben waarschijnlijk minder streng qua parsen dan de jury, maar ik ben wél strict als het gaat over gebruikte kaarten, verbonden met het huis, en dergelijke. Overigens denk ik niet dat veel mensen syntactisch foute uitvoer gegeven; het formaat is simpel en meer karakters toevoegen dan nodig lijkt me zinloos.)

Wel of geen newline wordt beiden goedgerekend als ik het goed begrijp.

Da's mooi. Ik blijf er bij dat wél een newline de standaard is, en géén newline afwijkend.

[joram.agten]

oei, nog een bug gevonden: bij het plaatsen van het huis doe ik

Java:

        // place the house on the board
        board.board[board.houseLeftPart[0]][board.houseLeftPart[1]] = "huis";
        board.board[board.houseLeftPart[0]][board.houseLeftPart[1] + 1] = "huis";

en 2 regels hoger zet ik in commentaar:

Java:

        // create a 2 dimensional array for the board, indexed [y][x]

dat moet dus worden

Java:

        // place the house on the board
        board.board[board.houseLeftPart[1]][board.houseLeftPart[0]] = "huis";
        board.board[board.houseLeftPart[1]][board.houseLeftPart[0] + 1] = "huis";

waardoor ik mijn huis op de verkeerde plaats zet x en y omgedraaid. Dat zal ook nog wel eens een leuke indexOutOfBoundsException kunnen geven.

[Soultaker]

Gaat dat niet al direct op de sample data fout? Immers bestaat (3,4) niet en (4,3) wel.

[liquid_ice]

Om alvast een voorbeeld van de validator output te geven:

code:

Score from file is: 26
12 points for the IOs (exl. house)
13 points for the IOs (incl. house)
3 points for the Wind/Cover (exl. house)
3 points for the Wind/Cover (incl. house)
10 points for the Sun/Shade (exl. house)
10 points for the Sun/Shade (incl. house)
TOTAL SCORE: 26
Score properly calculated


Underneath, the score for each card is printed split up for IO points, Sun/Shade & Wind/Cover
[X01:Y01]; IO score:00; Sun/Shade score:00; Wind/Cover score:00; Name:k003
[X02:Y01]; IO score:01; Sun/Shade score:00; Wind/Cover score:00; Name:k005
[X03:Y01]; IO score:00; Sun/Shade score:00; Wind/Cover score:00; Name:k002
[X04:Y01]; IO score:03; Sun/Shade score:00; Wind/Cover score:02; Name:k006
[X01:Y02]; IO score:02; Sun/Shade score:00; Wind/Cover score:00; Name:k005
[X02:Y02]; IO score:04; Sun/Shade score:02; Wind/Cover score:00; Name:k001
[X03:Y02]; IO score:00; Sun/Shade score:02; Wind/Cover score:00; Name:k002
[X04:Y02]; IO score:00; Sun/Shade score:02; Wind/Cover score:00; Name:k002
[X01:Y03]; IO score:00; Sun/Shade score:00; Wind/Cover score:00; Name:huis
[X02:Y03]; IO score:00; Sun/Shade score:00; Wind/Cover score:00; Name:huis
[X03:Y03]
[X04:Y03]


Underneath, the entire score bord is printed to show how it is filled
[H][H][ ][ ]
[X][X][X][X]
[X][X][X][X]

( Ik heb er met de hand in geedit, dus de scores kloppen niet meer )

[joram.agten]

Soultaker schreef op dinsdag 25 juni 2013 @ 16:15:
Gaat dat niet al direct op de sample data fout? Immers bestaat (3,4) niet en (4,3) wel.

Het is iets subtieler: eerstehuisdeel=3,3 gaat nog wel, want ik tel wel bij de x 1 erbij.
maar eerstehuisdeel=4,3 geeft direct Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3

[liquid_ice]

De validator staat online en is te vinden op:

http://www.tuintopia.nl/wedstrijd.rar

Deze en komende week zal ik nog proberen feedback te verwerken, maar daarna ben ik dus voor 3 weken op vakantie. Het kan dus zijn dat je waardevolle feedback even op de plank blijft liggen, maar het wordt niet ZOMAAR genegeerd.

Vanaf nu tot en met 17-Juli om 23:59:59 mogen comments en feedback op de validator worden benoemd hier in het topic, hierna wordt de validator als heilig beschouwd en zijn z'n uitkomsten onbetwistbaar.
Maak gebruik van deze kans.
Mocht je mooie corner cases bedenken ben ik er altijd geïnteresseerd in om die over te nemen.


have fun

PS : niet ruziën he

[ Voor 34% gewijzigd door liquid_ice op 26-06-2013 14:46 ]

[joram.agten]

het is hier weer stil, iedereen aan het wachten tot net voor de deadline?

[Soultaker]

Waarom niet? Als 'ie wilde dat we eerder reageren had 'ie de deadline eerder moeten zetten.

(Eigenlijk heb ik even kort naar de validator gekeken maar ik zag niet zo 1-2-3 bugs, dus vind ik het wel OK.)

[liquid_ice]

Ik heb geen stress, ik ben zo op vakantie

Maar naast bugs zijn C# dingen ook altijd welkom, waarschijnlijk is aan de code wel af te zien dat ik geen native C# spreker ben.

[ Voor 60% gewijzigd door liquid_ice op 01-07-2013 17:52 ]

[Daos]

Kickje. De deadline voor aanmerkingen op de validator is verleden tijd.

edit:
In oktober is er een borrel en een aansluitend (luxe) etentje voor de hele Devschuur® (naast mensen uit dit forum Programming ook zij die websites bouwen en zij die tekenen). Zie: Devschuur meeting W

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)

[ Voor 78% gewijzigd door Daos op 22-07-2013 16:58 ]

[Corniel]

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

[Verwijderd]

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.

[Verwijderd]

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:

Verwijderd 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...

[Verwijderd]

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.

[Verwijderd]

Verwijderd 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 ]

[Verwijderd]

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 Verwijderd 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)

[Verwijderd]

@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]

Verwijderd 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.