[Programming Contest 5] Tuintopia

[liquid_ice]

Programming Contest Contest 5 : Tuintopia

Inhoudsopgave

• Eerdere contests
• Inleiding
• De opdracht
• Het huis
• Uitvoer
• Spelregels
• De regels en andere afspraken
• Hoe worden de inzendingen beoordeeld?
• Wat kan ik eigenlijk winnen?
• Om je op weg te helpen
• Tot slot...

Eerdere contests

^

• Programming Contest Nieuwe Stijl: Contest 1 *uitslagen!*
• Programming Contest Nieuwe Stijl: Contest 2 *WINNAARS LEZEN*
• Programming Contest Nieuwe Stijl: Contest 3 *uitslagen!*
• Programming Contest Nieuwe Stijl: Contest 4 *Score-update*

Inleiding

^

Na het grote succes van de eerste t/m vierde door tweakers geleide contests
komt er nu een nieuwe contest. Ook dit keer hebben we weer een leuke opdracht die elke
programmeur, beginner of ervaren diehard, een uitdaging moet kunnen bieden.

De opdracht

^

Het idee voor deze contest komt voort uit het spel Tuintopia. In het spel ben je eigenaar van
een stuk grond met een huis erop. Het doel is om een tuin te maken met zoveel mogelijk
verbindingen in de tuin. Zo levert een waterpomp water aan de groentetuin en levert een
zonnepaneel stroom aan het huis.

De basis van het spel is als volgt, je begint het spel met het huis (2 kaarten groot), dit zijn de
startkaarten. Elke beurt leg je een kaart aansluitend aan de al bestaande kaarten aan. Op
iedere kaart staat wat de kaart nodig heeft en wat de kaart levert. Het water dat de
waterpomp levert heeft de groentetuin nodig. Als je deze 2 kaarten naast elkaar neerlegt
krijg je 1 punt:





Verbindingen kunnen worden gemaakt met kaarten die recht naast elkaar, recht boven elkaar
en diagonaal van elkaar liggen. Als je een kaart slim neerlegt kan je soms wel meer dan
8 punten in 1 beurt halen.
De 2 kaarten van het huis tellen als 1 kaart. Hierdoor krijg je GEEN dubbele punten als je
een nieuwe kaart direct onder of boven het huis legt.
Zodra de tuin vol is wint de speler met de meeste punten.

Om het spel spannender en nog leerzamer te maken, kun je het spel ook op een hoger niveau spelen. Op het tweede niveau kun je door rekening te houden met de invloed van de zon en de wind nog meer punten scoren.

De uitdaging wordt: Maak een programma die in maximaal 5 minuten tijd een zo hoog
mogelijke score behaalt (op basis van geldige kaart-combinaties op het speelveld). Als
output geeft de applicatie de highscore en de kaart combinatie die deze highscore oplevert.

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.
Om de codes te beoordelen worden deze allemaal getest op dezelfde machine

Voorbeeld voor speelveld.ini:

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

Uitleg: Bovenstaand speelveld is gelijk aan het voorbeeld op: http://www.tuintopia.nl/speldemo
"eerstehuisdeel" is de locatie van het linker huis deel, rechts van dit huisdeel staat altijd het
andere huisdeel. Deze 2 delen vormen samen 1 kaart.

Het onderstaande plaatje geeft een overzicht van het voorbeeld speelveld en de coördinaten.
De donkere velden stellen de plaats van het huis voor.



Voorbeeldstukje uit kaarten.ini:

[schuur]
aantal=2
input=water,stroom
output=afvalwater,afdak
zon=
schaduw=levert
wind=
windbeschutting=levert

[vijver]
aantal=2
input=
output=voedsel,water,plaagbestrijders
zon=nodig,levert
schaduw=
wind=
windbeschutting=

Uitleg: Bovenstaand stukje uit kaarten.ini is 1 type speelkaart, genaamd schuur. De naam is
het begin van een kaart en staat tussen haakjes.

Hierna komt de key "aantal" die geeft aan hoe vaak deze kaart mag voorkomen op het
speelveld. Aantal kan ook 0 ( nul ) zijn.

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
in totaal zijn er 11 mogelijke input/output types. Deze types zijn:
"voedsel", "water", "mest", "plantenresten, "nectar", "bevruchting", "stro", "afvalwater", "plaagb
estrijders", "stroom" en "afdak".
De schuur heeft stroom nodig, als er langs de schuur een kaart ligt die stroom als output
heeft, levert dat 1 punt op. Als er aangrenzend aan de schuur 2 stroom leverende kaarten
liggen, dan levert dat 2 punten op. Op deze manier kan 1 input van 1 kaart maximaal 8
punten opleveren (een van elke aangrenzende kaart).

De keys "zon", "schaduw", "wind" en "windbeschutting" zijn voor het hogere niveau. Als er
achter "zon", "schaduw", "wind" of "windbeschutting" het woord "levert" staat heeft deze key
een betekenis voor een buur kaart, namelijk dat de kaart dit aspect levert aan de buur. Als er

"nodig" staat bij een key betekent dat, dat de kaart dat aspect nodig heeft. Een kaart kan ook
zowel zon nodig hebben als zon leveren, zie hierboven bij de vijver.

De zon schijnt vanuit het zuiden en de wind waait vanuit het westen. Dat betekent concreet
het volgende:

De 3 kaarten onderaan een bepaalde kaart (linksonder, recht eronder en rechtsonder)
kunnen de kaart zon of schaduw leveren. Een kaart kan zelf zon of schaduw leveren aan de
3 kaarten erboven.

Voor iedere match krijgt de speler 1 punt. Een match ontstaat als volgt:
Een kaart levert zon aan een kaart die zon nodig heeft (onderste kaart: zon=levert; bovenste
kaart: zon=nodig).
Een kaart levert schaduw aan een kaart die schaduw nodig heeft (onderste kaart:
schaduw=levert; bovenste kaart: schaduw=nodig).

Voor iedere mismatch krijgt de speler 1 minpunt. Een mismatch ontstaat als volgt:
Een kaart levert zon aan een kaart die schaduw nodig heeft (onderste kaart: zon=levert;
bovenste kaart: schaduw=nodig).
Een kaart levert schaduw aan een kaart die zon nodig heeft (onderste kaart: schaduw=levert;
bovenste kaart: zon=nodig).



De 3 kaarten links van een bepaalde kaart kunnen de kaart wind of beschutting leveren. Een
kaart kan zelf wind of beschutting leveren aan de 3 kaarten rechts ervan.

Hierbij geldt ook: voor iedere match krijgt de speler weer 1 punt en voor iedere mismatch 1
minpunt.

Een key die geen waarde heeft, zal wel aanwezig zijn.

De eindscore is een optel som van de punten per kaart. Min punten zijn NIET gratis als de
score 0 is, in dat geval ga je gewoon de min in.

Het Huis

^

Zoals hierboven beschreven tellen de 2 kaarten van het huis als 1 kaart.

Dit heeft op een aantal aspecten van het spel een invloed. Deze invloeden zullen we hieronder extra verduidelijken.

kaarten.ini
Omdat het huis 1 kaart is van dubbel formaat hebben we besloten om in de kaarten.ini deze ook als aantal=1 op te geven. Het gaat namelijk om 1 huis.

verbindingen en key's
Doordat het huis het formaat heeft van 2 kaarten kan deze verbindingen aangaan met alle 10 zijn buren. Denk eraan dat er geen dubbele punten worden geteld als je kaart recht onder of boven het huis ligt.

wind
Doordat het huis het formaat heeft van 2 kaarten heeft deze ook een invloed op meer buur kaarten als het om de wind gaat.
Zie:

Denk er ook hierbij aan dat er geen dubbele punten geteld gaan worden.

Het maakt qua punten geen verschil of een buurkaart van het huis wind of beschutting levert aan een deel van het huis, of aan het gehele huis. In beide gevallen gaat het om 1 punt.

