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

[Janoz]

pedorus schreef op maandag 03 november 2008 @ 09:57:
[...]

Vooral bij veel verschillende stenen wil je vaak juist zo hoog mogelijk in het veld iets doen. Als er hoog iets kan, en er daaronder iets verandert, dan kan de move hoog vaak niet meer. Andersom, als er hoog iets verandert, dan blijft de lage move ook nog mogelijk. Veel zo hoog mogelijke moves doen is een goede tactiek om redelijk ver te komen in het originele spel (link van Megamind is stiekem toch v1, maar met minder reclames). Sterker nog, het lijkt wel alsof dat spel nooit eindigt...

De afweging die je daarbij moet maken is hoe groot de kans is dat er geen zet meer te doen is. Beide keuzes gaan op maar hebben een andere motivatie:

Zo lang mogelijk doorspelen: Zetten hoog doen
Zo hoog mogelijke score met gelijkblijvend aantal zetten: Zetten laag doen

[.oisyn]

rwb schreef op maandag 03 november 2008 @ 09:04:
[...]

Het hoeft natuurlijk helemaal niet recursief. In pseudocode heb ik het gewoon zo

code:

DoMove();

do
{
    DropBlocks();
} while( RemoveShapes() );

Ik gok dat je dit bedoelt:

code:

DoMove();

while( RemoveShapes() )
{
    DropBlocks();
}

Of doet je DoMove() ook al een DropBlocks() RemoveShapes()?

[Woy]

.oisyn schreef op maandag 03 november 2008 @ 12:06:
[...]

Ik gok dat je dit bedoelt:

code:

DoMove();

while( RemoveShapes() )
{
    DropBlocks();
}

Of doet je DoMove() ook al een DropBlocks()?

Nee mijn DoMove verwijderd wel shapes, maar dropt nog geen blocks, in DoMove controleer ik namenlijk op een andere manier welke shapes er verwijderd moeten worden.

[ Voor 12% gewijzigd door Woy op 03-11-2008 12:24 ]

[.oisyn]

Euh ja ik bedoelde ook RemoveShapes()

[Woy]

.oisyn schreef op maandag 03 november 2008 @ 12:32:
Euh ja ik bedoelde ook RemoveShapes()

Ja dus Al heten de methods bij mijn weer anders, waardoor het in die context wat duidelijker is.

[ Voor 21% gewijzigd door Woy op 03-11-2008 12:37 ]

[RayNbow]

Ik heb geen idee of ik tijd heb om mee te doen, maar...

-NMe- schreef op dinsdag 28 oktober 2008 @ 20:41:
[...]

De regels en andere afspraken

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

1. [...]
2. [...]
3. 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 liever de file uploadt en ernaar linkt vanuit je email, dan mag dat ook. Als je executable afhankelijk is van minder gangbare DLL's of als deze andere afhankelijkheden heeft, stuur dan instructies mee voor het runnen van je applicatie.

[...]

...mag je ook instructies meesturen betreffende commandline flags? De RTS van een Haskell progsel gebruikt standaard namelijk maar 1 OS thread. Met de volgende flags kun je 2 OS threads inzetten:

> foo.exe +RTS -N2 -RTS

@.oisyn hieronder:
Crap... die post gemist

[.oisyn]

-NMe- in "Programming Contest Nieuwe Stijl: Contest 4"
Ja dus

[NMe]

ScottB schreef op maandag 03 november 2008 @ 04:54:
Op de beginscore (1250) kwam ik wel

Is dat een tikfout, of had je echt 1250? Want volgens alle validators die ik tot nu toe voorbij heb zien komen zou de uitkomst bij het eerste stabiele veld een score van 1950 moeten zijn.

[Verwijderd]

-NMe- schreef op maandag 03 november 2008 @ 14:44:
[...]

Is dat een tikfout, of had je echt 1250? Want volgens alle validators die ik tot nu toe voorbij heb zien komen zou de uitkomst bij het eerste stabiele veld een score van 1950 moeten zijn.

Waarschijnlijk bedoelt hij dat hij op 1250 punten uitkomt na de eerste serie blokjes verwijderen. Het veld is dan nog niet stabiel, je moet nog twee keer blokjes droppen en weghalen voor het veld stabiel is. Die 1250 punten klopt dan wel (is ook meerdere keren genoemd).

[.oisyn]

-NMe- schreef op maandag 03 november 2008 @ 14:44:
[...]

Is dat een tikfout, of had je echt 1250? Want volgens alle validators die ik tot nu toe voorbij heb zien komen zou de uitkomst bij het eerste stabiele veld een score van 1950 moeten zijn.

Het blijft blijkbaar een steeds terugkomend probleem. Wellicht handig om in de topicstart te vermelden dat bij de testset de volgende rijen worden verwijderd: .oisyn in "Programming Contest Nieuwe Stijl: Contest 4", en dat de totaalscore na elke stap resp. 1250 en 1950 punten is?

Ik vind trouwens dat er veel te weinig outputs getoond worden. Kom op, ik wil resultaten zien! Anders heb ik niets om tegenop te werken (of gaan jullie pas posten als de behaalde score hoger is dan die van mij? )

[ Voor 14% gewijzigd door .oisyn op 03-11-2008 15:04 ]

[Woy]

.oisyn schreef op maandag 03 november 2008 @ 15:00:
[...]
Ik vind trouwens dat er veel te weinig outputs getoond worden. Kom op, ik wil resultaten zien! Anders heb ik niets om tegenop te werken (of gaan jullie pas posten als de behaalde score hoger is dan die van mij? )

Maar als ik een output post, dan pas jij alleen je programma aan zodat die dezelfde output geeft . Vanavond zal ik er weer eens verder mee gaan, en kijken of ik een wat slimmere AI kan maken.

[.oisyn]

Klopt, het enige wat mijn AI doet is een handmatig in programmacode ingevoerde lijst van moves outputten

[ Voor 49% gewijzigd door .oisyn op 03-11-2008 15:09 ]

[BalusC]

Of je hebt plenty tijd over of je bent echt goed vanwege je ervaring als gamedeveloper. Ik heb niet hele dagen de tijd gehad. Ik heb in totaal ongeveer 8 uur aan tijd ingestoken tot de huidige status (domweg 1e de beste matches vinden zonder enige moves), dat lijkt me wel netjes voor een developer zonder enige game-AI ervaring. Ik heb ook een beroep en een sociaal leven Ach, we hebben nog 2 maanden

[Pinobigbird]

Games programmeren is tegenwoordig kinderspel geworden:
nieuws: Microsoft wil kinderen laten programmeren met Boku

[Woy]

.oisyn schreef op maandag 03 november 2008 @ 15:09:
Klopt, het enige wat mijn AI doet is een handmatig in programmacode ingevoerde lijst van moves outputten

Dan kan je aardig snel typen, als je die 100.000 moves overgetyped heb. Dat vind ik eigenlijk nog indrukwekkender!

Pinobigbird schreef op maandag 03 november 2008 @ 15:18:
Games programmeren is tegenwoordig kinderspel geworden:
nieuws: Microsoft wil kinderen laten programmeren met Boku

Dat was het toch altijd al?
Wikipedia: Logo (programming language)
Toen ik klein was speelde ik daar ieder geval mee.

[ Voor 24% gewijzigd door een moderator op 03-11-2008 16:30 . Reden: Linkje was stuk :P ]

[.oisyn]

BalusC schreef op maandag 03 november 2008 @ 15:13:
Of je hebt plenty tijd over of je bent echt goed vanwege je ervaring als gamedeveloper. Ik heb niet hele dagen de tijd gehad.

Mijn ervaring als gamedeveloper zit voornamelijk in technologie (3d engines), niet in AI . In fact, dit is pas mijn 2e serieuze AI attempt, de vorige was die tetris got contest (waarin ik overigens alleen de eerste paar weken enthousiast was en er daarna geen aandacht meer aan heb besteed). Ik denk dat ik er nu ongeveer 24 uur in heb zitten, waarvan iets van 8 in alleen m'n AI (de rest is framework en validator).

dat lijkt me wel netjes voor een developer zonder enige game-AI ervaring

Beetje suffe opmerking gezien het feit dat voor dat deel wat je nu gedaan hebt totaal geen AI ervaring nodig hebt

[ Voor 16% gewijzigd door .oisyn op 03-11-2008 15:30 ]

[BalusC]

Ja, dat was bij nader inzien een suffe opmerking

[NMe]

rwb schreef op maandag 03 november 2008 @ 15:29:
Dat was het toch altijd al?
Wikipedia: Logo (programming language)
Toen ik klein was speelde ik daar ieder geval mee.

SuperLOGO toevallig?

[Woy]

-NMe- schreef op maandag 03 november 2008 @ 16:31:
[...]
SuperLOGO toevallig?

Het zou kunnen ja, ik weet het niet precies meer. Het was ieder geval een of andere variant van Logo

[Scott]

rwb schreef op maandag 03 november 2008 @ 09:04:
[...]

Het hoeft natuurlijk helemaal niet recursief. In pseudocode heb ik het gewoon zo

code:

DoMove();

do
{
    DropBlocks();
} while( RemoveShapes() );

[...]

.oisyn heeft hierboven de juiste zetten gezet die gedaan moeten worden voordat je de eerste zet kunt doen.

Hmm, stom, heb me blind zitten staren op een oplossing die duidelijk ook anders kan.. Thanks, ik ga hier eens naar kijken

Verwijderd schreef op maandag 03 november 2008 @ 14:51:
[...]

Waarschijnlijk bedoelt hij dat hij op 1250 punten uitkomt na de eerste serie blokjes verwijderen. Het veld is dan nog niet stabiel, je moet nog twee keer blokjes droppen en weghalen voor het veld stabiel is. Die 1250 punten klopt dan wel (is ook meerdere keren genoemd).

Klopt.

[.oisyn]

rwb schreef op maandag 03 november 2008 @ 15:29:
[...]

