Het Grote Tweakers Programmeervuur

[D-Raven]

Vindt dit eigenlijk niet iets voor alle niveau's. Meer beginner, de uitdaging ligt hem hier in de wiskunde, en deze is van het niveau wat mijn zusje van 17 nog kan oplossen.

[.oisyn]

HawVer schreef op woensdag 28 oktober 2009 @ 12:35:
[...]

Volgens mij is P het aantal plekken in het vierkant, dus breedte x hoogte.

dat noemt men ook wel oppervlakte

[HawVer]

.oisyn schreef op woensdag 28 oktober 2009 @ 13:21:
[...]
dat noemt men ook wel oppervlakte

Stel dan geen vraag, als je het antwoord gebruikt om af te zeiken.

[Soultaker]

De verwarring zit 'm er in dat perfect square vertaald is als perfect vierkant terwijl geheeltallig kwadraat bedoeld wordt. .oisyn had 't best kunnen begrijpen als 'ie wat beter z'n best had gedaan, maar de verborgen boodschap was waarschijnlijk dat de probleemstelling iets helderder zou kunnen.

Ik zou simpelweg stellen dat het bericht in een zo klein mogelijk vierkant geplaatst moet worden; een vierkant is immers al een gelijkzijdige rechthoek. Dan kun je zelf wel bedenken dat de zijden van dat vierkant ceil(sqrt(lengte van de invoer)) worden. Een voorbeeldje erbij en 't is duidelijker dan met een wiskundige definitie.

[.oisyn]

HawVer schreef op woensdag 28 oktober 2009 @ 13:23:
[...]

Stel dan geen vraag, als je het antwoord gebruikt om af te zeiken.

Het was ten eerste geen afzeiking (is dat een woord? nu wel ), en ten tweede was oppervlakte een van de mogelijke antwoorden op mijn vraag, waar jij voor koos om te negeren, waardoor je de indruk wekte dat je zelf niet helemaal doorhad dat het over oppervlakte ging en ik je dus aan die associatie wilde helpen

Soultaker schreef op woensdag 28 oktober 2009 @ 13:56:
De verwarring zit 'm er in dat perfect square vertaald is als perfect vierkant

Ah ja, makes sense idd.

maar de verborgen boodschap was waarschijnlijk dat de probleemstelling iets helderder zou kunnen.

Klopt als een bus . Áls je al de wiskundige definitie van het probleem wilt geven moet je er natuurlijk ook voor zorgen dat die helemaal klopt, want itt geschreven tekst waar je fouten uit kunt filteren mbv begrijpend lezen kan het voor wiskundige definities desastreuze gevolgen hebben. Maar nog beter...:

Ik zou simpelweg stellen dat het bericht in een zo klein mogelijk vierkant geplaatst moet worden; een vierkant is immers als een gelijkzijdige rechthoek. Dan kun je zelf wel bedenken dat de zijden van dat vierkant ceil(sqrt(lengte van de invoer)) worden. Een voorbeeldje erbij en 't is duidelijker dan met een wiskundige definitie.

Helemaal mee eens.

[ Voor 10% gewijzigd door .oisyn op 28-10-2009 14:09 ]

[Soultaker]

Een oplossing in Haskell:

Haskell:

import System
import List

rotate      = map reverse.transpose
addSide r   = [0..length r - 1]:(map.map) (+length r) (rotate r)
squares     = iterate (addSide.addSide) []
permFor     = concat.(squares!!).ceiling.sqrt.fromIntegral.length
invert p    = map snd $ sort $ zip p [0..]
permute     = map.(!!)
padWith c   = (++ repeat c)
rtrim c     = reverse.dropWhile (==c).reverse
encode s    = permute (padWith '$' s) $ permFor s
decode s    = rtrim '$' $ permute (padWith ' ' s) $ invert $ permFor s

main = getArgs >>= (putStrLn.run)
    where   run ["-e", s]   = encode s
            run ["-d", s]   = decode s
            run _           = "usage:\tzitscode -d <text> (to decode)\n"
                                 ++ "\tzitscode -e <text> (to encode)"

$ ./zitscode -e 'Hello world!'
Hell!$$od$$ lrow
$ ./zitscode -d 'Hell!$$od$$ lrow'
Hello world!

Wellicht zijn imperatieve talen toch wat geschikter voor dit probleem. (Code zoals van RobIII is wel wat efficiënter, hoewel dat voor strings tot lengte duizend natuurlijk niet heel belangrijk is.)

[RayNbow]

Soultaker schreef op woensdag 28 oktober 2009 @ 18:57:
Een oplossing in Haskell:

Haskell:

import System
import List

rotate      = map reverse.transpose
addSide r   = [0..length r - 1]:(map.map) (+length r) (rotate r)
squares     = iterate (addSide.addSide) []
squareFor   = (squares!!).ceiling.sqrt.fromIntegral.length
permFor     = foldr (++) [].squareFor
invert p    = map snd $ sort $ zip p [0..]
permute s   = map (s!!)
padWith c   = (++ repeat c)
rtrim c     = reverse.dropWhile (==c).reverse
encode s    = permute (padWith '$' s) $ permFor s
decode s    = rtrim '$' $ permute (padWith ' ' s) $ invert $ permFor s

main = getArgs >>= (putStrLn.run)
    where   run ["-e", s]   = encode s
            run ["-d", s]   = decode s
            run _           = "usage:\tzitscode -d <text> (to decode)\n"
                                 ++ "\tzitscode -e <text> (to encode)"

$ ./zitscode -e 'Hello world!'
Hell!$$od$$ lrow
$ ./zitscode -d 'Hell!$$od$$ lrow'
Hello world!

Wellicht zijn imperatieve talen toch wat geschikter voor dit probleem. (Code zoals van RobIII is wel wat efficiënter, hoewel dat voor strings tot lengte duizend natuurlijk niet heel belangrijk is.)

Twee suggesties van hlint:

C:\tmp>hlint soultaker.hs
test.hs:8:1: Error: Use concat
Found:
  foldr (++) [] . squareFor
Why not:
  concat . squareFor

test.hs:10:1: Warning: Eta reduce
Found:
  permute s = map (s !!)
Why not:
  permute = map . (!!)

Found 2 suggestions (1 error)

[schoene]

Mijn eerste poging:

C++:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <exception>

enum ZitCoding {zitEncode, zitDecode};

std::string zit (const std::string& source, ZitCoding coding)
{
    size_t p = static_cast<size_t> (std::ceil (std::sqrt (source.size ())));

    if (coding == zitDecode && p*p != source.size ())
        throw std::exception ();

    std::string target (p*p, '$');

    size_t x = 0, y = 0;
    int incx = 1, incy=0;
    size_t maxsteps = p, currentsteps=1;

    for (size_t i=0; i < source.size (); ++i)
    {
        if (coding == zitDecode)
            target[i] = source [y*p + x];
        else
            target[y*p + x] = source [i];

        x += incx;
        y += incy;
        ++currentsteps;

        if (currentsteps == maxsteps)
        {
            currentsteps = 0;

            if (! incy)
                --maxsteps;
            else
                incy = -incy;

            std::swap (incx, incy);
        }
    }

    return target;

}

std::string encode (const std::string& source)
{
    return zit (source, zitEncode);
}

std::string decode (const std::string& source)
{
    std::string target = zit (source, zitDecode);

    int size = target.size ();

    while (size > 0 && target [size-1] == '$')
        --size;

    target.resize (size);

    return target;
}

int main()
{
    std::cout << "Enter line: " << std::endl;
    std::string inputString;
    std::getline (std::cin, inputString);
    //std::cin >> inputString; <-- code plaatsen zonder testen is nooit slim :)

    std::string encoded = encode (inputString);
    std::string decoded = decode (encoded);

    std::cout << encoded << std::endl;
    std::cout << decoded << std::endl;

    return 0;
}

Enter line:
abcd fgh jklmn pqrstu wxyz1 34567
abcd ftu wxgs67$yhr5$$z q43 1jp nmlk
abcd fgh jklmn pqrstu wxyz1 34567

Nadien de bestaande oplossingen bekeken, werkwijze is zoals bij RobIII

[ Voor 3% gewijzigd door schoene op 28-10-2009 23:31 ]

[Verwijderd]

.oisyn schreef op woensdag 28 oktober 2009 @ 12:14:
[...]

Que? Wat is dan >= M? Een zijde van P? De oppervlakte van P? De omtrek? P is het vierkant, dat is op zichzelf geen getal.

Ik heb "letterlijk" vertaald wat er als uitleg stond. Daarom staat er niet voor niets een link naar de opdracht zelf om dit soort situaties te voorkomen.

D-Raven schreef op woensdag 28 oktober 2009 @ 13:15:
Vindt dit eigenlijk niet iets voor alle niveau's. Meer beginner, de uitdaging ligt hem hier in de wiskunde, en deze is van het niveau wat mijn zusje van 17 nog kan oplossen.

Klagen, klagen maar zelf niet met iets komen is makkelijk.

Soultaker schreef op woensdag 28 oktober 2009 @ 13:56:
De verwarring zit 'm er in dat perfect square vertaald is als perfect vierkant terwijl geheeltallig kwadraat bedoeld wordt. .oisyn had 't best kunnen begrijpen als 'ie wat beter z'n best had gedaan, maar de verborgen boodschap was waarschijnlijk dat de probleemstelling iets helderder zou kunnen.

Hmm, my bad.

[Soultaker]

RayNbow schreef op woensdag 28 oktober 2009 @ 19:12:
Twee suggesties van hlint:

Handig tooltje. De functie concat kende ik niet eens en de tweede vereenvoudiging had ik over het hoofd gezien. Ik heb 't even aangepast in m'n post. (Overigens vind ik error wel erg sterk voor wat feitelijk neerkomt op het herimplementeren van een standaardfunctie onder een andere naam.)

Het is trouwens de vraag of al die point-free definities het veel leesbaarder maken, maar goed, het is wel heel functioneel natuurlijk.

---

schoene schreef op woensdag 28 oktober 2009 @ 20:23:
Mijn eerste poging: [..]

Enter line:
abcd fgh jklmn pqrstu wxyz1 34567
abcd ftu wxgs67$yhr5$$z q43 1jp nmlk
abcd fgh jklmn pqrstu wxyz1 34567

Leuk geprobeerd, maar ik geloof niet dat die uitvoer door het door jou gepostte programma gegenereerd is.

[ Voor 57% gewijzigd door Soultaker op 28-10-2009 22:43 ]

[crisp]

Ook een bijdrage:

JavaScript:

function zitscode(o,s)
{
    var e=[],w=x=y=Math.ceil(Math.sqrt(s.length)),i=1,j=k=0,l=w*w;
    o=o=='d';
    while(l--)
    {
        e[k]=s.charAt(j)||'$';

        if(!--y)
        {
            i=i*i==1&&x--?i*w:-i/w;
            y=x;
        }

        j+=o?i:1;
        k+=o?1:i;
    }
    e=e.join('');
    return o?e.replace(/\$+$/,''):e;
}

alert(zitscode('e','The quick brown fox jumps over the lazy dog'));

alert(zitscode('d','The quips ovecm dogrkuy$$$  jz$$$tb al ehrxof nwo'));

[schoene]

Soultaker schreef op woensdag 28 oktober 2009 @ 20:59:
Leuk geprobeerd, maar ik geloof niet dat die uitvoer door het door jou gepostte programma gegenereerd is.

Haha, je bedoelt waarschijnlijk dat de 'Enter line' niet in de code staat? ik was al mn post aan het maken, met mn code reeds gepaste, en om de output te genereren had ik ondertussen nog die 'Enter line' er aan toegevoegd. Echter die nog vergeten toevoegen in mn code hier

edit: ik merk nu pas dat ik mn code toen iets te vroeg gepost had: tijdens testen gebruikte ik std::cin niet, en ik paste nadien de code zonder eventjes te testen aan, en eventjes vergeten dat ik getline moest gebruiken. lol, bij deze is het aangepast

[ Voor 27% gewijzigd door schoene op 28-10-2009 23:33 ]

[RayNbow]

Soultaker schreef op woensdag 28 oktober 2009 @ 20:59:
[...]

Handig tooltje. De functie concat kende ik niet eens en de tweede vereenvoudiging had ik over het hoofd gezien. Ik heb 't even aangepast in m'n post. (Overigens vind ik error wel erg sterk voor wat feitelijk neerkomt op het herimplementeren van een standaardfunctie onder een andere naam.)

Mjah, ik vind zelf de melding "error" ook niet zo geweldig. Let wel dat het gebruik van foldr (++) [] als mogelijk nadeel heeft dat bepaalde optimalisaties niet worden doorgevoerd.

* RayNbow ziet namelijk in de source van GHC een rewrite rule voor het gebruik van concat...

Het is trouwens de vraag of al die point-free definities het veel leesbaarder maken, maar goed, het is wel heel functioneel natuurlijk.

Ik ben een voorstander van point-free mits duidelijk.

[BtM909]

crisp schreef op woensdag 28 oktober 2009 @ 23:14:
Ook een bijdrage:

JavaScript:

WTF, nice

[RobIII]

BtM909 schreef op donderdag 29 oktober 2009 @ 00:44:
[...]

WTF, nice

Nu nog effe jsmin+ eroverheen

[Verwijderd]

Zoals al gemerkt hebben is er voor deze week geen nieuwe opdracht.
Dit ivm met verhuizing van TS. En dat zal twee weken nog wel zo zijn.

Van mij mag er iemand een vrije opdracht oppperen.

[Soultaker]

Om het topic niet dood te laten bloeden wil ik wel een voorstel doen voor het spelen van een Rummikubtoernooi. Dat kan wat langer dan één week lopen (aangezien Typnix druk bezig is met verhuizen, en er toch nog geen concurrerende GoTPC is). Ik zal de opdracht voor de overzichtelijkheid in een aparte post plaatsen.

Het is maar een voorstel, dus suggesties en correcties zijn welkom, maar ik zou wel graag weten wie er zoal van plan is om een speler te schrijven. Als er enig enthousiasme is wil ik wel wat testscriptjes enzo schrijven, maar als ik de enige ben die mee wil doen heeft dat natuurlijk weinig zin. Met minstens vier spelers kunnen we een toernooitje van N ronden doen en de punten optellen. (Puur voor de lol, er valt niets te winnen behalve eeuwige roem natuurlijk.)

[Soultaker]

Rummikub

Velen van jullie zullen het gezelschapsspel Rummikub wel kennen. Wie het spel niet kent, doet er misschien goed aan de officiële regels te lezen, hoewel die niet normatief zijn.

Het doel is om een programma te schrijven dat een vereenvoudigde variant van Rummikub kan spelen via een webinterface. Die kan dan gebruikt worden om een toernooitje te spelen met alle deelnemers.

Moeilijkheidsgraad

Gemiddeld tot moeilijk. Het is lastig om een perfecte speler te maken, maar een niet al te snuggere speler moet kunnen. Meedoen is belangrijker dan winnen.

Spelregels

Rummikub wordt gespeeld met stenen die elk een kleur (rood, groen, blauw of zwart) en een waarde (tussen 1 en 13, inclusief) hebben. Elke combinatie komt twee keer voor, dus er zijn in totaal 4x13x2=104 stenen. We doen niet aan jokers.

Het spel wordt gespeeld met vier spelers, die elk een eigen rekje met stenen hebben (bij de tegenstanders is het aantal bekend). In het begin krijgt elke speler veertien willekeurige stenen; de overige stenen kunnen later gepakt worden. Spelers zijn om de beurt aan zet, en moeten proberen zo snel mogelijk hun stenen zien kwijt te raken.

Als je aan de beurt bent, mag je ofwel één steen trekken (als er nog over zijn) of één of meer stenen op tafel leggen (spelen). Je mag daarbij alle stenen op tafel hergroeperen zoals je wil, zolang er uiteindelijk maar een geldige configuratie op tafel ligt. (Alleen als je niet kunt spelen én er zijn geen stenen meer om te trekken kun je passen, d.w.z. de beurt doorgeven zonder te spelen of te trekken.)

Een configuratie is geldig als alle stenen zijn ondergebracht in groepjes. Een groepje bestaat uit:

1. drie of meer stenen met dezelfde waarde maar verschillende kleuren:
   
2. drie of meer stenen met dezelfde kleur en strict opvolgende waarden:
   

Logischerwijs kunnen in zo'n groepje maximaal vier respectievelijk dertien stenen zitten.

Het spel eindigt zodra een speler zijn rekje leeggespeeld heeft, of er vier keer op een rij gepast wordt. De score van een speler is de som van de waarden van de stenen die hij nog over heeft; hoe lager hoe beter.

Technische regels

Implementeer een Rummikubspeler met een webinterface, zodat een spelsituatie ofwel in de query string van een GET request gegeven kan worden, ofwel in de request body van een POST request, en de speler zijn zet als plain-text response body teruggeeft.

Request parameters

Elke request krijgt de volgende parameters. Je mag er vanuit gaan dat de parameters consistent zijn, d.w.z. overeenkomen met een geldig lopend spel en voldoen aan de hier beschreven formattering.

Stenen worden gecodeerd met een letter voor de kleur (R, G, B of K) gevolgd door een getal. Bijvoorbeeld R11 is de rode elf.

Parameter	Betekenis	Voorbeeld
yourTiles	Jouw stenen, gescheiden door punten.	R7.G10.B2
table	Huidige configuratie op tafel. Stenen in een groepje gescheiden door punten, groepjes gescheiden door streepjes. Stenen in een groepje zijn gesorteerd op kleur en daarna op getal; de groepjes zelf staan in willkeurige volgorde.	G3.G4.G5-R7.G7.B7.K7
poolTiles	Aantal te pakken stenen over.	70
opponentsTiles	Aantal stenen dat je tegenstanders nog overhebben, gescheiden door punten, in speelvolgorde.	3.13.8

De meeste spelers zullen aan de eerste twee parameters genoeg hebben. De laatste twee zijn wellicht handig als je geavanceerde strategiën wil implementeren. Een volledige request URL kan er bijvoorbeeld zo uit zien:

code:

http://example.com/rummikub.cgi?yourTiles=R12.B12.K13.R3.R2.K4.B9.B8.K11&table=G6.G7.G8.G9-B1.B2.B3-R5.R6.R7-R7.R8.R9.R10-R1.G1.B1-K5.K6.K7-B4.B5.B6.B7&poolTiles=47&opponentsTiles=5.13.6

Response body

Eén regel plain text met ofwel de tekst draw (om te trekken indien mogelijk, of anders te passen) of een nieuwe tafelconfiguratie. Deze nieuwe configuratie moet gevormd worden met álle oude stenen op tafel én minstens één van jouw stenen. De groepjes of stenen in een groepje hoeven niet op een bepaalde manier gesorteerd te worden, maar moeten wel voldoen aan de bij table genoemde syntax.

De respons op het eerdergenoemde voorbeeld kan bijvoorbeeld zijn:

code:

G6.G7.G8.G9-B1.B2.B3-R5.R6.R7-R7.R8.R9.R10-R1.G1.B1-K5.K6.K7-B4.B5.B6.B7.B8.B9

Hierbij legt een speler een blauwe 8 en 9 aan het laatste rijtje op tafel aan.

Uitzonderingen

Mocht een programma een ongeldige zet doen, dan wordt die zet automatisch omgezet in een draw om het spel door te kunnen laten gaan. Er geldt een tijdlimiet van vijf seconden per zet. (Ik gebruik een iets hogere request timeout om te compenseren voor network latency.)

Testen

Je kunt hier je speler testen en zo verifiëren dat je de regels en het protocol goed geïmplementeerd hebt.

Competities

	Datum	Tijd	Deelnemers	Resultaten
Testcompetitie 1	Zondag 15 november	19:00-23:00	EdwinG, Soultaker, Onbekend, qanar, GuidoH	post, html
Testcompetitie 2	Zondag 22 november	19:00-23:00	bat266, Bolukan, EdwinG, GuidoH, jfeitsma, joostvanpinxten, Memorice, Onbekend, Soultaker, Vaan Banaan	post, html
Eindcompetitie	Zondag 29 november	19:00-23:00	bat266, Bolukan, Cavalera125, Domdo, dragontje124, EdwinG, GuidoH, jfeitsma, joostvanpinxten, Memorice, Onbekend, Soultaker, Tharulerz, Vaan Banaan	post, html

[ Voor 41% gewijzigd door Soultaker op 30-11-2009 00:35 ]

[writser]

Klinkt als een leuke opdracht. En heb tijd zat dus doe wel mee! Maar wat is de bedoeling van de web-interface? Dat je je bot thuis laat draaien? Is het gebaseerd op HTTP? En is het makkelijk om zo'n interface te implementeren in C++?

[ Voor 5% gewijzigd door writser op 05-11-2009 18:45 ]

[Soultaker]

Het idee achter de webinterface is dat ik vermoed dat veel Tweakers toch wel aan webdevelopment doen, en op deze manier ik makkelijk een toernooitje kan draaien met alle deelnemers door HTTP requests te doen op hier aangekondigde URLs, zonder dat ik mensen specifieke talen/platforms/hardware moet opleggen of heel veel moeite moet doen om zelf alle programma's lokaal te draaien.