zon
Doordat het huis het formaat heeft van 2 kaarten heeft deze ook meer een grotere invloed als het om zon en schaduw gaat.
Zie:

Denk er ook hierbij aan dat er geen dubbele punten geteld gaan worden.

Het maakt qua punten geen verschil of een buurkaart van het huis zon of schaduw levert aan een deel van het huis, of aan het gehele huis. In beide gevallen gaat het om 1 punt.

Uitvoer

^

Uitvoer komt terecht in een bestand genaamd output.ini. Dit bestand ziet er als volgt uit:

Score:<< de door jou berekende score >>
[groentetuin][graanveld][huis][huis][schuur][mesthoop]
[paddestoelenstam][regenton][notenboom][vlinderstruik][bijenkorf][waterzuivering]
[insectenhotel][boomgaard][heg][insectenhotel][compostvat][waterpomp]

Op regel 1 staat de eindscore volgens jouw programma.
Op elke volgende regel staat 1 regel van de eind uitkomst die de score maakt.
De bovenste van deze regels is de meest noordelijke, de onderste de zuidelijkste regel.
Links staan de meest westelijke kaarten, rechts de meest oostelijke.
Mocht je een leeg veld innemen in je uitkomst, dan gebruik je de blokhaken zonder tekst erin, dus zo: "[]"

In de uitvoer en de score gaan we uit van het hogere spel niveau, dus met de keys "zon",
"schaduw", "wind" en "windbeschutting" erbij.

De regels en andere afspraken

^

Uiteraard zijn er aan deze contest wat regeltjes verbonden. Om alles eerlijk te laten verlopen
gelden de volgende spelregels:

1. Inzendingen voor de contest stuur je naar [e-mail]; neem daarbij in
   de subjectregel de tekst "Inzending PRG Contest 5 - <nickname>" op. Zet de
   bestanden niet ergens publiek neer voordat de sluitingsdatum is bereikt, om het zo
   voor iedereen leuk te houden. Stuur bovendien geen code op waar je niet 100%
   achter staat. Je eerste inzending is de enige inzending die telt, een tweede inzending
   zullen we niet in ogenschouw nemen.
   
   
2. Voeg bij je inzending een omschrijving van de gebruikte algoritmen en manieren
   waarom je code werkt, deze willen we na afloop publiceren samen met je score en
   broncode. Zo kunnen we allemaal wat leren van elkaar.
   
   
3. De sluitingsdatum van de contest is 2 maanden na de plaatsing van dit topic 16 april
   2013. Elke inzending die binnenkomt ná 16 juni om 23:59:59 is helaas uitgesloten
   van deelneming, zonder uitzondering.
   
   
   We hebben bewust een datum gekozen die nog redelijk ver in de toekomst ligt, zodat
   niemand echt tijdsdruk zal ondervinden en zoveel mogelijk mensen mee kunnen
   doen, dus ik denk niet dat een strakke deadline een probleem zal zijn.
   
   
4. Neem in je mailtje een zip- of rar-file op met daarin een uitvoerbare versie van je
   programma én je programmacode. In het geval van scripttalen zoals PHP is één
   bestand uiteraard voldoende.
   
   
   Als je executable afhankelijk is van minder gangbare DLL's of als deze andere
   afhankelijkheden heeft, stuur dan duidelijke instructies mee voor het runnen van je
   applicatie.
   
   
5. Je applicatie wordt gerund in een map met daarin alleen je executable(s) en de
   invoerbestanden. Maak je programma dus ook niet afhankelijk van de aanwezigheid
   van de uitvoerbestanden of andere files!
   
   
6. Als OS wordt er gebruik gemaakt van Windows 7 of Linux mint 14 (beide 64 bit).
   
   
7. Je mag elke programmeertaal gebruiken die je wilt, met uitzondering van Brainfuck.
   
   
8. Samenwerken mag, maar meld het wel even als je dit doet. Neem in je
   inzendingsmailtje de nicknames van alle programmeurs op.
   
   
9. De ingestuurde zipfiles worden na de contest publiek gemaakt, inclusief je
   sourcecode. Als je hiertegen bezwaar hebt, dan kun je beter niet meedoen.
   Uiteraard staat het je vrij om elke willekeurige opensource licentie aan je code te
   verbinden en de credits liggen uiteraard gewoon bij jou.
   
   
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.
    
    
11. Het berekenen van een foutieve eindscore kost je de punten die het huis zou hebben
    opgeleverd, als het huis een negatieve score heeft krijg je er GEEN punten bij.
    Wij herberekenen de eindscore altijd nog eens en gaan ook uit van ONZE berekening.
    
    
12. Alle genoemde in- en uitvoerbestanden bevinden zich in dezelfde directory als het
    uitvoerbare bestand van je programma.
    
    
13. Als je programma langer dan een 5 minuten nodig heeft om te runnen op de pc die
    je score berekent, dan heb je pech. Na een 5 minuten wordt je applicatie gestopt en
    alleen de uitvoer die op dat moment in je output.ini bestand zit wordt gebruikt voor
    het berekenen van je score. Je kan ervan uit gaan dat de pc waarop je programma
    gerund wordt sneller is dan de gemiddelde consumenten pc, maar probeer je
    programma zo snel mogelijk te houden.
    
    
14. Het heeft geen zin om bij moderators te gaan vragen naar de lijst met deelnemers
    en inputgegevens. Deze files worden namelijk pas ná de sluitingsdatum überhaupt
    gemaakt, dus we kúnnen je die files niet geven, zelfs al zouden we het willen.
    Natuurlijk geven we uiteindelijk wel de precieze files vrij, samen met de uitslag van de
    contest, en niet eerder dan dat om zo een beetje de spanning erin te houden.
    
    
15. Neem voldoende en zinnig commentaar op in je code.
    
    

Hoe worden de inzendingen beoordeeld?

Elke inzending wordt minimaal 3 keer aan de tand gevoeld, elke keer met een andere testset (bord en speelkaarten).
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.

Wie de minste punten verzameld over de 3 test sets wint, mochten er nu nog steeds meerdere winnaars zijn zal een 4de beslissende set worden gedraaid met de winnaars

Wat kan ik eigenlijk winnen?

^

Nou, dat is vrij simpel: Tuintopia als werkelijk analoog spel wordt uitgedeeld aan de 3 beste
inzendingen. De hoofdprijs is een Raspberry Pi (B). Deze prijs wordt gesponsord door Farnell.com.
En het belangrijkste wat je overhoudt is natuurlijk de eeuwige roem en de eer om de vijfde contest in dit nieuwe format gewonnen te hebben!

Om je op weg te helpen

^

Om te zorgen dat jullie alvast van start kunnen gaan bieden we jullie graag een testset aan
van invoerbestanden. Bedenk wel dat de uiteindelijke bestanden anders zullen zijn!

Je kunt natuurlijk ook voor testdoeleinden (aanbevolen zelfs!) je eigen speelveld en
kaarten.ini bestanden maken. Helemaal leuk wordt het als jullie onderling testsets gaan
delen en kijken wie het best scoort totdat de deadline gekomen is. Zo zijn je tests niet al te
eentonig met altijd dezelfde data.

Testset:
speelveld.ini
kaarten.ini

Daarnaast ben je, net als in vorige contest, vrij om zelf een 'validator' te schrijven (en online
te zetten) om te controleren of je uitvoer voldoet aan de eisen. Wij, de organisatie, zullen
onze eigen validator inzetten om de uiteindelijke uitvoer van jullie inzendingen te controleren.
Laatstgenoemde blijft, in ieder geval tot na de deadline, intern en is dus niet voor jullie
beschikbaar.

Ook kan je gebruik maken van de demo applicatie in tuintopia.nl. qua kaarten en speelveld
moet deze gelijk zijn aan de testset. In deze demo worden echter de zon en wind aspecten
niet meegenomen.