Dan kan je aardig snel typen, als je die 100.000 moves overgetyped heb. Dat vind ik eigenlijk nog indrukwekkender!

Met Find&Replace en regular expressions kom je een heel end in Visual Studio hoor
Iets als
find "{:d} {:d} {.}"
replace "game.ApplyMove(\1, \2, '\3');"

[Serpie]

.oisyn schreef op maandag 03 november 2008 @ 15:00:
[...]
Ik vind trouwens dat er veel te weinig outputs getoond worden. Kom op, ik wil resultaten zien! Anders heb ik niets om tegenop te werken (of gaan jullie pas posten als de behaalde score hoger is dan die van mij? )

Ik ben verkeerd begonnen en zit nu met een veels te traag algoritme, vanavond even wat anders proberen. Maar tot nu toe heb ik nog geen output kunnen genereren

[Brian]

Zo, ik ben ook maar eens begonnen. Ik heb geen idee waar mijn schip zal stranden, ik heb slechts een klein jaar Java ervaring maar ben toch vast besloten om een heel eind te komen. Ik ga sowieso niet voor een snelste score of veiligste code. Nee, mijn persoonlijk doel is om dit uberhaupt werkend te krijgen. En zoals je ziet ben ik wel een beetje GUI geil

Tot nu toe kan mijn progsel speelvelden inlezen, kolommen inlezen en beide tekenen op een leuk panel die daar voor bedoelt is

edit: Oh, en nog héél erg bedankt voor de icoontjes

[ Voor 7% gewijzigd door Brian op 03-11-2008 18:37 ]

[RobIII]

Brian schreef op maandag 03 november 2008 @ 18:30:
edit: Oh, en nog héél erg bedankt voor de icoontjes

Volgens mij zijn die niet van "ons" of crisp AFAIK. En ik mis nog 0, 8 en 9 volgens mij

Edit:
Ah, ik zie nu era.zer in "Programming Contest Nieuwe Stijl: Contest 4" pas; laatste wat ik gezien had daarover was crisp in "Programming Contest Nieuwe Stijl: Contest 4".

[ Voor 27% gewijzigd door RobIII op 03-11-2008 19:03 ]

[Bolukan]

Ik zie er nu maar zes. Waar zijn die anderen?

[Brian]

RobIII schreef op maandag 03 november 2008 @ 18:55:
[...]

Volgens mij zijn die niet van "ons" of crisp AFAIK. En ik mis nog 0, 8 en 9 volgens mij

Die staan volgens mij niet in de test kolommen.txt. Maar hoe dan ook, toch bedankt voor het rippen/zippen Scheelt weer een hoop werk.

[Megamind]

Nee idd, ik kijk net effe, in de testset komen geen 0, 8 of 9ens voor

[pedorus]

Bolukan schreef op maandag 03 november 2008 @ 18:55:
Ik zie er nu maar zes. Waar zijn die anderen?

era.zer in "Programming Contest Nieuwe Stijl: Contest 4"

Ik zou trouwens dat grid met witte lijnen weghalen. Dan krijg je geen hermann rooster.

[TaraWij]

.oisyn schreef op zondag 02 november 2008 @ 22:01:
[...]

Waarom heb je de illusie dat je eventueel de compiler eruit programmeert met je naar eigen zeggen zeer beperkte asm kennis?

Daar ken ik zowat de basis wel van, ik doelde eigenlijk eerder op nog niet veel af te weten van hoe te optimaliseren, ga wanneer optimalisaties nog de enkele taak is hier enkele artikelen en voorbeelden voor zoeken. Ik moet uiteindelijk ergens beginnen om te leren dingen te optimaliseren, uiteraard moet ik er dan ook op letten dat dit niet ten koste gaat van andere pluspunten. ;-)

---

Op het moment kan hij enkel nog maar het speelveld inlezen en mooi weergeven (wel in console maar dat doet er niet zo toe), volgende stap is natuurlijk tot een staat geraken waar de AI uiteindelijk iets kan doen.

[ Voor 22% gewijzigd door TaraWij op 03-11-2008 20:02 ]

[Verwijderd]

TaraWij schreef op maandag 03 november 2008 @ 19:56:
[...]
Ik moet uiteindelijk ergens beginnen om te leren dingen te optimaliseren

Tuurlijk moet je ergens beginnen, maar dat doe je niet door te proberen snellere assembly te schrijven dan je compiler. Optimaliseren doe je (in 99% van de gevallen) door
1) Is je algorithme wel optimaal? Je kunt misschien wel 10% tijdwinst halen door allerlei kleine micro-optimalisaties, maar als iemand anders en 10 keer zo snel algorithme heeft heb je daar niets aan.
1A) Hoe sla je je data op? Kun je daar iets aan verbeteren?
2) Ben je niet telkens bezig dezelfde dingen te berekenen? Oftewel kun je bepaalde data cachen en hergebruiken?
3) En dan ook echt pas als derde stap, niet als eerste: Probeer de meest tijdrovende functies nog wat te optimaliseren.

[BalusC]

Cool, dat GUI .. * BalusC is helaas niet zo'n GUI held. Hopelijk verlies ik hiermee niet punten

Als ik vanavond tijd heb dan zal ik beginnen met code dat (vooralsnog de eerste de beste) valide move opzoekt

[ Voor 35% gewijzigd door BalusC op 03-11-2008 20:28 ]

[RobIII]

BalusC schreef op maandag 03 november 2008 @ 20:26:
Hopelijk verlies ik hiermee niet punten

Die kun je ruimschoots goedmaken door eender welke bribe bij je inzending in te sturen Voor de 'main contest' doet alleen de pure uitvoer + score er toe; dat we als bijzaak naar andere zaken kijken (robuustheid, coolness etc. ) en daar eventueel ook wat eervolle vermeldingen van doen is bijzaak.

[? ?]

Dat kruis net voor het stabiel worden vormt een probleempje...
mijn recursief algoritme om figuren te vinden/tellen verhindert het teruggaan naar het blokje vanwaar men net kwam (kwestie van niet oneindig te loopen of noord-zuid dubbel te tellen). Maar bij zo'n kruis moet het eigenlijk wél terug gaan. Grrr...
Misschien altijd eerst helemaal naar links gaan ofzo, ik ga er wat op bedenken, maar de komende dagen even niet.

Over de AI's:
Gaat iemand iets anders doen dan mogelijkheden in tree-vorm afgaan, de 'beste' nemen en doorrekenen?
In principe is zo'n pad geen garantie op het beste pad, dat kan evengoed beginnen met de 100 slechts-moves-ever.

[ Voor 53% gewijzigd door ? ? op 03-11-2008 21:42 ]

[writser]

Een soort flood-fill algoritme moet wel werken lijkt me.

[RobIII]

Mijn validatortje nog even bijgeschaafd en optimized (van ~5 sec. naar <1 sec):

[table border=1 bordercolor=#000 fontsize=8][tr][td bgcolor=#fff][/td][td bgcolor=#fff width=10 height=10]0[/td][td bgcolor=#fff width=10 height=10]1[/td][td bgcolor=#fff width=10 height=10]2[/td][td bgcolor=#fff width=10 height=10]3[/td][td bgcolor=#fff width=10 height=10]4[/td][td bgcolor=#fff width=10 height=10]5[/td][td bgcolor=#fff width=10 height=10]6[/td][td bgcolor=#fff width=10 height=10]7[/td][td bgcolor=#fff width=10 height=10]8[/td][td bgcolor=#fff width=10 height=10]9[/td][td bgcolor=#fff width=10 height=10]10[/td][td bgcolor=#fff width=10 height=10]11[/td][td bgcolor=#fff width=10 height=10]12[/td][td bgcolor=#fff width=10 height=10]13[/td][td bgcolor=#fff width=10 height=10]14[/td][td bgcolor=#fff width=10 height=10]15[/td][td bgcolor=#fff width=10 height=10]16[/td][td bgcolor=#fff width=10 height=10]17[/td][td bgcolor=#fff width=10 height=10]18[/td][td bgcolor=#fff width=10 height=10]19[/td][td bgcolor=#fff width=10 height=10]20[/td][td bgcolor=#fff width=10 height=10]21[/td][td bgcolor=#fff width=10 height=10]22[/td][td bgcolor=#fff width=10 height=10]23[/td][td bgcolor=#fff width=10 height=10]24[/td][/tr][tr][td height=10 bgcolor=#fff]0[/td][td bgcolor=#f0f]4[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0f0]1[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f00]3[/td][/tr][tr][td height=10 bgcolor=#fff]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#0f0]1[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f00]3[/td][/tr][tr][td height=10 bgcolor=#fff]2[/td][td bgcolor=#000]x[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f00]3[/td][td bgcolor=#f00]3[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0f0]1[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]3[/td][td bgcolor=#000]x[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0ff]2[/td][td bgcolor=#aaa]6[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0ff]2[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f00]3[/td][td bgcolor=#ff0]5[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]4[/td][td bgcolor=#000]x[/td][td bgcolor=#aaa]6[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f00]3[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f00]3[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]5[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f00]3[/td][td bgcolor=#0f0]1[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0f0]1[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]6[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f00]3[/td][td bgcolor=#ff0]5[/td][td bgcolor=#000]x[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]7[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0ff]2[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#f00]3[/td][td bgcolor=#0ff]2[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]8[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#ff0]5[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#f00]3[/td][td bgcolor=#0ff]2[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]9[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f00]3[/td][td bgcolor=#aaa]6[/td][td bgcolor=#0ff]2[/td][td bgcolor=#ff0]5[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#0ff]2[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]10[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#f00]3[/td][td bgcolor=#0f0]1[/td][td bgcolor=#f0f]4[/td][td bgcolor=#ff0]5[/td][td bgcolor=#aaa]6[/td][td bgcolor=#f0f]4[/td][td bgcolor=#f00]3[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]11[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#ff0]5[/td][td bgcolor=#0ff]2[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]12[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][tr][td height=10 bgcolor=#fff]13[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][td bgcolor=#000]x[/td][/tr][/table]
Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Total gems removed.......: 1253659
Gems per move removed....: 12,54
Average score per move...: 243,03 points
Move with highest score..: #17330 (1550 points)

Nu ook met HTML output:

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

1

2

3

4

5

6

7

8

9

10

11

12

13

Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Total gems removed.......: 1253659
Gems per move removed....: 12,54
Average score per move...: 243,03 points
Move with highest score..: #17330 (1550 points)

En PNG output:

[.oisyn]

era.zer schreef op maandag 03 november 2008 @ 21:28:
Dat kruis net voor het stabiel worden vormt een probleempje...
mijn recursief algoritme om figuren te vinden/tellen verhindert het teruggaan naar het blokje vanwaar men net kwam (kwestie van niet oneindig te loopen of noord-zuid dubbel te tellen). Maar bij zo'n kruis moet het eigenlijk wél terug gaan. Grrr...

Kwestie van bijhouden waar je al geweest bent, en als je bij een blokje komt waar je nog niet geweest bent een recursieve aanroep doen om dat blokje ook te controleren in de andere richting dan degene waarmee je nu aan het werk bent (maar wel eerst markeren dat je er al geweest bent).

TaraWij schreef op maandag 03 november 2008 @ 19:56:

Daar ken ik zowat de basis wel van

Dat is niet genoeg . Om betere asm te schrijven dan je compiler moet je echt enorm veel details kennen van de processor waar je code op runt. Weten hoe instructies pipelinen, wat hun latencies zijn, etc.. Vroeger heb ik daar veel mee gespeeld (386/486 tijdperk), maar tegenwoordig vind ik het echt niet meer de moeite waard. Ten eerste zijn de verschillen tussen de verschillende compatible CPU's veel groter, en ten tweede zijn de compilers ook een stuk beter. En er zijn zat low-level zaken die je in een high-level taal ook aan kunt pakken. Denk aan de memory layout en alignment van je data structures, weten wanneer het zinnig is om een berekening wel opnieuw te doen en wanneer niet (lookup-tables zijn allang geen heilige graal meer), het gebruiken van compiler intrinsics voor het gebruik van SSE, enzovoorts. En dan heb je nog over relatief onbelangrijke micro-optimalisaties, die je pas aan het eind gaat oplossen als je weet waar de hotspots zitten.

Optimaliseren is een belangrijk deel van m'n werk (een cross platform 3d engine voor de games in m'n sig), maar als ik in de afgelopen 4 jaar dat ik dat werk gedaan heb 5 regels asm heb geschreven dan is dat veel. Dat ging er vroeger idd heel anders aan toe, maar dat is voor mijn tijd .

