Het Grote Tweakers Programmeervuur

[dragontje124]

naja mijn bot gaat het zowiezo niet winnen, maar foutloos moet toch lukken

[Jegorex]

dragontje124 schreef op zondag 29 november 2009 @ 00:06:
naja mijn bot gaat het zowiezo niet winnen, maar foutloos moet toch lukken

Wat de invoer ook is gewoon altijd passen, dan ben je er zeker van dat hij foutloos is

[dragontje124]

Jegorex schreef op zondag 29 november 2009 @ 00:19:
[...]

Wat de invoer ook is gewoon altijd passen, dan ben je er zeker van dat hij foutloos is

haha, ik zat ook te denken, wat nou als ik mijn input data doorstuur naar de bot van iemand anders en de output van die bot zelf output

[Soultaker]

Tharulerz schreef op zaterdag 28 november 2009 @ 23:21:
Mijn rummibot is af buiten dat hij nog niets gaat splitsen op tafel... ik kijk of ik daar nog tijd voor heb!

Klopt 't dat ik nog geen URL van je heb?

dragontje124 schreef op zondag 29 november 2009 @ 00:54:
haha, ik zat ook te denken, wat nou als ik mijn input data doorstuur naar de bot van iemand anders en de output van die bot zelf output

Geniaal. Makkelijk te fixen door deelnemers die hun URL geheim houden en/of toegang beperken tot mijn host.

[dragontje124]

Soultaker schreef op zondag 29 november 2009 @ 01:14:
[...]

Klopt 't dat ik nog geen URL van je heb?


[...]

Geniaal. Makkelijk te fixen door deelnemers die hun URL geheim houden en/of toegang beperken tot mijn host.

ja dat wel , maar als ik dit hier niet gepost had, had denk ik niemand daar aan gedacht .
(niet dat ik denk dat iemand dit überhaupt gaat doen)
wat is de URL naar jouw bot Soultaker ?

[ Voor 13% gewijzigd door dragontje124 op 29-11-2009 01:24 ]

[Onbekend]

dragontje124 schreef op zondag 29 november 2009 @ 00:54:
[...]

haha, ik zat ook te denken, wat nou als ik mijn input data doorstuur naar de bot van iemand anders en de output van die bot zelf output

Die gedachte had ik ook al, al was het maar voor het testen van mijn bot.

Zelf schiet ik nog niet zoveel op. Ik heb er deze week tot nu to totaal 4 uurtjes aan besteedt, en dat is veel te weinig voor wat ik erin wilde zetten. Ik hoop dat ik vanmiddag nog een paar uurtjes kan vinden waardoor ik in ieder geval een deel van de uitbreiding klaar heb. Anders is hij nog maar even slim als vorige week...

[Soultaker]

@Onbekend: publiceer je 'm dan op dezelde URL als vorige week (in tegenstelling tot twee weken geleden)? Zo niet, vergeet dan niet op tijd de URL door te geven.

edit:
Grmbl, hoe meer ik "verbeter" aan m'n speler, hoe slechter de resultaten lijken te worden.

  #   Deelnemer   Score     Winst   Fouten   Tijd      Tijd      Tijd
                                             Totaal   Gemiddeld  Maximaal
  1   player-1a      11917      357      0    89.990s    0.005s    0.065s
  2   player-2       12737      302      0    94.366s    0.005s    0.075s
  3   player-3       12819      336      0    96.120s    0.006s    0.069s
  4   simple1        28642       33      0   273.773s    0.015s    0.152s
  5   simple2        29529       29      0   277.006s    0.016s    0.110s
  6   simple3        29759       20      0   287.458s    0.016s    0.190s
  7   drawing1      233429        0      0    13.103s    0.001s    0.052s

Lijkt erop dat ik nog de meeste kans maak door gewoon de eerste versie van de speler te gebruiken (wel met bugfix) maar dat is ook weer zo lam...

[ Voor 74% gewijzigd door Soultaker op 29-11-2009 13:10 ]

[bat266]

* bat266 is online op zelfde link als vorige week

1 kleine verbetering aan de speler. Het zou me iets minder punten moeten op leveren. Ook ik had het probleem dat een verbetering een verslechtering was , dus alleen nog een bugfix doorgevoerd

[ Voor 63% gewijzigd door bat266 op 29-11-2009 15:05 ]

[Vaan Banaan]

De bot van mij is wel wat verbeterd wat betreft snelheid en wegleggen, maar verder is er niet veel aan veranderd.
Ik heb, net als sommige deelnemers, nog een beetje zitten brainstormen om stenen achter te houden, maar dat zal niet bepaald revolutionair worden. Misschien dat ik voor 19uur nog iets kan fabrieken, maar voorlopig vind ik hem nu goed genoeg zo. Ben benieuwd hoeveel, hee weer 3 nieuwe bij, nu al 13 spelers! Ok, dit gaat erg leuk worden vanavond!

[EdwinG]

Soultaker schreef op zondag 29 november 2009 @ 12:07:
Grmbl, hoe meer ik "verbeter" aan m'n speler, hoe slechter de resultaten lijken te worden.

Lijkt erop dat ik nog de meeste kans maak door gewoon de eerste versie van de speler te gebruiken (wel met bugfix) maar dat is ook weer zo lam...

Speel je hiermee jouw versies onderling tegen elkaar? Of tegen andere spelers (die ondertussen ook veranderd (en hopelijk verbeterd) zijn)

Mijn deelnemer heeft nog twee punten (voor zover ik nu weet) waar minder optimale keuzes gemaakt worden:
1) Bij een rij van 7 of meer stenen worden de middelste stenen niet als 'vrij' beshouwd:

Hand: R4, B4
Tafel: G1.G2.G3.G4.G5.G6.G7

2) Groepjes worden nog niet aan elkaar geplakt om stenen vrij te maken.

Hand: R1, G1
Tafel: B1.B2.B3-K8.R8.B8-B4.B5.B6

[Soultaker]

EdwinG schreef op zondag 29 november 2009 @ 15:20:
Speel je hiermee jouw versies onderling tegen elkaar? Of tegen andere spelers (die ondertussen ook veranderd (en hopelijk verbeterd) zijn)

Mijn versies onderling (ik wil andermans server niet nodeloos belasten), waarbij ik dus mijn simpele testspeler en een textfile met "draw" erin ook mee laat doen, om de variatie in speelsterkte die er in een echte competitie ook is een beetje te benaderen.

[Cavalera125]

Mijn botje is inmiddels in de lucht en wacht met spanning af

[Onbekend]

Mijn laaste versie staat op http://tweakers.awardspace.com/Rummikub.php

Er is weinig aangepast sinds de vorige versie.
Helaas zijn er een aantal wijzigingen verloren gegaan doordat ik het bestand door een oudere backup heb overschreven.

De wijzigingen van vanmiddag kostten me veel te veel tijd om het nog correct werkend te krijgen, dus die zitten er ook helaas niet in.
De tactiek was dus om alle legale (kleinste) combinaties voor elke steen te vinden. Daarna zou ik per combinatie elke steen afgaan of deze direct beschikbaar is, of anders indirect beschikbaar is door een andere steen bij een reeks aan te sluiten.

Bijvoorbeeld bij yourTiles=G7.K7&table=B7.B8.B9-K10.B10.R10.G10
Dan zou ik voor mijn stenen o.a. moeten zoeken naar de B7 om de combinatie B7.G7.K7 te maken.
Die B7 mag ik niet gebruiken omdat die reeks dan niet lang genoeg zou zijn. Dus ik moet zoeken of er ergens een B10 beschikbaar is om die reeks aan te vullen en zo verder.... Ik zou dan als resultaat G7.K7.B7-B8.B9.B10-K10.R10.G10 terug kunnen geven.

Maar dit was te lastig om dit in 3 uurtjes te programmeren en het foutloos werkend te krijgen....


Ik ben benieuwd naar de uitslag vanavond.

[dragontje124]

Onbekend schreef op zondag 29 november 2009 @ 17:28:
Mijn laaste versie staat op http://tweakers.awardspace.com/Rummikub.php

Er is weinig aangepast sinds de vorige versie.
Helaas zijn er een aantal wijzigingen verloren gegaan doordat ik het bestand door een oudere backup heb overschreven.

De wijzigingen van vanmiddag kostten me veel te veel tijd om het nog correct werkend te krijgen, dus die zitten er ook helaas niet in.
De tactiek was dus om alle legale (kleinste) combinaties voor elke steen te vinden. Daarna zou ik per combinatie elke steen afgaan of deze direct beschikbaar is, of anders indirect beschikbaar is door een andere steen bij een reeks aan te sluiten.

Bijvoorbeeld bij yourTiles=G7.K7&table=B7.B8.B9-K10.B10.R10.G10
Dan zou ik voor mijn stenen o.a. moeten zoeken naar de B7 om de combinatie B7.G7.K7 te maken.
Die B7 mag ik niet gebruiken omdat die reeks dan niet lang genoeg zou zijn. Dus ik moet zoeken of er ergens een B10 beschikbaar is om die reeks aan te vullen en zo verder.... Ik zou dan als resultaat G7.K7.B7-B8.B9.B10-K10.R10.G10 terug kunnen geven.