Tot slot...

^

...willen we jullie natuurlijk weer heel veel succes wensen. We hopen dat je er plezier in gaat
hebben om aan deze contest mee te doen, en natuurlijk hopen we dat je niet de enige bent.
Hoe meer competitie, hoe beter!

Voor wat extra achtergrond informatie kan je kijken in het topic: [algoritme] bordspel doorrekenen

Als jullie nog vragen hebben, stel ze dan maar gewoon in dit topic.

[ Voor 219% gewijzigd door RobIII op 02-05-2013 01:54 ]

[Anoniem: 303530]

In de regels staat dat diegene met het hoogste puntenaantal in 5 minuten wint.

Maar: het oogt relatief triviaal (lees: op basis van mijn programma) om binnen een gedeelte van die tijd het absolute maximum te berekenen. Wat gebeurt er dan als de helft van de spelers dat voor elkaar krijgt?

"indien er meerdere personen met dezelfde score zijn wint de snelste" ofzo.

[ Voor 9% gewijzigd door Anoniem: 303530 op 16-04-2013 21:17 ]

[.oisyn]

tvp

[liquid_ice]

@Darkstone, dan wint de snelste inderdaad

[Creepy]

Tssk. Nog niemand heeft een entry opgestuurd. Duurt lang!

[Anoniem: 303530]

Ik heb nog niet eens een file parser in elkaar gezet

[Matis]

Misschien wel eens leuk om weer te gaan proberen

[Bolukan]

Trouwens nette uitgebreide start-post !! Met leuke plaatjes, ook nog mooi voor het oog.
Iemand die samen in C# aan de slag wil gaan?

[ Voor 12% gewijzigd door Bolukan op 16-04-2013 22:26 ]

[Soultaker]

Zo, dat duurde nogal, maar dan heb je ook wat!

Je mag elke programmeertaal gebruiken die je wilt, met uitzondering van Brainfuck.

Als Brainfuck-programmeur voel ik me buitengesloten.

Anoniem: 303530 schreef op dinsdag 16 april 2013 @ 20:43:
"indien er meerdere personen met dezelfde score zijn wint de snelste" ofzo.

Eigenlijk vind ik dat ook een rare regel, aangezien het best mogelijk is dat je een hoge score vind zonder dat je weet of dat de maximale score is (zie het eerdere topic, waarin jij een programma schreef dat uren nodig had om te verifëren dat 88 punten het maximaal haalbare was — die oplossing had ik veel sneller gevonden, maar jouw resultaat was eigenlijk beter).

Misschien kan beoordeeld worden op de modification time van output.ini? Dan kun je tiebreaken op basis van wie het eerste het maximale resultaat gevonden heeft.

[Anoniem: 303530]

Soultaker schreef op dinsdag 16 april 2013 @ 23:59:
Eigenlijk vind ik dat ook een rare regel, aangezien het best mogelijk is dat je een hoge score vind zonder dat je weet of dat de maximale score is (zie het eerdere topic, waarin jij een programma schreef dat uren nodig had om te verifëren dat 88 punten het maximaal haalbare was — die oplossing had ik veel sneller gevonden, maar jouw resultaat was eigenlijk beter).

Maar inmiddels draait datzelfde algoritme in 3 minuten

Ik vind het bepalen van de 'winnaars' ook vreemd. Zoals ik het lees wordt er op 1 nader te bepalen gridsize getest. Maar mijn algoritme presteer op een 6x3 grid goed en op een 4x4 grid überslecht. Moet ik dan maar hopen dat er geen 4x4 grid wordt gekozen?

Edit: mijn algoritme doet het goed op de testdata. Met een aantal hand-tuned parameters welke in principe 'gewoon' te berekenen zijn) verifieert-ie de maximale score van 80 -waarvan er 2688 bestaan- in 17 seconden. Ik negeer dan even de 'nieuwe' mechanieken zon, schaduw en dubbele kaarten.

[ Voor 17% gewijzigd door Anoniem: 303530 op 17-04-2013 00:29 ]

[RobIII]

Bij een gelijkspel (qua score / tijd / ...) o.i.d. kan altijd nog uitgeweken naar een tweede (derde, ...) set. Afgaand op vorige jaren wordt er waarschijnlijk mogelijk ook nog een "bogus" setje getest om te zien hoe inzendingen daar mee om gaan.

Let wel: ik post hier enkel speculatie. Ik ben amper-tot-niet bezig geweest met de organisatie en vermoed ook niet deel te nemen of de afhandeling (deels) op me te nemen. Definitieve uitspraken zijn voor Creepy / liquid_ice weggelegd (of een andere rooie uit de Devschuur die wel uitspraken hierover durft te kan doen )

[ Voor 7% gewijzigd door RobIII op 17-04-2013 00:12 ]

[liquid_ice]

Een paar scherpe opmerkingen inderdaad.

Ik ga in conclaaf met Creepy en Arjan (mede organisator van deze wedstrijd) om ervoor te zorgen dat er meer duidelijkheid komt en dat de update van de regels mbt het kiezen van de winnaar volledig, duidelijk en eerlijk zullen zijn voor een ieder.

[TheNephilim]

Ziet er goed uit! Zelf geen kennis genoeg en eigenlijk ook geen tijd om mee te doen, succes allemaal!

[Creepy]

Anoniem: 303530 schreef op woensdag 17 april 2013 @ 00:02:
[...]

Maar inmiddels draait datzelfde algoritme in 3 minuten

Ik vind het bepalen van de 'winnaars' ook vreemd. Zoals ik het lees wordt er op 1 nader te bepalen gridsize getest. Maar mijn algoritme presteer op een 6x3 grid goed en op een 4x4 grid überslecht. Moet ik dan maar hopen dat er geen 4x4 grid wordt gekozen?

Je moet inderdaad maar hopen dat het grid dat gekozen gaat worden goed voor je uitpakt. Of je code zo lopen schrijven dat dat ineens minder van invloed is

Het doel is het bereken van de hoogste score, in een zo'n kort mogelijke tijd op een nog nader te bepalen bord met nog nader te bepalen kaartesetn. Wat is daar dan nu precies vreemd aan? De regels lijken me vrij helder. Je kan nu wel gaan lopen coden om 1 specifiek bord met 1 specifieke set met kaarten zo snel mogelijk op te lossen maar dat is nu juist niet de bedoeling.

We gaan nog even in overleg om te kijken wat er gebeurd met een gelijk stand, maar als ik het zo zie is het dan logisch om een groter bord te pakken (en wat meer kaarten ofzo). Of we gooien de boel iets om en diegene met de totale kortste tijd over minimaal 3 verschillende borden/sets wint puur om het feit dat ik de excuses "maar op bord x bij x presteert mijn code optimaal" nu al de kiem in wil smoren

[ Voor 17% gewijzigd door Creepy op 17-04-2013 14:27 ]

[Sjaaky]

Zijn aantalveldenxas en aantalveldenyas gelimiteerd? Zo ja, maken jullie deze waardes bekend?

Als de runtime een factor is, krijg je een extra vraagstuk. Reken je na het vinden van je tot dan toe beste score verder in de hoop op een betere score, of stop je in de hoop dat de score door niemand overtroffen wordt en jij de snelste bent die dat behaald heeft.

[ Voor 59% gewijzigd door Sjaaky op 17-04-2013 15:16 ]

[TheDevilOnLine]

Kunnen we met de parameters niet wat limitien stellen á la Google Codejam:

Limits

1 ≤ T ≤ 100.

Small dataset
1 ≤ N, M ≤ 10.
1 ≤ ai,j ≤ 2.

Large dataset
1 ≤ N, M ≤ 100.
1 ≤ ai,j ≤ 100.

