Programming Contest Nieuwe Stijl: Contest 4 *Score-update*

Toch zijn er 126 moves. Maar er zijn maar 63 mogelijke swaps.

Bugje ook al gevonden. Ik miste nog een paar patronen

quote:

rwb schreef op vrijdag 07 november 2008 @ 12:48:
[...]

Ja het is maar net wat je als unieke move defineert. ( Al had ik dat woord wel express weggelaten )

Een move is het verwisselen van twee aangrenzende blokjes. Dat je dat met de huidige methode op twee manieren kunt representeren maakt het niet twee verschillende moves. Imho. Of vind jij 23 ook een ander getal dan 0x17?

Ik denk dat ik deze keer ook maar eens ga proberen een werkend resultaat in te sturen.
Heb nu enige jaren programmeer ervaring maar heb nog nooit iets dergelijks gemaakt (met AI enz.).

Waarschijnlijk zal ik het in C# maken (hier ben ik nu sinds een maand of 2 mee bezig en vind het wel fijn werken).

Ben nu in ieder geval zover dat ik de bestanden uit kan lezen en in een speelveld kan plaatsen.
Zodra ik een beetje op de hoogte waar jullie ong. zijn zal ik eens wat posten!

Succes allemaal!

quote:

.oisyn schreef op vrijdag 07 november 2008 @ 13:26:
[...]
Een move is het verwisselen van twee aangrenzende blokjes. Dat je dat met de huidige methode op twee manieren kunt representeren maakt het niet twee verschillende moves. Imho. Of vind jij 23 ook een ander getal dan 0x17?

Ok in de uitleg staat inderdaad dat een Move het wisselen van 2 blokjes is, en niet het verplaatsen in de richting waarop je aangeeft.

Een nieuw persoonlijk record

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
2
1
5
6
3
5
6
3
1
5
2
1
6
6
4
2
6
6
1
2
6
4
1
5
1
4
5
6
2
5
2
3
4
2
6
4
3
4
6
4
5
1
3
5
6
2
3
1
2
6
2
x
3
4
1
6
6
1
5
3
1
3
5
4
5
3
3
2
6
4
1
6
3
6
3
x
3
x
1
3
3
5
5
2
6
4
3
5
1
6
1
2
4
6
5
2
5
4
2
x
x
x
4
x
4
4
3
6
6
5
1
2
4
3
2
1
6
3
2
5
4
6
1
2
6
x
x
x
5
x
x
1
5
4
2
6
3
1
3
4
3
5
3
3
4
3
5
2
4
1
5
x
x
x
6
x
x
6
1
6
4
5
2
5
2
3
3
6
2
6
1
4
x
1
3
4
x
x
x
x
7
x
x
3
5
6
1
6
1
1
3
2
1
2
6
4
5
x
x
x
x
x
x
x
x
x
8
x
x
1
1
3
2
3
4
4
5
5
2
5
1
6
x
x
x
x
x
x
x
x
x
x
9
x
x
2
2
4
6
5
6
5
6
3
x
x
4
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
2
3
3
2
6
5
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 1349100 points
Total moves..............: 6000
Succesful moves..........: 6000
Average score per move...: 225 points

Slow as hell, maar het is toch al iets werkend
Gevalideerd met oisyns validator. Mijn DoBestMove() functie lijkt wel niet 100% aangezien ik een ander pad neem na een aantal moves dan wat oisyn postte.

Twee verschillende moves kunnen exact dezelfde score opleveren. Welk pad wordt doorlopen is in dat geval afhankelijk van de volgorde waarin je de bestmove aanroept

quote:

Even voor de zekerheid: er mogen in kolommen.txt dus minder gems per kolom zijn dan er in de cellen van het speelveld passen? Is er geen minimumaantal aan gems per kolom?

Klopt.

Het minimum is wel 1 toch, lijkt me

Herko_ter_Horst wijzigde dit bericht 07-11-2008 14:26 (19%)

quote:

Herko_ter_Horst schreef op vrijdag 07 november 2008 @ 14:25:
[...]

Het minimum is wel 1 toch, lijkt me

eerder 2, anders wordt je veld nooit stabiel, maar je niet op 1 of 2 of whatever vast pinnen

Fastman wijzigde dit bericht 07-11-2008 14:30 (10%)

Kan ook 1 wezen, wanneer je veld op dat punt maar 2 blokjes hoog is

En dus kan het ook best 0 zijn

quote:

.oisyn schreef op vrijdag 07 november 2008 @ 14:39:
En dus kan het ook best 0 zijn

Wat natuurlijk alleen valide is als er een complete kolom een muur is.

Hoezo dat? 0 betekent gewoon dat een kolom niet meer bij wordt gevuld. Bijvullen hoef je alleen te doen wanneer je blokjes uit het veld hebt verwijderd.

voor normale oplossingen zullen er geen null-cellen zijn neem ik aan. Voor een robustheid-check misschien wel. maar ik zou er niet al te veel tijd spenderen aan null-cellen

quote:

RayNbow schreef op vrijdag 07 november 2008 @ 15:37:
Hoezo dat? 0 betekent gewoon dat een kolom niet meer bij wordt gevuld. Bijvullen hoef je alleen te doen wanneer je blokjes uit het veld hebt verwijderd.

We hadden het over het aantal gems voor een kolom in kolommen.txt. Als een muur helemaal tot bovenaan komt kunnen er 0 gems voor die kolom in kolommen.txt staan (oftewel een lege regel)

quote:

-NMe- schreef op vrijdag 07 november 2008 @ 05:53:
[...]

Dat gaat in de uiteindelijke set niet gebeuren, hooguit in een secundaire set die we eventueel uitvoeren om kijken hoe jullie scoren op het punt van defensief programmeren.

Nieuw vraagje: is een speelveld kolom met alleen maar een muur ook toegestaan? Hoe wordt dit dan voorgesteld in de kolommen.txt? Als een lege regel?

Does it matter? Je kunt prima 100 gems in die kolom zetten. Ze worden alleen nooit gedropt.

Erg verleidelijk om ook te beginnen aan deze contest. Heel leuk gedaan. Eerst maar even kijken of ik straks tijd vrij heb en het niet ten koste zal gaan van andere projecten

Wat ik wel vreemd vind is dat je weet welke stenen er zullen vallen en je daar dus gebruik van kan maken, terwijl dat bij de echte bejeweled niet het geval is.
Ook vind ik het score systeem een beetje jammer, waarbij alles boven de 4 stenen dezelfde score krijgt.
En een combosysteem had het allemaal een stuk interessanter gemaakt, aangezien je dan wat meer voordeel hebt bij het vooruit denken.

BarôZZa wijzigde dit bericht 07-11-2008 16:17 (53%)

quote:

.oisyn schreef op vrijdag 07 november 2008 @ 16:10:
Does it matter? Je kunt prima 100 gems in die kolom zetten. Ze worden alleen nooit gedropt.

^^ wat hij zegt.

quote:

rwb schreef op vrijdag 07 november 2008 @ 15:28:
[...]

Wat natuurlijk alleen valide is als er een complete kolom een muur is.

Nee hoor. We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven. Ik zeg niet dát het gebeurt, maar het zou zomaar kunnen. Neem dus niet zomaar wat aan.

NMe wijzigde dit bericht 07-11-2008 16:17 (49%)