Maar dit was te lastig om dit in 3 uurtjes te programmeren en het foutloos werkend te krijgen....


Ik ben benieuwd naar de uitslag vanavond.

mooi kan ik jouw botje lekker misbruiken om te winnen
nee, just kidding
ik weet wel zeker dat ik niet ga winnen vanavond (wordt waarschijnlijk de laatste plek), ik had helaas niet zoveel tijd om eraan te werken, maar mn bot kan in iedergeval combinaties in zn eigen hand herkennen en aanleggen op de tafel

[Tharulerz]

Als je het zo uitschrijft onbekend is het vrij simpel om te programmeren, gewoon 1 recursieve functie isAvailable()

Maarjah, mijn versie is ook niet alles maar ik laat hem toch meedoen just for fun: http://platogt.dyndns.org/rummikub/index.php (werkt met GET)

[Onbekend]

Het programmeren was wel klaar, maar met het testen kwam ik op probleempjes uit waarvan ik de oorzaak niet zo snel kon vinden. Vandaar mijn keuze om de aanpassing verder te laten liggen...

(Ik heb de logfiles uitgezet, dus ik verwacht dat hij iets sneller reageert.)

[Soultaker]

Oe, last minute entries.

@Onbekend: geupdatet.
@Tharulerz: toegevoegd.

@dragontje124: we zullen zien. In competitie 2 was er al aardig wat variatie in het niveau van de spelers, dus ik denk dat het voor idereen wel een interessante competitie wordt (en niemand zich van zijn plek zeker is).

[dragontje124]

Soultaker schreef op zondag 29 november 2009 @ 17:44:
Oe, last minute entries.

@Onbekend: geupdatet.
@Tharulerz: toegevoegd.

@dragontje124: we zullen zien. In competitie 2 was er al aardig wat variatie in het niveau van de spelers, dus ik denk dat het voor idereen wel een interessante competitie wordt (en niemand zich van zijn plek zeker is).

ach joh mijne wint zelfs maar 1 van de 10 keer van de simples en als ik voor alle 4 de spelers mijn bot invul kunnen ze (bijna) nooit uit, maarja misschien zijn er meer mogelijkheden als ie tegen betere spelers speelt

[Domdo]

De bot die ik geschreven wint gegarandeerd geen potjes. Ik ben echt veel te laat begonnen maar toch doe ik even mee

[dragontje124]

we gaan aftellen, nog 3 minuten (en daarna nog 4 uur I guess? )

[Vaan Banaan]

Ok, de dood of de gladiolen. Mijn bot kijkt nu hoeveel stenen de tegenstanders hebben.
Als die de minste of een na minste stenen overhoudt na een setje of aanleggen, legt hij zo min mogelijk nieuwe stenen op tafel. Dus als hij R1-R2-R3-R4 op tafel kan gooien, maar R4 ligt nog niet op tafel, zal hij eerst R1-R2-R3 op tafel gooien.
Hij zet daardoor nu soms ontzettend tenenkrommend, maar toch werkt dit redelijk goed. Ben heel benieuwd wat het gaat worden. Ik hoop op deze manier de zwaargewichten wat tegen te werken.
Succes iedereen!!
edit 21:38 WHAAA BSOD terwijl ik alleen maar wat aan het browsen was!! 8 minuten offline

[ Voor 8% gewijzigd door Vaan Banaan op 29-11-2009 21:47 ]

[dragontje124]

zijn we al begonnen?
hoeveel potjes worden er gespeeld? en hoelang gaat dat ongeveer duren?

Veel succes iedereen trouwens!
Edit: laat maar staat al in de "startpost"
edit 2 :@Vaan Banaan auch, stond je bot op je eigen PC?

[ Voor 27% gewijzigd door dragontje124 op 29-11-2009 22:06 ]

[Verwijderd]

Ga je het redden voor 23u, Soultaker? Ik zie mn logbestand nog steeds gestaag groeien.

[edit] laatste activiteit van mijn speler was om 22:59

[ Voor 25% gewijzigd door Verwijderd op 29-11-2009 23:00 ]

[dragontje124]

Verwijderd schreef op zondag 29 november 2009 @ 22:40:
Ga je het redden voor 23u, Soultaker? Ik zie mn logbestand nog steeds gestaag groeien.

is ie nog steeds bezig?

[Domdo]

Bij mij nu nog wel. Ik krijg nog steeds requests binnen.

[dragontje124]

Domdo schreef op zondag 29 november 2009 @ 23:02:
Bij mij nu nog wel. Ik krijg nog steeds requests binnen.

hmm dat gaat dan waarschijnlijk nog wel ff duren

[Vaan Banaan]

De laatste was bij mij 3 minuten geleden. Even afwachten nog maar dan

[ Voor 6% gewijzigd door Vaan Banaan op 29-11-2009 23:17 ]

[EdwinG]

Ik heb sinds 19:00 ongeveer 2250 requests binnen gehad. Het totaal aantal requests (testrondes + eigen tests + deze wedstrijd) komt daarmee net onder de 8.000.
Het laatste kwartier is niets meer binnen gekomen.

[Soultaker]

Sorry jongens, in de traditie van de PRG Contests post ik de resultaten pas volgend jaar.

Ik had op basis van de tijden van competitie 2 ingeschat dat we in totaal 448 spelletjes zouden moeten kunnen doen (128 per speler), en dat kwam bijna precies uit: het laatste spelletje werd voltooid om 23:11. Daarna was ik zelf even afwezig, vandaar dat jullie even op de resultaten moesten wachten. Without further ado:

Eindklassement Finale Rummikubcompetitie

Plaats	Deelnemer	Totaalscore	Aantal gewonnen	Aantal fouten	Tijd
					Totaal	Gemiddeld	Maximaal
1	Bolukan	1723	55	8	601.566s	0.281s	8.681s
2	jfeitsma	1830	51	0	212.269s	0.098s	2.291s
3	Soultaker	1974	44	0	378.592s	0.176s	1.405s
4	Vaan Banaan	2566	32	38	852.178s	0.369s	8.161s
5	EdwinG	3304	10	22	546.538s	0.243s	9.029s
6	Onbekend	3490	16	20	388.801s	0.166s	4.307s
7	Cavalera125	3932	5	0	285.663s	0.127s	0.580s
8	dragontje124	5299	1	0	148.999s	0.065s	0.506s
9	GuidoH	5311	3	35	114.449s	0.051s	1.707s
10	bat266	5396	4	6	203.541s	0.089s	8.013s
11	Tharulerz	6142	2	55	615.527s	0.263s	9.066s
12	Memorice	18665	40	66	4009.009s	1.742s	8.768s
13	Domdo	19570	0	24	889.430s	0.358s	4.431s
14	joostvanpinxten	23932	0	2160	15137.642s	6.079s	9.280s

De tussenresultaten staan hier (om al te veel topicvervuiling te voorkomen post ik ze deze keer niet in het topic).

Zoals te verwachten was, zit de top 3 dicht op elkaar, maar Bolukan is de onbetwiste winnaar. Bolukan, van harte gefeliciteerd!

Ik hoop dat jullie het leuk vonden om mee te doen. Ik vond 't in ieder geval wel leuk om naast het schrijven van een speler ook eens een (mini-)contest te organiseren. Hopelijk stimuleert dit de GoT crew om werk te maken van een officiële Programming Contest #5 (waar naar mijn idee wel animo voor is) en wat mij betreft krijgt Typnix z'n topic terug om kortere/eenvoudigere problemen in te posten.

Ik zal morgen de broncode van m'n speler en de jurysoftware openbaar maken voor geinteresseerden. Mijn speler staat online op http://hell.student.utwente.nl/cgi-bin/rummikub-player (POST of GET) voor testdoeleinden en de rest van de testsite blijft voorlopig ook nog wel even online.

[ Voor 97% gewijzigd door Soultaker op 30-11-2009 00:02 ]

[dragontje124]

WHOOOHOOOO niet laatste en 1 potje gewonnen xD (en foutloos )
ik ben zeker geïnteresseert in die jurysoftware, lijkt me leuk om dit een keertje op school te doen ofzo
Gefeliciteerd Bolukan !
edit: hmm ik zie al dat ik (minstens) 1 potje heb verloren door een faal in m'n code

[ Voor 179% gewijzigd door dragontje124 op 30-11-2009 00:17 ]

[Vaan Banaan]

Bolukan gefeliciteerd! Ook jfeitsma gefeliciteerd met je 2de plek, want Soultaker was toch wel the man to beat na 2 overwinningen in de testcompetitie.
De paar minuten dat ik offline was, heeft me weinig nadeel opgeleverd. Sterker nog, ik heb zelfs nog een potje gewonnen tussen de paniek reboots door, omdat ik ineens een waslijst goede stenen op mjn plankje had.staan
Al met al een zeer leuke "mini" contest. Het kostte wel wat nachtrust, maar dat was het uiteindelijk wel waard.
Voor wie er wat aan heeft: Hier de C source code van mijn bot. Er staat wel wat commentaar in, maar verwacht geen hoogstaande kwaliteit.