Maar dan dus met:
- Aantal soorten kaarten
- Maximale aantal inputs/outputs
- De grootte van het speelveld

Waar het huis staat hoeft hierin niet voor te komen omdat dit altijd ergens op het speelveld is

Voor de score zou ik het volgende willen voorstellen:

Maak meerdere datasets (levels). Geef een score per dataset (dus de persoon met de laagste score krijgt 1 punt, de een na laagste 2 etc). In het geval van een gelijke score geef je die personen het gemiddelde aantal punten (dus bij 100 spelers en plek 1, 2 en 3 hebben de zelfde score dan krijgen ze elk (100 + 99 + 98) / 3 = 99 punten. Hier kan je eventueel nog aan toevoegen dat de tijd waarin de score berekend is ook meetelt. Foute output is altijd 0 punten.

Op deze manier voorkom je dat één bepaald programma/script hoog scoort op geluk (of bijvoorbeeld voor 1 situatie geoptimaliseerd is).

[Anoniem: 510923]

Beste mensen, mijn naam is Arjan de Vries. Ik ben bedenker van het spel Tuintopia. Zelf heb ik geen programmeer ervaring, maar ik vind het erg leuk dat het spel als basis voor deze wedstrijd dient!

Ik zal de wedstrijd in de gaten houden om eventuele vragen over het spelsysteem te beantwoorden en waar mogelijk over de wedstrijd zelf.

[ Voor 34% gewijzigd door Anoniem: 510923 op 17-04-2013 17:52 ]

[Lucacker]

Leuk idee, zit er zeker aan te denken om mee te doen, weet alleen nog niet welke taal.
Mag het met php ook in meerdere php bestanden? en is GameMaker ook toegestaan?

[Corniel]

Count me in.

Twee opmerkingen direct:
- Waarom niet zero-based coördinaten?
- Waarom huis als int[], en dimensies van het veld niet?

[Lucacker]

Als ik het in php maak, op welke manier wordt dit dan uitgevoerd? Op linux,windows,apache,lighttpd en welke php versie etc? Is wel handig om te weten

[Anoniem: 303530]

Creepy schreef op woensdag 17 april 2013 @ 14:17:
Het doel is het bereken van de hoogste score, in een zo'n kort mogelijke tijd op een nog nader te bepalen bord met nog nader te bepalen kaartesetn. Wat is daar dan nu precies vreemd aan? De regels lijken me vrij helder. Je kan nu wel gaan lopen coden om 1 specifiek bord met 1 specifieke set met kaarten zo snel mogelijk op te lossen maar dat is nu juist niet de bedoeling.

Wat ik wil zeggen is dat als de eindstand wordt bepaald door de prestaties op één bord, de uiteindelijke winnaar wel erg afhankelijk wordt van welk formaat bord precies wordt gekozen. Misschien heb ik iets slims bedacht waardoor een 6x3 bord triviaal te berekenen valt en iemand anders iets waardoor een datzelfde geld voor een 4x4 bord. 'winnen' is dan gewoon het opgooien van een dobbelsteen.

Je kan de 'winnaar' natuurlijk minder 'random' maken door gewoon op meerdere borden te testen, zodat het algoritme wat gemiddeld het beste scoort wint. In plaats van een algoritme bedoeld voor een specifiek formaat bord wat toevallig gekozen wordt.

[Soultaker]

Lucacker schreef op woensdag 17 april 2013 @ 18:01:
Als ik het in php maak, op welke manier wordt dit dan uitgevoerd? Op linux,windows,apache,lighttpd en welke php versie etc? Is wel handig om te weten

Als je een oplossing in PHP schrijft draait die hopelijk gewoon op de commandline? Wat was je precies van plan dat je er een webserver bij nodig hebt?

Als je een specifieke versie van PHP nodig hebt, of bepaalde modules en/of bepaalde instellingen, is het waarschijnlijk handig om de gewenste interpreter te bundelen in je oplossing.

[ Voor 28% gewijzigd door Soultaker op 17-04-2013 18:07 ]

[Lucacker]

Ooja, je kan php natuurlijk ook via de command line draaien, even vergeten.

[Bolukan]

Corniel schreef op woensdag 17 april 2013 @ 17:34:
Count me in.

Twee opmerkingen direct:
- Waarom niet zero-based coördinaten?
- Waarom huis als int[], en dimensies van het veld niet?

Waarom wel? Ergens moeten mensen op stuklopen
En het huis staat altijd op de x-as (2 breed), dus x,y en x+1,y

Doe je mee met C#

TheDevilOnLine schreef op woensdag 17 april 2013 @ 15:38:
Kunnen we met de parameters niet wat limitien stellen á la Google Codejam:

Het is ook een idee dat je in die 5 minuten meerdere problemen moet oplossen, dat maakt de taktiek keuze interessanter

[ Voor 31% gewijzigd door Bolukan op 17-04-2013 18:43 ]

[MLM]

Over het speelveld, waarop een huis staat. Klopt het als ik stel:
1) Het huis is altijd 2 breed en 1 hoog.
2) Er is altijd maar 1 kaart beschikbaar met titel "huis" (ie, in kaarten.ini zal exact 1 sectie zitten met de titel "huis" en deze sectie zal bevatten "aantal=1"). Deze kaart (ondanks dat hij op het speelveld groter is) telt altijd als "1" (ie, in de uitvoer ga ik 2x [huis] hebben, maar dat telt voor "1"), en staat altijd op een vaste plaats op het veld.

Daarnaast, klopt dit ook:
3) In de TS gesproken word over "Elke beurt leg je een kaart aansluitend aan de al bestaande kaarten aan". In de invoer is geen sprake van een volgorde van kaarten, dus ik kan uit het gehele deck kiezen? Tevens impliceert dit dat in geval van meer ruimte op het speelveld dan er kaarten in het deck zitten (ie, er moeten lege kaarten in de uitvoer zitten), je moet garanderen dat alle kaarten verbonden zijn (ie, geen eilandjes van kaarten).

[.oisyn]

Lucacker schreef op woensdag 17 april 2013 @ 18:33:
Ooja, je kan php natuurlijk ook via de command line draaien, even vergeten.

Even los hiervan, heeft php tegenwoordig niet een ingebouwde webserver zodat je je "stand-alone" script alsnog in een webomgeving kunt draaien?

[liquid_ice]

LET OP :

Er waren wat vragen mbt de beoordelingen, deze hebben we verduidelijkt in de openingspost onder het kopje:

Hoe worden de inzendingen beoordeeld?

[TheDevilOnLine]

liquid_ice schreef op woensdag 17 april 2013 @ 22:22:
LET OP :

Er waren wat vragen mbt de beoordelingen, deze hebben we verduidelijkt in de openingspost onder het kopje:

Hoe worden de inzendingen beoordeeld?

Goede keuze :-)

[Anoniem: 303530]

Merci. Nu hoef ik er ook niet meer op te hopen dat er een 6x3 bord langs komt. Tussen de borden zit er altijd wel een van afwijkende grootte.

[CodeCaster]

Anoniem: 510923 schreef op woensdag 17 april 2013 @ 15:40:
Beste mensen, mijn naam is Arjan de Vries. Ik ben bedenker van het spel Tuintopia. Zelf heb ik geen programmeer ervaring, maar ik vind het erg leuk dat het spel als basis voor deze wedstrijd dient!

Ik zal de wedstrijd in de gaten houden om eventuele vragen over het spelsysteem te beantwoorden en waar mogelijk over de wedstrijd zelf.

Dan weet jij vast deze wel. In de teksts staat:

in totaal zijn er 11 mogelijke input/output types. Deze types zijn:
"voedsel",
"water",
"mest",
"plantenresten,
"nectar",
"bevruchting",
"stro",
"afvalwater",
"plaagbestrijders",
"stroom" en
"water".