In C/C++ kun je vrij simpel een CGI app coden. Bijvoorbeeld, onderstaand programma parset de query string en print de parameters in plain text terug. (Ik denk dat je 't zelf wel naar smaak kunt aanpassen aan de specificaties hierboven.)

C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char *data, *k, *v;

    if (!(qs = getenv("QUERY_STRING")))
    {
        fprintf(stderr, "No query string!\n");
        return EXIT_FAILURE;
    }

    printf("Content-type: text/plain\n\n");

    for (k = strtok(qs, "&"); k; k = strtok(NULL, "&"))
    {
        if ((v = strchr(k, '=')))
        {
            *v++ = '\0';
            printf("'%s' -> %s\n", k, v);
        }
    }

    return EXIT_SUCCESS;
}

Ik kan me voorstellen dat je om zelf te ontwikkelen een andere interface zou willen gebruiken (bijvoorbeeld, als in het voorbeeld hierboven QUERY_STRING niet gezet is, haal je je invoer uit een bestand of de command line ofzo). Mochten mensen het problematisch vinden om een webapp te bouwen dan kan ik eventueel wel een wrapper schrijven en programma's lokaal draaien. Doe maar een voorstel zou ik zeggen. (Dan ben je overigens wel gebonden aan Linux en niet al te veel CPU tijd en geheugen gebruiken.)

[ Voor 8% gewijzigd door Soultaker op 05-11-2009 19:19 ]

[writser]

Niemand anders enthousiast? Of mis ik het nieuwe topic ..

[.oisyn]

Ja, we zijn allemaal verhuisd maar hebben jou niets verteld

[Soultaker]

FWIW ik heb even snel iets in elkaar gehackt om je speler online te kunnen testen. (Zie link in de opdrachtbeschrijving hierboven).

offtopic:
Ik ben me bewust van de beveiliginsrisico's van het doen van server-side requests naar gebruikergespecificeerde URLs; gelieve daar gewoon geen misbruik van te maken.

[EdwinG]

Soultaker schreef op donderdag 05 november 2009 @ 18:22:
en er toch nog concurrerende GoTPC is

Mis ik hier het woord geen of een compleet topic?

[Soultaker]

Ja, ik bedoelde geen (of ik heb het topic ook gemist )

[Soultaker]

*schop*

Geen animo?

[ Voor 3% gewijzigd door Soultaker op 10-11-2009 18:10 ]

[compufreak88]

Ik lees deze opdracht nu pas. Lijkt me wel interessant.

[Dricus]

Wel animo, maar deze week helaas erg weinig tijd...

[Sebazzz]

Soultaker schreef op dinsdag 10 november 2009 @ 18:10:
*schop*

Geen animo?

Het is zowat PRG contest waardig, misschien daarom

[Onbekend]

compufreak88 schreef op dinsdag 10 november 2009 @ 18:48:
Ik lees deze opdracht nu pas. Lijkt me wel interessant.

Ik lees hem nu ook pas, een Rummicub lijkt mij ook wel leuk om de programmeren. Er zijn weinig spelregels wat je moet programmeren, dus de tijd die je daaraan moet besteden valt mee en je kan de meeste tijd besteden aan het hoofdonderdeel; namelijk het algoritme.
Vanaf morgen ga ik een beginnetje maken, en hoop van het weekend iets te kunnen posten....

Edit: Hoe weet ik of ik al de eerste 30 punten al heb gelegd?

[ Voor 14% gewijzigd door Onbekend op 10-11-2009 19:21 ]

[Soultaker]