[Memorice]

@Bolukan, jfeitsma & Soultaker
Gefeliciteerd met jullie scores! Ik weet niet of het verschil tussen jullie significant is, maar het zijn mooie scores!

@Soultaker
Hulde voor je organisatie!

Ik heb niets meer aan mijn speler veranderd, omdat ik op reis was. Dus de speler speelde nog steeds alles of niets, interessant is wel dat er minder spellen gewonnen werden (in verhouding) ten opzichte van de test ronde. Mocht iemand nog geinteresseerd zijn in mijn code, dan is deze hier te vinden: 128.2.208.139:8080/Rummikub.java

[Cavalera125]

Gefeliciteerd Bolukan! (ondanks 8 fouten )

Woohoo, middenmoot geeindigd, dat valt me niet tegen. Een aantal potjes bekeken en gezien dat ik gisteren toch nog een uurtje had moeten besteden om te optimaliseren. Ik laat nog enkele mooie combinaties liggen.

Soultaker, leuke contest, bedankt voor de organisatie. Klein vraagje, de servercode, is die toevallig beschikbaar?

[Onbekend]

Nog steeds fouten in m'n code.

Iedereen gefeliciteerd met de resultaten. Het was een leuke contest.
Soultaker, bedankt voor de organisatie.

[Bolukan]

Joepie !! Helemaal blij.

Soultaker bedankt voor de uitdaging.

Mijn taktiek was om een potentieel bord (aanwezige stenen plus een of meerdere stenen van mijn hand) geheel door te rekenen. Er zijn 185 potentiele rijtjes (5 verticaal (3/4 lang) x 13 nummers en 30 horizontaal (3/4/5 lang) x 4 kleuren), waarvan uitgezocht moet worden of ze kunnen. Voor de snelheid bleek de volgorde waarop je de setjes uitprobeert essentieel. Mijn oplossing is om te beginnen met de kleur/nummer combinatie met de minste mogelijke sets (1 of meer), om maar snel vast te lopen of de oplossing te vinden. Als potentiële borden onderzocht ik: a) complete sets in mijn hand, b) alle stenen, c) bord + 1 steen uit mijn hand, d) bord + 2 stenen, 3 stenen of 4 stenen uit mijn hand.

De fouten van vorige week zaten in een tijdsoverschrijding in 4 opeenvolgende zetten in één spel. Dat kan nu weer het geval zijn. Ook ik zal de source snel beschikbaar maken.

[Verwijderd]

Gefeliciteerd Bolukan, ik ben verrekte benieuwd hoe je zo'n significante voorsprong hebt gehaald.
En Soultaker, nogmaals bedankt.

Mijn speler heet "greedy-by-value": maximaliseer de weg te spelen waarde. Dit om de uiteindelijke score te minimaliseren en relatief goed te spelen tegen spelers die veel steentjes opeten.

Ik schrijf een spelsituatie op als een ILP-probleem en voer het dan aan glpk. Ik doe niks aan het achterhouden van bv melds of analyse van tegenstanders/eindsituaties via tilecounts, want ik kreeg op tijd geen consistent betere speler dan de "greedy-by-value". Kennelijk is dit Bolukan wel gelukt?

Mijn aanpak is trouwens makkelijk te generaliseren naar het spel met jokers. Alleen moet er dan wel iets slims gedaan worden mbt bewaren van joker, want "greedy-by-value" zal 'm direct afleggen en dat lijkt me niet optimaal.

[Domdo]

Soultaker bedankt voor het (goed) regelen van deze (mini)-contest. De volgende keer zal ik zeker meedoen (en wat eerder beginnen). Al met al vindt ik mijn score nog niet eens zo heel slecht gezien het feit dat mijn bot alleen maar steentjes bij kon leggen op dezelfde nummer combinaties die door andere bots begonnen was.

[stategamer]

Feli aan de top 3 !
Ben erg benieuwd naar de source's.
Ik heb deze voorbij laten schieten vanwege de tijd die nog over was(zag de opdracht pas 4-5 dagen voor einde).

Wat gaat de volgende opdracht worden?

[bat266]

Feli at all. Soultaker

Helaas dat ik de afgelopen week geen tijd had om nog een aantal van de 16 nog openstaande potentiele situaties af te handelen

[Vaan Banaan]

@Bolukan: Mijn bot doet ongeveer hetzelfde als jouw bot. Inderdaad uit 185 mogelijke groepen met de beschikbare stenen zoveel mogelijk punten weg spelen, maar dan andersom geredeneerd. Kijk steeds naar alle stenen op de plank en pak steeds meer groepen van tafel om te combineren.
Dus ongeveer zo:
Kijk eerst wat de beste combinaties op de plank zijn.
Pak dan 1 groep van tafel en doe die bij de stenen op de plank en maak dan weer de beste combinaties. De groep die van tafel getrokken is, slaat hij over, want die maximale score heeft de bot al berekend met alleen de stenen op de plank. Pak dan een volgende groep en doe hetzelfde, enzovoort.
Doe hetzelfde voor 2, 3 en 4 willekeurige groepen van tafel.
Mijn bot deed bij de 2de testcompetitie trouwens hetzelfde, maar pakte maximaal 2 groepen van tafel. Met de eindcompetitie heb ik nog iets geprobeerd met stenen achter te houden.

[dragontje124]

mijn code in PHP: http://informatica.ghlyceum.nl/users/22408/game.phps
(ja ik weet dat het bagger is )

[ Voor 23% gewijzigd door dragontje124 op 30-11-2009 20:41 ]

[.oisyn]

Jammer, net nu ik tijd heb om ook mee te doen is het afgelopen

[joostvanpinxten]

Daar gaat ie dan. Na mijn grote afgang, tweemaal zelfs, ga ik toch de code openbaar maken, ter lering ende vermaak: dit is dus een zeer (brute-force) speler die op zich werkt, maar op de een of andere manier krijg ik de recursiviteit niet binnen de perken...Erg jammer... (ook voor het doorspelen van de potjes...,)

Overigens kan je deze speler testen, waarbij je de lookup optimalisatie aan en uit kan zetten en kan zien op welke manier dat ie probeert om de puzzel op te lossen.

In verband met het ontbreken van een [inklap][/inklap] tag en een wel erg lange lap code heb ik de code nu hier geplaatst. Ben trouwens zeer benieuwd naar de code van de top3!

@SoulTaker, sorry dat ik er niet meer aan gewerkt heb en dat ik mezelf niet afgemeld heb...Kudos voor deze opzet!

[ Voor 6% gewijzigd door joostvanpinxten op 30-11-2009 15:56 ]

[Soultaker]

De broncode van mijn speler staat hier. Mijn high-level algoritme is vergelijkbaar met dat van Bolukan en jfeitsma: ik neem alle stenen op tafel en op m'n rekje bij elkaar, en probeer daarmee een geldige tafelconfiguratie te maken, waarbij ik natuurlijk oppas dat ik alle stenen die op tafel lagen op tafel blijven liggen. Daarbij probeer ik de totale waarde van stenen op tafel te maximaliseren (wat betekent dat de waarde van stenen die ik overhoud geminimaliseerd wordt).

Ik heb dus een functie die gegeven een set stenen op tafel en een set stenen op hand een tafelconfiguratie van maximale waarde teruggeeft. Om die functie efficient te implementeren maak ik gebruik van dynamic programming, waarmee ik elke stelling, ongeacht de complexiteit, binnen een paar miljoen instructies door kan rekenen. In de praktijk heb ik zelden meer dan enkele tientallen milliseconden nodig.

Om uit te leggen hoe dit algoritme werkt is het makkelijker om er van uit te gaan dat we proberen om álle stenen uit te leggen (het terugnemen van stenen die ik niet kwijt kan en het maximaliseren van het resultaten maken de implementatie wat ingewikkelder, maar veranderen niet veel aan het principe). Ik verwerk stenen per waarde (dus eerste de 1'en, dan de 2'en, et cetera). Stel nu dat ik bijvoorbeeld bij de 7s aangekomen ben. Dan heb ik al eerder een aantal groepjes op tafel gelegd (van drie 5en of vier 6en bijvoorbeeld) maar die zijn niet meer relevant voor hoeveel stenen ik verder nog op tafel kan leggen (ik kan immers nooit een 7 of hoger aanleggen bij een groepje van 6en). Om dezelfde reden zijn straatjes die eindigen op een 5 of lager niet meer van belang (want ik kan een 7 alleen aan een straatje dat eindigt op een 6 aanleggen). Elke 7 die ik op tafel leg, moet dus óf aan het eind van een straatje komen, óf met twee of drie andersgekleurde 7s in een groepje komen.