quote:

We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven.

quote:

Dat gaat in de uiteindelijke set niet gebeuren, hooguit in een secundaire set die we eventueel uitvoeren om kijken hoe jullie scoren op het punt van defensief programmeren.

Spreek je hier jezelf tegen of snap ik niet helemaal wat je bedoelt?

quote:

-NMe- schreef op vrijdag 07 november 2008 @ 16:15:
[...]
Nee hoor. We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven. Ik zeg niet dát het gebeurt, maar het zou zomaar kunnen. Neem dus niet zomaar wat aan.

Ok dus je kunt ook een impliciete "muur" krijgen.

quote:

writser schreef op vrijdag 07 november 2008 @ 16:27:
[...]


[...]


Spreek je hier jezelf tegen of snap ik niet helemaal wat je bedoelt?

Klopt, maar kun je voortaan linkjes naar de originele post toevoegen zodat de context waaruit je de quote hebt gehaald ook makkelijk opzoekbaar is?

quote:

writser schreef op vrijdag 07 november 2008 @ 16:27:
[...]

[...]

Spreek je hier jezelf tegen of snap ik niet helemaal wat je bedoelt?

Ik doelde in die tweede post eigenlijk meer op dat defensief coden waar ik het in de eerste post over had. Mijn boodschap is kort samengevat: hou gewoon met zoveel mogelijk dingen die niet gedefinieerd zijn rekening. Er zijn in deze contest een aantal manieren om robuustheid te checken, en de kans is groot dat we daar, naast de score-check, even de tijd voor nemen.

quote:

rwb schreef op vrijdag 07 november 2008 @ 09:07:
[...]

Wat is er dan zo complex aan je puntentelling? Bij mij is dat echt maar een paar regels code.

Bij mij is het een grote recursieve zooi van if-statements.

quote:

-NMe- schreef op vrijdag 07 november 2008 @ 16:15:
[...]

^^ wat hij zegt.

[...]

Nee hoor. We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven. Ik zeg niet dát het gebeurt, maar het zou zomaar kunnen. Neem dus niet zomaar wat aan.

Ik maakte me alleen zorgen om het aantal kolommen v.s. de breedte van het speelveld Ik ga er nu iig ervan uit dat deze altijd gelijk zijn.

Overigens, weer een klein performancehit geoptimaliseerd: testset is nu in 20 secs klaar ipv 25
Biedt tzt wel ruimte om te gaan denken over een vooruitdenkend AI

BalusC wijzigde dit bericht 07-11-2008 19:02 (13%)

Yoepie, 1.950 punten !

Een groot aantal dagen zitten aanhikken hoe ik de verticale en horizontale lijnen zou combineren tot een figuur, waarbij vierkantjes of andere vreemde situaties geen probleem zijn, en de code toch simpel blijft. Vanavond eruit gekomen met de gewenste korte code.

Op naar de AI voor de zetten.

Nou, ik heb de 1950 en de 3450 ook gehaald (C++). Tijd om een AI te schrijven en wat te profilen. Of misschien eerst een simpele GUI. Ik ben nu al helemaal tureluurs van het controleren van speelvelden in de console

quote:

BalusC schreef op vrijdag 07 november 2008 @ 19:00:
[...]

Ik maakte me alleen zorgen om het aantal kolommen v.s. de breedte van het speelveld Ik ga er nu iig ervan uit dat deze altijd gelijk zijn.

Het aantal rijen in het kolommenbestand zal altijd overeen komen met de breedte van het speelveld.

Hoe is robuustheid hier eigenlijk gedefinieerd? Als je mijn programma bijvoorbeeld een kolommen.txt geeft met meer regels dan dat er kolommen zijn in speelveld.txt of met rare tekens, etc, dan exit hij gewoon met een foutmelding dat de input niet valide is.
Of is het beter als ik de input zodanig interpreteer/aanpas dat er toch iets van output uit komt? Bijv. door bij te veel input kolommen maar gewoon de eerste X te nemen? Maar dan kan de output (misschien) niet meer goed gevalideerd worden, omdat de validator en mijn oplossing verschillende interpretaties kunnen doen.

Bij overduidelijk verkeerde input zie ik liever een foutmelding dan een geforceerde run zonder betekenis omdat je niet weet hoe die extra kolom geïnterpreteerd dient te worden of wat je met die andere tekens aan moet. Robuust wil in mijn ogen zeggen dat je programma ziet dat de input niet in orde is en daarnaar handelt, in plaats van blind toch aan het rekenen te slaan.

quote:

writser schreef op vrijdag 07 november 2008 @ 22:44:
Ik ben nu al helemaal tureluurs van het controleren van speelvelden in de console

Gewoon een nette toRML() schrijven en GoT misbruiken om velden te controleren

Wat is het bestandsformaat van RML? Is het een soort UBB-code? Het staat niet eens op wikipedia: Wikipedia: RML .

quote:

writser schreef op zaterdag 08 november 2008 @ 11:23:
Wat is het bestandsformaat van RML? Is het een soort UBB-code? Het staat niet eens op wikipedia: Wikipedia: RML .

Zie era.zer in "Programming Contest Nieuwe Stijl: Contest 4" en verder. Hier wordt de taal uitgelegd: Overzicht van UBB-codes

quote:

BalusC schreef op zaterdag 08 november 2008 @ 01:45:
[...]

Gewoon een nette toRML() schrijven en GoT misbruiken om velden te controleren

Of GetHTML(), GetPNG() etc.

quote:

writser schreef op vrijdag 07 november 2008 @ 22:44:
Ik ben nu al helemaal tureluurs van het controleren van speelvelden in de console

SetConsoleTextAttribute() op windows, en anders iets met ncurses op linux

Ik heb ook 1950 punten (was wel even puzzelen waar het nou fout ging bij het matchen van shapes ).

Nog output wegschrijven, een AI en wat optimaliseren.

Heb eindelijk een iets van werkende versie hij vind constant combinaties. haalt ze ook weg enz .. vandaag het XL veld eens geprobeerd .. foutje opgelost dus gaat lekker.
Zal in de komende dagen hem proberen zo te krijgen dat ik heb in de andere Validator kan proberen en kijken of alles dan ook echt klopt (moet naar Output file nog maken) maar heb er goede hoop op.

Trouwens wat iemand anders zei over combo's .. vind ik ook . waarom niet een combosysteem.. want nu is alles boven 5 gewoon 5.. terwijl als je een T als combinatie hebt:

11111
00100
00100

heb je 7 stenen maar toch nog maar 250 punten. dus maakt een combinatie met 2 meer stenen zonder enig nut .. nu is dit wel aan te passen dat hij die combinaties niet zelf maakt . maar toch. zou leuker zijn als je voor die combinaties wel meer punten kreeg.

quote:

freaky1983 schreef op zaterdag 08 november 2008 @ 17:06:
Trouwens wat iemand anders zei over combo's .. vind ik ook . waarom niet een combosysteem.. want nu is alles boven 5 gewoon 5.. terwijl als je een T als combinatie hebt:

a) liggen de regels nu vast; als je dat "halverwege" gaat veranderen is de contest zo kapot
b) die regel maakt het IMHO juist alleen maar leuker; je moet nu een beetje intelligent je score zien te behalen i.p.v. gewoon "dom" zo groot mogelijke figuren wegspelen