[pedorus]

writser schreef op maandag 03 november 2008 @ 21:49:
Een soort flood-fill algoritme moet wel werken lijkt me.

Ik denk dat era.zer nu zeg maar de stap veranderkleur na de recursie zet ipv ervoor. Omdraaien dus
Daarnaast lijkt het me handig om een hele horizontale of hele verticale rij in een keer af te handelen, dus er is maar 1 recursieve aanroep nodig ipv 4 zoals bij het voorbeeld op Wikipedia. Wat .iosyn dus ook lijkt te doen. Let er op dat iets als een "o"- of "g"-vorm ook goed moet gaan

[RobIII]

Ik zoek gewoon lijnen van 3+ lengte (eerst horizontaal, dan verticaal), mikker die allemaal in een nieuw figure object (die dus dan maar 1 lijn bevat) welke ik in een lijst rag en daarna jaag ik de lijst door een recursieve CombineFigures die alle lijnen uit een figuur naloopt op lijnen in een tweede figuur met dezelfde kleur die overlap hebben en dan combineert naar 1 enkel figuur (met daarin dan die 2+ lijnen). Zo hou ik altijd referenties naar de originele losse lijnen die ik gevonden heb en kan ik ook losse figures die ik gedetecteerd heb outputten om zo het debuggen te vergemakkelijken.

Benodigdheden:

• Een "Map" (speelveld) object met:
  • Scanlines methode die de map scanned op lijnen van 3+ lengte en een lijst met figuren teruggeeft; elk daarvan bevat op dat moment 1 lijn
  • CombineFigures methode die alle figuren met elkaar probeert te combineren wanneer de figuren dezelfde kleur hebben en een overlap/snijpunt in 1 van de lijnen in dat figuur
• Line object met wat properties en methods als Line.Intersects(Line otherline)
• Figure object met wat properties methods als Figure.HasOverlap(Figure otherfigure)

Zoiets; kort door de bocht.

Voordeel, behalve dat ik voornamelijk een validator aan 't schrijven was, is dat ik straks veel van die dingen kan hergebruiken mocht ik nog mee willen spelen. Ik vrees dat 't er niet van komt i.v.m. een verbouwing en zwangerschapje maar je weet nooit

[ Voor 58% gewijzigd door RobIII op 03-11-2008 22:34 ]

[Marcj]

.oisyn schreef op maandag 03 november 2008 @ 15:00:
[...]

Ik vind trouwens dat er veel te weinig outputs getoond worden. Kom op, ik wil resultaten zien! Anders heb ik niets om tegenop te werken (of gaan jullie pas posten als de behaalde score hoger is dan die van mij? )

Sorry, ik heb er nog niet echt tijd voor gehad. Ik heb nu al wel de data-objecten gedefinieerd, de BejeweledLoader om de data in te lezen van bestanden en het 'droppen' zit er goed in. Nu nog even moves vinden en combinaties verwijderen.

Daarna wil ik weer eens gaan refactoren om het geheel weer netjes te krijgen

[pedorus]

RobIII schreef op maandag 03 november 2008 @ 22:21:
Benodigdheden:

• Een "Map" (speelveld) object met:
  • Scanlines methode die de map scanned op lijnen van 3+ lengte en een lijst met figuren teruggeeft; elk daarvan bevat op dat moment 1 lijn
  • CombineFigures methode die alle figuren met elkaar probeert te combineren wanneer de figuren dezelfde kleur hebben en een overlap/snijpunt in 1 van de lijnen in dat figuur
• Line object met wat properties en methods als Line.Intersects(Line otherline)
• Figure object met wat properties methods als Figure.HasOverlap(Figure otherfigure)

Zoiets; kort door de bocht.

Kleine optimalisatie: Ik zou dan onderscheid maken tussen horizontale lijnen en verticale lijnen, en eerst alleen lijnen retourneren en niets met figuren doen. Bij het checken van een horizontale lijn hoef je alleen de verticale lijnen na te zoeken, en omgekeerd. Let er wel op dat je voor elke lijn die je vind ook na moet gaan of die overlapt met nog niet afgehandelde lijnen.
Op zich is dat Figure-object niet echt nodig, omdat je slechts 1 figuur tegelijkertijd hoef af te handelen. Kan wel handig zijn voor de toekomst natuurlijk, maar voor de contest is snelheid wel handig

[Confusion]

Ik doe zoiets als wat RobIII beschrijft. Tot nu toe scoor ik daarmee ~100 punten per zet, tegen 100 zetten per seconde .

[Verwijderd]

Ik was ook wel even aan het puzzelen hoe ik het identificeren van shapes precies moest aanpakken (moet het nog steeds implementeren ). Het eerste zoeken van individuele lijnen en daarna ze koppelen tot één figuur is denk ik wel een goede methode. Iemand (ik weet niet meer precies wie) bracht me al eerder in het topic op dat idee.

RobIII schreef op maandag 03 november 2008 @ 22:21:
• CombineFigures methode die alle figuren met elkaar probeert te combineren wanneer de figuren dezelfde kleur hebben en een overlap/snijpunt in 1 van de lijnen in dat figuur

Het matchen op dezelfde kleur is denk ik niet nodig, aangezien lijnen met overlap/snijpunt altijd van dezelfde kleur zijn.

[ Voor 3% gewijzigd door Verwijderd op 03-11-2008 23:12 ]

[BastiaanN]

Oeh, lijkt me erg leuk dit! doet me denken aan de programmeer opdrachten op school ten behoeve van het ASP en Traveling Salesman probleem.

Ik ga eens een gokje wagen

[RobIII]

pedorus schreef op maandag 03 november 2008 @ 22:51:
Kleine optimalisatie: Ik zou dan onderscheid maken tussen horizontale lijnen en verticale lijnen, en eerst alleen lijnen retourneren en niets met figuren doen. Bij het checken van een horizontale lijn hoef je alleen de verticale lijnen na te zoeken, en omgekeerd.

Mijn Line object heeft een IsHorizontal en een IsVertical property dus bij het controleren op snijpunten ga ik sowieso eerst daar op af ( H + V ) voordat ik uberhaupt aan 't "rekenen" sla of er snijpunten zijn.

pedorus schreef op maandag 03 november 2008 @ 22:51:
Let er wel op dat je voor elke lijn die je vind ook na moet gaan of die overlapt met nog niet afgehandelde lijnen.

Nope, want mijn "ClearLine" method cleared hooguit 1x een positie; ZOU er onverhoopt een overlap zijn die er niet in thuis hoort dan is het nog safe

pedorus schreef op maandag 03 november 2008 @ 22:51:
Op zich is dat Figure-object niet echt nodig, omdat je slechts 1 figuur tegelijkertijd hoef af te handelen.

Ik kan werken met meerdere figuren, en voor de score is een figure object wel degelijk handig

Verwijderd schreef op maandag 03 november 2008 @ 23:10:
Het matchen op dezelfde kleur is denk ik niet nodig, aangezien lijnen met overlap/snijpunt altijd van dezelfde kleur zijn.

Voordat ik een figure ga (proberen te) combineren met een andere kan ik de iteratie al afbreken als de figuren niet van dezelfde kleur zijn; dan heb ik nog niet eens naar snijpunten gekeken

[.oisyn]