Hoe weet ik nu welke steen aan een straatje moet komen, en welke in een groepje? Helaas weet ik dat niet, maar ik kan makkelijk alle mogelijke combinaties proberen, want er zijn toch maximaal acht (twee van elke kleur) 7s in het spel, en dat is vrij weinig. De enige beperking hierbij is dat als er straatjes zijn van één of twéé lang, dan moet ik daar verplicht een 7 achter leggen (want een straatje moet minstens 3 lang zijn). Vervolgens probeer ik voor elke combinatie recursief de volgende stenen (8 en verder) aan te leggen.

Nu zou je denken dat hoewel het aantal branches voor één waarde niet zo hoog is, door de recursie het total aantal mogelijkheden wél heel groot wordt. Dat is ook zo, maar gelukkig zijn er heel veel dubbele stellingen die ik niet apart probeer uit te rekenen. Zoals hierboven beschreven zijn alleen lopende straatjes relevant bij het bepalen hoeveel stenen ik nog kan neerleggen vanaf een bepaalde waarde. De lengte van die straatjes is maar in beperkte mate van belang: alle straatjes die uit 3 of meer stenen bestaan hebben dezelfde aansluitmogelijkheden (immers, ik kan een 7 net zo makkelijk achter 3-4-5-6 leggen als achter 4-5-6, of geen van beide; dat geldt niet voor een straatje 5-6 want dat straatje is pas twee lang en dus is het aanleggen van een 7 verplicht!)