Zo groot mogelijke figuren zijn te krijgen lijkt me nog best lastig(T-vorm komt niet bepaald snel voor).
Met combo's bedoelde ik overigens niet (en dit is tegen freaky1983) het aantal stenen boven de 5, maar dat wanneer je een paar stenen wegspeelt, de rest wegzakt en er gelijk weer stenen weggaan dat je dan een extra score krijgt.

De meest simpele:

00100
11200
00022

Dus dat je dan de 2's pakt, waarna de 1tjes een combo opleveren (meestal krijg je dan een multiplier bonus, dus dat de 2x combo 2x zoveel punten oplevert. Als er daarna weer stenen gelijk weggaan bijvoorbeeld 3x).

Overigens kunnen de regels nu natuurlijk niet meer veranderd worden. Maar misschien een leuk idee voor een eventuele volgende contest.

Vandaag weer verder gegaan. Heb eindelijk de findSets() method geïmplementeerd. In deze method markeer ik alle sets en bereken ik de score. Dit alles in een enkele in iteratie met daarin een recursieve call. Ik heb de testset van BalusC gebruikt en heb ook 2450 > 3150 > 3400 > 3450 punten..

Het starten van de game, inlezen v/d files, de [het finden van sets + opvullen + score berekenen ]-loop duurt bij deze 50 bij 50 testset met 4 stappen op mijn C2D-E6600 en 2GB mem 'slechts' 17 ms, waarvan 12 ms voor het inlezen en initializeren, en 5 ms voor de loop met berekeningen. Genoeg voor vandaag.

Volgende stap is findMoves(), en daarna natuurlijk de AI.

Pinobigbird wijzigde dit bericht 08-11-2008 22:39 (6%)
Reden: tijden opgesplitst

quote:

BarôZZa schreef op zaterdag 08 november 2008 @ 20:38:
Overigens kunnen de regels nu natuurlijk niet meer veranderd worden. Maar misschien een leuk idee voor een eventuele volgende contest.

Een volgende contest gaat niks meer met Bejeweled te maken krijgen, denk ik. Verder: het is minstens net zo tricky om te zorgen dat je precies 5 (niet meer, niet minder) gems wegspeelt voor je score-optimalisatie.

Whoehoe! 1950 na de eerste stabilisatieslag. Uiteindelijk met een paar kleine aanpassingen volgens mij best wel efficiënt en met mijn initiële idee. Het vinden van de combo's vond ik trouwens niet zo'n heel groot probleem. Nu maar eens een poging doen om een AI te bakken.

Het is een interessante contest en ik zie dat er al heel wat mensen goede prestaties hebben neergezet.
Zelf was ik ook aan een algoritme begonnen, maar aangezien ik voor m'n werk ook full time programmeur ben, heb ik geen zin meer om 's avonds ook nog te programmeren. Hierom heb ik helaas moeten besluiten om deze contest te laten varen...