Dat zijn er inderdaad elf, maar water staat er twee keer in. Omdat deze belofte gedaan werd, wilde ik wat strong-typedness gaan doen, maar dat wordt op deze manier lastig.

Wat o wat is dat elfde type? Is het "afdak", en heeft dat nog invloed op de zon?

[Corniel]

Volgens mijn unittest komt "afdak" voor. Dat zou dus ipv water moeten zijn.

@Bolukan: Ja, met C-hekje. Echte talen heb ik nooit (goed) geleerd.

[Anoniem: 303530]

Een uitstekende kans om dat dus wel te doen

[TheDevilOnLine]

Vraagje:

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.

Stel dat ik teveel kaarten van 1 soort neerleg (dus meer dan er volgens de .ini zijn), hoe wordt dan bepaald welke als lege kaartlocatie wordt beschouwd?

[king_charles]

TheDevilOnLine schreef op donderdag 18 april 2013 @ 09:33:
Vraagje:


[...]


Stel dat ik teveel kaarten van 1 soort neerleg (dus meer dan er volgens de .ini zijn), hoe wordt dan bepaald welke als lege kaartlocatie wordt beschouwd?

In foutsituaties kun je nooit het gedrag voorspellen. Dit is daar weer een mooi voorbeeld van. Fout zou gewoon fout moeten zijn en niet zoiets als nouja dan laten we wel 1 kaart weg want dat zal het programma wel bedoeld hebben, IMO .

[Anoniem: 510923]

@CodeCaster

Klopt de 2de keer 'water' moet 'afdak' zijn! Verder heeft 'afdak' geen invloed op de zon.

[Corniel]

Belangrijke vragen:

• Is er altijd een [huis] in een ini-file?
• Worden altijd alle 8 properties van een kaart gespect?
• Klopt het dat het [huis] ipv maximaal 4, maximaal 6 directe buur kaarten heeft? (voor in en out)?
• Klopt het dat het [huis] ipv maximaal 3, maximaal 4 buur kaarten voor zon en schaduw heeft?
• Klopt het dat huis0 en huis1 geen dubbele punten krijgen voor velden die aan beide grenzen? (het is immers een kaart staat er)

Verder zag ik in de voorbeeld ini een "in=water,". Die comma op het einde lijkt me niet de bedoeling.

Leuke uitdaging trouwens. (input lezen is af, net als een initieel model). Mijn bot heet trouwens DessertStorm.

[TheDevilOnLine]

king_charles schreef op donderdag 18 april 2013 @ 11:16:
[...]


In foutsituaties kun je nooit het gedrag voorspellen. Dit is daar weer een mooi voorbeeld van. Fout zou gewoon fout moeten zijn en niet zoiets als nouja dan laten we wel 1 kaart weg want dat zal het programma wel bedoeld hebben, IMO .

Ben ik helemaal met je eens hoor, ik probeer gewoon te voorkomen dat er discussie achteraf gaat plaatsvinden als dit bij iemand het geval is ;-)

[CodeCaster]

Anoniem: 510923 schreef op donderdag 18 april 2013 @ 11:19:
@CodeCaster

Klopt de 2de keer 'water' moet 'afdak' zijn! Verder heeft 'afdak' geen invloed op de zon.

Mooi, dank je! Ik kan over het spel zelf nog niks zeggen, ga vanavond weer verder hobbyen. Leuk dat je hier van je laat horen.

Corniel schreef op donderdag 18 april 2013 @ 11:33:
Belangrijke vragen:
• Is er altijd een [huis] in een ini-file?

Je begint tegen mij over unit tests, maar defensief programmeren is je vreemd? TS vermeldt:

je begint het spel met het huis (2 kaarten groot), dit zijn de startkaarten.

Als de sectie 'huis' dus niet in de ini staat, is de ini ongeldig, want dan kan het spel niet beginnen.
[quote]
• Worden altijd alle 8 properties van een kaart gespect?

Afwezig = null, lijkt me?

Verder zag ik in de voorbeeld ini een "in=water,". Die comma op het einde lijkt me niet de bedoeling.

Dat lijkt me wederom een test voor het defensief programmeren van het inlezen van data.

[Corniel]

@CodeCaster: ik weet niet hoe je er bij komt dat defensief programmeren mij vreemd is. Ik heb alleen nooit goed een echte taal (C, C++, Cobol ) geleerd. Alleen maar van die fluttaaltjes als C#, Java, Basic, Pascal e.d. elende.

Je zou kunnen voortellen dat het [huis] vaste eigenschappen heeft. Dan hoef je deze niet te speccen, maar moet je dus zorgen dat er een default implementatie van [huis] is.

Het feit dat je het kan interpreteren betekent natuurlijk niet dat je vermeende fouten aan de andere kant niet moet melden, of vragen of je het wel goed begrepen hebben. Je weet wel: de C in ICT.

[Soultaker]

CodeCaster schreef op donderdag 18 april 2013 @ 12:25:
Dat lijkt me wederom een test voor het defensief programmeren van het inlezen van data.

Vind ik niet; de invoer moet gewoon aan het gespecificeerde formaat voldoen, en geen rare karakters bevatten die daar volgens de specificatie niet in thuis horen. Ik vind niet dat deelnemers gediskwalificeerd moeten worden wanneer de organisatie zich niet aan haar eigen (nogal informeel gespecificeerde) invoerformaat houdt.

[CodeCaster]

Volgens mij is de OP veranderd, want ik meen eerder iets gelezen te hebben dat er bij gelijke scores ook wordt gekeken naar hoe je inzending met aparte / ongeldige invoer omgaat.

Corniel schreef op donderdag 18 april 2013 @ 12:43:
@CodeCaster: ik weet niet hoe je er bij komt dat defensief programmeren mij vreemd is.

Dat was een garpje, zie de knipoog. Ik zou graag ook een "echte" taal gebruiken hiervoor, maar val toch weer terug naar het vertrouwde C# omdat ik bang ben niets te kunnen inleveren als ik nog een taal en paradigma moet oppikken.

Welke voordelen ten opzichte van bijvoorbeeld C# zou een functionele taal hier kunnen bieden, al red ik me aardig met LINQ?

Je zou kunnen voortellen dat het [huis] vaste eigenschappen heeft. Dan hoef je deze niet te speccen, maar moet je dus zorgen dat er een default implementatie van [huis] is.

Een huis is niets anders dan iedere andere kaart, behalve dat 'ie al op het bord ligt als het spel begint. Als een [huis]-sectie enkel aantal=2 heeft (en zo niet, is de ini ongeldig?), levert en vraagt 'ie blijkbaar niets. Dat lijkt me iets waar de kaarten-ini-lezer wel mee om moet kunnen gaan, omdat nergens staat dat een kaart verplicht iets levert of vraagt.

[ Voor 95% gewijzigd door CodeCaster op 18-04-2013 13:48 ]

[Anoniem: 303530]

nvm...

[ Voor 98% gewijzigd door Anoniem: 303530 op 18-04-2013 13:31 ]

[Corniel]

code:

[huis][a]
[w][c][o]
[a][z][a]

Gegeven het bovenstaande zou ik veronderstellen dat kaart [c] zeven buren heeft, en niet twee maal het huis. Dat is wat de tekst suggereert. Het plaatje suggereert namelijk iets anders. Kan iemand daar uitsluitsel over doen?

Op en 7x9 bord kan ik nu 80.000.000 borden doorrekenen in 5 minuten. Dat gaat de goede kant op.

[liquid_ice]

@Corniel: In jou voorbeeld heeft kaart [c] INDERDAAD zeven buren. Het huis is 1 ding, ookal is deze dubbel het formaat.

Scherp gezien dat het plaatje wat anders suggereert
[smoesjes mode]
Dit komt uit het feit dat het ook een werkelijk spel is waarbij het huis is geprint op 2 kaarten
[/smoesjes mode]

Moet nog even overleggen wat we met het plaatje doen.