Voor elke kleur zijn er maximaal twee lopende straatjes, en elk straatje heeft lengte 1, 2 of 3+. Als ik de afwezigheid van een straat codeer als lengte 0, dan kom ik in totaal op maximaal 13 x 4⁸ = 851,968 mogelijke toestanden die ik maximaal moet doorrekenen. Voor elke toestand moet ik alle combinaties van maximaal 8 stenen doorrekenen, wat neerkomt op maximaal 3⁸ = 6561 operaties (elke steen komt in een straat, in een groep, of terug in m'n hand). In totaal heb ik dus maximaal iets van 5 miljard iteraties nodig, en iets van 2MB aan opslagruimte, wat op zich al binnen vijf seconden moet lukken, maar dit is in een grove overschatting; zelfs in de moeilijkste situaties wordt maar een fractie van de toestanden bezocht.

Als je de details wil bekijken verwijs ik je door naar de bovengenoemde broncode. Het high-level algoritme staat beschreven in play.c en de essentiële functie die het hierboven beschreven algoritme implementeert is in calc.c geïmplementeerd. (De functie waar een spelsituatie in gaat en een maximale tafelconfiguratie uitkomt, heet max_value(); dat is wel een aardig beginpunt.) Datastructuren worden gedefinieerd in player.h; de overige files zijn niet zo boeiend (een beetje parsing/formatting, CGI en memory management code).

[ Voor 5% gewijzigd door Soultaker op 30-11-2009 18:03 ]

[Verwijderd]

Helaas ben ik er niet meer aan toe gekomen om mijn speler te verbeteren, de final versie van mij was dus hetzelfde als die van de eerste testronde. Eigenlijk wel jammer, want aangezien ik met deze al 9e was, had ik nog een stuk hoger kunnen eindigen met de ideeën die ik nog had. Ah, zie wel dat ik de snelste speler had. (niet dat ik daar wat aan heb...)

Anyway, gefeliciteerd Bolukan!

[Soultaker]

Tenslotte zal ik zoals beloofd de jurysoftware posten. De arbiter is geschreven in C++ en de rest van het "systeem" bestaat uit een zwik sh en Python scripts die in elkaar gehackt zijn wanneer ik ze nodig had, waarmee matches gegenereerd worden, competities gespeeld worden, en stenen geschud worden. Voor het converteren van XML resultaten naar HTML heb ik een XQuery template; om die te processen raad ik (de gratis versie van) Saxon aan.

Al mijn data (broncode van arbiter en speler, data van spelers, competities en resultaten) staat in een Git repositry git://hell.student.utwente.nl/GoT/rummikub (ook beschikbaar via gitweb). Een snapshot in zip-formaat: rummikub.zip

Voor wie onder Windows wil testen heb ik een win32 build van de arbiter gemaakt: arbiter-win32.zip. (Ik ga er vanuit dat gebruikers van andere besturingssystemen zelf wel een compiler kunnen installeren en make kunnen typen).

De arbiter krijgt vijf argumenten: vier spelers en een lijst van stenen. Een speler wordt beschreven in een tekstbestand van drie regels: naam, URL en request method (GET/POST). Het laatste bestand bevat de 104 stenen in het spel op één regel (geformatteerd zoals de yourTiles parameter dus) in een willekeurige volgorde.

Onder Linux (maar niet onder Windows!) lockt de arbiter de spelerbestanden, waardoor je in principe spelletjes parallel kunt spelen zonder dat tegelijkertijd meerdere requests op dezelfde speler gedaan worden. Het run-comp.sh script lockt match bestanden om ervoor te zorgen dat elke match precies een keer gespeeld wordt, dus om een hele competitie runnen kun je dat script meerdere keren starten.

[Bolukan]

Hier de source en laatste versie met correcties, zie hieronder. Wel de langste code

[ Voor 85% gewijzigd door Bolukan op 30-11-2009 22:51 . Reden: ook als phps. Edit2: werkt niet, 2 versies ]

[Soultaker]

Jouw oplossing is geschreven in PHP?! Nice! Had ik niet verwacht omdat 'ie behoorlijk snel was.

Btw, waarom posten jullie allemaal je php sources als .txt? Als je 'm naar .phps renamet, krijg je fancy syntax highlighting (aangenomen dat je webserver daarvoor geconfigureerd is)

edit:
@Bolukan, lijkt bij jou niet helemaal te werken toch. Mijn server maakt er dit van: bolukan.phps

En dat komt omdat ik in m'n Apache 2 config dit heb staan:

code:

AddHandler application/x-httpd-php .php
AddHandler application/x-httpd-php-source .phps

Wellicht werkt dit in andere webservers niet/anders.

[ Voor 103% gewijzigd door Soultaker op 30-11-2009 22:45 ]

[dragontje124]

damn alle mogelijke groepen in een array, hoe kom je erop
@soultaker I'll try

[ Voor 16% gewijzigd door dragontje124 op 30-11-2009 20:40 ]

[Verwijderd]

Ik heb alle spelletjes even geanalyseerd (64KB gzipped) op suboptimale zetten van de top11, wat maximaliseren van gelegde waarde betreft. Dan kun je dus precies zien wanneer spelers iets expres achterhouden, of gewoon een combinatie gemist hebben.

@Bolukan: wat is jouw strategie qua stenen achterhouden? In spelletje 0049 bv, beurt 37 hou je twee 13s terwijl je ze af kan leggen. In beurt 41 kies je met dezelfde configuratie zelfs om te pakken. Heb je misschien berekend dat een steentje pakken op termijn meer mogelijkheden oplevert dan de 13s af te leggen?! Uiteindelijk leg je de 13s NET op tijd af, voordat Memorice in 1x alles neer kwakt.

@oisyn: we kunnen natuurlijk met jokers verder gaan... dan wordt het spel strategisch gezien een stuk interessanter.

[dragontje124]

Verwijderd schreef op maandag 30 november 2009 @ 21:38:
Ik heb alle spelletjes even geanalyseerd (64KB gzipped) op suboptimale zetten van de top11, wat maximaliseren van gelegde waarde betreft. Dan kun je dus precies zien wanneer spelers iets expres achterhouden, of gewoon een combinatie gemist hebben.

@Bolukan: wat is jouw strategie qua stenen achterhouden? In spelletje 0049 bv, beurt 37 hou je twee 13s terwijl je ze af kan leggen. In beurt 41 kies je met dezelfde configuratie zelfs om te pakken. Heb je misschien berekend dat een steentje pakken op termijn meer mogelijkheden oplevert dan de 13s af te leggen?! Uiteindelijk leg je de 13s NET op tijd af, voordat Memorice in 1x alles neer kwakt.

@oisyn: we kunnen natuurlijk met jokers verder gaan... dan wordt het spel strategisch gezien een stuk interessanter.

beetje jammer dat dan net iedereen zijn source heeft gedumpt he ?
verder begrijp ik echt helemaal niks van dat bestand

[Onbekend]

Mijn huidige code is vrij onduidelijk voor de ander, dus vandaar dit stappenplan:

1: De invoer inlezen en bruikbaar maken.
2: De bestaande reeksen op het speelbord samenvoegen. Dus 456 en 789 samenvoegen tot 456789
3: De eigen stenen zoveel mogelijk groeperen. De groepjes van drie worden apart gelegd, en zo'n groepje wordt alleen gebruikt als ik geen andere steen heb kunnen leggen. Dit scheelt weer een steen van de pakstapel.
4: Zoek reeksen van gelijke getallen waar we mijn eigen stenen aan toe kunnen voegen.
5: Doe dit hetzelfde met de runs (oplopende reeksen)
6: Doorzoek de beschikbare groepjes op het speelbord waarvan we van de uiteinde een steen kunnen afhalen. Met een eigen steen en 2 van het speelbord kan dan weer een nieuw groepje worden gevormd.
7: Zoek reeksen van oplopende getallen weer we een steen in kwijt kunnen door deze in tweeën te splitsen. Dus een losse 4 en een reeks 23456 kan naar 234 en 456 gesplitst worden.

8: Als er niets is gelegd, neem dan een gereserveerd groepje en plaats die op het speelbord. Als er geen losse stenen meer zijn, dan moeten alle groepjes gelegd worden, en is dit de laatste beurt.

9: Splits de bestaande reeksen in groepen van max. 5 stuks zodat slechtere tegenstanders er lastig stenen tussenuit kunnen halen.
10: Verplaats de volgorde van alle groepjes in een willekeurige volgorde.
11: Zet de uiteindelijke groepjes als output.

[EdwinG]

En nu in de finale heb ik dus wel foute responses gegenereerd. Alle fouten waren overigens (voor zover ik ze heb gezien) een time-out of een Out-of-memory exception.
De nieuwe 'analyses' die ik in mijn script had ingebouwd vroegen dus veel meer resources dan ik had verwacht. Ik wist dat vooral groepjes van 4 stenen met dezelfde waarde gevaarlijk waren door mijn manier om permutaties te berekenen.

Ik herken overigens diverse stappen in de methode die Onbekend hier vlak boven mij beschrijft. Deze week (waarschijnlijk morgen) zal ik mijn code ook online plaatsen.

[Bolukan]

Verwijderd schreef op maandag 30 november 2009 @ 21:38:
@Bolukan: wat is jouw strategie qua stenen achterhouden? In spelletje 0049 bv, beurt 37 hou je twee 13s terwijl je ze af kan leggen. In beurt 41 kies je met dezelfde configuratie zelfs om te pakken. Heb je misschien berekend dat een steentje pakken op termijn meer mogelijkheden oplevert dan de 13s af te leggen?! Uiteindelijk leg je de 13s NET op tijd af, voordat Memorice in 1x alles neer kwakt.

Hmmm, zou niet moeten, maar het reproduceert wel zo...
Gevonden: regel 811, zie hieronder. Eerste regel is fout, tweede is goed. Who can enlighten me why?
De code checkt of er 1 of 2 stenen beschikbaar zijn (in dit geval R13 en G13).

PHP:

 if (($TilesYour[$TileID1]) & ($TilesYour[$TileID2])) {
 if (($TilesYour[$TileID1] > 0) & ($TilesYour[$TileID2] > 0)) {
 if (($TilesYour[$TileID1]) && ($TilesYour[$TileID2])) {

Edit: Ik snap het al: 2 AND 1 = 0. Oplossing 3 toegevoegd.
Edit2: [Bolukan past het op tiental plekken aan.] Misschien was de fout een goede strategie.

[ Voor 10% gewijzigd door Bolukan op 30-11-2009 22:46 ]

[CoolGamer]

Bolukan schreef op maandag 30 november 2009 @ 22:33:
[...]


Hmmm, zou niet moeten, maar het reproduceert wel zo...
Gevonden: regel 811, zie hieronder. Eerste regel is fout, tweede is goed. Who can enlighten me why?
De code checkt of er 1 of 2 stenen beschikbaar zijn (in dit geval R13 en G13).

PHP:

 if (($TilesYour[$TileID1]) & ($TilesYour[$TileID2])) {
 if (($TilesYour[$TileID1] > 0) & ($TilesYour[$TileID2] > 0)) {

De & is een binaire and, && is een booleanse. Ik denk dat je die twee door elkaar haalt. De & kijkt op bit niveau, && kijkt naar true of false.

Bijvoorbeeld A =1 en B=2 levert bij de eerste 0 (is false in een if) op, bij de tweede (A en B worden omgezet naar boolean, ze zijn niet 0, dus true) levert het true op.

EDIT: te laat, je zag het zelf al.

[ Voor 6% gewijzigd door CoolGamer op 30-11-2009 22:39 ]

[Soultaker]

Verwijderd schreef op maandag 30 november 2009 @ 21:38:
Ik heb alle spelletjes even geanalyseerd (64KB gzipped) op suboptimale zetten van de top11, wat maximaliseren van gelegde waarde betreft. Dan kun je dus precies zien wanneer spelers iets expres achterhouden, of gewoon een combinatie gemist hebben.

Leuk ja. Het achterhouden van combinaties (maar alleen als de waarde van de gespeelde + achtergehouden combinaties even hoog is als wanneer je niets zou achterhouden) is iets wat ik in ronde 2 had toegevoegd en in ronde 3 verbeterd. Maar het lijkt erop dat dit me alleen maar slechtere scores opleverde (dat waren ook de scores die ik al eerder postte).

Waarom dat zo is, is me niet helemaal duidelijk. Ik had zelf de resultaten van competitie 2 al geanalyseerd en daarin kwam het nooit voor dat ik op het eind met combinaties bleef zitten (terwijl iemand anders dus uit was). Dat komt omdat je vooral in het begin van het spel combinaties hebt om achter te houden (maar dan heeft iedereen nog volle handen) en laat in het spel vaak met twee of drie stenen overblijft.

Ik vermoed dus dat de mindere performance komt doordat je het spel vertraagd, maar het is me niet helemaal duidelijk hoe dat werkt. Het verbaast me in ieder geval niet dat Bolukan, met een speler die eigenlijk hetzelfde doet als ik in competitie 1, een goede score wist te behalen, want die aanpak leverde ook bij mijn tests lokaal goede resultaten.

[Verwijderd]

Schuifpuzzel

Iedereen kent wel die schuifpuzzels die je alleen maar kon oplossing dmv van schuiven.
Dus deze week zal dit de opdracht zijn.

Voor degene die het niet kennen: een schuifpuzzel is een puzzel waar bij je 4 rijen van vier vakken met cijfers hebt minus 1 leeg vak.

vb:

code:

1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-X

De vakken stonden door elkaar en deze kon je alleen oplossen dmv schuiven.

vb:

code:

1-2-3-4
5-6-7-8
9-10-11-X
13-14-15-12

Opdracht

Maak dus zo'n puzzel waarvan de input handmatig ingevoert moet worden.
Deze input moet bestaan uit zetten om de puzzel op te lossen.
Voorbeeld:

code:

1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-X

puzzel -s C

Met alleen de opdracht "puzzel" weer output geeft

code:

1-2-3-4
5-6-7-8
9-10-11-X
13-14-15-12

Geef ook de gebruiker de mogelijkheid om een serie schuifacties te maken.

puzzel -n genereert nieuwe puzzel.
Als de gebruiker een invalide zet maakt, moet het programma een foutmelding geven.

Zorg ervoor dat wanneer de puzzel is opgelost dat het een nieuwe lukrake puzzelprobleem genereert.
Gebruik voor notatie van de vakken het hexadecimaal stelsel:
1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

De char X stelt het gat voor waar geschoven kan worden.

Regels

Er kan alleen geschoven worden naar het lege vak.
En er kan alleen horizontaal en verticaal geschoven worden.

Have fun en tot volgende week.

[ Voor 20% gewijzigd door Verwijderd op 02-12-2009 12:30 ]

[.oisyn]

Ik snap 'm niet Moet je nou een solver schrijven, of eentje die de puzzel speelt aan de hand van input?

Wat bedoel je met deze zin:

Zorg ervoor dat wanneer de puzzel is opgelost dat het een nieuwe lukrake puzzelprobleem genereert.

[ Voor 39% gewijzigd door .oisyn op 02-12-2009 12:02 ]

[Jaap-Jan]

Met .oisyn.

[Verwijderd]

.oisyn schreef op woensdag 02 december 2009 @ 12:02:
Ik snap 'm niet Moet je nou een solver schrijven, of eentje die de puzzel speelt aan de hand van input?

Wat bedoel je met deze zin:

[...]

Met manuele input bedoel ik: input die handmatig ingevoert moet worden.

En wat ik met de zin bedoel is dat wanneer de puzzel is opgelost dat je het zo bouwt dat er een nieuwe schuifpuzzel probleem wat at random wordt genereert aan de gebruiker voorschotelt.

[qanar]

Schuifpuzzel had ik tijdens de vorige wedstrijd gepost.

Hier een omschrijving van mijn gebruikte klasses ed.

http://qanar.be/index.php?id=13 (code in het artikel is ietwat outdatet, heb wat dingen veranderd voor het spel. Bv getPossibleMoves geeft een vector van Directions terug ipv een vector van PuzzleStates.

Daarvoor heb ik dan een Breadth en Depth-first solver geschreven (redelijk makkelijk)

Java:

public static void depthFirst( PuzzleState begin )
    {
        Stack  < PuzzleState > open   = new Stack  < PuzzleState >() ;
        Vector < PuzzleState > closed = new Vector < PuzzleState >() ;
                
        PuzzleState current = begin ;
        closed.add( current ) ;
                
        while( ! current.isCorrect() )
        {
            for( PuzzleState.Direction d : current.getPossibleMoves() )
            {
                PuzzleState ps = current.makeMove( d ) ;
                if( ! closed.contains( ps ) )
                    open.push( ps ) ;
            }
            
            current = open.pop() ;          
            closed.add( current ) ;
        }
        
        System.out.println( "SOLUTION FOUND" ); 
        System.out.println( current.toString() ) ;
    }
    
    public static void BreadthFirst( PuzzleState begin )
    {
        Vector < PuzzleState > open   = new Vector < PuzzleState >() ;
        Vector < PuzzleState > closed = new Vector < PuzzleState >() ;
                
        PuzzleState current = begin ;
        closed.add( current ) ;
                
        while( ! current.isCorrect() )
        {
            for( PuzzleState.Direction d : current.getPossibleMoves() )
            {
                PuzzleState ps = current.makeMove( d ) ;
                if( ! closed.contains( ps ) )
                    open.add( ps ) ;
            }
            
            current = open.firstElement() ; 
            
            open  .remove( current ) ;
            closed.add   ( current ) ;
        }
        
        System.out.println( "SOLUTION FOUND" ); 
        System.out.println( current.toString() ) ;
    }

Enige probleem dat ik hiermee heb is het tonen/bijhouden van het gevolgde pad. Ik weet niet juist wat hiervoor de methode zou zijn.

en als extra bonus het spel zelf: http://www.qanar.be/programs/SliderV3.jar

[ Voor 5% gewijzigd door qanar op 02-12-2009 12:11 ]

[Verwijderd]

qanar schreef op woensdag 02 december 2009 @ 12:08:
Schuifpuzzel had ik tijdens de vorige wedstrijd gepost.
[

Welke wedstrijd?

Enige probleem dat ik hiermee heb is het tonen/bijhouden van het gevolgde pad. Ik weet niet juist wat hiervoor de methode zou zijn.

Misschien dan gelijk een kans om dit recht te trekken ipv neer te dumpen? Het programma is toch niet klaar en je hebt een week om het uit te vogelen.

[ Voor 5% gewijzigd door Verwijderd op 02-12-2009 12:15 ]

[.oisyn]

Verwijderd schreef op woensdag 02 december 2009 @ 12:07:
[...]

Met manuele input bedoel ik: input die handmatig ingevoert moet worden.

Ja duh maar wat is die input, alleen de initiele configuratie van een schuifpuzzel of de door de gebruiker te zetten acties op die puzzel?

Al met al is de uitleg nogal karig. Een simpel voorbeeld van input en output had al een hoop gescheeld.

[Verwijderd]

.oisyn schreef op woensdag 02 december 2009 @ 12:15:
[...]

Ja duh maar wat is die input, alleen de initiele configuratie van een schuifpuzzel of de door de gebruiker te zetten acties op die puzzel?

Al met al is de uitleg nogal karig. Een simpel voorbeeld van input en output had al een hoop gescheeld.

noted...

Alleen de zetten van de gebruiker. Output moet opgevraagt kunnen worden door gebruiker.

[qanar]

Verwijderd schreef op woensdag 02 december 2009 @ 12:12:
Welke wedstrijd?

Zeer vreemd... nu had ik echt het idee dat ik tijdens de rummikub wedstrijd dit als een mogelijk alternatief probleem gepost had... Blijkbaar gedroomd (kan de post dus ook niet terugvinden)

Misschien dan gelijk een kans om dit recht te trekken ipv neer te dumpen? Het programma is toch niet klaar en je hebt een week om het uit te vogelen.

Datastructuur is af (zie java files in blogpost), enige wat hier nog bij zou kunnen is een methode om de correctheidsgraad van een PuzzleState te berekenen en op basis van die informatie kiezen welke tak het algoritme gaat aflopen.

Mijn breadth en depth-first implementaties zijn erg standaard (zoals je vast wel ziet) en gebaseerd op enkele wiki artikelen + andere internet informatie. Wat ik deed in mijn vorige post was (though misschien wat onduidelijk) een vraag om hulp of iemand een idee of de kennis had om mij op de goede weg te zetten om het afdrukken van het gevolgde pad toch te kunnen tonen.

Datastructuur bevat ook een manier om roosters te genereren, though geen
constructor waar je een lijstje getallen aan meegeeft (dit omdat niet alle mogelijkheden solvable zijn). Dus eigenlijk zou ik jou opdracht perfect kunnen doen (als ik die constructor nog maak, wat niet echt moeilijk is he). Echter omdat ik dacht dat jou opdracht gebaseerd was op een eerdere post (die ik dus blijkbaar niet gemaakt heb ) en van wat ik begrepen had de opdrachten meer een leidraad dacht ik dat ik meer dan genoeg programma had om al een eerste oplossing te posten.

[armageddon_2k1]

qanar schreef op woensdag 02 december 2009 @ 12:28:
[...]


Zeer vreemd... nu had ik echt het idee dat ik tijdens de rummikub wedstrijd dit als een mogelijk alternatief probleem gepost had... Blijkbaar gedroomd (kan de post dus ook niet terugvinden)

Ik wist dat je het gepost had, maar alleen niet in dit topic
qanar in "[Alg] Welke tools heb jij gemaakt? - dee..."

[Verwijderd]

qanar schreef op woensdag 02 december 2009 @ 12:28:
Zeer vreemd... nu had ik echt het idee dat ik tijdens de rummikub wedstrijd dit als een mogelijk alternatief probleem gepost had... Blijkbaar gedroomd (kan de post dus ook niet terugvinden)

Ik kan je verzekeren dat ik deze opdracht niet heb gebaseert naar aanleiding van een tip van iemand in deze topic. Sterker nog: ik wilde de opdracht al eerder geven maar ik wist nog niet wanneer.

Wat ik deed in mijn vorige post was (though misschien wat onduidelijk) een vraag om hulp of iemand een idee of de kennis had om mij op de goede weg te zetten om het afdrukken van het gevolgde pad toch te kunnen tonen.

Dat was inderdaad onduidelijk. Dus m,n botte reactie was gebaseert op misinterpretatie wat overigens niet de bedoeling was.

Echter omdat ik dacht dat jou opdracht gebaseerd was op een eerdere post (die ik dus blijkbaar niet gemaakt heb ) en van wat ik begrepen had de opdrachten meer een leidraad dacht ik dat ik meer dan genoeg programma had om al een eerste oplossing te posten.

Als je de opdracht verder leest dan zie je dat je wat meer moet doen dan de oplossing die je hebt gegeven.

[pixeled]

Leuke opdracht Typnix, maar twee details ontgaan me even.

Verwijderd schreef op woensdag 02 december 2009 @ 11:58:
Maak dus zo'n puzzel waarvan de input handmatig ingevoert moet worden.
Deze input moet bestaan uit zetten om de puzzel op te lossen.
Voorbeeld:

code:

1-2-3-4
5-6-7-8
9-10-11-12
13-14-15-X

puzzel -s C

1.) Bedoel je hier met de "C" in het commando "puzzel -s C" het nummer/karakter van het blokje dat verplaatst moet worden?

Gebruik voor notatie van de vakken het hexadecimaal stelsel:
1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

2.) Bedoel je dit als volgt (bij een opgeloste puzzel, anders zou het gehusselt staan natuurlijk)?:
1 2 3 4
5 6 7 8
9 A B C
D E F X

[Verwijderd]

je kunt beter een return waarde geven als het volgende:

HTML: voorbeeld.txt

U
U
L
L
D
R

bijvoorbeeld..

U betekent UP, vakje onder de X word omhoog geschoven
L, D, en R spreken voor zich...

laat hem een .txt bestandje teruggeven met de oplossing... dan zijn er meer talen die werken dan php

that is, zo zou ik het doen als ik een wedstrijd zou maken...

[Verwijderd]

pixeled schreef op woensdag 02 december 2009 @ 22:56:
1.) Bedoel je hier met de "C" in het commando "puzzel -s C" het nummer/karakter van het blokje dat verplaatst moet worden?

Ja

2.) Bedoel je dit als volgt (bij een opgeloste puzzel, anders zou het gehusselt staan natuurlijk)?:
1 2 3 4
5 6 7 8
9 A B C
D E F X

Ja

[Cavalera125]

Zie hier http://pastebin.com/fa114ae mijn sliderpuzzel oplossing in Java. Het zijn nogal veel regels code geworden, vandaar maar even in pastebin geplaatst. Bij het aanmaken van een nieuwe puzzel (puzzel -n) kan de gebruiker de gewenste grootte opgeven.

De PuzzleController leest de gebruikersinput en doet er vervolgens iets mee. De Puzzle heeft alle PuzzlePositions (stenen) en maakt een nieuwe random puzzle. Puzzle zorgt ook voor het checken of de puzzel is opgelost en voor het printen naar het scherm.

[- peter -]

Hmm, ik zou nog wel weer zo'n opdracht willen zien waarbij je zoals bij de rummikub wedstrijd via het web partijtjes tegen elkaar aangaat, met een of ander ander spel. Helaas heb ik de rummikub gemist.

[Onbekend]

LoBbY_1 schreef op donderdag 26 november 2009 @ 13:24:
zeeslag:P

Ik wil wel een zeeslagcompetitie in elkaar zetten.
De opdracht van Typnix met de schuifpuzzel is nu bezig dus het lijkt mij het beste dat we eerst wachten totdat deze opdracht is afgelopen.

Daarnaast zal ik zelf eerst iets moeten schrijven en uitgebreid testen of mijn code goed werkt en of het wel een opdracht waard is.

[dragontje124]

Onbekend schreef op donderdag 03 december 2009 @ 18:33:
[...]

Ik wil wel een zeeslagcompetitie in elkaar zetten.
De opdracht van Typnix met de schuifpuzzel is nu bezig dus het lijkt mij het beste dat we eerst wachten totdat deze opdracht is afgelopen.

Daarnaast zal ik zelf eerst iets moeten schrijven en uitgebreid testen of mijn code goed werkt en of het wel een opdracht waard is.

je kan altijd nog een nieuw topic maken.

[- peter -]

zeeslag

Dat klinkt als een leuk idee!

[ Voor 30% gewijzigd door - peter - op 03-12-2009 20:35 ]

[Verwijderd]

Deze topic niet bedoelt om hier competities te organiseren maar opdrachten te geven en op te lossen. Dat ik de competitie van Soultaker heb toegelaten is alleen vanwege het feit geweest dat ik tijdelijk afwezig was. En dit eigenlijk als een eenmalig iets zie. Wil je kleine competities houden. bespreek dit dan met een mod hierover om een aparte topic ervoor te openen.

Maar ik sta niet onwelwillend tegenover het idee om nog een competitie te houden maar dan niet voor nu.

[ Voor 95% gewijzigd door Verwijderd op 03-12-2009 22:42 ]

[Bolukan]

Ik zat te denken aan regenwormen. Zeeslagje lijkt me ook leuk, wel met bonuspunten voor animatie

Edit: ok mod...

[ Voor 4% gewijzigd door Bolukan op 03-12-2009 22:41 ]

[Soultaker]

Het lijkt me sowieso aan te raden om dat in een apart topic te doen. Ik vond 't persoonlijk niet heel handig om de rummikubcompetitie midden in dit topic te hebben staan. Omdat er toch de nodige pagina's aan posts aan besteed werden, lijkt een apart topic me wel zinnig.

Bovendien:

Creepy schreef op dinsdag 17 november 2009 @ 09:07:
Mocht iemand in de toekomst zo'n soort contest willen starten laat het dan even aan de mods hier weten. Gezien de uitgebreide post voor de uitleg, regels, implementatie e.d. kunnen we dat prima in een PRG contest gieten en ook een apart topic ervoor starten.

[Verwijderd]

Wat is gedaan is gedaan, Soultaker. Maar voor nu is inderdaad het beste om een aparte topic aan te maken voor contests.

[EdwinG]

De broncode van mijn rummikubspeler:

http://typefreak.nl/rummikub/basic.txt
http://typefreak.nl/rummikub/functions.txt

Veel chaotischer en ongestructureerder dan ik gewend ben, voornamelijk omdat ik direct begonnen ben met de code, in plaats van het ontwerp.

Config.php (niet beschikbaar) bevatte de credentials van de database ivm logfunctionaliteit. (welke uit deze code is verwijderd)

[ Voor 1% gewijzigd door EdwinG op 04-12-2009 21:07 . Reden: iets met extensies (php, txt, maakt het ook uit) ]

[Soultaker]

Ik denk dat je .txt in plaats van .php bedoelt?
Is gefixt.

[ Voor 17% gewijzigd door Soultaker op 07-12-2009 13:09 ]

[Verwijderd]

Gezien ik niemand nog wat heb zien posten aangaande de laatste opdracht: hoe gaat het ermee?

[Cavalera125]

Verwijderd schreef op zaterdag 05 december 2009 @ 22:17:
Gezien ik niemand nog wat heb zien posten aangaande de laatste opdracht: hoe gaat het ermee?

http://gathering.tweakers...message/33038988#33038988

[Jornn]

Soultaker schreef op vrijdag 04 december 2009 @ 20:38:
Ik denk dat je .txt in plaats van .php bedoelt?

ik denk dat hij .txt bedoelt, zodat wij de broncode kunnen bekijken

goed lezen op maandag ochtend is ook een vak apart hoor... sorry!

[ Voor 13% gewijzigd door Jornn op 07-12-2009 09:39 ]

[Verwijderd]

Word Searching

De opdracht voor deze week is eentje waar het de bedoeling is dat je een programma schrijft die woorden uit een woordenboek kan vinden uit een twee-dimensionale array van letters kan halen.
Zoals:

code:

                     m v j l i x a p e
                     j h b x e e n p p
                     h k t t h b s w y
                     r w a i n u y z h
                     p p f x r d z k q
                     t p n l q o y j y
                     a n h a p f g b g
                     h x m s h w y l y
                     u j f j h r s o a

Ter verduidelijking heb ik een externe link: uitleg
Als enige regels zijn is dat het wel om Nederlandse woorden.
En dat het zoeken verticaal, horizontaal en diagonaal gebeurt.

[ Voor 4% gewijzigd door Verwijderd op 08-12-2009 21:16 ]

[Verwijderd]

Misschien heeft iemand een linkje naar een .txt of iets dergelijks met een aantal duizend Nederlandse woorden erin? Ik ben nu al een beetje aan het googlen, maar ik kom niet zo snel iets tegen.

<edit> hier iets gevonden, er staan echter een hoop woorden in die niet in zo'n schema kunnen (cijfers, 's Gravenhage, a.u.b, enzovoorts)

[ Voor 36% gewijzigd door Verwijderd op 09-12-2009 00:51 ]

[Verwijderd]

hmm, dat is de woordenlijst van Opentaal

[ Voor 11% gewijzigd door Verwijderd op 09-12-2009 08:43 ]

[hostname]

Verwijderd schreef op woensdag 09 december 2009 @ 00:05:
<edit> hier iets gevonden, er staan echter een hoop woorden in die niet in zo'n schema kunnen (cijfers, 's Gravenhage, a.u.b, enzovoorts)

Daarvoor zijn we toch tweakers?

code:

cat file | grep '^[a-z]*$'

[Verwijderd]

hostname schreef op woensdag 09 december 2009 @ 15:18:
[...]
Daarvoor zijn we toch tweakers?

code:

cat file | grep '^[a-z]*$'

Dit gaat natuurlijk niet werken op Windows .
Maar met een beetje Google kom je voor bijna alle talen wel een manier tegen om regexp toepassen. Helaas gaat dat niet op voor C/C++ zonder PCRE of Boost libs.

Om de mensen die daarin programmeren tegemoet te komen zal de opdracht dan alleen voor Engelse woorden gaan.

[Soultaker]

Hier een lijstje met woorden vanaf vier letters (en vier tot tien, voor een wat kleiner woordenboek) zonder woorden met leestekens of diakritische tekens: woorden.zip

Hier moet wel wat leuks mee te bouwen zijn. Sowieso hoort volgens de officiële specificatie het woordenboek ook aan het eind van de invoer gegeven te worden (met kleine letters etc.) dus ik zou niet weten waarom je in je programmeertaal dan support voor reguliere expressies ofzo nodig hebt. Je zou het woordenboek niet meer hoeven filteren.

[ Voor 26% gewijzigd door Soultaker op 09-12-2009 17:41 ]

[Verwijderd]

Toch wil ik jullie een aantal vragen stellen:

Hoe vinden jullie het tot nu toe gaan kwa opdrachten?

Wat voor opdrachten zou je terug willen zien?

Zijn de opdrachten die tot nu gegeven zijn ook voor iedereen te doen. Zoja en zo nee, waarom?

[Ram0n]

De opdrachten wisselen enorm qua moeilijkheidsgraad. Het leuke aan de eerste (met de diamanten van letters) was dat het simpel was, en toch (of juist daarom) héél veel verschillende antwoorden opleverde.

Ook de nieuwe opdracht (woordzoeker) is extreem simpel (ik heb dit probleem 2 weken geleden behandeld met eerstejaars als oefententamenvraag), maar ik zou daar liever wat meer structuur in de opdracht zien om hem interessant te maken. Geef bijvoorbeeld een standaard woordenboek en een standaard set problemen, met de te verwachten output. Dan kunnen we het pas echt leuk met elkaar vergelijken

Verder zijn er opdrachten als het doolhof die weer een graadje moeilijker zijn. Helemaal prima wat mij betreft, maar let erop dat de verschillende moeilijkheidsgraden wel goed verdeeld zijn.

[Verwijderd]

Misschien is het wel leuk om met deze woordenset ook iets anders te doen, bijvoorbeeld een neuraal netwerk. Je traint het met de woorden en daarna moet het programma zeggen of een willekeurig ingevoerd woord wel of geen Nederlands woord is. Uiteraard mag de woordenlijst hiervoor niet gebruikt worden (en bij voorkeur ook geen woorden vragen uit de woordenlijst zelf).

Ik zie nu trouwens net dat dit ongeveer is wat Ram0n ook voorstelde.

[Onbekend]

Eventjes een update voor de komende zeeslagopdracht:
Mijn testspeler is klaar en ook de server is bijna klaar.
Ik heb de afgelopen dagen zitten zoeken naar een probleem in de GET en POST commando's waardoor regelmatig geen data werd uitgelezen. Zojuist heb ik, na lang testen, de oorzaak gevonden en het blijkt dat dit probleem alleen bij kleine hoeveelheden data van bijvoorbeeld 4 bytes lijkt te ontstaan. Nu ik een aantal willekeurige bytes extra verstuur treedt dat probleem niet meer op.

Gezien mijn beperkte beschikbare tijd voor de rest van deze week verwacht pas volgende week de opdracht hier op GoT neer te kunnen zetten.

[Verwijderd]

Ram0n schreef op woensdag 09 december 2009 @ 19:42:
De opdrachten wisselen enorm qua moeilijkheidsgraad. Het leuke aan de eerste (met de diamanten van letters) was dat het simpel was, en toch (of juist daarom) héél veel verschillende antwoorden opleverde.

Ook de nieuwe opdracht (woordzoeker) is extreem simpel (ik heb dit probleem 2 weken geleden behandeld met eerstejaars als oefententamenvraag), maar ik zou daar liever wat meer structuur in de opdracht zien om hem interessant te maken. Geef bijvoorbeeld een standaard woordenboek en een standaard set problemen, met de te verwachten output. Dan kunnen we het pas echt leuk met elkaar vergelijken

Verder zijn er opdrachten als het doolhof die weer een graadje moeilijker zijn. Helemaal prima wat mij betreft, maar let erop dat de verschillende moeilijkheidsgraden wel goed verdeeld zijn.

Het is voor mij heel moeilijk om te peilen wanneer een potentiele opdracht makkelijk en/of te moeilijk is.
Dit omdat ik zelf geen guru ben in programmeren. Ik doe het slechts als hobbie. Dat veel opdrachten zo makkelijk zijn is ook vanwege het feit dat iedereen de opdrachten kan maken ipv een selecte groep.
Maar ik heb wel in het verleden gezegt: mocht er iemand een opdracht hebben: opper het dan misschien kan deze wel gepost worden.

Ook wil ik voorkomen dat een opdracht over meerdere files aan broncode beslaat. Als je dan met een probleem zit, kan je het makkelijker uitleggen hoe de werking van je code is zonder dat je alle files erbij moet gaan plakken. Tenzij jullie daar anders tegenaan kijken en/of een oplossing voor dit probleem hebben, hou ik mijzelf aanbevolen.

Verwijderd schreef op woensdag 09 december 2009 @ 22:27:
Misschien is het wel leuk om met deze woordenset ook iets anders te doen, bijvoorbeeld een neuraal netwerk. Je traint het met de woorden en daarna moet het programma zeggen of een willekeurig ingevoerd woord wel of geen Nederlands woord is. Uiteraard mag de woordenlijst hiervoor niet gebruikt worden (en bij voorkeur ook geen woorden vragen uit de woordenlijst zelf).

Ik zie nu trouwens net dat dit ongeveer is wat Ram0n ook voorstelde.

<edit>Om even in te lezen in de materie

[Soultaker]

Verwijderd schreef op dinsdag 08 december 2009 @ 21:07:
De opdracht voor deze week is eentje waar het de bedoeling is dat je een programma schrijft die woorden uit een woordenboek kan vinden uit een twee-dimensionale array van letters kan halen.

Mijn oplossing:

C++:

#include <iostream>
#include <string>
using namespace std;

static const int DR[8] = { -1, -1, -1,  0,  0, +1, +1, +1 };
static const int DC[8] = { -1,  0, +1, -1, +1, -1,  0, +1 };

struct Trie
{
    Trie() {
        for (int n = 0; n < 26; ++n) m_child[n] = NULL;
    }

    ~Trie() {
        for (int n = 0; n < 26; ++n) delete m_child[n];
    }

    void insert(const char *str) {
        if (*str < 'a' || *str > 'z') return;
        Trie *&child = m_child[*str - 'a'];
        if (!child) child = new Trie;
        child->insert(str + 1);
    }

    bool find(const char *str) {
        if (*str == '\0') return true;
        if (*str < 'a' || *str > 'z') return false;
        Trie *child = m_child[*str - 'a'];
        if (!child) return false;
        return child->find(str + 1);
    }

private:
    Trie *m_child[26];
};

int main()
{
    // Read size of grid
    int N;
    if (!(cin >> N) || (N < 1) || (N > 30000))
    {
        cerr << "ongeldige invoer!\n";
        return 1;
    }

    // Read grid
    char grid[N][N];
    for (int r = 0; r < N; ++r)
        for (int c = 0; c < N; ++c) cin >> grid[r][c];

    // Construct suffix trie of all lines in the grid
    Trie trie;
    for (int r1 = 0; r1 < N; ++r1)
        for (int c1 = 0; c1 < N; ++c1)
            for (int d = 0; d < 8; ++d)
            {
                std::string line;
                for ( int r = r1, c = c1; r >= 0 && r < N && c >= 0 && c < N;
                      r += DR[d], c += DC[d] ) line += grid[r][c];
                trie.insert(line.c_str());
            }

    // Read dictionary and match words against suffix trie:
    std::string word;
    while (cin >> word) if (trie.find(word.c_str())) cout << word << '\n';
}

Een simpel invoerbestand om mee te testen:

10
rexnelmilq
untokpeyvo
diisqiepsf
irkoswoopa
eacovilbba
btobskersa
rcgananasp
eedadeleba
onirmbnrcp
mmufdewskp
aardbei
ananas
appel
banaan
bosbes
braam
citroen
dadel
druif
framboos
jujube
kiwi
kokosnoot
kruisbes
limoen
lychee
mango
meloen
mispel
moerbei
nectarine
papaja
peer
perzik
pruim

Verwachtte uitvoer:

ananas
appel
dadel
kiwi
moerbei
nectarine

Hier is een nog een wat grotere testcase: large.in (uitvoer: large.out)

[ Voor 3% gewijzigd door Soultaker op 10-12-2009 16:53 ]

[Soultaker]

Verwijderd schreef op woensdag 09 december 2009 @ 18:53:
Hoe vinden jullie het tot nu toe gaan kwa opdrachten?

Ik vind ze wel leuk, maar ik vind nog steeds dat de uitwerking wat beter kan. Ik zou graag zien dat de volledige opdracht duidelijk en compleet beschreven wordt in je post, inclusief voorbeeldin- en uitvoer (indien van toepassing), zodat deelnemers na het lezen van jouw post direct aan de slag kunnen. Aangezien je streeft naar het posten van één probleem per week, lijkt me dat dat moet kunnen.

Als iedereen eerst allerlei externe pagina's moet lezen, dan nog het internet moet afzoeken naar een woordenlijst, die parsen en filteren om een invoerbestand te verkrijgen, dan nodigt dat niet bepaald uit om een (half)uurtje te besteden aan het schrijven van een oplossing voor het daadwerkelijke probleem.

Ook wil ik voorkomen dat een opdracht over meerdere files aan broncode beslaat. Als je dan met een probleem zit, kan je het makkelijker uitleggen hoe de werking van je code is zonder dat je alle files erbij moet gaan plakken.

Dat lijkt me een goed streven.

[Verwijderd]

Ik heb op Google gezocht naar de theorie van een neuraal netwerk. Echter ontbreekt bij mij even de logica om het in een opdracht te proppen. Heeft iemand een idee om dit te implementeren?

[Verwijderd]

Ik gebruik al tijden 'Neuro-Evolving of Augmenting Topologies' (NEAT). Ik zoek nog leuke mogelijkheden om dit in te zetten, dus ik lees zeker verder mee

[Memorice]

Verwijderd schreef op donderdag 10 december 2009 @ 23:01:
Ik heb op Google gezocht naar de theorie van een neuraal netwerk. Echter ontbreekt bij mij even de logica om het in een opdracht te proppen. Heeft iemand een idee om dit te implementeren?

Een Neural Network is gewoon een machine learning techniek voor bijvoorbeeld classification. Om eerlijk te zijn zie ik niet echt in hoe je dit in een geschikte opdracht om kunt vormen, met name omdat er ook alternatieve mogelijkheden zijn. Het enige wat ik zou kunnen bedenken is een bredere 'opdracht', waarin het gebruik van Neural Networks een mogelijke aanpak kan zijn. Zo zou je bijvoorbeeld een dataset kunnen nemen, vervolgens dit opsplitsen in een train en test gedeelte, het train gedeelte beschikbaar maken en er dan een classification task van maken, maar ik beschouw dit toch niet echt meer als een opdracht die in de context van dit topic past. Wanneer hier anders over gedacht wordt, dan kan ik best een dataset leveren...