Vanavond is het me gelukt om (valide) zetten te maken. Zonder AI is de score nog laag. (Komt er ook een prijs voor de laagste score bij 100.000 zetten Echter, het is nu formeel gezien inzendbaar, een mijlpaal voor mij . Ik zal me nu gaan richten op de AI. Btw, oplossing draait in 9 seconde (VB Express 2008).

Edit: En van onderen af zoeken naar een zet levert 8.606.750 punten op.

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
2
4
4
5
4
1
3
2
4
3
4
3
4
5
4
6
1
1
3
1
6
2
5
4
1
1
2
6
4
3
5
4
2
1
2
4
6
1
5
3
3
5
6
2
5
2
4
6
6
5
6
2
x
1
5
4
6
2
3
6
4
3
1
2
6
4
2
1
4
5
4
5
6
5
5
4
x
3
x
4
5
2
1
1
5
5
6
3
1
3
2
3
3
4
1
4
6
4
6
4
x
x
x
4
x
6
6
5
4
6
3
6
5
6
4
2
4
1
6
6
2
2
1
6
4
6
x
x
x
5
x
x
1
1
3
2
4
5
2
5
1
1
6
6
1
3
6
1
2
5
2
5
x
x
x
6
x
x
3
5
6
5
2
1
6
5
6
3
6
5
1
6
3
x
6
6
2
x
x
x
x
7
x
x
5
1
2
4
1
3
2
3
5
1
5
4
4
5
x
x
x
x
x
x
x
x
x
8
x
x
6
6
4
2
5
3
3
1
1
3
4
5
4
x
x
x
x
x
x
x
x
x
x
9
x
x
2
2
5
3
5
1
2
5
4
x
x
4
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
1
6
1
6
4
2
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
4
6
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 7894300 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 78 points
Move with highest score..: #43499 (1150 points)

Kijk, daar komen de smoesjes al

quote:

Onbekend schreef op zaterdag 08 november 2008 @ 23:21:
Het is een interessante contest en ik zie dat er al heel wat mensen goede prestaties hebben neergezet.
Zelf was ik ook aan een algoritme begonnen, maar aangezien ik voor m'n werk ook full time programmeur ben, heb ik geen zin meer om 's avonds ook nog te programmeren. Hierom heb ik helaas moeten besluiten om deze contest te laten varen...

Chickeeeen! Bokôôk bok bok bok bok.

quote:

Bolukan schreef op zaterdag 08 november 2008 @ 23:45:
Edit: En van onderen af zoeken naar een zet levert 8.606.750 punten op.

Hmm goeie tip:

Bejeweled started at Sat Nov 08 19:15:21 BOT 2008

Result:
             111111111122222
   0123456789012345678901234
  ---------------------------
 0|2511465325311344642452451|
 1|2652556256245314122656646|
 2|#45561516543641645643654#|
 3|#266522654631345265325###|
 4|#243136543424655414612###|
 5|##41335465515511254146###|
 6|##524415543641254#232####|
 7|##63322463526424#########|
 8|##6562331261255##########|
 9|##225461534##6###########|
10|###2453454###############|
11|#######63################|
12|#########################|
13|#########################|
  ---------------------------

Total score........: 13488450
Total matches......: 237692
Total moves........: 100000
Duration...........: 28183ms
Output written to..: C:\Java\workspace2\Bejeweled\uitvoer.txt

Bejeweled finished at Sat Nov 08 19:15:49 BOT 2008

Ipv 7705450 in 20 secs.

offtopic:
Hmm, die accent grave voor de 1 in de inhoudsopgave, hoort die daar

quote:

Patriot schreef op zondag 09 november 2008 @ 00:20:

offtopic:
Hmm, die accent grave voor de 1 in de inhoudsopgave, hoort die daar

offtopic:
Alswe dan toch de startpost aan het verbeteren zijn:

In kolommen.txt wordt bepaald met hoeveel verschillende blokjes je te maken krijgt. Dit zijn er minimaal vier en maximaal tien, genummerd van 0 tot 9.

Dat moet van 0 tot en met 9 zijn.

quote:

Patriot schreef op zondag 09 november 2008 @ 00:20:

offtopic:
Hmm, die accent grave voor de 1 in de inhoudsopgave, hoort die daar

Lang leve ` als push-to-talk button in Ventrilo.

quote:

Pinobigbird schreef op zondag 09 november 2008 @ 00:54:
[...]

offtopic:
Alswe dan toch de startpost aan het verbeteren zijn:

In kolommen.txt wordt bepaald met hoeveel verschillende blokjes je te maken krijgt. Dit zijn er minimaal vier en maximaal tien, genummerd van 0 tot 9.

Dat moet van 0 tot en met 9 zijn.

Dat staat er toch ook?

Kunnen er linkjes geplaatst worden naar oisyns validator en enkele posts met testsets? Zoals mijn 50x50 ding

Done.

quote:

Onbekend schreef op zaterdag 08 november 2008 @ 23:21:
maar aangezien ik voor m'n werk ook full time programmeur ben, heb ik geen zin meer om 's avonds ook nog te programmeren.

En ik zie dat je C# kunt, je bent welkom om mee te werken aan m'n code. Alles werkt in principe, dus kun je wat AI doen, of performance

quote:

Pinobigbird schreef op zondag 09 november 2008 @ 00:54:
[...]

offtopic:
Alswe dan toch de startpost aan het verbeteren zijn:

In kolommen.txt wordt bepaald met hoeveel verschillende blokjes je te maken krijgt. Dit zijn er minimaal vier en maximaal tien, genummerd van 0 tot 9.

Dat moet van 0 tot en met 9 zijn.

Samenwerken mag, maar meld het wel even als je dit doet.

Daarnaast moet meld volgens mij met dt.

edit: staan de linkjes naar de validator e.d. in de startpost?

JMfx wijzigde dit bericht 09-11-2008 12:10 (6%)

Wel, ik ben eigenlijk ook stiekem aan het meewerken Maar ik wilde zeker zijn dat mijn C#-progseltje effectief goeie uitvoer zou produceren voor ik dat publiek maakte. Als ik straks geen tijd genoeg meer heb om verder te werken heb ik tenminste iets toonbaars om in te leveren.

Met de eerste set krijg ik 7653500 punten in 100.000 moves, loopt 187 seconden lang. Moet alleen nog de output even gaan valideren en wat zoekalgoritme's optimaliseren.

quote:

JMfx schreef op zondag 09 november 2008 @ 12:06:
[...]

Samenwerken mag, maar meld het wel even als je dit doet.

Daarnaast moet meld volgens mij met dt.

offtopic:
In elk geval niet in hedendaags Nederlands voor zover ik weet.

quote:

edit: staan de linkjes naar de validator e.d. in de startpost?

Kijk eens 2 en 3 posts boven je en onderaan de startpost.

quote:

-NMe- schreef op zondag 09 november 2008 @ 13:59:
[...]

offtopic:
In elk geval niet in hedendaags Nederlands voor zover ik weet.

[...]

Kijk eens 2 en 3 posts boven je en onderaan de startpost.

Ah gevonden, bedankt. Meld is hier toch persoonsvorm, of is het gebiedende wijs dat er geen t achter komt?

quote:

JMfx schreef op zondag 09 november 2008 @ 14:54:
[...]


Ah gevonden, bedankt. Meld is hier toch persoonsvorm, of is het gebiedende wijs dat er geen t achter komt?

Kwestie van vervangen door lopen. Het is 'gebiedende wijs' als je er dan toch een label aan wil hangen (en als ik me niet vergis); ik kan best aardig spellen maar weet zelden hoe die flauwekul ook weer allemaal heet

' t Kan wel met een t, maar da's wel een beetje ouderwets.

_{tijden op een eeepc, dus enkel relatief vergelijken}
5000 keer mijn field clonen door manueel rows/cols te doorlopen: 1000ms
met array.copy 176ms

Ik had alles mooi OO uitgewerkt.. In mijn jagged field array (jagged is vlugger dan multi) zitten nu Stone objecten.
Als ik nu gewoon een int array maak met de waarden van de stenen. En dan een array met hun dirty bits of andere zaken die nu een property zijn van, zou dat een merkbaar verschil in snelheid geven?

Waarom zijn jagged arrays sneller dan gewone rechthoekige arrays? Bij jagged arrays is het noodzakelijk om twee maal te controleren of een index niet buiten bereik is. Bij een rechthoekige array (die eenvoudig gesimuleerd kan worden door een enkele array) is dit slechts eenmaal nodig.

Dat ligt er maar net aan of Stone een ref-type of value-type is. Als het een value-type was dan niet, maar anders waarschijnlijk wel, zeker gezien het feit dat die code zo vaak aangeroepen wordt.

Ik ben de laatste paar dagen bezig geweest m'n code om te gooien zodat er gebruik kan worden gemaakt van meerdere processoren (en tegelijkertijd tussentijdse states te bewaren zodat ze niet meerdere keren hoeven worden doorgerekend), en m'n code is nu langzamer terwijl hij minder berekeningen doet. Puur door het feit dat eerst alles lekker bij elkaar stond en dus alles in de cache bleef staan, ookal werden dingen dubbel berekend. 't Is ook duidelijk dat m'n solver memory-bound is. Door twee cores te gebruiken haal ik maar 13% winst (en met die twee cores is het alsnog iets langzamer dan m'n vorige implementatie, maar dat heeft waarschijnlijk ook te maken dat ik de taken nog iets te fine-grained opsplits, en op een quad core boek ik waarschijnlijk wel wat winst)

.oisyn wijzigde dit bericht 09-11-2008 18:19 (5%)

quote:

Marcj schreef op zondag 09 november 2008 @ 18:17:
Waarom zijn jagged arrays sneller dan gewone rechthoekige arrays? Bij jagged arrays is het noodzakelijk om twee maal te controleren of een index niet buiten bereik is. Bij een rechthoekige array (die eenvoudig gesimuleerd kan worden door een enkele array) is dit slechts eenmaal nodig.

In v1 was er in ieder geval een verschil, maar het hangt er maar net van af. Ik denk dat era.zer niet daadwerkelijk getest heeft, aangezien het performance-verschil vooral in onnodige (un)boxing lijkt te zitten, maar hij gebruikt nu geen primitief type.

Maar voor de beste performance denk ik dat je het beste kan kiezen voor een doodnormale array van lengte hoogte*breedte van een primitief type (byte?). Ik denk dat sneller een field clonen dan met deze representatie niet mogelijk is. De eerste bytes zijn dan kolom 1, daarna komt kolom 2, etc. De volgorde kolom, rij is niet toevallig. Aangezien je meer met kolommen doet, is het handig om met "++" en "--" snel naar een volgende/vorige rij te gaan. Mooier wordt het er allemaal vast niet op, maar hopelijk wel sneller. Van een dirty bit heb ik al beweerd dat die niet perse nodig is.

quote:

Marcj schreef op zondag 09 november 2008 @ 18:17:
Waarom zijn jagged arrays sneller dan gewone rechthoekige arrays

hier zijn ze ook rechthoekig, maar jagged is in C# normaal vlugger en ze waren makkelijker om de velden in te lezen. Een veld heeft bij mij sowieso een rows en columns property waar ik de veldgrootte bijhoud.
Het verschil:
jagged: 7662ms
multi: 8019ms

5000 loops in 100x100 veld. Dus het maakt toch iets uit.

Ik gebruik dirty bits en moet ze ook elke keer 'resetten', uiteindelijk duurt dat 1ms op een ganse testset, dus veel maak het niet uit.

Voor de mensen die een soort van flood-algo gebruiken, dit is wat ik doe:
dmv iteratie: voor elke cel: calclength()
daarin recursief calclength() aanroepen voor elke buur. voor de huidige steen wordt er gekeken of hij 2 buren heeft en als dat zo is length++ en het resultaat dat calcLength() van de kinderen returnt erbij op tellen.
Stenen die deel uit maken van een scorende figuur worden dirty gemarkeerd. De eerste iteratie laat dirty stones links liggen.

Het werkt perfect qua logica en het is toch een mooi alogritme? Alleen traag-als-**** en ik zie niet in waarom.

Fastman wijzigde dit bericht 09-11-2008 19:20 (22%)

quote:

pedorus schreef op zondag 09 november 2008 @ 18:58:
Van een dirty bit heb ik al beweerd dat die niet perse nodig is.

En ik heb al beweerd dat het niet gebruiken van een dirty bit niet per se sneller is.

quote:

era.zer schreef op zondag 09 november 2008 @ 19:01:
[...]

hier zijn ze ook rechthoekig, maar jagged is in C# normaal vlugger

Heb je daar een bron danwel eigen argumentatie van, want ik geloof er geen zak van namelijk
Oh nvm, ik zie nu pas de link die pedorus gaf.

.oisyn wijzigde dit bericht 09-11-2008 19:45 (36%)

Ik denk dat ik vanavond of anders deze week de relevante zooi eens ga interfacen en een andere, erg basale, implementatie ga uitproberen om tijd te winnen en zodoende tijd over heb om vooruit te kijken naar moves/matches

quote:

era.zer schreef op zondag 09 november 2008 @ 19:01:
[...]

hier zijn ze ook rechthoekig, maar jagged is in C# normaal vlugger en ze waren makkelijker om de velden in te lezen. Een veld heeft bij mij sowieso een rows en columns property waar ik de veldgrootte bijhoud.
Het verschil:
jagged: 7662ms
multi: 8019ms

Nadat ik die link heb gelezen snap ik het probleem, maar ik ging even uit van Java. Heb je ook al geprobeert het om te zetten naar een single array, waarbij je zelf de index berekent? Dit zou nog sneller moeten zijn.

quote:

Het werkt perfect qua logica en het is toch een mooi alogritme? Alleen traag-als-**** en ik zie niet in waarom.

Vergeet niet dat recursie een redelijke overhead heeft. Zoals je het nu verteld is er vrij weinig logica met veel recursie, waar bij elke nieuwe call een aantal dingen op de stack worden geplaatst. Probeer de recursie is om te zetten naar een normale loop, dit zou al best kunnen schelen.

Status-update wat mij betreft: ik ga nu eindelijk weer eens verder, mijn validator doet het nog niet eens goed

ik ga er nog wat aan prutsen en anders vliegt de recursie eruit. Een single array ga ik ook eens proberen, dat zou supersnel moeten gecopy'd kunnen worden dan. Misschien wordt het dan eens tijd voor wat comments in de code

quote:

era.zer schreef op zondag 09 november 2008 @ 19:01:
trager is een jagged in ieder geval niet.

In sommige situaties zou dat dus wel kunnen (bijv: alleen aanmaken)

quote:

Voor de mensen die een soort van flood-algo gebruiken, dit is wat ik doe:
dmv iteratie: voor elke cel: calclength()

Dit is inefficiënt. Het lijkt me een stuk sneller om in dat for-loopje gelijk een huidige waarde en huidige rijlengte bij te houden, en er zo achter te komen dat je een groepje hebt gevonden. Daarna kun je alsnog (bijvoorbeeld (deels) recursief) bijzondere groepjes afhandelen. Dan vergelijk je dezelfde buren niet steeds opnieuw.

quote:

pedorus schreef op zondag 09 november 2008 @ 20:47:
[...]

Dit is inefficiënt. Het lijkt me een stuk sneller om in dat for-loopje gelijk een huidige waarde en huidige rijlengte bij te houden, en er zo achter te komen dat je een groepje hebt gevonden. Daarna kun je alsnog (bijvoorbeeld (deels) recursief) bijzondere groepjes afhandelen. Dan vergelijk je dezelfde buren niet steeds opnieuw.

Ik pak het op precies dezelfde manier aan. Een loop om door elke rij te gaan en telkens bijhouden wat de waarde en coordinaten zijn van de huidige reeks. Als je een nieuwe waarde (kleur) tegenkomt betekent dit dat de huidige reeks is afgelopen. Je evalueert de oude reeks (3 of meer in lengte) en start een nieuwe.

Daarna reduceer je de rij shapes door shapes met overlappende coordinaten (en waarde) te matchen tot één shape. Je kan dit in stappen doen door eerst twee lijn shapes te matchen en daarna te controleren of deze nieuwe shape ook weer te matchen is met andere lijn shapes.

JMfx wijzigde dit bericht 09-11-2008 21:28 (15%)

Ben vandaag ook maar eens begonnen aan een implementatie.
Stenen droppen en verwijderen doet ie al.
Volgende stap is de eerste de beste move maken.
Daarna eens over de AI beginnen denken.

Gisteravond ook begonnen en heb inmiddels een frameworkje waarbij een speelveld word gegenereerd met de mogelijkheid tot het verwijderen van stenen en het automatisch binnenvallen van nieuwe (het prille begin dus ). Ben nu bezig met validatie.

Eerst met c++ aan de slag gegaan maar toch maar overgestapt naar c#. Laatstgenoemde is het eigenlijk het enige waar ik de laaste 2 jaar meer gewerkt heb, persoonlijk vind ik het ook een stuk fijner .

Enfin, zo te zien zijn er aardig wat deelnemers. Ik ben benieuwd hoeveel mensen ook daadwerkelijk een (werkend) programma insturen .

quote:

JMfx schreef op zondag 09 november 2008 @ 21:25:
[...]


Ik pak het op precies dezelfde manier aan.

Nee, dat is niet de manier waar pedorus het over heeft . Het ging om een floodfill algo. Overigens ben ik nu de laatste hand aan het leggen aan een plane sweep algo die alle blokjes maar 1x visit (dus O(n)), nog even de laatste bugs eruit vissen en dan kijken hoe de performance is tov mijn vorige floodfill implementatie...

quote:

JMfx schreef op zondag 09 november 2008 @ 21:25:
Ik pak het op precies dezelfde manier aan. Een loop om door elke rij te gaan en telkens bijhouden wat de waarde en coordinaten zijn van de huidige reeks. Als je een nieuwe waarde (kleur) tegenkomt betekent dit dat de huidige reeks is afgelopen. Je evalueert de oude reeks (3 of meer in lengte) en start een nieuwe.

Coordinaten? Ik zou zeggen dat startpositie (int) genoeg is. En de zoekpositie natuurlijk waarover het forloopje loopt, hm toch 'coordinaten' idd

quote:

Daarna reduceer je de rij shapes door shapes met overlappende coordinaten (en waarde) te matchen tot één shape. Je kan dit in stappen doen door eerst twee lijn shapes te matchen en daarna te controleren of deze nieuwe shape ook weer te matchen is met andere lijn shapes.

Dat zou ik afraden, want dat is potentieel O(N^2) speed. Als je een rijtje gevonden hebt, dan kun je gewoon gelijk checken of er rijtjes de andere richting op zijn van hetzelfde soort. Zo ja, dan zet je het aantal punten van het groepje op 250, en begin je de floodfill-achtige procedure op die extra gevonden diamantjes. Dit hoef je natuurlijk alleen voor de eerste richting te doen (zeg kolom).

quote:

.oisyn schreef op zondag 09 november 2008 @ 23:02:
[...]

Nee, dat is niet de manier waar pedorus het over heeft . Het ging om een floodfill algo. Overigens ben ik nu de laatste hand aan het leggen aan een plane sweep algo die alle blokjes maar 1x visit (dus O(n)), nog even de laatste bugs eruit vissen en dan kijken hoe de performance is tov mijn vorige floodfill implementatie...

Inderdaad. Ik denk dat het voordeel toch vooral te halen valt door niet het hele veld te gaan checken. 2x visiten (horizontaal en vertikaal) is ook O(n), en het hele veld visiten hoeft waarschijnlijk maar 1x te gebeuren (beginsituatie).

quote:

.oisyn schreef op zondag 09 november 2008 @ 23:02:
[...]

Nee, dat is niet de manier waar pedorus het over heeft . Het ging om een floodfill algo. Overigens ben ik nu de laatste hand aan het leggen aan een plane sweep algo die alle blokjes maar 1x visit (dus O(n)), nog even de laatste bugs eruit vissen en dan kijken hoe de performance is tov mijn vorige floodfill implementatie...

offtopic:
Ahh, dat doet me denken aan het vak Computational Geometry bij informatica. Het mooie plane sweep-algoritme om een Voronoi-diagram te construeren. Voor veel studenten een ware marteling . Linkje met coole applet: http://www.personal.kent....ronoi/Fortune/fortune.htm

Leuk, ik ben erg benieuwd naar de performance. Ik weet niet precies wat je aan het implementeren bent, maar een klassiek scanline algoritme met een binaire boom waar je alle 'horizontale figuurtjes tot-nu-toe' in op slaat is O(N log N) maar de constante kosten lijken me vrij hoog.

writser wijzigde dit bericht 09-11-2008 23:36 (15%)

quote:

pedorus schreef op zondag 09 november 2008 @ 23:10:
Dat zou ik afraden, want dat is potentieel O(N^2) speed. Als je een rijtje gevonden hebt, dan kun je gewoon gelijk checken of er rijtjes de andere richting op zijn van hetzelfde soort. Zo ja, dan zet je het aantal punten van het groepje op 250, en begin je de floodfill-achtige procedure op die extra gevonden diamantjes. Dit hoef je natuurlijk alleen voor de eerste richting te doen (zeg kolom).

Jep. het probleem (de "challenge") is dat in een groot figuur ook kan voorkomen dat je weer naar links, rechts, boven en onder moet gaan zoeken. Je moet eigenlijk bijhouden van welke richting je komt, bedenk ik me net. Misschien ga ik dat eens implementeren.

p.s.: als de concurrent een O(N^2) oplossing heeft kan je dat toch alleen maar aanmoedigen!

Wel interessant allemaal dat O gebeuren. Ik zal er eens na kijken nadat ik mijn implementatie af heb. Misschien kan ik er dan nog wat aan verbeteren

quote:

writser schreef op zondag 09 november 2008 @ 23:21:
[...]

offtopic:
Ahh, dat doet me denken aan het vak Computational Geometry bij informatica. Het mooie plane sweep-algoritme om een Voronoi-diagram te construeren. Voor veel studenten een ware marteling . Linkje met coole applet: http://www.personal.kent....ronoi/Fortune/fortune.htm

offtopic:
Ik heb de master GIVE (Geometry, Imaging and Virtual Environments) gevolgd aan de UU, dat zat vol met dat soort dingen

quote:

Leuk, ik ben erg benieuwd naar de performance. Ik weet niet precies wat je aan het implementeren bent, maar een klassiek scanline algoritme met een binaire boom waar je alle 'horizontale figuurtjes tot-nu-toe' in op slaat is O(N log N) maar de constante kosten lijken me vrij hoog.

Denk eraan dat je hier te maken hebt met een vast raster. Veel O(n log n) dingen kunnen dan ineens in O(n). Een goed voorbeeld hiervan is de radix sort. Zo hoef je in dit geval geen boom te gebruiken omdat je (bijvoorbeeld) in elk blokje dat deel uitmaakt van een figuur een referentie mee kunt geven naar dat figuur. Kijken of op een plek een figuur zit is dan dus O(1).

quote:

pedorus schreef op zondag 09 november 2008 @ 23:10:
[...]

Inderdaad. Ik denk dat het voordeel toch vooral te halen valt door niet het hele veld te gaan checken. 2x visiten (horizontaal en vertikaal) is ook O(n), en het hele veld visiten hoeft waarschijnlijk maar 1x te gebeuren (beginsituatie).

Ik checkte sowieso al niet het hele veld

quote:

JMfx schreef op maandag 10 november 2008 @ 00:01:
Wel interessant allemaal dat O gebeuren.

Leesvoer dan: Wikipedia: Big O notation

Ik ga ook maar eens proberen mee te doen aan deze contest.

De enige taal waar ik echt een expert in ben is PHP maar dat is me toch iets te langzaam. Dus ik ga het toch maar in C++ of Java maken. Mijn voorkeur gaat uit naar C++ maar aan de andere kant leer is java ook wel een handige keuze omdat ik dan meteen weer een heleboel extra java kennis opdoe voor school

Maarja, dat zie ik van de week nog wel :-)

quote:

Jasperrr schreef op maandag 10 november 2008 @ 00:39:
Ik ga ook maar eens proberen mee te doen aan deze contest.

De enige taal waar ik echt een expert in ben is PHP maar dat is me toch iets te langzaam.

Ik zou het niet te zwart/wit stellen. Sure, C++ of Java is leuk, maar je kunt (bijv.) ook je idee eerst uitwerken en verfijnen in PHP en het dan omklussen naar een andere taal. Zo heb je waarschijnlijk veel sneller je proof-of-concept werkend en wie weet, voldoet die al best leuk. Zo niet dan kan omklussen nog altijd.

Ik zeg niet dat dit "the way to go" is, maar ik vind wel dat er wat meer grijstinten zijn

Toch een paar vreemde uitkomsten in C#

5 miljoen keer een array clonen geeft:
- byte array clonen: 1690ms
- int array clonen: 2338ms
- jagged byte array clonen: 1478ms
- multi byte array clonen: 16756ms

multi arrays zijn dus 11 keer trager en zelfs een 1-dimensionale array is trager dan een jagged.

Fastman wijzigde dit bericht 10-11-2008 10:50 (12%)

quote:

era.zer schreef op maandag 10 november 2008 @ 09:31:
Toch een paar vreemde uitkomsten in C#

5 miljoen keer een array clonen geeft:
- byte array clonen: 1690ms
- int array clonen: 2338ms
- jagged byte array clonen: 1478ms
- multi byte array clonen: 16756ms

multi arrays zijn dus 11 keer trager en zelfs een 1-dimensionale array is trager dan een jagged.

Hoe test jij dit dan? Ik krijg hele andere uitslagen als ik het test, en bij mij is het clonen van een Jagged array juist een stuk langzamer. Clone je bij een Jagged array wel alle Child array's?
Mijn test resultaten zijn

Aanmaken van Array van 50*50 en 5.000.000 keer clonen
- Byte Array: 759 ms
- Int Array: 1938 ms
- Jagged Byte Array: 9425 ms
- Multi Byte Array: 655 ms

dus bij mij is een multidimensionale array het snelst

Woy wijzigde dit bericht 10-11-2008 10:16 (16%)

quote:

Jasperrr schreef op maandag 10 november 2008 @ 00:39:
Ik ga ook maar eens proberen mee te doen aan deze contest.

De enige taal waar ik echt een expert in ben is PHP maar dat is me toch iets te langzaam. Dus ik ga het toch maar in C++ of Java maken. Mijn voorkeur gaat uit naar C++ maar aan de andere kant leer is java ook wel een handige keuze omdat ik dan meteen weer een heleboel extra java kennis opdoe voor school

Maarja, dat zie ik van de week nog wel :-)

Om die big O notatie er nog even bij te halen:

Een in Assembly geschreven O(2^N) algoritme zal trager zijn dan een in php geïmplementeerd O(N log N) algoritme.

Laat je niet afschrikken door alle praat over C++. Ook in voorgaande contests zijn php oplossingen ingeleverd. De php oplossing bij de eerste contest is bijvoorbeeld in geen enkele categorie als laatste geeindigd.

De PHP-inzendingen van contest 2 en 3 wel dus?

writser: je legt Janoz nu woorden in de mond, dat heeft ie niet gezegd. Je kan uiteraard zelf even de uitslagen opzoeken

Het nadeel wat sommige mensen denken te hebben omdat ze PHP gebruiken is echt nagenoeg 0. Een slim algoritme in PHP is vele malen beter dan iets gaan schrijven in C++ waar je totaal niet mee bekend bent
Er wordt wat mij betreft net iets teveel gefocused nu op de te gebruiken taal. PHP kan met deze contest prima meedoen (en ja, ook winnen), dat hebben de eerdere contests zeker bewezen.

Creepy wijzigde dit bericht 10-11-2008 10:43 (5%)

quote:

rwb schreef op maandag 10 november 2008 @ 09:57:
Aanmaken van Array van 50*50 en 5.000.000 keer clonen
- Byte Array: 759 ms
- Int Array: 1938 ms
- Jagged Byte Array: 9425 ms
- Multi Byte Array: 655 ms

dus bij mij is een multidimensionale array het snelst

Bij era.zer krijg ik het idee dat hij misschien Stopwatch.Reset() vergeet. Bij jou krijg ik het idee dat je niet vooraf GC.Collect() doet en achter elkaar door test (hoewel zelfs met GC.Collect() latere tests het iets makkelijker kunnen krijgen...). Toch maar zelf even getest dan (12*25 array):

Elapsed for single = 00:00:01.0296696
Elapsed for singleint = 00:00:02.2187403
Elapsed for multi = 00:00:01.1283383
Elapsed for jagged = 00:00:06.8589683

50*50:

Elapsed for single = 00:00:04.7934620
Elapsed for singleint = 00:00:16.0538065
Elapsed for multi = 00:00:04.8475214
Elapsed for jagged = 00:00:33.2332729

En zoals ik al verwachte is single toch gewoon het snelst... (Hoewel het verschil niet significant is.)

lol dat van die multi klopt niet had een nulletje teveel maar is nog steeds traagst

quote:

Clone je bij een Jagged array wel alle Child array's?

code:

jaggedclone = (byte[][])jagged.Clone();

Meer moet dat toch niet zijn.

code: http://cl1p.net/gotttt/
toch niets mis mee?

Fastman wijzigde dit bericht 10-11-2008 11:07 (99%)

quote:

pedorus schreef op maandag 10 november 2008 @ 10:43:
[...]

Bij era.zer krijg ik het idee dat hij misschien Stopwatch.Reset() vergeet. Bij jou krijg ik het idee dat je niet vooraf GC.Collect() doet en achter elkaar door test (hoewel zelfs met GC.Collect() latere tests het iets makkelijker kunnen krijgen...). Toch maar zelf even getest dan (12*25 array):

Elapsed for single = 00:00:01.0296696
Elapsed for singleint = 00:00:02.2187403
Elapsed for multi = 00:00:01.1283383
Elapsed for jagged = 00:00:06.8589683

50*50:

Elapsed for single = 00:00:04.7934620
Elapsed for singleint = 00:00:16.0538065
Elapsed for multi = 00:00:04.8475214
Elapsed for jagged = 00:00:33.2332729

En zoals ik al verwachte is single toch gewoon het snelst... (Hoewel het verschil niet significant is.)

Idd was ik GC.Collect vergeten. Doe nu een GC.Collect en Thread.Sleep voor elke test.

ByteArray: 2.657 ms
IntArray: 4.211 ms
JaggedArray: 22.282 ms
MultiArray: 2.598 ms
MultiStructArray: 2.599 ms
MultiClassArray: 4.188 ms

de onderste 2 zijn een multidimensionale array waarvan er een met een struct met een byte value en de andere een class met een byte value.

edit:

Soms is de ByteArray inderdaad iets sneller als de MultiArray, maar het ontloopt elkaar niet echt.

Woy wijzigde dit bericht 10-11-2008 11:02 (4%)

quote:

era.zer schreef op maandag 10 november 2008 @ 10:50:
lol dat van die multi klopt niet had een nulletje teveel maar is nog steeds traagst


[...]

Opvullen met random data en loopje.


[...]
code:

jaggedclone = (byte[][])jagged.Clone();

Meer moet dat toch niet zijn.

code: http://cl1p.net/gotttt/
toch niets mis mee?

dan moet je deze code eens uitvoeren
C#:

1 2 3 4 5 6 7 8 9 10 11 12

byte[][] jagged = new byte[2][]; for (int x = 0; x < 2; x++ ) {     jagged[x] = new byte[2]; } byte[][] cloned = (byte[][]) jagged.Clone(); cloned[0][0] = 20; Console.WriteLine("Cloned[0][0]: {0}", cloned[0][0]); Console.WriteLine("jagged[0][0]: {0}", jagged[0][0]);

okay that might be an problem

Dat is wel een groot verschil tussen een single en jagged array. Ik neem aan dat het hier over C# gaat. Zelf gebruik ik Java, waarin de multi arrays (byte[,] b) niet bestaan. Daarvoor gebruik ik een array van arrays (jagged, byte [][] b), die dus in C# het traagst zijn.

Ik vraag me nu af wat sneller is (in Java): Een single array waarbij je telkens zelf de index moet berekenen
(b[x][y] wordt b[x+y*(rowLength)]) in een enkele for-loop, of gewoon een 2D array met een dubbele for-loop. Een voordeel van de 2D array is natuurlijk wel dat de kolom-array in een rij-array slechts zo lang hoeft te zijn als de kolom diep is, wat dus in het speelveld per kolom verschilt.

quote:

Pinobigbird schreef op maandag 10 november 2008 @ 11:03:
Dat is wel een groot verschil tussen een single en jagged array. Ik neem aan dat het hier over C# gaat. Zelf gebruik ik Java, waarin de multi arrays (byte[,] b) niet bestaan. Daarvoor gebruik ik een array van arrays (jagged, byte [][] b), die dus in C# het traagst zijn.

Ik vraag me nu af wat sneller is (in Java): Een single array waarbij je telkens zelf de index moet berekenen
(b[x][y] wordt b[x+y*(rowLength)]) in een enkele for-loop, of gewoon een 2D array met een dubbele for-loop. Een voordeel van de 2D array is natuurlijk wel dat de kolom-array in een rij-array slechts zo lang hoeft te zijn als de kolom diep is, wat dus in het speelveld per kolom verschilt.

De index zelf berekenen is niet veel anders dan wat de compiler voor je doet bij een 2D array, alleen als je alle formaten variabel hebt kan het wat uitmaken, maar dat is performance technisch waarschijnlijk niet interessant.

Ik zelf had een week geleden ofzo een brainwave gehad mbt. het opslaan van het grid. Nu ik deze methode uitgewerkt heb lijkt het echter veel trager te zijn dan wat ik al had
Nog maar eens goed naar de implementatie kijken en anders is het back to the drawing board...

quote:

Janoz schreef op maandag 10 november 2008 @ 10:13:
[...]

Om die big O notatie er nog even bij te halen:

Een in Assembly geschreven O(2^N) algoritme zal trager zijn dan een in php geïmplementeerd O(N log N) algoritme.

Veel te kort door de bocht. Bij grote N natuurlijk wel, maar je vergeet voor het gemak maar even de invloed van c (nee, niet de lichtsnelheid, hoewel het algoritme op relatvistische snelheden natuurlijk ook langzamer draait ). En die c is in PHP wel behoorlijk hoog.

quote:

Pinobigbird schreef op maandag 10 november 2008 @ 11:03:
Dat is wel een groot verschil tussen een single en jagged array. Ik neem aan dat het hier over C# gaat. Zelf gebruik ik Java, waarin de multi arrays (byte[,] b) niet bestaan. Daarvoor gebruik ik een array van arrays (jagged, byte [][] b), die dus in C# het traagst zijn.

Nee! We hebben nu alleen het stukje getest waarop jagged arrays in .NET het slechtste presteren: het kopieren. Over het algemeen zijn jagged arrays juist sneller dan multi-arrays (maar niet sneller dan single), omdat multi-arrays slecht geoptimized worden (in ieder geval in de eerste versies).

Voor Java zou ik trouwens ook eens kijken naar de winnaar van de Tetris-contest, daarin zit onder andere een truc voor geheugenbeheer (weet niet of dat nog steeds opgaat). Verder gok ik dat single het snelst is in Java, ja.

Over PHP: Ik ben nu toevallig bezig aan een projectje in ASP.NET, omdat het sterke vermoeden is dat PHP slecht presteert op algoritmisch vlak, terwijl je ASP.NET ook makkelijk shared kan hosten (kan ik van java/c++ niet zeggen)... In heb ik ook wel een oplossing gezien waarbij een PHP-site gewoon een system(...) call deed naar een C++ applicatie. Aan de andere kant heb ik in talen als PHP en Javascript best nog wel ingewikkelde algoritmes gezien/gemaakt die toch snel genoeg draaiden. Het is ook niet zo dat PHP altijd te traag is, maar in deze contest gok ik toch dat je makkelijk met PHP in de middenmoot kan eindigen, maar dat de echte top toch lastig wordt.

Het is iig minder kort door de bocht dan 'met php ben je bij voorbaat kansloos binnen deze contest'

quote:

Pinobigbird schreef op maandag 10 november 2008 @ 11:03:
Dat is wel een groot verschil tussen een single en jagged array. Ik neem aan dat het hier over C# gaat. Zelf gebruik ik Java, waarin de multi arrays (byte[,] b) niet bestaan. Daarvoor gebruik ik een array van arrays (jagged, byte [][] b), die dus in C# het traagst zijn.

Dat ligt niet aan het platform, maar in de inherente opslag van een dergelijke datastructuur. Bij jagged arrays staan je rijen (of kolommen) niet bij elkaar in een enkel geheugenblok, wat nadelig is voor je cache (de cpu kan dan ook niet meer speculeren door alvast data dat verderop ligt naar binnen te halen). Daarnaast heb je een extra level van indirectie (een extra stall omdat eerst array[x] moet worden uitgelezen voor array[x][y] kan worden uitgelezen).

Overigens, het performanceverschil in .Net waar pedorus het over heeft is jagged versus multi, niet jagged versus single. En het lijkt me echt stug dat jagged arrays ook sneller performen dan single arrays met eigen indexing.

quote:

(b[x][y] wordt b[x+y*(rowLength)]) in een enkele for-loop, of gewoon een 2D array met een dubbele for-loop. Een voordeel van de 2D array is natuurlijk wel dat de kolom-array in een rij-array slechts zo lang hoeft te zijn als de kolom diep is, wat dus in het speelveld per kolom verschilt.

Ik zou sowieso column-major gaan werken (dus [x][y] of [x * height + y]) wegens de aard van de game. Ik gebruik zelf trouwens een column-major array waarin alle muren zijn weggelaten (niet elke kolom neemt dus even veel ruimte in in de array). Indexering doe ik dmv een lookup-table. De extra indirectie hier is niet erg omdat ik dezelfde table overal gebruik en hij vrij klein is (max 100 bytes, past dus in 2 cachelines omdat ik hem op 64 bytes align)

.oisyn wijzigde dit bericht 10-11-2008 11:57 (7%)

quote:

.oisyn schreef op maandag 10 november 2008 @ 11:53:
En het lijkt me echt stug dat jagged arrays ook sneller performen dan single arrays met eigen indexing.

Ik bedenk me nu dat jagged arrays 2 voordelen hebben. Naast dat je muren niet hoeft op te slaan, is er nog een belangrijk voordeel: Je hoeft natuurlijk alleen maar kolommen te kopieren als er iets in veranderd. Meestal gaat dat maar om 1 of 3 kolommen van de zeg 25...
Als ik dit eens snel test dan is kopieren met jagged met kolomhoogte 50 behoorlijk sneller (factor 2), maar met hoogte 12 bepaald niet (ook factor 2 trager).

pedorus wijzigde dit bericht 10-11-2008 12:28 (13%)

quote:

pedorus schreef op maandag 10 november 2008 @ 12:13:
[...]

Ik bedenk me nu dat jagged arrays 2 voordelen hebben. Naast dat je muren niet hoeft op te slaan

Als je de rest van mijn post ook had gelezen dan had je gezien dat ik dat met een single array ook niet deed

quote:

is er nog een belangrijk voordeel: Je hoeft natuurlijk alleen maar kolommen te kopieren als er iets in veranderd. Meestal gaat dat maar om 1 of 3 kolommen van de zeg 25...

Nou vergeet je de chain reactions (die behoorlijk vaak voorkomen in de testset), maar los daarvan kun je losse kolommen ook gewoon kopieren in een single array. Bovendien kun je de aansluitende kolommen ook in 1 keer kopiëren ipv dat je n afzonderlijke kolommen moet gaan kopiëren.

Wat heb je nou precies getest? Heb je sourcecode?

.oisyn wijzigde dit bericht 10-11-2008 12:35 (3%)

Heb die van mij eindelijk goed door de Validator gekregen (na kleine bugs eruit gehaald te hebben) weet ik iig dat hij drops en checks goed doet .. ook combinaties er goed uit haalt en die punten ook goed bijrekend.. Nu tijd om de computer het "simpele" werk te doen en uit te bereiden

Toch blij eindelijk weer iets verder te zijn