pedorus schreef op maandag 03 november 2008 @ 22:14:
Daarnaast lijkt het me handig om een hele horizontale of hele verticale rij in een keer af te handelen, dus er is maar 1 recursieve aanroep nodig ipv 4 zoals bij het voorbeeld op Wikipedia. Wat .iosyn dus ook lijkt te doen.

Klopt, behalve dat ik het dan niet letterlijk recursief geïmplementeerd heb maar iteratief en ik een queue gebruik voor de checks die ik nog moet doen. Maar algoritmisch is dat in feite hetzelfde (of eigenlijk niet helemaal - ik maak effectief dus eerst de huidige lijn af voor ik verder ga met de rest - als je direct een recursieve call zou doen voor elk blokje dan moet je denk ik extra oppassen met infinite loops).

RobIII schreef op maandag 03 november 2008 @ 22:21:
Ik zoek gewoon lijnen van 3+ lengte (eerst horizontaal, dan verticaal), mikker die allemaal in een nieuw figure object (die dus dan maar 1 lijn bevat) welke ik in een lijst rag en daarna jaag ik de lijst door een recursieve CombineFigures die alle lijnen uit een figuur naloopt op lijnen in een tweede figuur met dezelfde kleur die overlap hebben en dan combineert naar 1 enkel figuur (met daarin dan die 2+ lijnen). Zo hou ik altijd referenties naar de originele losse lijnen die ik gevonden heb en kan ik ook losse figures die ik gedetecteerd heb outputten om zo het debuggen te vergemakkelijken.

Klinkt wat omslachtig. In het aantal operaties dat je moet doen bedoel ik dan. Je moet eerst alle blokjes langslopen, en daarna moet je ook nog eens alle figuren met elkaar matchen. En ondertussen loop je flink te strooien met losse objecten. Ik loop één keer over alle blokjes heen en dan heb ik meteen alle informatie die ik moet hebben (totaalscore voor die stap en een bitmap van blokjes die verwijderd moeten worden).

RobIII schreef op maandag 03 november 2008 @ 23:23:
Voordat ik een figure ga (proberen te) combineren met een andere kan ik de iteratie al afbreken als de figuren niet van dezelfde kleur zijn; dan heb ik nog niet eens naar snijpunten gekeken

Ik zou ze in een interval tree zetten, zodat je O(n log n) bent ipv O(n²)

[ Voor 10% gewijzigd door .oisyn op 03-11-2008 23:30 ]

[RobIII]

.oisyn schreef op maandag 03 november 2008 @ 23:23:
Klinkt wat omslachtig.

Klopt. Dat is deels uit een te-zeer OO ontwerp waar ik mss beter arrays had kunnen gebruiken (nu heb ik voor elke scheet een object ) maar ook omdat ik allerlei tussentijdse info wil kunnen visualiseren etc. en het proces qua code logisch wilde houden zonder 24 in elkaar genestte for-loops

.oisyn schreef op maandag 03 november 2008 @ 23:23:
Ik zou ze in een interval tree zetten

Veel te veel gedoe Ik reken nu 100.000 zetten door in <1 sec; dat vind ik goed zat voor een validator Als ik ga deelnemen zie ik wel of ik er nog wat mee kan doen. Mijn profiler zegt me iig dat ik in CombineFigure voorlopig niet hoef te rommelen; daar wordt maar een paar procent van de tijd gespendeerd. Mijn scanlines zou sneller moeten maar ook dat boeit me niet nu

[ Voor 41% gewijzigd door RobIII op 03-11-2008 23:31 ]

[Serpie]

Eindelijk mijn eerste valide output, ik denk dat ik nooit de tijden ga halen die hier gehaald worden maar kan wellicht nog wat uithalen met de profiler. Toch leuk om me hier mee bezig te houden, en algoritmes te zoeken.

ik krijg hier op mijn werk niet echt mee te maken en hoop dan ook op andere snellere dotnet implementaties om mee te vergelijken, leest vergelijkt toch makkelijker als c++

Deze output pakt de eerste mogelijke zet, mijn programma doet hier al 60 20 seconden over