[Anoniem: 303530]

Corniel schreef op donderdag 18 april 2013 @ 15:26:


Op en 7x9 bord kan ik nu 80.000.000 borden doorrekenen in 5 minuten. Dat gaat de goede kant op.

Dan heb je 1:5675540678545737086983159234619855620429648413719092193883296697602190186286062778712064000000000 van de mogelijkheden gecoverd met het test dataset

800000000 / (85! / (( 85 - 7 * 9 + 2)!) )

Edit: wacht, er zijn 48 kaarten, niet 85. Bovendien klopt de berekening voor geen kant. Laat me heel even denken..

De berekening klopt wel, maar de input zelf is ongeldig. Er is helemaal geen veld van 7*9 mogelijk met de test input, er zijn te weinig kaarten daarvoor.

[ Voor 19% gewijzigd door Anoniem: 303530 op 18-04-2013 16:49 ]

[Corniel]

@Darkstone: true, maar het is wel prettig dat je veel pogingen kan doen. Mijn inschatting is dat je eerst moet zorgen dat het snel draait (ik doe nu random sets) en pas daarna kan gaan optimaliseren op het vinden van goede oplossingen.

[liquid_ice]

Corniel, neem je ook al de zon en de wind mee?

[Corniel]

@liquid_ice: ja, maar daar zit nog een bugje in. Maar goed, er moet hier ook gewerkt worden.

[Anoniem: 303530]

Corniel schreef op donderdag 18 april 2013 @ 17:03:
@Darkstone: true, maar het is wel prettig dat je veel pogingen kan doen. Mijn inschatting is dat je eerst moet zorgen dat het snel draait (ik doe nu random sets) en pas daarna kan gaan optimaliseren op het vinden van goede oplossingen.

Moah. Het idee dat er een methode bestaat die de score van een oplossing berekent is haast al flawed. Je gaat heus niet elke frame de score van je complete bord berekenen

Mijn algoritme berekent overigens 300.000.000 3x3 borden per seconde zonder de pruning. Elke 10 klok cycles op een sandy bridge CPU één. Das best efficiënt..

[liquid_ice]

@Sjaaky: Wij doen geen beloften omtrend het maximale bordformaat, we raden je aan om defensief te programmeren. Dit staat in de OP onder de variabelen die we open houden.
Let ook goed op de andere variabelen die we open houden, zoals het aantal kaarten.

@MLM:
Klopt, het huis is altijd 2 breed en 1 hoog.

@TheDevilOnline:
ga er maar van uit dat een foute uitvoer afdoende bestraft wordt

Er komt een update van de OP om de regels omtrent het huis te verduidelijken.

[ Voor 12% gewijzigd door liquid_ice op 19-04-2013 13:04 ]

[Anoniem: 303530]

Een huis telt als een kaart.

Maar, wat gebeurt er dan als een huis 'gedeeltelijk' is overlapt door een wind of zon area. Krijgt het huis dan nog steeds 'slechts' 1 punt per wind/zon bron?

[Corniel]

Volgens mij is het zo, dat een huis dus wel telt als een kaart, maar de afmetingen heeft van twee. Daardoor heeft het huis (als ik het goed begrepen) dus een afwijkend (hoger aantal buren). Alleen het aantal windzijde en beschuttingzijde buren is gelijk aan dat van gewonen kaarten.

[liquid_ice]

Dat is juist het deel dat ik wil verduidelijken, maar dat kan ik pas online zetten als ik met Arjan heb overlegd.

[zwippie]

Leuk, weer een contest. Grappig spelletje ook, leuk bedacht Arjan.

Vraag: Blijft het bij deze (officiële?) kaarten, resources en zon/wind mogelijkheden? Of kunnen we ook nieuwe dingen verwachten zoals:

• Barbecue: input [afdak, voedsel], output [plantenresten]
• Paardenstal: input [stro, water, voedsel], output [mest, rundvlees] (en dan het vlees weer op de bbq)
• Megaturbine: input [stroom], wind=levert

Het lijkt me dat aan dat het zon/wind gedeelte weinig te veranderen valt, dat moet je wel hardcoden.

Maar door nieuwe resources te bedenken kun je er in principe ook een, bedenk eens wat, citybuilder mee maken. Kaarten als politiebureau, brandweer, winkel, bushalte. Resources als: voedsel, stroom, verlichting, warmte, afval, veiligheid, transport, etc.

Hoeveel veranderingen kunnen we verwachten tijdens de eindronde?

[Corniel]

@Zwippie: de kaarten blijven niet gegarandeerd hetzelfde. Alleen er komen (als ik het goed lees) geen andere resources bij.

[liquid_ice]

Klopt

[iRolfje]

Cool! Leuke wedstrijd. Ga eens kijken of ik er tijd voor vrij kan maken.

[spleethoven]

De kaarten worden ingelezen. Nu nog de rest

[Corniel]

Algoritme werkt (denk ik). Alleen nog wat speed tweaken. Ik heb trouwens ook een testset generator. Iemand interesse?

[spleethoven]

Graag, lijkt me handig :-)

Nog een vraagje:
Kunnen er meerder huizen zijn? Of mogen we ervan uitgaan dat er maar een huis in het spel komt?

[ Voor 69% gewijzigd door spleethoven op 23-04-2013 16:41 ]

[Corniel]

Een aantal testsets is te downloaden op: http://www.corniel.nl/download/

Als het goed is bevatten alle sets een kaart met de naam huis. Alle kaarten hebben een unieke naam en unieke eigenschappen. De naam convesie is: x maal y _ plus/min het aantal kaarten dat er meer is dan het aantal velden.

[Bolukan]

Corniel schreef op dinsdag 23 april 2013 @ 19:59:
Een aantal testsets is te downloaden op: http://www.corniel.nl/download/

Kan je de source van je code er ook bijzetten?

[ Voor 31% gewijzigd door Bolukan op 23-04-2013 20:13 ]

[Corniel]

@Bolukan: Nee. De code maakt gebruik van een deel van de code die ook door m'n solver gebruikt wordt. En die houd ik (al was het maar omdat er om geraagd is door de organisatie) nog even geheim.

[Daos]

In kaarten.ini staat er bij de vlinderstruik een komma bij "input = water,". Kan deze weg of moeten we er met parsen rekening mee houden?

[RobIII]

Daos schreef op dinsdag 23 april 2013 @ 23:59:
In kaarten.ini staat er bij de vlinderstruik een komma bij "input = water,". Kan deze weg of moeten we er met parsen rekening mee houden?

Ik spreek hier als iemand die (waarschijnlijk) niet meedoet en al zeker als non-organiserende en/of mod, maar ik zou persoonlijk Postel's Law hanteren (RobIII's version ):

quote: http://en.wikipedia.org/wiki/Jon_Postel#Postel.27s_Law

Be liberal in what you accept, and conservative in what you send output

[raptorix]

spleethoven schreef op dinsdag 23 april 2013 @ 14:27:
De kaarten worden ingelezen. Nu nog de rest

Hier ook, Models gemaakt, en kaarten worden ingelezen.

Leuk spel trouwens

[Daos]

Nog iets: in de voorbeeld output.ini staat paddenstoelenstam met tussen-n en in kaarten.ini zonder tussen-n

Verder staat er dat een huis uit twee velden bestaat, maar telt als 1 kaart. Telt die punt voor windbeschutting dan niet daartussen?

(ben nog steeds met parsen bezig; daarna eerst maar eens een validator maken die punten kan tellen)

edit:
Bij de voorbeeld output.ini kom ik uit op een score van 33. Is dit correct?

[ Voor 14% gewijzigd door Daos op 24-04-2013 20:30 . Reden: score gewijzigd ]

[raptorix]

Ik heb ook nog een vraag, is het aantal kaarten gelijk aan de oppervlakte?