Die 30 punten doen we niet aan. (Ik heb de regels iets veranderd om de opdracht zo simpel mogelijk te houden. Er zitten ook geen jokers in 't spel.) Ik vraag me sowieso af wat de meerwaarde van die regel is, maar dat terzijde.

[Jaap-Jan]

En is er een maximale tijd per zet?

edit:
De officiële regels (de Sabra- versie) spreken van maximaal 2 minuten per zet. Is het een idee om dat aan te houden?

[ Voor 73% gewijzigd door Jaap-Jan op 11-11-2009 12:25 ]

[Verwijderd]

Mocht je bij normaal Rummikub nou ook stenen bij tegenstanders aanleggen? Zo ja, mag dat hier ook?
/me heeft niet zo vaak Rummikub gespeeld

[Jaap-Jan]

Je hebt gewoon stenen in groepjes van minimaal 3 op tafel liggen en daar mag je mee schuiven wat je wilt, zolang je uiteindelijk maar groepjes overhoudt van minimaal 3 stenen. Stenen die op tafel liggen, mag je niet pakken (op je eigen rekje zetten).

[Verwijderd]

Jaap-Jan schreef op woensdag 11 november 2009 @ 01:07:
Je hebt gewoon stenen in groepjes van minimaal 3 op tafel liggen en daar mag je mee schuiven wat je wilt, zolang je uiteindelijk maar groepjes overhoudt van minimaal 3 stenen. Stenen die op tafel liggen, mag je niet pakken (op je eigen rekje zetten).

Ah dat was 't. Denk dat ik hem even oversla, wordt iets te.

[Onbekend]

Mogen bij groepjes van gelijke nummers de zelfde kleuren voorkomen? Oftewel: is dat ook versimpeld of moeten we daar wel rekening mee houden?

[compufreak88]

Onbekend schreef op woensdag 11 november 2009 @ 07:59:
Mogen bij groepjes van gelijke nummers de zelfde kleuren voorkomen? Oftewel: is dat ook versimpeld of moeten we daar wel rekening mee houden?

Staat in de regels:

Soultaker schreef op donderdag 05 november 2009 @ 18:26:

1. drie of meer stenen met dezelfde waarde maar verschillende kleuren:
   [afbeelding]

[ Voor 102% gewijzigd door compufreak88 op 11-11-2009 09:24 ]

[joostvanpinxten]

Interessante opdracht! Ook leuk verzonnen dat je op deze manier een toernooi via HTTP-requests kan uitvoeren!

Ik zal er eens over nadenken en kijken of ik iets geinigs in PHP kan bedenken, dan kom ik miss ook wel met een opzet. Hoe lang gaat deze opdracht nog duren? Want als het op de 14e af moet zijn, dan haal ik dat waarschijnlijk niet meer.

[Verwijderd]

Soultaker schreef op dinsdag 10 november 2009 @ 18:10:
*schop*

Geen animo?

cool, heb ooit het spel TriOminos gemaakt in een ver verleden ('91-'92 ofzo), wat weer een afgeleide is van rumnikub. 's kijken of we wat tijd kunnen vrijmaken.

[armageddon_2k1]

Klinkt erg interessant Misschien dat ik ook mee ga doen. Leuke manier om Ruby eens te leren, maar moet een kijken of ik de tijd kan vinden. Heb namelijk wel een leuke strategie bedacht.

[Soultaker]

Jaap-Jan schreef op dinsdag 10 november 2009 @ 23:48:
En is er een maximale tijd per zet?

edit:
De officiële regels (de Sabra- versie) spreken van maximaal 2 minuten per zet. Is het een idee om dat aan te houden?

Ik zou een veel lagere limiet aanhouden. Voorstel: 5 seconden.

Één potje duurt immers al gauw rond de 100 beurten (het maximum is 147 als ik het goed berekend heb) en met 5 seconden per beurt zit je dan rond de 8 minuten voor een spelletje (terwijl je met 2 minuten ruim drie uur bezig bent!) Voor menselijke spelers zou vijf seconden niet te doen zijn, maar met een computerprogramma zou je een heel eind moeten kunnen komen.

Onbekend schreef op woensdag 11 november 2009 @ 07:59:
Mogen bij groepjes van gelijke nummers de zelfde kleuren voorkomen? Oftewel: is dat ook versimpeld of moeten we daar wel rekening mee houden?

Nee, dat is niet versimpeld, en dat mag dus niet. (Vandaar dat een groepje stenen met dezelfde waarde uit maximaal vier stenen kan bestaan, in plaats van acht.)

joostvanpinxten schreef op woensdag 11 november 2009 @ 09:34:
Hoe lang gaat deze opdracht nog duren? Want als het op de 14e af moet zijn, dan haal ik dat waarschijnlijk niet meer.

Mijn plan was om aanstaande zondag (15 november) een testcompetitie te doen, en dan een week erna (21 november) een officiële competitie te houden. Gezien de recente belangstelling is het misschien beter de officiële competitie een week later te houden, maar wat mij betreft is dat het maximum om GoTPC-achtige toestanden te voorkomen waarbij één opdracht een jaar in beslag neemt.

Vereiste voor de officiële competitie is wel dat alle spelers tegelijk online zijn. (Zoals gezegd ben ik wel bereid om enkele spelers lokaal draaien voor mensen die 'm niet zelf online kunnen zetten op een vast tijdstip.) Misschien handig om even een poll te maken:

edit:
Resultaat poll: competities op zondagavond (poll), eindcompetitie op zondag 29 november (poll). Ik heb de opdracht aangepast.

[ Voor 25% gewijzigd door Soultaker op 14-11-2009 20:01 ]

[EdwinG]

Volgens mij kan een potje uit maximaal 150 beurten bestaan:

48 'draw' (na de start zitten er nog 48 stenen in de pot)
1x 3 stenen uitleggen (begin)
101x 1 steen bijleggen

Als ik op tijd iets afkrijg, zal ik dat met PHP maken. Dat kan ik dus gewoon op mijn eigen site plaatsen, altijd online dus.

[armageddon_2k1]

Oei, ik ga dat denk ik niet op tijd af krijgen. Helaas pindakaas.

[Bolukan]

EdwinG schreef op woensdag 11 november 2009 @ 20:00:
48 'draw' (na de start zitten er nog 48 stenen in de pot)

Dan ga je uit van 4 spelers... Met 2 spelers zitten er 76 stenen in de pot, die in 38 rondes zijn te trekken. Dan legt iedere speler in 50 rondes zijn stenen weg (1x3 en 49x1).
Ik kom op maximaal 88 rondes, oftewel 176 beurten.

Edit:
Sorry, in opzet staat dat met 4 spelers wordt gespeeld:

Het spel wordt gespeeld met vier spelers, die elk een eigen rekje met stenen hebben (bij de tegenstanders is het aantal bekend).

[ Voor 21% gewijzigd door Bolukan op 12-11-2009 15:08 ]

[Soultaker]

Bedenk ook dat het spel eindigt zodra een speler zijn stenen kwijt is, óf de trekstapel leeg is. Dus je kunt 47x een steen trekken (dan zijn er 103 stenen bij spelers, en 1 nog te trekken), vervolgens kunnen daarvan 100 stenen gespeeld worden totdat iemand zonder stenen zit, dus kun je sowieso maximaal 147 beurten spelen.

Als je er bedenkt dat er geopend moet worden met een drietal wordt dat aantal 145. Om een tweede kleur op tafel te krijgen heb je ook (eenmalig) een drietal of twee tweetallen nodig, denk ik, dus dan wordt het minimum op beide manieren 143. De overige stenen kun je wel één voor één aanleggen.

Ik denk dus dat een spelletje maximaal 143 beurten duurt. In de praktijk red je dat zelden of nooit natuurlijk, maar je kunt wel aardig in de buurt komen (meer dan 100 beurten is geen uitzondering met mijn simpele spelers).

[ Voor 39% gewijzigd door Soultaker op 12-11-2009 16:33 ]

[Woy]

Maar kan het ook niet gebeuren dat een speler niet meer kan, nadat alle stenen uit de pot zijn? Dat hij afhankelijk is van wat een andere speler doet. Dan zou je dus een Draw kunnen doen, terwijl er geen stenen meer in de pot zitten.

[Vaan Banaan]

Leuk idee, ik heb waarschijnlijk te weinig tijd om mee te doen, maar even voor de zekerheid:
Als je aan de beurt bent, mag je ofwel één steen pakken (als er nog over zijn) of één of meer stenen op tafel leggen. Je mag daarbij alle stenen op tafel hergroeperen zoals je wil, zolang er uiteindelijk maar een geldige configuratie op tafel ligt
Dan zou dit dus een geldige zet zijn:

code:

plank          tafel          resultaat
R1, G3, G5     R2, R3, R4     R1, R2, R3
               B4, G4, K4     B4, K4, R4
                              G3, G4, G5

^{Hmm, ik zit hier wat op een A4-tje te krabbelen en krijg al allerlei algoritme ideetjes. Misschien toch maar eens kijken of ik een gaatje kan vinden of met wat minder slaap kan.}

[Soultaker]

@Woy: als de pot leeg is, eindigt het spel. Dus als je aan de beurt bent, kun je áltijd trekken (als je niet kan/wil spelen). Het is dus zaak je stenen kwijt te raken voor dat gebeurt.

@Vaan Banaan: klopt precies! Dat soort ingewikkelde operaties zijn waarin goede spelers zich kunnen onderscheiden.

[gammuts]

Ik kom in de knoei met de de puntkomma in je POSTs/URLs. Ik gebruik Perl en de module CGI. Blijkbaar gebruikt CGI de puntkomma op dezelfde manier als de ampersand: als scheidingsteken.

Nu kan ik ten dele die Perl-module de schuld geven, maar RFC 3986 (http://www.ietf.org/rfc/rfc3986.txt) doet ook een duit in het zakje:

sub-delims = "!" / "$" / "&" / "'" / "(" / ")"
/ "*" / "+" / "," / ";" / "="

...

Aside from dot-segments in hierarchical paths, a path segment is
considered opaque by the generic syntax. URI producing applications
often use the reserved characters allowed in a segment to delimit
scheme-specific or dereference-handler-specific subcomponents. For
example, the semicolon (";") and equals ("=") reserved characters are
often used to delimit parameters and parameter values applicable to
that segment. The comma (",") reserved character is often used for
similar purposes. For example, one URI producer might use a segment
such as "name;v=1.1" to indicate a reference to version 1.1 of
"name", whereas another might use a segment such as "name,1.1" to
indicate the same. Parameter types may be defined by scheme-specific
semantics, but in most cases the syntax of a parameter is specific to
the implementation of the URI's dereferencing algorithm.

Vandaar de vraag: wil je een ander scheidingsteken gebruiken? Zo nee, dan ga ik lekker hacken in CGI.pm

N.B.: ook de optie -oldstyle_urls van module CGI lijkt niet te helpen.

[Soultaker]

Hmz, vervelend. Ik heb daar nog over nagedacht maar de HTTP spec verbiedt die karakters niet specifiek, dus ik ging er vanuit dat 't wel goed zou gaan.

Twee voor de hand liggende opties: protocol veranderen en alleen unreserved characters gebruiken, óf de gereserveerde karakters escapen. (In het eerste geval moet ook de komma vervangen worden.) Escapen is vervelend voor mensen die handmatig de query string willen parsen, dus misschien is het beter de scheidingstekens te veranderen.

Voorstel: stenen scheiden door punten (in plaats van komma's) en groepjes door streepjes (in plaats van puntkomma)? Een configuratie op tafel wordt dan b.v. gecodeerd als: R1.R2.R3-G4.G5.G6-R11.K11.B11

Ziet iemand daar nog problemen mee?

[gammuts]

De hack in CGI.pm valt overigens behoorlijk mee:

sub parse_params {
my($self,$tosplit) = @_;
my(@pairs) = split(/[&;]/,$tosplit);

De puntkomma eruit fietsen en klaar.

De noodzaak voor aanpassing van het scheidingsteken is voor mij nu zwaar gedaald.

[Soultaker]

Dat is fijn, maar toch had je een goed punt. Het is maar een kwestie van tijd voordat iemand anders een soortgelijk probleem constateert. (Ik zie bijvoorbeeld dat je in PHP ook arg_separator.input kunt aanpassen om alternatieve scheidingstekens te gebruiken.)

Ik ga de probleembeschrijving dus toch maar aanpassen. Done.

edit:
Let op! Voor wie al een werkende speler gebouwd had: ik heb de scheidingstekens in de invoer en uitvoer aangepast. Lees de gewijzigde opdrachtomschrijving goed door als je speler niet (meer) lijkt te werken.

[ Voor 32% gewijzigd door Soultaker op 12-11-2009 20:32 ]

[Woy]

Soultaker schreef op donderdag 12 november 2009 @ 17:52:
@Woy: als de pot leeg is, eindigt het spel. Dus als je aan de beurt bent, kun je áltijd trekken (als je niet kan/wil spelen). Het is dus zaak je stenen kwijt te raken voor dat gebeurt.

Ok, maar het kan dus voordelig zijn om een draw te doen als je voor staat, als dat inhoud dat het spel over is

[Soultaker]

In principe klopt dat ja. Ik weet niet of dat een heel slimme strategie is als je ook had kunnen spelen (en daarmee dus stenen kwijt had kunnen raken).

Misschien is het spel laten doorgaan tot alle vier de spelers achter elkaar passen beter, maar dan kan het spel ook weer langer gaan duren. Ik denk dat we even een testcompetitie moeten afwachten om te zien of dat aanpassing behoeft.

[ Voor 9% gewijzigd door Soultaker op 12-11-2009 20:33 ]

[MLM]

leuk idee
ik zal eens een poging wagen mits ik snel iets aan de praat heb

[winkbrace]

Leuk! Ik zie het nu pas, maar hopelijk kan ik vanavond iets moois in elkaar fietsen

edit: Normaalgesproken is het spel natuurlijk pas afgelopen als iedereen gepast heeft.

[ Voor 34% gewijzigd door winkbrace op 13-11-2009 16:09 ]

[Soultaker]

Eigenlijk is dat wel logischer, en niet zo moeilijk te implementeren. Ik heb het aangepast in de opdrachtbeschrijving. (Zou voor spelers weinig uit moeten maken.)

[Onbekend]

Is het mogelijk om in jouw test-spel een knop toe te voegen die het gehele spel automatisch af maakt en dan de eindstand laat zien? Nu moet ik ongeveer 100 keer op die knop drukken.

De status van mijn programma is dat de invoer en mijn uitvoer eindelijk correct zijn. Nu kan ik eindelijk wat intelligentie toevoegen zodat ik ook wat stenen toe kan voegen.

[EdwinG]

Ik neem aan dat een pass automatisch gebeurt in het geval van een 'draw' bij een lege stapel?

Lastig trouwens dat ik nu enkele pagina's terug moet om de opdrachtbeschrijving te kunnen lezen. Misschien een idee om vanaf daar de relevante berichten af te splitsen tot een Rummikubtopic?

[qanar]

Wat ik nog niet gezien heb is hoe je past.

Voor het toernooi moet je dus gewoon een downloadbare php of cgi file geven?

[Verwijderd]

Ik ben ook al met een AI begonnen.
Goed idee om de competitie via HTTP te laten verlopen!

[Soultaker]

EdwinG schreef op vrijdag 13 november 2009 @ 20:19:
Ik neem aan dat een pass automatisch gebeurd in het geval van een 'draw' bij een lege stapel?

Klopt.

Lastig trouwens dat ik nu enkele pagina's terug moet om de opdrachtbeschrijving te kunnen lezen. Misschien een idee om vanaf daar de relevante berichten af te splitsen tot een Rummikubtopic?

Van mij mag 't. Lezen er moderators mee?

qanar schreef op vrijdag 13 november 2009 @ 20:44:
Wat ik nog niet gezien heb is hoe je past.

Zoals EdwinG al zei: gewoon draw teruggeven. Als er niets meer te trekken valt pas je impliciet (en dat is ook de enige situatie waarin je kunt passen).

Voor het toernooi moet je dus gewoon een downloadbare php of cgi file geven?

Het makkelijkst is als je je speler gewoon ergens online kan zetten in de tijdspanne waarin ik het toernooi uitvoer. Voor PHP scripts zou dat eenvoudig moeten kunnen. De broncode zelf hoef ik dan niet te hebben (maar het is waarschijnlijk wel leuk om die ná de competitie te delen, denk ik).

Van deelnemers die eigen hosting hebben hoef ik alleen een URL te ontvangen (per DM b.v.) en of ik GET of POST moet gebruiken. Voor mensen die niet zelf hun speler kunnen draaien (ook niet gewoon thuis b.v.) wil ik wel proberen die speler lokaal te draaien, maar dat moet je dan even met mij overleggen.

[qanar]

Soultaker schreef op vrijdag 13 november 2009 @ 20:56:
Het makkelijkst is als je je speler gewoon ergens online kan zetten in de tijdspanne waarin ik het toernooi uitvoer. Voor PHP scripts zou dat eenvoudig moeten kunnen. De broncode zelf hoef ik dan niet te hebben (maar het is waarschijnlijk wel leuk om die ná de competitie te delen, denk ik).

Van deelnemers die eigen hosting hebben hoef ik alleen een URL te ontvangen (per DM b.v.) en of ik GET of POST moet gebruiken. Voor mensen die niet zelf hun speler kunnen draaien (ook niet gewoon thuis b.v.) wil ik wel proberen die speler lokaal te draaien, maar dat moet je dan even met mij overleggen.

Ok, dus gewoon een link naar de PHP-file.

Voorlopig heb ik een speler die altijd drawt

[winkbrace]

qanar schreef op vrijdag 13 november 2009 @ 21:15:
[...]


Ok, dus gewoon een link naar de PHP-file.

Voorlopig heb ik een speler die altijd drawt

wtf! Ik heb ook al zo'n lamzak gebouwd!

@Soultaker: Wat betreft de test interface. Kun je de kaarten daar naast elkaar weergeven ipv onder elkaar? Zelf vind ik een table met 30 items per row wel mooi

[EdwinG]

Elke keer 'draw' werkt voorlopig beter dan mijn idee. Brute-force blijkt niet haalbaar met deze opdracht
Mijn idee was eerst om met volledige tafel + alle eigen stenen een oplossing te zoeken, en als die er niet was het zoeken te herhalen met 1 van mijn stenen minder hetzelfde te proberen, om zo verder te gaan.
(Eerst alle combinaties met nog 1 steen van mij op mijn plankje aan het eind, daarna de combinaties met 2 stenen e.d.)
Zit een klein nadeel aan: in het slechtste geval namelijk 2ⁿ combinaties om te proberen (voordat een 'draw' wordt gekozen). Bij de startpositie is dat 16383 combinaties. Dat kost nogal wat tijd om door te rekenen. En als je een lijst met alle permutaties in het geheugen wilt hebben, komt een out-of-memory snel dichtbij.

[Jaap-Jan]

Interessant leesvoer hierover: http://www.snl.salk.edu/~hendrik/f97/AI/Rummikub.html.

Hier wordt gesteld dat het maken van de lijst van permutaties in milliseconden gebeurd kan zijn, maar de daadwerkelijke berekening van een zet kost meer veel rekenkracht naarmate er meer dan 25 á 30 stenen op tafel liggen. In de tekst gaat het over het kaartspel, maar het idee is hetzelfde.

[Soultaker]

@EdwinG: het is maar wat je een "klein nadeel" noemt.

BazzPsychoNut schreef op vrijdag 13 november 2009 @ 22:32:
@Soultaker: Wat betreft de test interface. Kun je de kaarten daar naast elkaar weergeven ipv onder elkaar? Zelf vind ik een table met 30 items per row wel mooi

Ze staan al naast elkaar...? (Tenminste, in Firefox, Konqueror en Opera. Over Internet Explorer garandeer ik niets.)

[EdwinG]

Soultaker schreef op vrijdag 13 november 2009 @ 23:52:
@EdwinG: het is maar wat je een "klein nadeel" noemt.

Ik ben dan ook maar op een andere manier gevonden. Momenteel negeer ik de tafel, maar leg wel uit als dat mogelijk is. (betekent niet dat de beste uitleg gekozen wordt)

Soultaker schreef op vrijdag 13 november 2009 @ 23:52:Ze staan al naast elkaar...? (Tenminste, in Firefox, Konqueror en Opera. Over Internet Explorer garandeer ik niets.)

In Seamonkey staat alles onder elkaar, ziet er niet uit om eerlijk te zijn. Ik zal eens kijken of ik de oorzaak kan vinden in de html.

Gevonden: Seamonkey kan niet overweg met

code:

display: inline-block

waardoor alles als block wordt neergezet (en elke div dus op een aparte regel komt te staan)
Als de display voor de tileR, tileK etc. op 'inline' gezet kan worden: graag.

[ Voor 15% gewijzigd door EdwinG op 14-11-2009 00:09 . Reden: probleem met html/seamonkey gevonden ]

[EdwinG]

Voor de testcompetitie: Mijn deelnemer (in ontwikkeling) is te vinden op:

http://typefreak.nl/rummikub/basic.php
Methode: POST

Mag ook door andere deelnemers gebruikt worden als 'sparringspartner'.

[qanar]

_GET of _POST maakt niet veel uit neem ik aan? _GET maakt het mij iets makkelijker om te testen :-)

[CoolGamer]

Ik ga denk ook maar eens een poging wagen.

qanar schreef op zaterdag 14 november 2009 @ 00:36:
_GET of _POST maakt niet veel uit neem ik aan? _GET maakt het mij iets makkelijker om te testen :-)

POST is ook niet moeilijk om te testen hoor:

HTML:

<html>
    <head><title>Test POST</title></head>
    <body>
        <form method="POST" action="http://localhost/">
            yourTiles: <input type="text" value="R12.B12.K13.R3.R2.K4.B9.B8.K11" name="yourTiles"><br>
            table: <input type="text" value="G6.G7.G8.G9-B1.B2.B3-R5.R6.R7-R7.R8.R9.R10-R1.G1.B1-K5.K6.K7-B4.B5.B6.B7" name="table"><br>
            poolTiles: <input type="text" value="47" name="poolTiles"><br>
            opponentsTiles: <input type="text" value="5.13.6" name="opponentsTiles"><br>
            <input type="submit">       
        </form>
    </body>
</html>

[Soultaker]

EdwinG schreef op zaterdag 14 november 2009 @ 00:00:
Gevonden: Seamonkey kan niet overweg met

code:

display: inline-block

waardoor alles als block wordt neergezet (en elke div dus op een aparte regel komt te staan)
Als de display voor de tileR, tileK etc. op 'inline' gezet kan worden: graag.

Argh, ik haat HTML/CSS. Ik kan wel inline gebruiken maar dan kan ik de hoogte/breedte niet fixen. Weet iemand hoe dat wel moet?

En gaat deze layout ook stuk?

[Memorice]

EdwinG schreef op vrijdag 13 november 2009 @ 23:10:
Elke keer 'draw' werkt voorlopig beter dan mijn idee. Brute-force blijkt niet haalbaar met deze opdracht
Mijn idee was eerst om met volledige tafel + alle eigen stenen een oplossing te zoeken, en als die er niet was het zoeken te herhalen met 1 van mijn stenen minder hetzelfde te proberen, om zo verder te gaan.
(Eerst alle combinaties met nog 1 steen van mij op mijn plankje aan het eind, daarna de combinaties met 2 stenen e.d.)
Zit een klein nadeel aan: in het slechtste geval namelijk 2ⁿ combinaties om te proberen (voordat een 'draw' wordt gekozen). Bij de startpositie is dat 16383 combinaties. Dat kost nogal wat tijd om door te rekenen. En als je een lijst met alle permutaties in het geheugen wilt hebben, komt een out-of-memory snel dichtbij.

Volgens mij is je constatering niet correct, ik heb het idee dat dit vrij snel door gerekend kan worden. In ieder geval is het vrij eenvoudig om van een hoop stenen te bepalen of je er een correcte tafel van kunt maken. Dit kan volgens mij ruim binnen de 100 ms.

Om mijn idee te testen, heb ik zelf hiervoor even een stukje code geschreven. Om een voorbeeld te geven heb ik hieronder een random input ter grote van ongeveer 75% van alle stenen:

yourTiles=R1.R1.R2.R2.R3.R4.R4.R5.R5.R6.R7.R7.R8.R9.R10.R11.R12.B1.B2.B3.B4.B5.B5.B6.B7.B8.B8.B9.B9.B10.B10.B11.B11.B12.B12.G1.G1.G2.G2.G3.G3.G4.G4.G5.G6.G7.G7.G8.G9.G10.G11.G11.G12.G12.Z1.Z1.Z2.Z3.Z3.Z4.Z4.Z5.Z5.Z6.Z7.Z8.Z9.Z10.Z11.Z11.Z12

Dit volledig door rekenen kost 15 ms en levert als resultaat:

R4.R5.R6.R7-R2.R3.R4.R5-R7.R8.R9.R10-G3.G4.G5.G6.G7-G2.G3.G4-G7.G8.G9.G10-B3.B4.B5-B8.B9.B10-B5.B6.B7.B8.B9.B10-Z1.Z2.Z3.Z4.Z5-Z3.Z4.Z5.Z6.Z7.Z8.Z9.Z10.Z11-R1.G1.Z1-R2.G2.B2-R11.G11.B11-R12.G12.B12-R1.G1.B1-G11.B11.Z11-G12.B12.Z12

Kortom brute force moet volgens mij zeer goed mogelijk zijn. Wanneer ik mijn algoritme test met random input, heb ik altijd in ongeveer 10-20 ms een antwoord (of een correcte table of dat dit niet mogelijk is).

Merk op dat ik in mijn algoritme geen onderscheid maak tussen yourtiles en table, ik gooi gewoon alle stenen op een hoop. Verder geeft mijn algoritme als output een correcte table of dat een correcte table met alle stenen niet mogelijk is. Er is een erg kleine kans dat ik mee doe met deze contest, dit omdat ik de komende weken erg druk ben (conferenties en dergelijke). Deze code wil ik na afloop uiteraard wel beschikbaar stellen.

---

Om jullie wat inspiratie/denkwerk te geven, mijn code is ongeveer als volgt opgebouwd:

De datastructuur is een int[8], hierin worden alle beschikbare stenen opgeslagen; voor elke kleur zijn er twee integers en van elke integer gebruik ik de laatste 13 bits om aan te geven of een steen beschikbaar is of niet. Bijv. een 1 op het 4e bit van zowel de eerste als tweede int geeft aan dat de blauwe 4 twee maal voorkomt. Met behulp van deze datastructuur kun je zeer efficient bitwise operators toepassen, om bepaalde zaken gedaan te krijgen. De union tussen twee integers van dezelfe kleur geeft bijv. al je unieke stenen van die kleur en de intersection geeft alle dubbele stenen van die kleur.

Het algoritme zelf is vervolgens zeer eenvoudig, ga er eerst vanuit dat je alleen maar rijtjes mag maken van dezelfde kleur (dus bijv. geen R1.G1.B1). Zorg er voor dat je zo weinig mogelijk stenen over houdt bij het maken van deze rijtjes. Met behulp van bit flips is de complexiteit hiervan linear.

Vervolgens komt het exponentiele gedeelte van het algoritme om de hoek kijken. Elke steen die niet in een rijtje van 3 zit kun je op maximaal 3 manieren wegwerken, namelijk in een rijtje met drie andere stenen van dezelfde kleur of in een rijtje met twee andere stenen van dezelfde kleur (hiervoor zijn twee mogelijkheden). In de praktijk blijkt dat met behulp van dynamisch programmeren en depth first search, dit exponentiele gedeelte van het algoritme vrij weinig tijd kost. Je kunt namelijk al vrij snel takken in je zoekboom prunen.

Algemene opmerking: Dit algoritme op zichzelf is geen speler, maar slechts een stuk code dat kan bepalen of je van een hoop stenen een correcte table kunt maken of niet. Het algoritme zou dus onderdeel kunnen zijn van een speler.

[EdwinG]

MEMORICE schreef op zaterdag 14 november 2009 @ 04:44:
Kortom brute force moet volgens mij zeer goed mogelijk zijn. Wanneer ik mijn algoritme test met random input, heb ik altijd in ongeveer 10-20 ms een antwoord (of een correcte table of dat dit niet mogelijk is).

In dit geval weet je na die 10-20 ms of je, met alle stenen uit eigen hand, een geldige tafelcombinatie kan maken. Als dit niet het geval is zal je niets ondernemen. Het aantal keren dat je met een hand direct uit kunt zal vrij klein zijn. (Alhoewel 1x per potje natuurlijk voldoende is)

Voer je deze controle (worst-case) uit voor alle permutaties van je hand, dan zal met de openingshand (2¹⁴ combinaties) al 160 seconden nodig zijn als de 10ms het gemiddelde zou zijn. Als de eerste beurt vervolgens niets oplevert zal de de tweede ruim 5 minuten bezig zijn.

Het idee met de bitwise operatoren is wel een stuk efficienter dan ik zelf in elkaar had gezet, eens kijken of ik daar wat mee kan doen.

Soultaker schreef op zaterdag 14 november 2009 @ 02:42:
Argh, ik haat HTML/CSS. Ik kan wel inline gebruiken maar dan kan ik de hoogte/breedte niet fixen. Weet iemand hoe dat wel moet?

En gaat deze layout ook stuk?

hoogte/breedte? Daar zijn toch de width en height attributen voor?

De testpagina geeft bij mij hetzelfde resultaat als de originele pagina.

(overigens kan ik ook firefox gebruiken, echt een probleem is er dus niet)

[Soultaker]

EdwinG schreef op zaterdag 14 november 2009 @ 11:41:
hoogte/breedte? Daar zijn toch de width en height attributen voor?

Ja, maar die werken alleen op block elementen. (Vandaar de inline-block.)

De testpagina geeft bij mij hetzelfde resultaat als de originele pagina. (overigens kan ik ook firefox gebruiken, echt een probleem is er dus niet)

Ik zou zeggen: gebruik voor deze contest dan maar Firefox of Opera, dat scheelt me een hoop werk.
(edit: Zelfs Konqueror en Chromium doen 't goed!)

Overigens genereer ik die volledige reports met XQuery vanuit XML dus als iemand een mooiere lay-out weet te produceren met XSLT/CSS hou ik me aanbevolen.

@MEMORICE: Ik heb zo mijn eigen ideeën voor een algoritme, maar die houd ik nog lekker geheim tot na de contest. Let trouwens op: zwarte stenen worden gecodeerd met K niet met Z!

[ Voor 13% gewijzigd door Soultaker op 15-11-2009 01:30 ]

[Memorice]

EdwinG schreef op zaterdag 14 november 2009 @ 11:41:
[...]
In dit geval weet je na die 10-20 ms of je, met alle stenen uit eigen hand, een geldige tafelcombinatie kan maken. Als dit niet het geval is zal je niets ondernemen. Het aantal keren dat je met een hand direct uit kunt zal vrij klein zijn. (Alhoewel 1x per potje natuurlijk voldoende is)

Voer je deze controle (worst-case) uit voor alle permutaties van je hand, dan zal met de openingshand (2¹⁴ combinaties) al 160 seconden nodig zijn als de 10ms het gemiddelde zou zijn. Als de eerste beurt vervolgens niets oplevert zal de de tweede ruim 5 minuten bezig zijn.

Het idee met de bitwise operatoren is wel een stuk efficienter dan ik zelf in elkaar had gezet, eens kijken of ik daar wat mee kan doen.

Nee, je kunt alle stenen van je eigen hand en de stenen van de tafel gewoon op een hoop gooien. Dus je probeert niet een geldige tafel combinatie met alleen de stenen van je hand te maken, maar in combinatie met de stenen die al op tafel liggen. Om dit vervolgens brute force door te rekenen kost echt max 10-20 ms. Bedenk dat je met 75% van alle stenen al wel in de buurt van het maximum zit (worst case). Immers met meer stenen is het te makkelijk uitleggen en met minder stenen is het minder reken werk...

@Soultaker
Mocht ik meedoen, dan zal ik er aan denken dat zwarte stenen met een K gerepresenteerd worden

[Soultaker]

Als we aan de vier deelnemers komen ga ik morgenavond een eerste testcompetitie runnen (een week daarna nog één, en een week daarna de finale; zie de opdrachtbeschrijving voor overige competitiedata).

Als je mee wil doen, stuur me dan vóór morgenavond een URL van je speler (en of je GET of POST requests verwacht). (Tot nu toe heb ik EdwinG staan, en ik heb zelf gisteren/vandaag een speler in elkaar gehackt.)

[compufreak88]

Ik weet niet of het lukt, maar ik probeer er nog een in elkaar te hacken.

[Onbekend]

Ik heb wel een speler die wel de eenvoudige handelingen doet, maar hij is niet slimmer dan een onervaren persoon.
Hij is beschikbaar op http://tweakers.awardspace.com/RummiDemo.php en maakt gebruik van GET-requests.

De definitieve speler voor de Eindcompetitie krijgt wat meer intelligentie en die zal ik t.z.t. via DM aan Soultaker doorgeven.

[qanar]

Mijn speler via GET. Kan voorlopig enkel stenen wegspelen, nog niet combinaties in eigen stenen zien of heel het speelveld herschikken. Eigenlijk is ie dus nog dommer dan de simpel-spelers.

Ik heb problemen met een goede datastructuur te vinden. Ook snap ik niet helemaal wat jullie bedoelen met bitwise operators. Daar moet ik me misschien eens over gaan inlezen. Leesvoer ergens?

Als andere opdracht dacht ik misschien nog aan dit. De datastructuur van mijn oplossing + link naar alle code staat hier.

[ Voor 21% gewijzigd door qanar op 14-11-2009 22:17 ]

[Verwijderd]

Soultaker schreef op zaterdag 14 november 2009 @ 14:48:
[...]

@MEMORICE: Ik heb zo mijn eigen ideeën voor een algoritme, maar die houd ik nog lekker geheim tot na de contest. Let trouwens op: zwarte stenen worden gecodeerd met K niet met Z!

Heeft dat een nut of is dat alleen maar om ons te pesten?

[Jaap-Jan]

Net zoals CYMK. De K staat voor 'Key'. De rest van de letters zijn hetzelfde in Nederlands en Engels, maar anders zou je de 'B' twee keer gebruiken, voor black en blue.

[Osxy]

Verwijderd schreef op zaterdag 14 november 2009 @ 22:39:
[...]

Heeft dat een nut of is dat alleen maar om ons te pesten?

CMYK?

[Memorice]

qanar schreef op zaterdag 14 november 2009 @ 21:54:
Ik heb problemen met een goede datastructuur te vinden. Ook snap ik niet helemaal wat jullie bedoelen met bitwise operators. Daar moet ik me misschien eens over gaan inlezen. Leesvoer ergens?

Een praktische datastructuur is dus bijv. een int[8], dus 8 integers, waarbij je per kleur 2 int values hebt, dit omdat elke steen twee maal voor kan komen (per kleur). Op integers kun je bitwise operators gebruiken, veel meer kennis dan hieronder heb je hiervoor niet nodig:

De computer rekent met binaire getallen in plaats van het tientallig stelsel. Als je de laatste 13 bits van een int gebruikt om te representeren of je een bepaalde steen hebt of niet. Dan is het 2^i-de bit dus 1 als je de steen hebt en anders 0. Omzetten van invoer naar deze datastructuur kan met de OR operatie, in veel talen gerepresenteerd met een enkele '|' en checken of je een steen hebt kan met een AND, in veel talen gerepresenteerd als een enkele '&'. Zoals ik in een eerdere post al zei kun je dus nog veel meer efficiente dingen doen met deze simpele bitwise operators, namelijk de union (OR) geeft alle unieke stenen en de intersection (AND) geeft al je dubbele stenen. Googlen naar bitwise operators moet je volgens mij voldoende informatie kunnen leveren...

Deze datastructuur is erg praktisch omdat alle operaties zeer efficient (zowel qua hoeveelheid code als qua rekenwerk voor de computer) kunnen gebeuren (bitwise operators) en tevens het geheugen gebruik klein is. Een ander groot voordeel is dat je bijv. heel goedkoop een state kunt kopieren en dus efficient recursie (met behulp van dynamisch programmeren) kunt toepassen.

[Onbekend]

Zelf gebruik ik in php de >> en de << operators bijna nooit.
Ik gebruik die dingen alleen maar als ik echte binaire of hexadecimale getallen binnen krijg, maar dan gebruik ik ook de andere wiskundige berekeningen zoals MOD.

@qanar:
Zie http://php.net/manual/en/language.operators.bitwise.php voor de bitwise operatoren.
Over het algemeen gebruik je alleen de bovenste twee.

[Soultaker]

MEMORICE schreef op zaterdag 14 november 2009 @ 23:02:
Een ander groot voordeel is dat je bijv. heel goedkoop een state kunt kopieren en dus efficient recursie (met behulp van dynamisch programmeren) kunt toepassen.

Grappig, dat klinkt naar mijn speler. Die is geschreven in C en ik gebruik momenteel voor alles een int (in PHP heb je daar weing keuze in) ook al tellen de meeste variabelen maar tot 2 of 3 en zou ik dus aan vier bits genoeg hebben. Het is i.m.o. niet heel erg de moeite waard om daar op te besparen totdat tijd echt een bottleneck wordt óf je een paar miljoen kopiën op moet slaan.

Overigens geef ik je in principe wel gelijk: compacte datastructuren kun je sneller kopieren, maar als je daarmee de complexiteit van je programma vergroot terwijl er belangrijkere dingen zijn om aan te werken, ben je i.m.o. verkeerd bezig.

[Soultaker]

Verwijderd schreef op zaterdag 14 november 2009 @ 22:39:
Heeft dat een nut of is dat alleen maar om ons te pesten?

De hele interface is Engelstalig en daar is K voor zwart gebruikelijk (als in CMYK). Zelf dacht ik altijd vanwege black maar dat blijkt dus niet juist te zijn. Het is vrij arbitrair welke letters je gebruikt natuurlijk; ik neem aan dat iedereen ze gewoon naar een getal 0..3 (of 1..4) parset dus dan maakt 't weinig uit, zolang maar duidelijk is welke letters er gebruikt worden (welke letters met welke kleuren corresponderen maakt niet eens uit, als je 't maar consequent doorvoert).

[Verwijderd]

Toch maar een poging gedaan, mijne is te vinden op:
http://www.guidohendriks.nl/got/rummikub/

Werkt met zowel GET als POST.

Hij is nog wel dom, speelt alles wat hij kan en schuift nog niet met wat op tafel ligt, dus het is nog niks eigenlijk. Maar ik ga hem nog verder updaten op dezelfde url.

[ Voor 192% gewijzigd door Verwijderd op 15-11-2009 10:59 ]

[Onbekend]

Ik heb mijn speler iets aangepast zodat er wat meer stenen gespeeld kunnen worden.
Helaas blijf ik regelmatig met 1 of 2 stenen zitten waar mijn geprogrammeerde algoritme niets mee kan.

De spelers van EdwinG en qanar sparen soms veel stenen op terwijl er combinaties genoeg zijn. Hierdoor kunnen de andere spelers weinig anders dan pakken en is de pakstapel snel leeg.

Ik ben benieuwd naar de resultaten vanavond.

[EdwinG]

Onbekend schreef op zondag 15 november 2009 @ 17:49:
De spelers van EdwinG en qanar sparen soms veel stenen op terwijl er combinaties genoeg zijn. Hierdoor kunnen de andere spelers weinig anders dan pakken en is de pakstapel snel leeg.

Mijn speler kan inderdaad nog lang niet met alle situaties overweg. De belangrijkste is het vinden van 'beschikbare' stenen. Oftewel, als ergens 4 dezelfde cijfers liggen als groep zal mijn (huidige) speler niet proberen om hier een steen uit te pakken om een nieuwe combinatie te maken. Daar werk ik nog aan. (al denk ik niet dat dit vandaag nog gaat lukken)

Overigens, de laatste tests resulteerden bij mij wel regelmatig in een spel waar een duidelijke winnaar (leeg bord) was, ondanks 4x mijn eigen speler.

[qanar]

Yes, ik heb ook gezien dat mijn speler niet altijd een steen wegspeeld, terwijl hij het wel zou kunnen... Maar ik ben dankzij de hints hierboven aan een nieuwe versie bezig, dus eigenlijk is de vorige speler die ik gelinkt heb overbodig geworden.

[Soultaker]

Uitslagen testcompetitie 1

Aangezien we maar met vijf spelers zijn, heb ik een competitie met alle 120 mogelijke permutaties van spelers gerund. Hieronder volgen de resultaten (let op: lage scores zijn beter!) Spelers die met rood zijn aangegeven hebben minsten één zet gefaald in dat potje. Alleen EdwinG en qanar slaagden erin om de competitie foutloos te doorstaan; de anderen hebben nog wat werk te doen.

Ronde	Speler 1	(score)	Speler 2	(score)	Speler 3	(score)	Speler 4	(score)	Details
1	EdwinG	54	GuidoH	43	Onbekend	0	Soultaker	24	html, xml
2	EdwinG	3	GuidoH	4	Onbekend	0	qanar	18	html, xml
3	EdwinG	23	GuidoH	49	Soultaker	0	Onbekend	43	html, xml
4	EdwinG	67	GuidoH	32	Soultaker	0	qanar	120	html, xml
5	EdwinG	27	GuidoH	36	qanar	30	Onbekend	78	html, xml
6	EdwinG	33	GuidoH	0	qanar	56	Soultaker	11	html, xml
7	EdwinG	28	Onbekend	41	GuidoH	40	Soultaker	0	html, xml
8	EdwinG	29	Onbekend	61	GuidoH	42	qanar	40	html, xml
9	EdwinG	3	Onbekend	22	Soultaker	0	GuidoH	15	html, xml
10	EdwinG	39	Onbekend	81	Soultaker	0	qanar	98	html, xml
11	EdwinG	60	Onbekend	12	qanar	84	GuidoH	16	html, xml
12	EdwinG	20	Onbekend	27	qanar	43	Soultaker	2	html, xml
13	EdwinG	22	Soultaker	0	GuidoH	27	Onbekend	26	html, xml
14	EdwinG	37	Soultaker	0	GuidoH	35	qanar	54	html, xml
15	EdwinG	13	Soultaker	0	Onbekend	28	GuidoH	16	html, xml
16	EdwinG	23	Soultaker	0	Onbekend	7	qanar	50	html, xml
17	EdwinG	54	Soultaker	0	qanar	77	GuidoH	18	html, xml
18	EdwinG	67	Soultaker	0	qanar	78	Onbekend	60	html, xml
19	EdwinG	11	qanar	17	GuidoH	0	Onbekend	14	html, xml
20	EdwinG	56	qanar	120	GuidoH	73	Soultaker	0	html, xml
21	EdwinG	25	qanar	8	Onbekend	0	GuidoH	12	html, xml
22	EdwinG	33	qanar	47	Onbekend	14	Soultaker	0	html, xml
23	EdwinG	82	qanar	55	Soultaker	0	GuidoH	36	html, xml
24	EdwinG	40	qanar	46	Soultaker	0	Onbekend	20	html, xml
25	GuidoH	54	EdwinG	80	Onbekend	29	Soultaker	0	html, xml
26	GuidoH	45	EdwinG	61	Onbekend	45	qanar	74	html, xml
27	GuidoH	25	EdwinG	46	Soultaker	0	Onbekend	38	html, xml
28	GuidoH	11	EdwinG	7	Soultaker	0	qanar	38	html, xml
29	GuidoH	56	EdwinG	67	qanar	64	Onbekend	0	html, xml
30	GuidoH	27	EdwinG	63	qanar	72	Soultaker	0	html, xml
31	GuidoH	65	Onbekend	27	EdwinG	59	Soultaker	0	html, xml
32	GuidoH	68	Onbekend	32	EdwinG	32	qanar	39	html, xml
33	GuidoH	53	Onbekend	28	Soultaker	0	EdwinG	49	html, xml
34	GuidoH	38	Onbekend	37	Soultaker	0	qanar	91	html, xml
35	GuidoH	26	Onbekend	54	qanar	71	EdwinG	34	html, xml
36	GuidoH	31	Onbekend	71	qanar	99	Soultaker	0	html, xml
37	GuidoH	0	Soultaker	9	EdwinG	3	Onbekend	4	html, xml
38	GuidoH	56	Soultaker	0	EdwinG	86	qanar	55	html, xml
39	GuidoH	23	Soultaker	0	Onbekend	107	EdwinG	61	html, xml
40	GuidoH	53	Soultaker	0	Onbekend	78	qanar	59	html, xml
41	GuidoH	47	Soultaker	0	qanar	55	EdwinG	65	html, xml
42	GuidoH	16	Soultaker	0	qanar	18	Onbekend	23	html, xml
43	GuidoH	59	qanar	84	EdwinG	7	Onbekend	88	html, xml
44	GuidoH	24	qanar	66	EdwinG	29	Soultaker	0	html, xml
45	GuidoH	0	qanar	89	Onbekend	29	EdwinG	49	html, xml
46	GuidoH	58	qanar	69	Onbekend	32	Soultaker	0	html, xml
47	GuidoH	13	qanar	64	Soultaker	0	EdwinG	20	html, xml
48	GuidoH	17	qanar	28	Soultaker	0	Onbekend	25	html, xml
49	Onbekend	48	EdwinG	24	GuidoH	67	Soultaker	0	html, xml
50	Onbekend	2	EdwinG	0	GuidoH	31	qanar	13	html, xml
51	Onbekend	36	EdwinG	77	Soultaker	0	GuidoH	53	html, xml
52	Onbekend	5	EdwinG	8	Soultaker	0	qanar	6	html, xml
53	Onbekend	60	EdwinG	51	qanar	110	GuidoH	54	html, xml
54	Onbekend	57	EdwinG	35	qanar	45	Soultaker	0	html, xml
55	Onbekend	36	GuidoH	59	EdwinG	65	Soultaker	0	html, xml
56	Onbekend	0	GuidoH	71	EdwinG	14	qanar	30	html, xml
57	Onbekend	29	GuidoH	41	Soultaker	0	EdwinG	29	html, xml
58	Onbekend	17	GuidoH	67	Soultaker	0	qanar	33	html, xml
59	Onbekend	2	GuidoH	0	qanar	13	EdwinG	1	html, xml
60	Onbekend	26	GuidoH	25	qanar	57	Soultaker	0	html, xml
61	Onbekend	30	Soultaker	0	EdwinG	14	GuidoH	11	html, xml
62	Onbekend	37	Soultaker	0	EdwinG	27	qanar	47	html, xml
63	Onbekend	44	Soultaker	1	GuidoH	0	EdwinG	15	html, xml
64	Onbekend	16	Soultaker	0	GuidoH	67	qanar	90	html, xml
65	Onbekend	4	Soultaker	0	qanar	24	EdwinG	21	html, xml
66	Onbekend	53	Soultaker	53	qanar	78	GuidoH	79	html, xml
67	Onbekend	0	qanar	39	EdwinG	38	GuidoH	13	html, xml
68	Onbekend	51	qanar	92	EdwinG	29	Soultaker	0	html, xml
69	Onbekend	38	qanar	94	GuidoH	22	EdwinG	54	html, xml
70	Onbekend	20	qanar	98	GuidoH	15	Soultaker	0	html, xml
71	Onbekend	13	qanar	68	Soultaker	0	EdwinG	22	html, xml
72	Onbekend	53	qanar	54	Soultaker	0	GuidoH	41	html, xml
73	Soultaker	0	EdwinG	22	GuidoH	32	Onbekend	7	html, xml
74	Soultaker	0	EdwinG	61	GuidoH	35	qanar	85	html, xml
75	Soultaker	0	EdwinG	9	Onbekend	16	GuidoH	39	html, xml
76	Soultaker	0	EdwinG	68	Onbekend	61	qanar	51	html, xml
77	Soultaker	0	EdwinG	53	qanar	56	GuidoH	38	html, xml
78	Soultaker	0	EdwinG	51	qanar	63	Onbekend	23	html, xml
79	Soultaker	0	GuidoH	20	EdwinG	9	Onbekend	23	html, xml
80	Soultaker	0	GuidoH	23	EdwinG	20	qanar	39	html, xml

[Soultaker]

Ronde	Speler 1	(score)	Speler 2	(score)	Speler 3	(score)	Speler 4	(score)	Details
81	Soultaker	0	GuidoH	40	Onbekend	29	EdwinG	16	html, xml
82	Soultaker	0	GuidoH	16	Onbekend	52	qanar	51	html, xml
83	Soultaker	0	GuidoH	24	qanar	87	EdwinG	17	html, xml
84	Soultaker	0	GuidoH	27	qanar	47	Onbekend	11	html, xml
85	Soultaker	0	Onbekend	20	EdwinG	23	GuidoH	67	html, xml
86	Soultaker	0	Onbekend	28	EdwinG	14	qanar	45	html, xml
87	Soultaker	0	Onbekend	55	GuidoH	65	EdwinG	35	html, xml
88	Soultaker	0	Onbekend	16	GuidoH	63	qanar	52	html, xml
89	Soultaker	0	Onbekend	70	qanar	113	EdwinG	63	html, xml
90	Soultaker	0	Onbekend	54	qanar	52	GuidoH	74	html, xml
91	Soultaker	0	qanar	47	EdwinG	4	GuidoH	28	html, xml
92	Soultaker	0	qanar	3	EdwinG	4	Onbekend	6	html, xml
93	Soultaker	0	qanar	44	GuidoH	41	EdwinG	55	html, xml
94	Soultaker	12	qanar	48	GuidoH	16	Onbekend	0	html, xml
95	Soultaker	0	qanar	85	Onbekend	116	EdwinG	59	html, xml
96	Soultaker	0	qanar	84	Onbekend	65	GuidoH	57	html, xml
97	qanar	42	EdwinG	22	GuidoH	0	Onbekend	10	html, xml
98	qanar	62	EdwinG	56	GuidoH	48	Soultaker	0	html, xml
99	qanar	146	EdwinG	76	Onbekend	48	GuidoH	72	html, xml
100	qanar	77	EdwinG	76	Onbekend	79	Soultaker	0	html, xml
101	qanar	27	EdwinG	14	Soultaker	0	GuidoH	14	html, xml
102	qanar	54	EdwinG	26	Soultaker	0	Onbekend	32	html, xml
103	qanar	27	GuidoH	0	EdwinG	23	Onbekend	20	html, xml
104	qanar	71	GuidoH	36	EdwinG	45	Soultaker	0	html, xml
105	qanar	54	GuidoH	23	Onbekend	39	EdwinG	57	html, xml
106	qanar	19	GuidoH	6	Onbekend	16	Soultaker	0	html, xml
107	qanar	65	GuidoH	43	Soultaker	0	EdwinG	85	html, xml
108	qanar	46	GuidoH	41	Soultaker	0	Onbekend	13	html, xml
109	qanar	95	Onbekend	35	EdwinG	17	GuidoH	49	html, xml
110	qanar	74	Onbekend	45	EdwinG	24	Soultaker	0	html, xml
111	qanar	50	Onbekend	64	GuidoH	42	EdwinG	48	html, xml
112	qanar	79	Onbekend	29	GuidoH	31	Soultaker	0	html, xml
113	qanar	135	Onbekend	74	Soultaker	0	EdwinG	64	html, xml
114	qanar	5	Onbekend	14	Soultaker	0	GuidoH	9	html, xml
115	qanar	97	Soultaker	0	EdwinG	73	GuidoH	35	html, xml
116	qanar	92	Soultaker	0	EdwinG	50	Onbekend	25	html, xml
117	qanar	97	Soultaker	0	GuidoH	30	EdwinG	53	html, xml
118	qanar	64	Soultaker	0	GuidoH	20	Onbekend	28	html, xml
119	qanar	84	Soultaker	0	Onbekend	24	EdwinG	20	html, xml
120	qanar	32	Soultaker	0	Onbekend	23	GuidoH	50	html, xml

Alle resultaten (html&xml): comp1.zip (625KB)

Eindklassement

Plaats	Deelnemer	Totaalscore	Aantal gewonnen	Aantal fouten	Tijd
					Totaal	Gemiddeld	Maximaal
1	Soultaker	112	89	15	271.546s	0.164s	0.529s
2	Onbekend	3228	7	1	646.659s	0.369s	8.795s
3	GuidoH	3329	8	29	27.177s	0.016s	1.096s
4	EdwinG	3603	1	0	64.334s	0.037s	1.258s
5	qanar	5813	0	0	381.749s	0.208s	2.379s

[ Voor 6% gewijzigd door Soultaker op 23-11-2009 15:49 ]

[qanar]

Soultaker schreef op zondag 15 november 2009 @ 19:50:
Alleen EdwinG en qanar slaagden erin om de competitie foutloos te doorstaan; de anderen hebben nog wat werk te doen.

Leuk, maar ik verlies wel :-)

[Onbekend]

120 spellen in een uur. Dat heb je vlot gedaan.
1807 keer heeft mijn speler een request gehad, waarvan er 1x een ongeldige uitvoer is gekomen. Dat vind ik wel een net eindresultaat.

Nu die ene fout uitzoeken, en een paar uurtjes vrijmaken om het algoritme uit te breiden.

Edit: Je hebt die spellen tegelijkertijd laten draaien. Nu staat alles door elkaar in m'n logfile.

[ Voor 15% gewijzigd door Onbekend op 15-11-2009 20:11 ]

[Soultaker]

Hehe ja, parallellisatie FTW! (Dankzij spelers die lekker doorzetten was 't binnen 20 minuten gepiept.) Wist ik veel dat je aan 't loggen was.

[qanar]

Na een hele dag prullen met een andere datastructuur en na met mijn oude code (die in de wedstrijd gebruikt werd) ook een error tegen gekomen te zijn trek ik mij terug.

spoiler:

code staat http://www.qanar.be/programs/rummikub.txt & http://www.qanar.be/programs/rummikub2.txt. Eerste is een bruteforce manier, tweede is leren werken met bitwise operators.

[EdwinG]

Wel opvallend dat de 'foutloze' spelers de slechtste score hadden uiteindelijk. Mooie score ook van Soultaker. (Die zal waarschijnlijk oplopen als de verschillen tussen de spelers minder worden.)

Ook ik heb een log bijgehouden. Fouten zal ik er niet mee kunnen opsporen (welke fouten), maar misschien haal ik er wel informatie uit voor betere functies.

[Onbekend]

Soultaker schreef op zondag 15 november 2009 @ 20:24:
Hehe ja, parallellisatie FTW! (Dankzij spelers die lekker doorzetten was 't binnen 20 minuten gepiept.) Wist ik veel dat je aan 't loggen was.

Het was eenvoudig te filteren hoor. Bij elk spel heb ik namelijk weer andere stenen op het bordje.

Ik kom alleen niet uit waarom mijn programma één keer een foute uitvoer heeft geleverd:
http://hell.student.utwen...nscripts/comp1/m0060.html
Dit komt uit mijn logfile:

code:

Input: yourTiles=R3.B3.K9.B5.B9.B10.K8.B9&table=R13.G13.B13-R13.G13.B13.K13-R12.G12.B12-K11.K12.K13-R11.G11.B11.K11-R10.G10.K10-R9.G9.K9-R8.G8.K8-R7.G7.B7.K7-R6.B6.K6-R5.R6.R7.R8-R4.B4.K4-K2.K3.K4.K5.K6-R2.G2.K2-R1.R2.R3&poolTiles=29&opponentsTiles=3.12.1
Output: K8.K9.K10.K11.K12.K13-R5.R6.R7.R8-K2.K3.K4.K5.K6.K7.K8.K9-R1.R2.R3-R13.G13.B13-R13.G13.B13.K13-R12.G12.B12-R11.G11.B11.K11-B10.G10.R10-B9.G9.R9-R8.G8.K8-B7.G7.R7-R6.B6.K6-R4.B4.K4-R2.G2.K2

Ik kan er zelf geen fout in vinden. Zou je misschien nog een keer willen kijken of mijn uitvoer een fout geeft? Als dat niet het geval is, vermoed ik dat mijn hosting wat langzamer dan 5 seconden reageerde en de uitvoer nog niet compleet op het scherm stond.

[Soultaker]

Onbekend schreef op zondag 15 november 2009 @ 21:45:
Dit komt uit mijn logfile:

code:

Input: yourTiles=R3.B3.K9.B5.B9.B10.K8.B9&table=R13.G13.B13-R13.G13.B13.K13-R12.G12.B12-K11.K12.K13-R11.G11.B11.K11-R10.G10.K10-R9.G9.K9-R8.G8.K8-R7.G7.B7.K7-R6.B6.K6-R5.R6.R7.R8-R4.B4.K4-K2.K3.K4.K5.K6-R2.G2.K2-R1.R2.R3&poolTiles=29&opponentsTiles=3.12.1
Output: K8.K9.K10.K11.K12.K13-R5.R6.R7.R8-K2.K3.K4.K5.K6.K7.K8.K9-R1.R2.R3-R13.G13.B13-R13.G13.B13.K13-R12.G12.B12-R11.G11.B11.K11-B10.G10.R10-B9.G9.R9-R8.G8.K8-B7.G7.R7-R6.B6.K6-R4.B4.K4-R2.G2.K2

Je gebruikt in je uitvoer drie keer een K8, waar komt die derde vandaan terwijl er maar twee in het hele spel voorkomen? (Overigens, als je de eerste K8 dropt, die je helemaal niet nodig hebt, dan is je zet wel geldig en ben je vier stenen kwijt!)

Wat voor iedereen wel handig is om te weten: alle informatie die ik heb is in de XML files te vinden. In het geval van een fout staat ook de HTTP response body erbij, en met behulp van de laatste tafelconfiguratie en je eigen stenen zou de situatie meestal wel te reproduceren moeten zijn. (Zoek naar <error> en <response> tags.) Meer informatie dan in de XML files zit heb ik zelf ook niet.

Onbekend schreef op zondag 15 november 2009 @ 21:45:
Als dat niet het geval is, vermoed ik dat mijn hosting wat langzamer dan 5 seconden reageerde en de uitvoer nog niet compleet op het scherm stond.

Dan zou je een andere foutmelding gekregen hebben. Er zijn drie typen:

• RPC failed: als de HTTP request faalt, wat legio redenen kan hebben: domein niet gevonden, webserver niet bereikbaar, reageert niet snel genoeg, of de response status is geen 200 (OK). In de praktijk zijn internal server errors of timeouts het waarschijnlijkst.
• Syntax error in request response: uitvoer is syntactisch niet in orde; is dus geen draw en voldoet ook niet aan de beschreven tafelsyntax. Dit kan kan gebeuren als PHP bijvoorbeeld warnings print, of als je script helemaal geen uitvoer produceert.
• Invalid table configuration: als de uitvoer syntactisch geldig is, maar de opgegeven tafel niet gemaakt kan worden omdat er bijvoorbeeld ongeldige groepjes in zitten, je niet alle stenen op tafel gebruikt, je geen stenen toevoegt, of je stenen toevoegt die je niet hebt. Deze fout blijkt in de praktijk het vaakst voor te komen en bij alle gevallen die ik heb gezien ligt de fout dan echt bij de speler.

EdwinG schreef op zondag 15 november 2009 @ 21:39:
Wel opvallend dat de 'foutloze' spelers de slechtste score hadden uiteindelijk. Mooie score ook van Soultaker. (Die zal waarschijnlijk oplopen als de verschillen tussen de spelers minder worden.)

Inderdaad, ik zag dat de foute zetten me niet zo veel kostten, omdat m'n speler een paar zetten later gewoon weer wat anders ging spelen. Maar 't is wel lelijk natuurlijk, dus ik ga het nog wel even debuggen komende week. En ik verwacht ook dat de verschillen nog wel wat kleiner worden; nu was ik vaak net als eerste uit wat in absolute zin heel goed lijkt, maar vaak zaten mijn tegenstanders ook nog maar met twee of drie stenen over...

[ Voor 14% gewijzigd door Soultaker op 15-11-2009 22:49 ]