[table border=1 cellpadding=1 bordercolor=#000 fontsize=8][tr][td bgcolor=#fff height=10 width=10].[/][td bgcolor=#fff height=10 width=10]0[/][td bgcolor=#fff height=10 width=10]1[/][td bgcolor=#fff height=10 width=10]2[/][td bgcolor=#fff height=10 width=10]3[/][td bgcolor=#fff height=10 width=10]4[/][td bgcolor=#fff height=10 width=10]5[/][td bgcolor=#fff height=10 width=10]6[/][td bgcolor=#fff height=10 width=10]7[/][td bgcolor=#fff height=10 width=10]8[/][td bgcolor=#fff height=10 width=10]9[/][td bgcolor=#fff height=10 width=10]10[/][td bgcolor=#fff height=10 width=10]11[/][td bgcolor=#fff height=10 width=10]12[/][td bgcolor=#fff height=10 width=10]13[/][td bgcolor=#fff height=10 width=10]14[/][td bgcolor=#fff height=10 width=10]15[/][td bgcolor=#fff height=10 width=10]16[/][td bgcolor=#fff height=10 width=10]17[/][td bgcolor=#fff height=10 width=10]18[/][td bgcolor=#fff height=10 width=10]19[/][td bgcolor=#fff height=10 width=10]20[/][td bgcolor=#fff height=10 width=10]21[/][td bgcolor=#fff height=10 width=10]22[/][td bgcolor=#fff height=10 width=10]23[/][td bgcolor=#fff height=10 width=10]24[/][/tr][tr][td bgcolor=#fff height=10 width=10]0[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][/tr][tr][td bgcolor=#fff height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#aaa height=10 width=10]6[/][/tr][tr][td bgcolor=#fff height=10 width=10]2[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]3[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]5[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]6[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]7[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]8[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]9[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]10[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#aaa height=10 width=10]6[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0ff height=10 width=10]2[/][td bgcolor=#f00 height=10 width=10]3[/][td bgcolor=#ff0 height=10 width=10]5[/][td bgcolor=#f0f height=10 width=10]4[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]11[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=#0f0 height=10 width=10]1[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]12[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][tr][td bgcolor=#fff height=10 width=10]13[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][td bgcolor=black height=10 width=10]x[/][/tr][/table]
Score....................: 7898400 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 78 points
Move with highest score..: #89791 (1500 points)

.oisyn bedankt voor de validator, deze heeft me tot nog toe aardig geholpen bij het debuggen

[TaraWij]

Verwijderd schreef op maandag 03 november 2008 @ 20:14:
Tuurlijk moet je ergens beginnen, maar dat doe je niet door te proberen snellere assembly te schrijven dan je compiler. Optimaliseren doe je (in 99% van de gevallen) door
[...]

.oisyn schreef op maandag 03 november 2008 @ 22:08:
Dat is niet genoeg . Om betere asm te schrijven dan je compiler moet je echt enorm veel details kennen van de processor waar je code op runt.
[..]

Interessant, allebei bedankt voor de informatie... Ben op het moment er op aan het letten dat ik efficient te werk ga, optimaliseren is voor op het einde en blijkbaar zag ik het gebruik van assembler verkeerd. (Dit was vroeger wel zo maar nu niet meer?)

Leuk dat er zo geholpen wordt, mijn doel was dan ook om mijn programmeren wat bij te schaven en nog wat bij te leren door mee te doen met deze contest. Zal tegen dat mijn code af is eens wat artikelen omtreft optimalisatie lezen, uiteraard zonder het keyword asm of assembler.

[.oisyn]

RobIII schreef op maandag 03 november 2008 @ 23:29:
en het proces qua code logisch wilde houden zonder 24 in elkaar genestte for-loops

Overdrijven is ook een vak . Ik denk dat mijn code niet dieper genest is dan de jouwe.

Veel te veel gedoe Ik reken nu 100.000 zetten door in <1 sec; dat vind ik goed zat voor een validator Als ik ga deelnemen zie ik wel of ik er nog wat mee kan doen. Mijn profiler zegt me iig dat ik in CombineFigure voorlopig niet hoef te rommelen; daar wordt maar een paar procent van de tijd gespendeerd. Mijn scanlines zou sneller moeten maar ook dat boeit me niet nu

Ik sta zelf ook niet achter die opmerking trouwens . Er zijn doorgaans veel te weinig figuren die tegelijk gevormd worden om de algoritmische complexiteit van een interval tree te verantwoorden.

[ Voor 51% gewijzigd door .oisyn op 03-11-2008 23:38 ]

[RobIII]

.oisyn schreef op maandag 03 november 2008 @ 23:32:
Overdrijven is ook een vak . Ik denk dat mijn code niet dieper genest is dan de jouwe.

Dat moest idd met een korreltje zout

.oisyn schreef op maandag 03 november 2008 @ 23:32:
Ik sta zelf ook niet achter die opmerking trouwens . Er zijn doorgaans veel te weinig figuren die tegelijk gevormd worden om de algoritmische complexiteit van een interval tree te verantwoorden.

Juistem

[DaCoTa]

Zo, eindelijk ook bij de 1950 aangekomen. Gedoe om die puntentelling te implementeren, wel jammer want dat was nogal wat werk wat m.i. niet nodig was geweest. Maargoed, ik ben er! Tenminste, ik neem aan dat als je de 1950 hebt, dat de puntentelling dan wel klopt. Hoop ik.

Morgen verder met het leuke deel

[pedorus]

RobIII schreef op maandag 03 november 2008 @ 23:23:
Mijn Line object heeft een IsHorizontal en een IsVertical property dus bij het controleren op snijpunten ga ik sowieso eerst daar op af ( H + V ) voordat ik uberhaupt aan 't "rekenen" sla of er snijpunten zijn.

Maar je moet ze toch allemaal even af Ik zat trouwens meer aan een aparte klasse HorizontalLine en VerticalLine te denken (met superklasse Line).

Nope, want mijn "ClearLine" method cleared hooguit 1x een positie; ZOU er onverhoopt een overlap zijn die er niet in thuis hoort dan is het nog safe

Ehh, zie ik zo even niet. Ik bedoelde dat je het figuur uit moest blijven breiden, voor de wat ingewikkeldere figuren (dus bijvoorbeeld iets als een n, o of G).

Ik kan werken met meerdere figuren, en voor de score is een figure object wel degelijk handig

Het combineren is sowieso alleen nodig voor een 100% correcte score. Dat lijkt me een groot voordeel van deze methode. Het blijft werken, ook als de score niet klopt Wellicht kun je ook gewoon geen rekening houden met ingewikkelde figuren, als extra optimalisatie. De score rekent de validator dan wel uit.

.oisyn schreef op maandag 03 november 2008 @ 23:23:
Klopt, behalve dat ik het dan niet letterlijk recursief geïmplementeerd heb maar iteratief en ik een queue gebruik voor de checks die ik nog moet doen. Maar algoritmisch is dat in feite hetzelfde (of eigenlijk niet helemaal - ik maak effectief dus eerst de huidige lijn af voor ik verder ga met de rest - als je direct een recursieve call zou doen voor elk blokje dan moet je denk ik extra oppassen met infinite loops).

Infinite loops heb je niet zoveel last van, zolang je maar de steen 'weghaalt' voor de call, zodat je er niet op terug kan komen. Ik zou enkel wel eerst de hele lijn detecteren, en dan pas de omzettingen en calls doen, zodat je wel steeds de hele regel hebt (je moet toch al testen of de lengte groter dan 2 is). En ja, dan lijkt me ook de optimalisatie van het werken zonder dirty bit mogelijk.

RobIII schreef op maandag 03 november 2008 @ 23:29:
Veel te veel gedoe Ik reken nu 100.000 zetten door in <1 sec; dat vind ik goed zat voor een validator Als ik ga deelnemen zie ik wel of ik er nog wat mee kan doen. Mijn profiler zegt me iig dat ik in CombineFigure voorlopig niet hoef te rommelen; daar wordt maar een paar procent van de tijd gespendeerd. Mijn scanlines zou sneller moeten maar ook dat boeit me niet nu

Ik vermoed dat er vast nog iets mogelijk is als je bijhoudt welke rijen en kolommen er gewijzigd zijn. En ik vermoed dat je je veld nu als een 'dubbele' array opslaat? Wellicht is een enkele iets sneller.

[BastiaanN]

Wat is nou exact de bedoeling van de GUI. Moet de GUI de begin situatie van de steentjes laten zien of de eind situatie?

Of, erger nog, de "moves"? Is wel een leuke feature maar niet om de snelheid van je algoritme mee te testen.

/me Voelt zich een beetje dom vandaag

[RobIII]

Een GUI is puur voor jezelf / voor de fun / visuele weergave / handig voor debuggen. Qua contest heeft het er geen drol mee van doen; we verwachten alleen een output.txt

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Ehh, zie ik zo even niet. Ik bedoelde dat je het figuur uit moest blijven breiden, voor de wat ingewikkeldere figuren (dus bijvoorbeeld iets als een n, o of G).

Dat doet CombineFigure. Voor een "O" zou je dus eerst 4 figures hebben:

code:

f1: ¯
f2:  |
f3: |
f4: _

combine >>
fc:
 _
|_|

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Het combineren is sowieso alleen nodig voor een 100% correcte score.

En dat is wel zo handig voor een officiële contest validator

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Dat lijkt me een groot voordeel van deze methode. Het blijft werken, ook als de score niet klopt Wellicht kun je ook gewoon geen rekening houden met ingewikkelde figuren, als extra optimalisatie. De score rekent de validator dan wel uit.

Zie mijn opmerking van zonet dus Ik ben niet bezig met een contest entry maar met de validator die we later over jullie resultaten laten buigen Of ik nog mee ga doen als deelnemer moet ik nog even bezien.

Overigens is een bijkomend voordeel dat ik nu de scanlines methode die relatief het meeste CPU tijd kost straks leuk kan optimaliseren zolang ik maar figures/lines blijf teruggeven; bij minder object oriented functies kwam je dan al snel in de knoei denk ik.

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Infinite loops heb je niet zoveel last van, zolang je maar de steen 'weghaalt' voor de call, zodat je er niet op terug kan komen. Ik zou enkel wel eerst de hele lijn detecteren, en dan pas de omzettingen en calls doen, zodat je wel steeds de hele regel hebt (je moet toch al testen of de lengte groter dan 2 is). En ja, dan lijkt me ook de optimalisatie van het werken zonder dirty bit mogelijk.

Ik weet dat je 't tegen .oisyn hebt, maar inderdaad met mijn bak Figure objecten die uit de scanlines komt (en een figure bestaande uit een bak Line objecten) heb ik geen dirty bit nodig; ik scan eerst voor lines/figures, bereken de score, clear de figure uit de map, drop & refill en ga door met move n+1

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Ik vermoed dat er vast nog iets mogelijk is als je bijhoudt welke rijen en kolommen er gewijzigd zijn. En ik vermoed dat je je veld nu als een 'dubbele' array opslaat? Wellicht is een enkele iets sneller.

Ja vast maar 100K zetten in sec. valideren vind ik voorlopig netjes Ik heb een goeie profiler en er is nog zat te optimizen; of ik daar de puf voor heb voor 0.5 sec. winst... nah

[ Voor 117% gewijzigd door RobIII op 04-11-2008 02:20 ]

[BalusC]

Mijn logica loopt elke ongescande en ongematchede jewel door en zoekt voor elke jewel in elke windrichting een match van minimaal 3 lang en vanuit elke jewel van de match scant ie weer voor een match van minimaal 3 lang, enzovoorts

[Scott]

Je hoeft niet eens een GUI te hebben. Het gaat uiteindelijk allemaal om het tekstbestandje met de zetten daarin

edit: ff f5-en voortaan...

[ Voor 11% gewijzigd door Scott op 04-11-2008 00:20 ]

[? ?]

edit: ik zat hier vanalles te typen en tijdens het nadenken kwam de oplossing me te binnen, waar dit topic niet allemaal goed voor is

mijn puntentelling moet volledig recursief gebeuren (voor alles vanaf een blokje, het speelveld zelf ga ik iteratief af; misschien zoals .oiysin), het kan makkelijker anders, maar ik wil het mooi en efficient. dat mooi is al wat minder mooi, want er moet toch op enkele zaken gecontroleerd worden.
Zo'n taak is wel goed voor de hersenen, moeten ze eens werken

[ Voor 223% gewijzigd door ? ? op 04-11-2008 00:39 ]

[Arjan]

Ik zie dat er veel mensen dezelfde aanpak hebben gekozen, ook ik detecteer blokken die weggespeeld worden in twee passes. Eentje voor horizontaal en eentje voor verticaal. Het framework heb ik nu wel afgerond, nu gaan werken aan de AI. Dat is hard nodig want qua scores is mijn oplossing vooralsnog geen hoogvlieger

[Megamind]

Hm dan ben ik de enige met een recursieve oplossing?

Kijk rechts, zijn de volgende 2 zelfde kleur? Zoja ga tellen, komt ie een zelfde blokje tegen boven of onder, kijk of dat er ook 2 zijn, en dan weer terug naar horizontale lijnen tellen.

Ik heb nog geen movie maker erin gezet dus kan niet testen hoe snel dit is.
(ook omdat alles nog in een grafisch grid gedaan wordt )

[BalusC]

Eerste stap van move logica is geimplementeerd Zoekt alle matches van 2 naast elkaar en daarvan 1 rechtsonder en voert de move van die rechtsonder naar boven uit.

             111111111122222
   0123456789012345678901234
  ---------------------------
 0|4623422614634541413162541|
 1|1515136535543536125246656|
 2|#65324542612312565456554#|
 3|#164153634622641446464###|
 4|#441411546564154121646###|
 5|##42642455454613212525###|
 6|##564256633165163#662####|
 7|##66335542525445#########|
 8|##1511216123454##########|
 9|##132464254##4###########|
10|###1223664###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Score:    3000
Matches:  29
Moves:    9
Duration: 85ms
Bejeweled finished at Mon Nov 03 20:24:36 BOT 2008

	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	6	2	3	4	2	2	6	1	4	6	3	4	5	4	1	4	1	3	1	6	2	5	4	1
1	1	5	1	5	1	3	6	5	3	5	5	4	3	5	3	6	1	2	5	2	4	6	6	5	6
2	#	6	5	3	2	4	5	4	2	6	1	2	3	1	2	5	6	5	4	5	6	5	5	4	#
3	#	1	6	4	1	5	3	6	3	4	6	2	2	6	4	1	4	4	6	4	6	4	#	#	#
4	#	4	4	1	4	1	1	5	4	6	5	6	4	1	5	4	1	2	1	6	4	6	#	#	#
5	#	#	4	2	6	4	2	4	5	5	4	5	4	6	1	3	2	1	2	5	2	5	#	#	#
6	#	#	5	6	4	2	5	6	6	3	3	1	6	5	1	6	3	#	6	6	2	#	#	#	#
7	#	#	6	6	3	3	5	5	4	2	5	2	5	4	4	5	#	#	#	#	#	#	#	#	#
8	#	#	1	5	1	1	2	1	6	1	2	3	4	5	4	#	#	#	#	#	#	#	#	#	#
9	#	#	1	3	2	4	6	4	2	5	4	#	#	4	#	#	#	#	#	#	#	#	#	#	#
10	#	#	#	1	2	2	3	6	6	4	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
11	#	#	#	#	#	#	#	1	6	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
12	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
13	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#

Nu nog alle andere mogelijke moves bedenken en implementeren

edit:

Aah fsck, een klein bugje, een move kan potentieel meerdere matches opleveren dan alleen die ene 3 .. Is nu fixed en output hierboven is ook fixed

[Verwijderd]

Megamind schreef op dinsdag 04 november 2008 @ 01:05:
Ik heb nog geen movie maker erin gezet dus kan niet testen hoe snel dit is.
(ook omdat alles nog in een grafisch grid gedaan wordt )

Met een movie maker wordt je programma iig een stuk trager

[BalusC]

Megamind schreef op dinsdag 04 november 2008 @ 01:05:
Hm dan ben ik de enige met een recursieve oplossing?

Mijn logica is ook recursief In ieder geval de logica die matches vindt. De logica die de moves vindt is nu nog rauw geschreven, die wordt op eind ongetwijfeld gerefactored naar een recursieve functie. Eerst moet ik alles op een lijn krijgen en een patroon vinden

[RobIII]

Toch blijft het leuk om het gevisualiseerd te zien. Niet vooruit te fikken, maar wel leuk om te zien:

Moves met de in-between drops en refills
[YouTube: http://www.youtube.com/v/wI1yvvWwI_U]

Enkel complete moves (dus geen drops/refills):
[YouTube: http://www.youtube.com/v/YD63jZ5rE8M]

Beide overigens niet op full speed laten tekenen, IRL gaat het nog sneller maar CamTasia begon dan te bokken dus ik heb er een Sleep(10) in gegooid. En nee, ik heb naast RML, HTML en PNG output geen zin om een AVI export te gaan zitten bakken

[ Voor 6% gewijzigd door RobIII op 04-11-2008 01:37 ]

[BalusC]

Coole filmpjes, rob

[.oisyn]

pedorus schreef op dinsdag 04 november 2008 @ 00:08:
Infinite loops heb je niet zoveel last van, zolang je maar de steen 'weghaalt' voor de call, zodat je er niet op terug kan komen. Ik zou enkel wel eerst de hele lijn detecteren, en dan pas de omzettingen en calls doen, zodat je wel steeds de hele regel hebt (je moet toch al testen of de lengte groter dan 2 is).

Ah ja idd, geen infinte loop, maar wel dat je overal meerdere keren komt als je niet eerst de hele lijn markeert als dirty, dat bedoelde ik meer

En ja, dan lijkt me ook de optimalisatie van het werken zonder dirty bit mogelijk.

Optimalisatie? Waarom? Hoe definieer je dat 'weghalen' dan, door 'm te vervangen door een blokje met een speciale waarde, zodat je uiteindelijk weer je veld moet doorscannen op zoek naar de lege plekken? Doe mij maar een dirty bit, kan ik ook veel sneller hele kolommen uitsluiten bij het zoeken naar lege plekken. Het hebben van een dirty bit is juist de optimalisatie . En de dirty bitmap voor het hele veld kan ik vervolgens ook weer voor andere doeleinden gebruiken. Maar nu stop ik want anders geef ik teveel info weg

[ Voor 7% gewijzigd door .oisyn op 04-11-2008 02:21 ]

[.oisyn]

BalusC schreef op dinsdag 04 november 2008 @ 01:14:
Eerste stap van move logica is geimplementeerd Zoekt alle matches van 2 naast elkaar en daarvan 1 rechtsonder en voert de move van die rechtsonder naar boven uit.

Hoe ga je dit allemaal samenvoegen, een hele zooi if-statements?
Hier heb ik trouwens een geniale oplossing voor gevonden waar ik best trots op ben, en daar ga ik lekker helemaal niets over zeggen

[BalusC]

Klaar Althans, een beetje klaar. De score is m.i. te laag en ik moet de output nog eens door een of ander validator gooien. Ook neemt de logica er best de tijd voor vind ik, hier moet ik nog naar kijken. Deze laptop is slechts voorzien van een Turion64 met 1GB. Doe ik morgen nog wel, straks slapen Vandaag in totaal ongeveer 3 uur besteed aan de move functie.

Bejeweled started at Mon Nov 03 22:05:55 BOT 2008
             111111111122222
   0123456789012345678901234
  ---------------------------
 0|2531412633553545244326261|
 1|4622355124536131332614121|
 2|#13542335336424142524355#|
 3|#546365513526426241451###|
 4|#511212345634625424663###|
 5|##25212136125536611421###|
 6|##646351546132422#464####|
 7|##46422424434653#########|
 8|##5231613662544##########|
 9|##232465655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Score:    7641900
Matches:  134556
Moves:    100000
Duration: 63020ms
Bejeweled finished at Mon Nov 03 22:06:58 BOT 2008

	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	5	3	1	4	1	2	6	3	3	5	5	3	5	4	5	2	4	4	3	2	6	2	6	1
1	4	6	2	2	3	5	5	1	2	4	5	3	6	1	3	1	3	3	2	6	1	4	1	2	1
2	#	1	3	5	4	2	3	3	5	3	3	6	4	2	4	1	4	2	5	2	4	3	5	5	#
3	#	5	4	6	3	6	5	5	1	3	5	2	6	4	2	6	2	4	1	4	5	1	#	#	#
4	#	5	1	1	2	1	2	3	4	5	6	3	4	6	2	5	4	2	4	6	6	3	#	#	#
5	#	#	2	5	2	1	2	1	3	6	1	2	5	5	3	6	6	1	1	4	2	1	#	#	#
6	#	#	6	4	6	3	5	1	5	4	6	1	3	2	4	2	2	#	4	6	4	#	#	#	#
7	#	#	4	6	4	2	2	4	2	4	4	3	4	6	5	3	#	#	#	#	#	#	#	#	#
8	#	#	5	2	3	1	6	1	3	6	6	2	5	4	4	#	#	#	#	#	#	#	#	#	#
9	#	#	2	3	2	4	6	5	6	5	5	#	#	4	#	#	#	#	#	#	#	#	#	#	#
10	#	#	#	1	2	2	3	6	5	4	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
11	#	#	#	#	#	#	#	1	6	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
12	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
13	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#

oisyn: de uiteindelijke moveFunctie bevat slechts 3 if statmenten. Eerste om te testen of de tweede jewel matcht, tweede om te testen of de derde jewel matcht en derde om te testen of de te moven jewel moveable is (d.i. geen muur in de weg).

[ Voor 100% gewijzigd door BalusC op 04-11-2008 03:24 ]

[Woy]

BalusC schreef op dinsdag 04 november 2008 @ 03:13:
oisyn: de uiteindelijke moveFunctie bevat slechts 3 if statmenten. Eerste om te testen of de tweede jewel matcht, tweede om te testen of de derde jewel matcht en derde om te testen of de te moven jewel moveable is (d.i. geen muur in de weg).

Hou je er rekening mee dat je altijd 2 blokjes tegelijk moved?

Voor het fillen gebruik ik gewoon een Grow functie die weer onderverdeeld is in een GrowHorizontal en GrowVertical, en een lijst met blokjes die ik nog moet checken ( en die al gematched zijn natuurlijk ). Om te testen of een move valid is heb ik overigens een andere functie, die wat sneller is, maar die wil ik nog optimaliseren zodat die ook meteen een Shape oplevert, zodat ik niet dubbel werk aan het doen ben.

[wackmaniac]

Megamind schreef op dinsdag 04 november 2008 @ 01:05:
Hm dan ben ik de enige met een recursieve oplossing?

Onder voorbehoud, want ik heb het nog niet daadwerkelijk geimplementeerd, is dat ook mijn plan. Zoals writser eerder ook al aandroeg, een soort van floodfill. Misschien wordt het wel niets en dan doe ik het alsnog op de wijze die o.a. RobIII aandroeg en waar ik eerder ook al aan had gedacht.

[Woy]

Megamind schreef op dinsdag 04 november 2008 @ 01:05:
Hm dan ben ik de enige met een recursieve oplossing?

Ik had eerst ook een recursieve oplossing, daar is op zich ook niks mis mee. Ik heb de recursieve manier echter omgebouwd zodat ik wat beter gebruik maak van mijn resources.

[.oisyn]

BalusC schreef op dinsdag 04 november 2008 @ 03:13:
oisyn: de uiteindelijke moveFunctie bevat slechts 3 if statmenten. Eerste om te testen of de tweede jewel matcht, tweede om te testen of de derde jewel matcht en derde om te testen of de te moven jewel moveable is (d.i. geen muur in de weg).

Maar je hebt 4 combinaties per richting. Even relatief aan het te verplaatsen blokje dat uiteindelijk deel uit gaat maken van de figuur, als je kijkt of je naar boven kunt dan moeten de volgende blokjes gelijk zijn aan de huidge:
(-2, -1) en (-1, -1), of
(-1, -1) en (1, -1), of
(1, -1) en (2, -1), of
(0, -2) en (0, -3)

[BalusC]

De te moven jewel is niet per se de eerste jewel

[.oisyn]

Dus als ik het goed begrijp roep je je moveFunctie meerdere keren aan voor hetzelfde te verplaatsen blokje met verschillende parameters?

[pedorus]

.oisyn schreef op dinsdag 04 november 2008 @ 02:14:
Optimalisatie? Waarom? Hoe definieer je dat 'weghalen' dan, door 'm te vervangen door een blokje met een speciale waarde, zodat je uiteindelijk weer je veld moet doorscannen op zoek naar de lege plekken?

Yep, specifiek gezien bijvoorbeeld de waarde 0x0. Maar je kan dan beter ook het volgende bijhouden:

• Eerste en laatste veranderde kolom
• Per kolom de laagste veranderde rij

Je kan 0x0 dan ook voor een muur gebruiken, terwijl je toch het onderscheid kan blijven maken. Daarnaast kun je deze info hergebruiken om 'opnieuw vallen' te onderzoeken, nieuwe mogelijke zetten te vinden, en niet meer mogelijke zetten weg te halen. Ik geef toe: wel of geen dirty-bits is nogal een micro-optimalisatie, zeker als je de dirty-bits in dezelfde map op slaat...

[.oisyn]

pedorus schreef op dinsdag 04 november 2008 @ 12:40:
[...]

Yep, specifiek gezien bijvoorbeeld de waarde 0x0.

Onhandig, 0 is ook een valide blokje . 0xff dan maar

Maar je kan dan beter ook het volgende bijhouden:

• Eerste en laatste veranderde kolom
• Per kolom de laagste veranderde rij

Je kunt zoveel doen. Waar ik op reageer is het feit dat jij het niet gebruik van bits als optimalisatie ziet, wat imho gewoon niet het geval is. Een dirty bit is een optimalisatie. Wat jij nu aanhaalt is ook een dergelijke optimalisatie (maar iets anders uitgewerkt).

Desalniettemin heb je me wel nieuwsgierig gemaakt en zal ik eens kijken hoe jouw methode performt.

Daarnaast kun je deze info hergebruiken om 'opnieuw vallen' te onderzoeken, nieuwe mogelijke zetten te vinden, en niet meer mogelijke zetten weg te halen.

Dat kan met een dirty bit dus ook

[pedorus]

.oisyn schreef op dinsdag 04 november 2008 @ 12:59:
Onhandig, 0 is ook een valide blokje . 0xff dan maar

Nee, '0' (0x30) is een valide blokje. Ik bedoel 0x0. Dat is niet toevallig gekozen, omdat in sommige talen dan 0x0 naar false evalueert, en de echte tekens naar true... Ook zijn er bepaalde extra optimalisaties mogelijk in assembler dacht ik, maar ik weet niet of dat nog steeds echt sneller is.

[.oisyn]

pedorus schreef op dinsdag 04 november 2008 @ 13:46:
[...]

Nee, '0' (0x30) is een valide blokje.

Of 0x94. Je kan er natuurlijk een arbritraire transformatie op toepassen.

Dat is niet toevallig gekozen, omdat in sommige talen dan 0x0 naar false evalueert, en de echte tekens naar true... Ook zijn er bepaalde extra optimalisaties mogelijk in assembler dacht ik, maar ik weet niet of dat nog steeds echt sneller is.

test al, al is niet sneller dan cmp al, 0xff. 't Scheelt wel 1 opcode, maar dat is marginaal en wordt waarschijnlijk teniet gedaan bij het alignen van labels. Maar goed, dit was allemaal niet het belangrijkste deel van de post.

[ Voor 5% gewijzigd door .oisyn op 04-11-2008 14:00 ]

[zwippie]

* zwippie meldt zich ook weer
Na drie avondjes heb ik wat 'werkends', al is de puntentelling nog niet helemaal correct.

Na het controleren met de validator van .oysin bleek dat ik toch nog iets niet goed had begrepen: het verschil tussen het laten inzakken van het veld, en het introduceren van nieuwe jewels. Dit zijn twee aparte stappen die niet samen mogen worden genomen. Tussen deze stappen in moet je nog controleren op combinaties en deze weghalen, waarna het veld weer opnieuw moet inzakken.

Wat ik eerst deed was deze twee stappen wel samen nemen. Dit ging nog goed tot het bereiken van de beginsituatie van de testset (de 1950 punten situatie), maar daarna ging het al snel mis.

Klopt dit verhaal?


Verder heb ik nog een mooi idee over het gebruiken van een super-loop:
Stel je maakt een move, waardoor hij maar blijft 'sweepen' en sweepen tot je in een situatie komt waarbij je weer dezelfde move kan doen. Resultaat: maximale punten binnen een minimaal aantal moves.

[RobIII]

zwippie schreef op dinsdag 04 november 2008 @ 16:25:
* zwippie meldt zich ook weer
Verder heb ik nog een mooi idee over het gebruiken van een super-loop:
Stel je maakt een move, waardoor hij maar blijft 'sweepen' en sweepen tot je in een situatie komt waarbij je weer dezelfde move kan doen. Resultaat: maximale punten binnen een minimaal aantal moves.

Je bent niet de eerste En "maximaal" zou dan "oneindig" zijn; je bent namelijk alleen beperkt in je aantal zetten (100K) en als je met 350 zetten die state weet te bereiken haal je dus een "oneindige" score en kom je niet verder dan je 350 zetten.

[ Voor 21% gewijzigd door RobIII op 04-11-2008 16:31 ]

[DaCoTa]

zwippie schreef op dinsdag 04 november 2008 @ 16:25:
Na het controleren met de validator van .oysin bleek dat ik toch nog iets niet goed had begrepen: het verschil tussen het laten inzakken van het veld, en het introduceren van nieuwe jewels. Dit zijn twee aparte stappen die niet samen mogen worden genomen. Tussen deze stappen in moet je nog controleren op combinaties en deze weghalen, waarna het veld weer opnieuw moet inzakken.

Wat ik eerst deed was deze twee stappen wel samen nemen. Dit ging nog goed tot het bereiken van de beginsituatie van de testset (de 1950 punten situatie), maar daarna ging het al snel mis.

Klopt dit verhaal?

Dit heb ik nog niet uit de regels gehaald. Dus je moet eerst het hele veld stabiel maken en pas daarna nieuwe jewels introduceren? En wat als daardoor weer nieuwe combinaties te maken zijn?

Het moet niet gekker worden...

[RobIII]

DaCoTa schreef op dinsdag 04 november 2008 @ 17:04:
En wat als daardoor weer nieuwe combinaties te maken zijn?

Dan is het veld dus nog niet stabiel. Kijk eens naar .oisyn in "Programming Contest Nieuwe Stijl: Contest 4"
Initieel beland je dus al op 1950 punten zonder ook maar 1 zet te hebben gedaan.

[ Voor 27% gewijzigd door RobIII op 04-11-2008 17:06 ]

[Woy]

zwippie schreef op dinsdag 04 november 2008 @ 16:25:
* zwippie meldt zich ook weer
Na het controleren met de validator van .oysin bleek dat ik toch nog iets niet goed had begrepen: het verschil tussen het laten inzakken van het veld, en het introduceren van nieuwe jewels. Dit zijn twee aparte stappen die niet samen mogen worden genomen. Tussen deze stappen in moet je nog controleren op combinaties en deze weghalen, waarna het veld weer opnieuw moet inzakken.

Ik weet niet precies wat je bedoelt, maar bij het verwijderen van de blokken en het introduceren gaat juist wel gelijkt. Je moet echter wel alle mogenlijke shapes tegelijk verwijderen, anders zou het onduidelijk zijn welke je als eerste moet verwijderen.

Wat je dus doet is

1. Nieuwe jewels droppen ( In het begin dus het hele veld )
2. Controleren op Shapes en deze allemaal verwijderen

en dan net zo lang 1 en 2 herhalen totdat je niks meer verwijderd hebt. Dan kun je een Move doen en dan begint het hele feest weer opnieuw.

[zwippie]

DaCoTa schreef op dinsdag 04 november 2008 @ 17:04:
[...]

Dit heb ik nog niet uit de regels gehaald. Dus je moet eerst het hele veld stabiel maken en pas daarna nieuwe jewels introduceren? En wat als daardoor weer nieuwe combinaties te maken zijn?

Het moet niet gekker worden...

Ik kon het eigenlijk ook niet uit de regels halen, maar liep er tegenaan bij het validaten van mijn zetten, dat ging mis. Het enige wat ik kon bedenken is dat het misging bij het inzakken/aanvullen van de jewels.

rwb schreef op dinsdag 04 november 2008 @ 17:09:
[...]

Ik weet niet precies wat je bedoelt, maar bij het verwijderen van de blokken en het introduceren gaat juist wel gelijkt. Je moet echter wel alle mogenlijke shapes tegelijk verwijderen, anders zou het onduidelijk zijn welke je als eerste moet verwijderen.

Ja, alle mogelijke combo's haal ik ook wel in 1 keer weg. Dat staat duidelijk beschreven.

Waar het mij om gaat is of het nou is:

1. move uitvoeren (2 jewels omwisselen)
2. haal alle combinaties weg
3. laat kolommen inzakken en laat nieuwe jewels van boven neerdalen
4. zijn er nog combinaties? ga dan verder met 2
5. beurt klaar

of

1. move uitvoeren (2 jewels omwisselen)
2. haal alle combinaties weg
3. laat kolommen inzakken
4. zijn er nog combinaties? ga dan verder met 2
5. laat nieuwe jewels van boven neerdalen
6. zijn er nog combinaties? ga dan verder met 2
7. beurt klaar

Ik ging eerst uit van de eerste methode, maar twijfel nu of het toch niet de tweede methode is.

[.oisyn]

Nee, het is wel de eerste. Als je laat inzakken moet je ook meteen nieuwe jewels introduceren.

[Verwijderd]

Voor mij was het in het begin ook niet helemaal duidelijk. Het is als volgt.

1. Je begint met het vullen van het speelveld vanuit de kolommen.
2. Loop onderstaande 3 stappen tot je geen combinaties meer kan wegspelen.
3. Je maakt een zet.
4. Loop onderstaande 3 stappen tot je geen combinaties meer kan wegspelen.
5. Etc, etc.
Het spel stopt na 100 000 zetten, 15 minuten óf als geen zetten meer mogelijk zijn.

1#. Je speelt alle combinaties weg.
2#. Je laat de blokjes afzakken naar beneden.
3#. Je vult het speelveld aan vanuit de kolommen.

[zwippie]

.oisyn schreef op dinsdag 04 november 2008 @ 18:23:
Nee, het is wel de eerste. Als je laat inzakken moet je ook meteen nieuwe jewels introduceren.

Ok, dan heb ik het dus wel goed begrepen en zit er dus nog ergens een dikke fout in mijn code.

[Serpie]

Ik ben ook weer wat verder met mijn programma, inmiddels heb ik het valideren van een output file terug van zo'n 12 naar ongeveer 3 seconden. Hier laat ik het voorlopig maar even bij, weet niet of ik dit nog verder terug kan krijgen (bijv. <1 seconden )

Eerst maar eens gaan concentreren op de AI, hier is nog veel meer uit te halen dan in het profilen. Ik probeer het trouwens deze keer ook weer in vb.net, alleen nu wat robuuster dan contest 2.

Terloops ook maar een UI maken voor het debuggen, toch wel makkelijk:

[Malthus]

Zo'n GUI ziet er toch wel erg fraai uit , dus misschien moet ik dat deze keer toch ook maar weer proberen te maken. Bij de vorige contest heeft de GUI mij echter vrij veel tijd gekost, die ik misschien beter voor het verbeteren en optimaliseren van m'n programma had kunnen gebruiken.

Ik ben nu ruim vier uur bezig, en ik heb kan nu de bestandjes inlezen, het veld vullen en de juiste vormen herkennen en verwijderen (tenminste, ik heb 1250 punten na de eerste iteratie en 1950 punten na de tweede, dus dat lijkt redelijk te kloppen).

[Soultaker]

Validator code werkt. Tenminste, ik kom op hetzelfde resultaat als .oisyn met de uitvoer die hij hier post. Was die al officieel geverifieerd?

.oisyn schreef op maandag 03 november 2008 @ 23:32:
Ik sta zelf ook niet achter die opmerking trouwens . Er zijn doorgaans veel te weinig figuren die tegelijk gevormd worden om de algoritmische complexiteit van een interval tree te verantwoorden.

Ik ben sneller dan O(N log N) maar ik vertel niet hoe.

[RobIII]

Soultaker schreef op dinsdag 04 november 2008 @ 23:34:
Validator code werkt. Tenminste, ik kom op hetzelfde resultaat als .oisyn met de uitvoer die hij hier post. Was die al officieel geverifieerd?

Nee, en dat doen we ook niet officieel ; desnoods kun je nog even met wat debugging en handmatig rekenwerk controleren of 't klopt. Ik kan wél zeggen dat .oisyn niet de enige is die op 1950 komt

[ Voor 10% gewijzigd door RobIII op 05-11-2008 00:23 ]

[Verwijderd]

Leuke contest .. zal kijken hoe het met de vrije tijd zit .. maar als ik zal dit zeker een gooi proberen te geven .

[Soultaker]

RobIII schreef op woensdag 05 november 2008 @ 00:22:
Nee, en dat doen we ook niet officieel ; desnoods kun je nog even met wat debugging en handmatig rekenwerk controleren of 't klopt.

Ok, het leek mij op zich wel redelijk om een officieel voorbeeld te geven van geldige uitvoer met bijhorende waardering, vooral omdat b.v. scoreregels wat moeite kosten om te interpreteren. Ik zou het flauw vinden om van iemand te winnen (of verliezen ) op een verkeerde interpretatie van het probleem, in plaats van een superieur programma.

Maar goed, jullie call.

Ik kan wél zeggen dat .oisyn niet de enige is die op 1950 komt

Dat is niet het spel dat ik had doorgerekend trouwens, maar ook ik kom op 1950 uit.

[ Voor 5% gewijzigd door Soultaker op 05-11-2008 01:04 ]

[RobIII]

Soultaker schreef op woensdag 05 november 2008 @ 01:03:
Maar goed, jullie call.

Kijk eens goed op 't eerste frame? Combineer dat met dit of dit en trek je conclusies

[ Voor 29% gewijzigd door RobIII op 05-11-2008 01:18 ]

[BalusC]

Jeuj, na enige tijd finetunen en debuggen (dank oisyn en phsmits voor de validators, kon er een nasty bugje mee vinden ) is de logica wmb wel prima zo. De rest van de tijd zal ik wel insteken om een beetje rustig aan te refactoren, commentariëren en het OO opzet van de matrix nog eens te herzien, want dat vind ik nog steeds niks.

Bejeweled started at Tue Nov 04 21:09:33 BOT 2008
             111111111122222
   0123456789012345678901234
  ---------------------------
 0|2364143126123566214425652|
 1|4265243134533646323535436|
 2|#34511562212643554141463#|
 3|#143236453411524325623###|
 4|#451316124152264221263###|
 5|##32562621166231416241###|
 6|##436531442623235#543####|
 7|##15654163613224#########|
 8|##4531545643454##########|
 9|##332455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Score....................: 7501350 points
Total moves..............: 100000
Average score per move...: 75
Duration.................: 43042ms
Output written to........: C:\Java\workspace2\Bejeweled\uitvoer.txt

Bejeweled finished at Tue Nov 04 21:10:16 BOT 2008

De uitvoer is valide bevonden door de beide validators

Ik moet wel even kwijt dat oisyns validator ongelooflijk snel is. Restecp.

[RobIII]

Ik heb eens even een heel snelle scan gedaan van dit topic. Ik wist al wel dat deze contest leuk liep en voor mijn gevoel zelfs beter dan de vorige 3 die ik, navenant, toch ook goed vond lopen. Maar nu heb ik even een lijstje gemaakt van mensen die zeggen een poging te willen doen* en dan kom ik (nu al, en we hebben nog ruim 2 maanden te gaan) op de volgende lijst:

1. Aloys
2. Aphelion
3. Arjan
4. BalusC
5. BastiaanN
6. Bolukan
7. Brian
8. chris
9. CodeCaster
10. coenbijlsma
11. Confusion
12. crisp
13. DaCoTa
14. EdwinG
15. era.zer
16. freaky1983
17. Gerco
18. GuidoH
19. Haan
20. JelmerHT
21. JMFX
22. letinon
23. LuCarD
24. Malthus
25. Marcj
26. Megamind
27. Morphie
28. MrWilliams
29. Nick The Heazk
30. --Niels--
31. Not Pingu
32. .oisyn
33. paknaald
34. pedorus
35. phsmit
36. Pinobigbird
37. prototype
38. rwb
39. ScottB
40. Serpie
41. Sh4wn
42. Standeman
43. sub0kelvin
44. The Fox NL
45. TomWij
46. Vaan Banaan
47. wackmaniac
48. Wouser
49. woutertje
50. wwwhizz
51. YeXo
52. zwippie

Dan heeft iedereen een beetje een idee tegen wie ze het nog meer opnemen Overigens was het aantal inzendingen voor contests 1 t/m 3 respectievelijk 8, 17, 13.

_{* Deze lijst heb ik samengesteld na een vlugge scan van het topic. Sommige mensen geven heel duidelijk aan mee te doen, anderen zeggen misschien mee te doen of misschien geen tijd te hebben maar wel mee te willen doen en anderen geven helemaal niets duidelijk aan, maar zie ik n.a.v. hun meedenken of tussen de regels door lezen ook wel mee doen. Iedereen waarvan ik een inzending mogelijk schat is vermeld in deze lijst. Verder pretendeert deze lijst niet 100% accuraat te zijn en zijn er uiteraard geen verplichtingen aan verbonden blah blah. Ik ga deze lijst ook verder niet actief onderhouden, je hoeft je dus niet te melden voor alsnog een vermelding in/verwijdering van deze lijst. Het is puur voor de fun en ter indicatie van het aantal deelnemers. Alleen het uiteindelijke aantal inzendingen zal hier uitsluitsel over geven, maar ik moest het toch even delen}

Rest mij niets anders dan (nu al) een kleine *hoezee* voor GoT, de community en in het bijzonder de Devschuur® users en ontzettend veel plezier en succes aan de deelnemers, ook toekomstige, toe te wensen!

* RobIII de Dikke Van Dale neemt en "bed" op zoekt

quote: http://www.vandale.nl/van...oordenboek/?zoekwoord=bed

bed het; o -den 1 matras 2 matras met dekens, lakens, kussens; (bij uitbr) het ledikant: in zijn ~ liggen; met iem naar ~ gaan geslachtsgemeenschap hebben; zijn ~(je) is gespreid voor zijn toekomst is gezorgd 3 verhoogd stukje tuin voor gewassen

Wat moet ik nou op dit tijdstip in mijn tuin?

[ Voor 10% gewijzigd door RobIII op 05-11-2008 03:22 ]

[BalusC]

Hopelijk krijgen jullie het niet te druk met het verwerken van de inzendingen

* BalusC zwaait ook vanuit de tuin aka porch
Het bed zoek ik binnenkort ook op

[Verwijderd]

Heb nu redelijke verbetering in de performance van mijn PHP-uitprobeersel: 21 -> 8 seconde bij uitvoeren van 1000 zetten. Heel erg slecht vergeleken met de andere dingen die ik hier voorbij zie komen, maar kan nog veel beter en weet ook al wel een beetje waar ik het moet zoeken, maar dat komt morgen ofzo wel...

Heel leuk contest!!!!

Grrr... Ik haat dit contest!!! Hierdoor mis ik veel te veel slaap waardoor ik morgen misschien wel mijn herkansing van 70-291 ga verkloten...

edit:
Terug weten te brengen naar 5,5 4,5 seconde. Er zijn meer mensen die het met PHP maken toch? Zouden die misschien kunnen posten hoe lang dingen daar duren, zodat ik beetje kan vergelijken?

gvd... nu blijf ik maar weer wakker, over 4 3 uurtjes moet ik al weer weg...

edit 2:
Yeah! Ik kan eindelijk zelf zetten berekenen! Nog niet heel goed, nog niet heel ver... Maar het begin is er! Nu douchen enzo en naar school...

[ Voor 32% gewijzigd door Verwijderd op 05-11-2008 06:54 ]

[Brian]

Dat is best een indrukwekkende lijst Rob

[veldsla]

En dan sta ik er nog niet bij

Mijn prog doet de start wel goed met 1950 punten, maar de eerste zet daarna scoort meteen anders dan de validators, dus ik schiet nog niet heel hard op.

[Woy]

veldsla schreef op woensdag 05 november 2008 @ 08:37:
En dan sta ik er nog niet bij

Mijn prog doet de start wel goed met 1950 punten, maar de eerste zet daarna scoort meteen anders dan de validators, dus ik schiet nog niet heel hard op.

Dan zou ik even wat hoger in het topic naar een post van .oisyn zoeken, die heeft de juiste handelingen voor het eerste bord neergezet, dat kan je dan mooi vergelijken met jouw tussentijdse output.

Ik had in het begin ook een bugje, maar die kwam pas voor bij de 3000'ste zet dus was wel blij met een andere validator waardoor ik wat makkelijker kon debuggen.