Dus wanneer het oppervlak 5x5 is betekend dat er dan 1 huiskaart is (die dus 2 posities in neemt) en er dus nog 18 andere kaarten zijn? Of kan het zijn dat er ook meer (of juist minder!) kaarten zijn dan het aantal "percelen".

[hiekikowan]

Ik hoop tijd te vinden om mee te doen dit keer... Vindt het een leuke uitdaging

@raptorix Lijkt me uit te rekenen... Iedere kaart heeft een aantal waarmee aangegeven wordt hoeveel kaarten hiervan max. op je veld mogen liggen (voorbeeld heeft max. 48 kaarten) en het veld heeft een vast aantal kaarten wat er kan liggen (in het voorbeeld 18-2=16) Dus je kan volgens mij meer kaarten hebben dan er plek is...

[Bolukan]

raptorix schreef op woensdag 24 april 2013 @ 22:12:
Dus wanneer het oppervlak 5x5 is betekend dat er dan 1 huiskaart is (die dus 2 posities in neemt) en er dus nog 18 andere kaarten zijn? Of kan het zijn dat er ook meer (of juist minder!) kaarten zijn dan het aantal "percelen".

<kuch>5 x 5 - 2 = 23</kuch>

Volgens mij kan het aantal kaarten minder zijn dan de ruimte, alsmede groter dan de ruimte.

Om te voorkomen dat jullie een clustertje huren en de uitkomst hardcoded implementeren
houden we een aantal variabelen open:
- De aantallen van de kaarten
<knip>
- De grootte van het speelveld

[ Voor 30% gewijzigd door Bolukan op 24-04-2013 22:25 ]

[raptorix]

Bolukan schreef op woensdag 24 april 2013 @ 22:21:
[...]


<kuch>5 x 5 - 2 = 23</kuch>

LOL, eh ja dat bedoel ik dus

[raptorix]

bdalenoord schreef op woensdag 24 april 2013 @ 22:16:
Ik hoop tijd te vinden om mee te doen dit keer... Vindt het een leuke uitdaging

@raptorix Lijkt me uit te rekenen... Iedere kaart heeft een aantal waarmee aangegeven wordt hoeveel kaarten hiervan max. op je veld mogen liggen (voorbeeld heeft max. 48 kaarten) en het veld heeft een vast aantal kaarten wat er kan liggen (in het voorbeeld 18-2=16) Dus je kan volgens mij meer kaarten hebben dan er plek is...

Oki, in mijn code heb ik daar ook al rekening mee gehouden, mijn Hoofd Class heeft een speelveld en een stapel waarin ik inititeel alle kaarten plaats (als een kaart dus 5 keer voorkomt plaats ik hem 5 keer in de stapel)

[Anoniem: 303530]

Dat lijkt mij suboptimaal. Als je de set kaarten vervolgens gebruikt in een standaard algoritme (bijvoorbeeld A* of bruteforce) is de kans groot dat je bepaalde identieke combinaties dubbel berekend.

Idealiter wil je de combinaties genereren / kaarten trekken in een volgorde waar elke unieke combinatie slechts één keer wordt behandeld. Ik ben mij hoofd nog aan het breken hoe ik dat efficiënt kan gaan doen.

[liquid_ice]

LET OP :

Er waren wat vragen mbt de regels van het huis, deze hebben we verduidelijkt in de openingspost.

@Daos, De namen van de kaarten kunnen in elke testset verschillen, zo kan er spontaan een tuinkabouter bij zijn gekomen of andere kaarten zijn verdwenen.
We hebben de extra 'n' verwijderd uit de openingspost, maar zoals RobIII al schreef:

Be liberal in what you accept, and conservative in what you send output

[liquid_ice]

@Cornie, Arjan en ik vragen ons af in wat voor huis dat jij woont, gezien het huis van jou eerste testset:

input=voedsel,water,bevruchting,stro

[raptorix]

Anoniem: 303530 schreef op woensdag 24 april 2013 @ 22:35:
Dat lijkt mij suboptimaal. Als je de set kaarten vervolgens gebruikt in een standaard algoritme (bijvoorbeeld A* of bruteforce) is de kans groot dat je bepaalde identieke combinaties dubbel berekend.

Idealiter wil je de combinaties genereren / kaarten trekken in een volgorde waar elke unieke combinatie slechts één keer wordt behandeld. Ik ben mij hoofd nog aan het breken hoe ik dat efficiënt kan gaan doen.

Brute forcen vind ik sowieso minder, ik heb persoonlijk een andere strategie in mijn hoofd die ik natuurlijk niet ga verklappen

[Corniel]

liquid_ice schreef op woensdag 24 april 2013 @ 23:14:
@Cornie, Arjan en ik vragen ons af in wat voor huis dat jij woont, gezien het huis van jou eerste testset:

[...]

Don't shoot the randomizer!

[Daos]

Heeft iemand al een werkende 'puntenteller'? Ik zit nog steeds te knoeien met dat huis.

edit:
Ik kom nu uit op 34 punten bij de gegeven output.ini.

edit2:
Mijn puntenteller: http://www.schind.nl/Tuintopia%20Puntenteller.zip Laat het weten als er bugs zijn. Dat het geen schoonheidsprijs verdient weet ik. Testcode?? Oei... (is altijd frustrerend; het telprogramma was in een paar uur in elkaar gezet, maar het gaat mij weken kosten om alles netjes te testen)

[ Voor 77% gewijzigd door Daos op 25-04-2013 12:44 ]

[liquid_ice]

Je kan je uitkomsten verifiëren met http://www.tuintopia.nl/speldemo
Daar wordt dezelfde set gebruikt als in de voorbeeld kaarten.ini.

Al gebruikt deze demo geen zon en wind factoren, maarja jullie zijn natuurlijk ook beter dan zo'n demo

Je hebt wel de verduidelijkte regels mbt het huis gezien in de OP ?

[Daos]

Dan moet ik het interactief maken en de zon/wind uitschakelbaar maken. Is misschien iets voor het weekend...

Wat zijn eigenlijk die cijfers in de zon/wind symbolen? Soms staat er een 4; andere keer weer een 6.

[Corniel]

Ik heb een (denk ik) werkende puntentelling, en twee implementaties van een zoekalgoritme. Wel heb ik vandaag de wind- en beschutting-buren va het huis uitgebreid. Ik ging er vanuit dat dit er normaal gesproken drie zouden zijn, en niet vijf. Zo is het wel duidelijker.

code:

Score:93 (5.8125 pt/kaart)
[dierenstal, 2][dierenweide, 6][huis,        6][huis,     0][boomgaard,  6][bijenkorf,     4]
[kas,        6][rijbessen,   8][groentetuin, 8][mesthoop, 8][rijbessen, 10][insectenhotel, 6]
[vijver,     0][mesthoop,    6][groentetuin, 6][vijver,   0][notenboom,  7][insectenhotel, 4]

Mijn eerste implementatie geeft deze score voor de gegeven set in 0.1 seconde. Ik werk aan een betere zoekstrategie, zeker voor kleine velden is deze te snel tevreden (denk ik).

[liquid_ice]

@Daos, Dat is de hoogte van een object.

Deze wordt niet meegenomen in de programmeer wedstrijd, zo blijft er een reden om het spel zelf te kopen

In het echte spel is het zo dat een struik alleen schaduw kan leveren aan lagere objecten, dus niet aan een notenboom.
Ditzelfde principe telt ook voor de wind natuurlijk.

[Daos]

liquid_ice schreef op woensdag 24 april 2013 @ 23:11:
LET OP :
We hebben de extra 'n' verwijderd uit de openingspost

Volgens vandale moet die tussen-n er wel in bij paddenstoel. Zo staat het ook in het papieren/demospel.

[Corniel]

@Daos: het is een indentifier. Alleen de identifier "huis" is meer dan dat.

Met mijn tweede implementatie heb ik een score van 96. Wie biedt meer? (of minder)

code:

Score:96 (6.000 pt/kaart)
[rijbamboe, 2][dierenstal,    4][huis,        9][huis,     0][rijbessen, 8][pergolametdruif, 6]
[notenboom, 4][mesthoop,      9][kas,         9][mesthoop, 9][vijver,    1][insectenhotel,   6]
[notenboom, 3][insectenhotel, 6][groentetuin, 7][vijver,   0][rijbessen, 8][groentetuin,     5]

[Daos]

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

(misschien laat ik hem wel uit ratelen om te kijken wat het maximum is)

[Corniel]

@Daos: Maar misschien is mijn score wel verkeerd?

Ben trouwens ook benieuwd naar de score per veld waar je opkomt. Wellicht dat je niet als ik een debug-output kan genereren?

[Daos]

Corniel schreef op donderdag 25 april 2013 @ 20:56:
@Daos: Maar misschien is mijn score wel verkeerd?

Jouw score lijkt te kloppen. Mijn puntenteller komt zowel bij jouw 93 als 96 op hetzelfde uit.

Ben trouwens ook benieuwd naar de score per veld waar je opkomt. Wellicht dat je niet als ik een debug-output kan genereren?

Hoe bepaal jij de punten per kaart? Als ik achteraf tel bij een vol veld, dan tel ik alle verbindingen dubbel. Ik moet dan nog door 2 delen. Per kaart krijg ik daardoor vrij zeker een hogere waarde die niet te vergelijken is met die van jou.

[liquid_ice]

Daos schreef op donderdag 25 april 2013 @ 21:06:
[...]
Als ik achteraf tel bij een vol veld, dan tel ik alle verbindingen dubbel. Ik moet dan nog door 2 delen.

goed gezien , je moet inderdaad oppassen dat je niet alles dubbel telt.

[Anoniem: 303530]

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

Geef het niet te snel op . Mijn eerste* versie had ook 8 uur nodig om de optimale score te vinden, maar na veel optimalisaties draait het in 2 minuten.

*dat wil zeggen, de eerste versie waarbij dat binnen een dag mogelijk was.


Ik heb mijn algoritme nu geport naar zon/wind. Het huis is nog niet geïmplementeerd. Het lijkt alsof het een paar uur gaat duren voordat de optimale score er uit komt rollen. Maar dat komt nog wel.

[ Voor 16% gewijzigd door Anoniem: 303530 op 25-04-2013 23:08 ]

[Bolukan]

Het valt me op dat geen enkele kaart aan een 2e exemplaar van zichzelf gelegd punten oplevert. Dus hier een voorstel:

code:

[rivier]
aantal=10
input=water,afvalwater
output=water
zon=
schaduw=
wind=
windbeschutting=

[Corniel]

@Bolukan: Maakt het uit voor de input?

@Daos: Ik tel per kaart alleen de punten voor binnenkomen. Uitgaande punten zijn immers voor andere kaarten weer ingaande punten.

[liquid_ice]

Probeer de gemaakte optimalisaties ergens op te schrijven, dat maakt een mooi begin voor de omschrijving van je code als je de inzending opstuurt.

Dat is heel leuk voor anderen om na te lezen

[Corniel]

liquid_ice schreef op vrijdag 26 april 2013 @ 07:52:
Probeer de gemaakte optimalisaties ergens op te schrijven, dat maakt een mooi begin voor de omschrijving van je code als je de inzending opstuurt (..)

Are you talking to ME? (ik documenteer mijn code standaard als ik ontwikkel)

[liquid_ice]

in general speaking

@Bolukan, dump jij afvalwater in een rivier? foei toch

[ Voor 61% gewijzigd door liquid_ice op 26-04-2013 09:59 ]

[Daos]

brute-force/dfs gaat veel trager dan eerder verwacht. Het gaat een miljoenmiljard jaar duren.

Met een ander algoritme haal ik ook de 96:

code:

Score:96
[heg][notenboom][huis][huis][kippenhok][waterzuivering]
[dierenstal][notenboom][mesthoop][rijbessen][dierenweide][groentetuin]
[mesthoop][boomgaard][insectenhotel][rijbessen][insectenhotel][groentetuin]

edit: zelfs de 98:

code:

Score:98
[graanveld][dierenstal][huis][huis][notenboom][bijenkorf]
[vijver][vijver][rijbessen][mesthoop][notenboom][insectenhotel]
[kas][mesthoop][rijbessen][insectenhotel][boomgaard][bijenkorf]

[ Voor 24% gewijzigd door Daos op 26-04-2013 10:12 ]

[Anoniem: 510923]

@ Daos
De kaarten op de demo zijn nu bijgewerkt zoals de ontwerpen naar de drukker zijn gegaan en we gebruiken paddestoel zonder tussen n.

We hebben uiteindelijk gekozen om de tussen n weg te laten bij padde(n)stoel omdat dit de meeste gebruikte vorm is in de praktijk. Voor een uitgebreid verhaal rondom de tussen n bij padde(n)stoel kun je kijken op: http://www.onzetaal.nl/ta...es/paddestoel-paddenstoel

Grappig trouwens he, dat je bij het ontwikkelen van spellen opeens verstand van spelling moet hebben!!

[Corniel]

Ik heb nu ook een brute-force implementatie.

Vrije kaarten	sec.
06	0,005
07	0,045
08	0,309
09	1,639
10	34,566
11	225,834
12	3451,720

In deze testset heb ik allemaal verschillende kaarten, en speelborden, met zo min mogelijk (0, 1 en eenmaal 2) kaarten die 'over' zijn. conclusie: ik kom tot 11 kaarten met brute-force weg. Iemand die 12 (of meer?) haalt?

[Anoniem: 303530]

Het dataset van pedorus heeft 13 vrije kaarten, welke ik in 2 minuten bruteforce. Ik ben nog bezig met de tuintopia variant. (maar die draait, met zonder zon/wind/huis, in een seconde of 15)

Mijn algoritme is grotendeels bruteforce, maar er wordt veel informatie gecached.

[DaCoTa]

RobIII schreef op woensdag 24 april 2013 @ 00:09:
[...]

Ik spreek hier als iemand die (waarschijnlijk) niet meedoet en al zeker als non-organiserende en/of mod, maar ik zou persoonlijk Postel's Law hanteren (RobIII's version ):



[...]

Over deze law, wat zijn precies de specificaties van labels? Alleen lowercase letters, geen leestekens, cijfers, etc? Zonder specs geen input verificatie

[Memorice]

Voor de mensen met een brute force aanpak vraag ik me af of ze dit op een efficiente volgorde doen, i.e. je kunt vrij goedkoop een kleine aanpassing berekenen (bijv. 2 kaarten swappen) door door simpelweg de kaart van het bord te halen en de punten van de score af te halen en vervolgens de kaart ergens anders op het bord te plaatsen en de punten er weer bij op te tellen. Op deze manier bespaar je enorm veel rekenwerk ter vergelijking met wanneer je in twee opvolgende iteraties twee totaal verschillende borden berekend.

Verder vraag ik me af dat wanneer een brute force aanpak niet mogelijk blijkt, hoe effectief een simpele local search is. Dus steeds twee kaarten swappen als zolang dit de score verbeterd. Wanneer er geen twee kaarten meer zijn om te swappen en je dus in een local optima zit, kun je er voor kiezen om random wat kaarten te swappen om het vervolgens weer een local optima te vinden. Afhankelijk van de zoekruimte (e.g. er zijn bijvoorbeeld vele local optima die dezelfde score hebben als het global optima), zou dit best een effectieve manier zijn om tot een goede score te komen.

P.S. Ik heb zelf geen tijd om aan deze contest mee te doen, dus ik dacht ik gooi maar een paar ideeen in de groep, aangezien ik het wel een interessant topic vind, hopelijk is dat ok.