Programming Contest Nieuwe Stijl: Contest 2 *WINNAARS LEZEN*

[Marcj]

RobIII schreef op donderdag 01 maart 2007 @ 10:30:
[...]

Euh, aan die bestanden mankeert nog het een en ander vrees ik Meer kan/ga ik niet zeggen.

Hmm, jammer. Ik ben nu zelf een validator aan het schrijven zodat ik het ook kan controleren. Op dit moment vertrouw ik blind op mijn programma, maar dat moet ik dus niet doen

Dido schreef op donderdag 01 maart 2007 @ 10:44:
Marcj: tel ik nou raar, of zitten er 4768 letters in invoerset 5, zodat een score van 2151 maar 45% zou zijn

Hmm, vreemd, ik heb hier staan:

code:

Lijst 5 heeft nu 487 woorden met 3178 letters

Of zou de fout nu mijn mijn woordenlijst zitten? Dat zou wel erg zijn, want dat is het makkelijkste stuk

edit: Door een hele domme fout vergat ik de laatste grid steeds zie ik nu . Ik ga nu wel ff druk debuggen en verder uittesten voordat ik met nog meer resultaten ga pronken

[ Voor 44% gewijzigd door Marcj op 01-03-2007 11:00 ]

[NMe]

EdwinG schreef op dinsdag 27 februari 2007 @ 22:12:
[...]

Net als bij de vorige contest, is dit de informatie die (vooraf) over de systemen beschikbaar is:
(Trouwens, vorige contest zijn meerdere ronden gehouden, op verschillende pc's)

Die twee rondes zijn verder wel op dezelfde pc (namelijk die van mij) uitgevoerd. Maar de kans zit erin dat deze contest door een ander crewlid beoordeeld wordt op dat vlak, dus ga niet zomaar uit van dezelfde pc als bij de vorige contest! Het is goed als je programma of script overweg kan met meerdere cores, maar maak daar geen vereiste van voor een goede werking.

T i M schreef op woensdag 28 februari 2007 @ 17:57:
Mag je grid in de breedte relatief (veel) groter zijn dan in de hoogte?

Waarom niet? Als je het aantal letters maar minimaliseert.

Marcj schreef op donderdag 01 maart 2007 @ 08:44:
edit: Dit is nog eigenlijk best wel brute-force (gewoon veel plaatsen uitproberen), nu heb ik wel een redelijk idee in mijn hoofd voor een echt leuk algoritme. Meer dan 100Mb geheugengebruik is toch geen probleem mag ik hopen?

Nee hoor.

[mOrPhie]

* mOrPhie heeft nog een vraagje:

Wat is het beleid met betrekking tot third party libs?
(en daarmee bedoel ik natuurlijk niet de Java.* en System.* namespaces van Java en .NET bijvoorbeeld. )

Marcj schreef op donderdag 01 maart 2007 @ 10:44:
Ik ga nu wel ff druk debuggen en verder uittesten voordat ik met nog meer resultaten ga pronken

Mwah, het pronken heeft je wel doen inzien dat je bugs hebt. Dus ga er vooral mee door.

[ Voor 11% gewijzigd door mOrPhie op 01-03-2007 11:17 ]

[M-ThijZ]

Ik denk dat ik ook maar eens een poging ga wagen om hiervoor wat leuks te bedenken, bij de vorige contest heb ik wel een beginnetje gewaagt, maar daar is uiteindelijk weinig uitgekomen.

Enige probleem is dat ik nog niet weet welke taal ik zal gebruiken. Normaal gezien gebruik ik overal Ruby voor, maar misschien is een hele mooie object georienteerde structuur in dit geval helemaal niet wensenlijk omdat het veel overhead met zich meebrengt.
De contest is een mooie uitdaging voor me, ik vind het best moeilijk uit te denken hoe ik met zo'n grid van letters om moet gaan.

[Marcj]

mOrPhie schreef op donderdag 01 maart 2007 @ 11:16:
* mOrPhie heeft nog een vraagje:

Wat is het beleid met betrekking tot third party libs?
(en daarmee bedoel ik natuurlijk niet de Java.* en System.* namespaces van Java en .NET bijvoorbeeld. )

Het lijkt me toch dat zolang deze gratis zijn en worden meegeleverd dat dit geen probleem mag zijn. Ik heb vorige keer ook JCmdLine gebruikt (voor parsen van command line opties).

[...]
Mwah, het pronken heeft je wel doen inzien dat je bugs hebt. Dus ga er vooral mee door.

Ja, bugs heb ik genoeg. Ik ben net m'n validator aan het testen en het lijkt er inderdaad op dat ik wat woorden mis. Geen idee hoe trouwens... Maar daarvoor gaan we debuggen

edit: De echte bug is nu getraceerd. Dit zat er in dat als woord X bevat werd in woord Y dat ik dan woord Y weggooide ipv X Gelukkig werkt het nu goed en heb ik ook een werkende validator. Hierdoor is uiteraard de score wel iets omhoog gegaan, maar gelukkig niet zoveel...

code:

Grid: 1
Score: 2208
Percentage van max: 68

Grid: 2
Score: 2510
Percentage van max: 66

Grid: 3
Score: 2477
Percentage van max: 67

Grid: 4
Score: 1852
Percentage van max: 67

Grid: 5
Score: 2181
Percentage van max: 68

Grid: 6
Score: 3189
Percentage van max: 66

Totale score: 14417
Totale percentage van max: 67
Tijd om uit te rekeken: 2125ms

[ Voor 28% gewijzigd door Marcj op 01-03-2007 12:19 ]

[NMe]

mOrPhie schreef op donderdag 01 maart 2007 @ 11:16:
* mOrPhie heeft nog een vraagje:

Wat is het beleid met betrekking tot third party libs?
(en daarmee bedoel ik natuurlijk niet de Java.* en System.* namespaces van Java en .NET bijvoorbeeld. )

Zolang het maar geen library is die je de hele opdracht uit handen neemt (MakePerfectGrid() ) is alles best. Vertel wel in je bijgeleverde readme of in de mail die je stuurt wat de dependancies zijn, en waar die libraries vandaan te halen zijn als het geen standaard libs zijn.

[mOrPhie]

-NMe- schreef op donderdag 01 maart 2007 @ 11:45:
[...]

Zolang het maar geen library is die je de hele opdracht uit handen neemt (MakePerfectGrid() )

Wat denk je nou?

is alles best. Vertel wel in je bijgeleverde readme of in de mail die je stuurt wat de dependancies zijn, en waar die libraries vandaan te halen zijn als het geen standaard libs zijn.

Ik weet nog niet eens of ik het ga gebruiken hoor, maar degene die ik op het oog heb is redistributable, dus daar hoeven jullie niets voor te doen. Bedankt voor de opheldering.

[Varienaja]

Marcj schreef op donderdag 01 maart 2007 @ 11:29:

code:

Grid: 1
Score: 2208
Percentage van max: 68

Ha competitie!

Vandaag op 't werk niets kunnen knutselen, maar de hele terugweg in de trein heb ik nagedacht en op m'n laptopje lopen tikken. Ik heb nu een vreselijke polynomiale (waanzinnig traag dus) oplossing gebrouwen die onder jouw grid 1 duikt.

Vanmorgen schrok ik even, toen ik zag dat je flink onder mijn oplossing dook, maar nu zit ik voor grid 1 op 2046. Ik zal meteen de andere gridjes ook even laten doorrekenen.


Nou, het is een half uur later en de eerste set is doorgerekend :

code:

Grid 1 : 2046/3231 ~ 63%
Grid 2 : 2330/3779 ~ 61%
Grid 3 : 2275/3661 ~ 62%
Grid 4 : 1738/2771 ~ 63%
Grid 5 : 1994/3178 ~ 63%
Grid 6 : 2903/4768 ~ 61%

Ik ben benieuwd hoe lang het duurt voordat ik links en rechts weer ingehaald ben.

[ Voor 20% gewijzigd door Varienaja op 01-03-2007 22:25 ]

[Arjan]

mijn bedroevende score er ook maar bij plaatsen dan, ik weet overigens waarschijnlijk wel waarom de huidige score zo laag is, dus ik hoop binnenkort mooiere resultaten te plaatsen

code:

Reading words.txt took 16ms.

Grid(1/6) {
        characters used:        2574
        characters stripped:    20 (47ms)
        words sorted in:        16ms
        solved in:              3250ms
}
Grid(2/6) {
        characters used:        2967
        characters stripped:    35 (62ms)
        words sorted in:        16ms
        solved in:              4453ms
}
Grid(3/6) {
        characters used:        2870
        characters stripped:    24 (47ms)
        words sorted in:        31ms
        solved in:              4141ms
}
Grid(4/6) {
        characters used:        2173
        characters stripped:    17 (31ms)
        words sorted in:        15ms
        solved in:              2532ms
}
Grid(5/6) {
        characters used:        2514
        characters stripped:    20 (47ms)
        words sorted in:        15ms
        solved in:              3172ms
}
Grid(6/6) {
        characters used:        3759
        characters stripped:    30 (93ms)
        words sorted in:        32ms
        solved in:              7078ms
}
Total characters used: 16857
Which is 78% of the initial characters.

Program done in 25110ms.

[Varienaja]

Atgast schreef op donderdag 01 maart 2007 @ 22:33:
mijn bedroevende score er ook maar bij plaatsen dan, ik weet overigens waarschijnlijk wel waarom de huidige score zo laag is, dus ik hoop binnenkort mooiere resultaten te plaatsen

Ha, dat klinkt goed.

Maar ik zit zelf intussen met een groot tijdsprobleem. Een half uur voor 6 lijstjes van elk ongeveer 350 woorden is veel teveel. Mocht de invoer in de uiteindelijke contest echt 99 lijstjes van 999 woorden bevatten, dan is mijn algoritme nooit binnen het uur klaar..

Ik hoop binnenkort ook mooiere resultaten te plaatsen, vooral wat betreft rekentijd dan.

[Arjan]

mijn nieuwe results:

code:

Reading words.txt took 16ms.

Grid(1/6) {
        characters used:        2259
        words stripped: 20 (47ms)
        words sorted in:        16ms
        solved in:              15625ms
}
Grid(2/6) {
        characters used:        2573
        words stripped: 35 (63ms)
        words sorted in:        15ms
        solved in:              21063ms
}
Grid(3/6) {
        characters used:        2545
        words stripped: 24 (47ms)
        words sorted in:        32ms
        solved in:              18906ms
}
Grid(4/6) {
        characters used:        1955
        words stripped: 17 (31ms)
        words sorted in:        16ms
        solved in:              12562ms
}
Grid(5/6) {
        characters used:        2216
        words stripped: 20 (47ms)
        words sorted in:        16ms
        solved in:              18218ms
}
Grid(6/6) {
        characters used:        3229
        words stripped: 30 (94ms)
        words sorted in:        47ms
        solved in:              33969ms
}
Total characters used: 14777
Which is 69% of the initial characters.

Program done in 120860ms.

(qua tijd is dit overigens de debug mode, met compiler optimalisaties doet ie ditzelfde in 72s)

[ Voor 4% gewijzigd door Arjan op 01-03-2007 23:50 ]

[Nick The Heazk]

Mijn programmaatje produceert nog niet veel output . Momenteel is de preprocessing fase bijna afgerond (moet nog beslissen hoe ik reversed woorden ga aanpakken). De output volgt;

code:

Reading and sorting completed in: 63ms.

Completed filtering for block 3 in: 797ms.
Redundant words: 17
    Overlappings of length 1: 13050
    Overlappings of length 2: 654
    Overlappings of length 3: 167
    Overlappings of length 4: 27
    Overlappings of length 5: 11
    Overlappings of length 6: 1
    Overlappings of length 7: 0

Completed filtering for block 4 in: 812ms.
Redundant words: 20
    Overlappings of length 1: 16788
    Overlappings of length 2: 992
    Overlappings of length 3: 219
    Overlappings of length 4: 40
    Overlappings of length 5: 3
    Overlappings of length 6: 4
    Overlappings of length 7: 0

Completed filtering for block 0 in: 875ms.
Redundant words: 20
    Overlappings of length 1: 16229
    Overlappings of length 2: 1254
    Overlappings of length 3: 291
    Overlappings of length 4: 52
    Overlappings of length 5: 5
    Overlappings of length 6: 0
    Overlappings of length 7: 0

Completed filtering for block 2 in: 891ms.
Redundant words: 24
    Overlappings of length 1: 20552
    Overlappings of length 2: 1449
    Overlappings of length 3: 411
    Overlappings of length 4: 42
    Overlappings of length 5: 4
    Overlappings of length 6: 0
    Overlappings of length 7: 0

Completed filtering for block 1 in: 1047ms.
Redundant words: 35
    Overlappings of length 1: 22479
    Overlappings of length 2: 1456
    Overlappings of length 3: 432
    Overlappings of length 4: 57
    Overlappings of length 5: 4
    Overlappings of length 6: 0
    Overlappings of length 7: 0

Completed filtering for block 5 in: 1141ms.
Redundant words: 30
    Overlappings of length 1: 34804
    Overlappings of length 2: 1933
    Overlappings of length 3: 442
    Overlappings of length 4: 96
    Overlappings of length 5: 13
    Overlappings of length 6: 1
    Overlappings of length 7: 0

All preprocessing done in: 1204ms.

[Glabbeek]

Ik ben ook gestart, en heb alvast een uitvoerbestand van woordenlijst 1, subset 1. Er zijn nog zeker optimalisaties te bedenken, maar het begin is er:

code:

** SCORE: 2196
Finished word list [0]
Duration (ms): 17135

Het grid: grid01.txt

Zou iemand deze door een validator heen kunnen halen?

[ Voor 10% gewijzigd door Glabbeek op 02-03-2007 01:24 ]

[Marcj]

Glabbeek schreef op vrijdag 02 maart 2007 @ 01:20:
Ik ben ook gestart, en heb alvast een uitvoerbestand van woordenlijst 1, subset 1. Er zijn nog zeker optimalisaties te bedenken, maar het begin is er:

code:

** SCORE: 2196
Finished word list [0]
Duration (ms): 17135

Het grid: grid01.txt

Zou iemand deze door een validator heen kunnen halen?

code:

Grid: 1
Score: 2196
Percentage van max: 67

Ziet er heel netjes uit

Varienaja schreef op donderdag 01 maart 2007 @ 21:39:
[...]

Ha competitie!

Vandaag op 't werk niets kunnen knutselen, maar de hele terugweg in de trein heb ik nagedacht en op m'n laptopje lopen tikken. Ik heb nu een vreselijke polynomiale (waanzinnig traag dus) oplossing gebrouwen die onder jouw grid 1 duikt.

Vanmorgen schrok ik even, toen ik zag dat je flink onder mijn oplossing dook, maar nu zit ik voor grid 1 op 2046. Ik zal meteen de andere gridjes ook even laten doorrekenen.


Nou, het is een half uur later en de eerste set is doorgerekend :

code:

Grid 1 : 2046/3231 ~ 63%
Grid 2 : 2330/3779 ~ 61%
Grid 3 : 2275/3661 ~ 62%
Grid 4 : 1738/2771 ~ 63%
Grid 5 : 1994/3178 ~ 63%
Grid 6 : 2903/4768 ~ 61%

Ik ben benieuwd hoe lang het duurt voordat ik links en rechts weer ingehaald ben.

Het verschil is natuurlijk wel dat mijn programma mijn score nu in 2 seconden behaald ipv een half uur Maar goed, ik ga de uitdaging aan en mijn algoritme wordt vandaag hopelijk een stuk beter.

[ Voor 49% gewijzigd door Marcj op 02-03-2007 08:11 ]

[Arjan]

voor de geïnteresseerde, hier staat een multithreaded versie van mijn exe
als iemand zich geroepen voelt deze te valideren, dan graag.

[MiezeL]

Ik mis SDL ofzo, helaas

[Arjan]

MiezeL schreef op vrijdag 02 maart 2007 @ 10:49:
Ik mis SDL ofzo, helaas

fixed

[Marcj]

Atgast schreef op vrijdag 02 maart 2007 @ 10:56:
[...]

fixed

Bij jouw komen er grid1.txt ipv grid01.txt uit. Dit moet je natuurlijk wel fixen. Na het renamen klopt jouw uitkomst echter wel:

code:

Grid: 1
Score: 2205
Percentage van max: 68

Grid: 2
Score: 2518
Percentage van max: 66

Grid: 3
Score: 2454
Percentage van max: 67

Grid: 4
Score: 1868
Percentage van max: 67

Grid: 5
Score: 2107
Percentage van max: 66

Grid: 6
Score: 3170
Percentage van max: 66

Totale score: 14322
Totale percentage van max: 66
Tijd om uit te rekeken: 562ms

[Glabbeek]

code:

Starting word list [0]
Filling raster (ms) [6141] per word [13]
Score: 2192
Duration (ms): 6298

Starting word list [1]
Filling raster (ms) [9548] per word [17]
Score: 2509
Duration (ms): 9689

Starting word list [2]
Filling raster (ms) [8986] per word [16]
Score: 2459
Duration (ms): 9111

Starting word list [3]
Filling raster (ms) [3860] per word [9]
Score: 1884
Duration (ms): 3938

Starting word list [4]
Filling raster (ms) [5860] per word [12]
Score: 2139
Duration (ms): 5954

Starting word list [5]
Filling raster (ms) [20409] per word [29]
Score: 3181
Duration (ms): 20628

Total duration (ms): 55696
Total score: 14364

Het gaat de goede kant op

[ Voor 93% gewijzigd door Glabbeek op 02-03-2007 11:30 ]

[Anoniem: 92106]

Atgast ga werken aan je scriptie jij

[Serpie]

Goed ik heb de basis nu ook draaiend, er zit nog niet echt veel intelligentie in. ik houd nog veel letters over maar de snelheid is goed dus heb nog ruimte genoeg over om te optimaliseren en betere posities te zoeken voor woorden. Ik pak nu nog het eerste het beste woord dat past

Grid 1 t/m 4 gingen goed, toen stuitte ik op een bug

grid 1: 812ms - 2533 tekens
grid 2: 203ms - 2916 tekens
grid 3: 125ms - 2851 tekens
grid 4: 265ms - 2153 tekens

Gaat de goede kant op, lekker veel deelnemers ook!

[Glabbeek]

Ik krijg ondertussen steeds betere scores, maar ik kom wel in tijdsnood komen als er inderdaad 99 lijsten van 999 woorden komen, wat het maximum is. In dat geval heb je namelijk maar 36 seconden per grid, wat best wel weinig volgens mij.

Met mijn huidige algoritme zit ik op 92 seconden voor een lijst van 560 woorden (bestand 1, lijst 3). Hier komt een score uit van 2237.

[ Voor 25% gewijzigd door Glabbeek op 02-03-2007 16:25 ]

[DaCoTa]

Glabbeek schreef op vrijdag 02 maart 2007 @ 16:21:
Ik krijg ondertussen steeds betere scores, maar ik kom wel in tijdsnood komen als er inderdaad 99 lijsten van 999 woorden komen, wat het maximum is. In dat geval heb je namelijk maar 36 seconden per grid, wat best wel weinig volgens mij.

Met mijn huidige algoritme zit ik op 92 seconden voor een lijst van 560 woorden (bestand 1, lijst 3). Hier komt een score uit van 2237.

Kan de organisatie iets van een idee geven over hoeveel sets er in de contest set zitten? Want er zit inderdaad nogal een verschil tussen 99 lijsten en 4 a 5 zoals in de voorbeeldsets.

[Dido]

DaCoTa schreef op vrijdag 02 maart 2007 @ 16:32:
Kan de organisatie iets van een idee geven over hoeveel sets er in de contest set zitten? Want er zit inderdaad nogal een verschil tussen 99 lijsten en 4 a 5 zoals in de voorbeeldsets.

Misschien is een deel van de uitdaging om met steeds verfijndere optimalisaties te werken afhankelijk van de grootte van de contestset?

[Serpie]

Hier nog even de output van grid1, wellicht dat iemand hem even kan valideren? Dan weet ik tenminste dat ik op de goede weg ben en dat mijn eigen validator het ook doet

                                                N                                     
                                                A                                     
                                                A                                     
                                           L    R                                     
                                           E    L   D                                 
                                           R    I   N                                 
                                           O    N   E                                 
                                L          M HANGOORI                                 
                              R E    RIATILEKLEINVEEE         L                       
                              E I    NEVEGNISECTIE BOG L      E                       
                              D T      DEELKTOPES ZALE E      V                       
                              D N     HINDOERNAASTTSGREVD     E                       
                              E E      TNARVANEDALREHIDEO     N                       
                              L VT    BWATJEMSTEPPEN BURM  EVIDENT                    
                        REIREOK AE ZR OGTCERIDNII HONDOEHSTATTEN                      
                             WA LRLEU TO KFIEZC MKEP EKNENROOHVERGEN                  
                         MAGGIKLSMAII TU AIANEL POJKKLREEGAZNIIG                      
                        WOLLENEALIGKM IDHJGEEEIPEETLNIEKRAKEELEO B                    
                      VOORRAADMTONAET NEEUALMRVILLNAARWROMMEL ZR EB                   
                       S  P  VESTAAREFERCIRCEOICEWORUIGETUALNIED EO                   
                       N  R TANIRLRGEERTHTOUWBAANELEWUAWASSALONEPREW                  
                  I  SEEMAISINTREEVNSMUST  NZIJWEGKN MDNC      L TT                   
                Z NNAABEREK RGSKWKOISEZUSUPERAIMULTIPLEIRIPMEGATS E                   
                E WPEDELA A OIIWREEPALACE UVFARESEKSSHOPERINEUMATMAT                  
                EGILLETSN L TLLEEJGPPA ILGIOFWE BKAZKEOHMADREEK                       
                RMNSTRIKE K ULUZPSWOMA GAETUOZS EPSEWLAGABBEROULEREN                  
                OONEREGIVCACAOCESUETIRFACKGWRWSFEIVELEGISCHERLEZENEREKREK             
            RUIGTEERZEEPOKROOBOLVORMLEERHUIDMIILNAOMTNEPPALKNEUZENRAATNALTA           
                 SNOOTLEB MKEUZENEKAHFATBIFEAJVEWAOASEJSIUMARITIEMRALA                
              A MOLSLAFTELLENOBALGREIFEZUFTUTM BEBRCLSSMEDERIJIREVA                   
          KLEINEKKELVOORKOOPEFOKKERIJOYRIDERIESURFFHUSISDLEEBMAAUTOGEEN               
              NWARTAALOHOCLAK SCOULOMBOUWORDELIJKWITHIMA ETGNENOHGEW                  
              ANAAPMITNUMSAPEGRAFIUDSOBTEWMAARKURDLEIWTG PSIENIPULEDNORG              
              VEAIONISCHABELOOIZUURKASTSSUBMYZNE NMLSFHTPSIRINPANDIGAADNAV            
              AGNNEKJIIOAOKEBTJEDARGPUFIULEAANHEFJIFAACHOSREULTIEM                    
              HEND G PCNTLAPFSK STAYERIXL SJM ERCINMW ICOAOVRENUEJEDNEEKOL            
               NEOZIESEKPKLEAAKNABNJIPLAYBOYENTUHCKADSLILWLIKREWLETREUREN             
               TMO DRARSANVLSVERMINKTYOTTRNPSEREEUUPFGELR OUPHALL                     
               AER REJOLKAJOURNAALATACRNCOPASFOFMPK ONIEUWCHONAAGPO                   
               LR  AKWRAAKICSUIZONZIJDEYAOYFEFFFIAENOIKKUUDAKENAMEIRD                 
               GOOGAKOOGBALCPULBHFEORHCSDDHFRUUICKLEHTLTDWUORTEGNOTEEZ                
             EGADNOBUILDINGUEMEOCRAM  YPUM EPNAKUCPKAJEUKBNNISDHETERO                 
              SPINDETPARABELCEPKAPTAFELAOI NXSESSIUUNIUUAAIEJAIEITITON                
              EROPNAACROBAATTMPSSTOFFIGNGXHIERBIJMNEDWRJVREKTLUIL T                   
             EJTLEEDAHAMEATSOBEBEDELNAPYFLOGNOOLHMTHIKD GGHOEEDDE AS                  
             DOUANIERIAHSNAOORZAPARCOURSOPPOMPENCIUCC E EOORNBEND IIG                 
               NEEHMOLJOTKDOPAELGZI PLECTRUMFRATSGOSA R WENT  BODNVEI                 
             LAATSTEJINOUOWDKASALOBRUUVISRIJKELUIABOPHOGINGIMROVIEERD                 
            VERARMENA AGRMEINNDAIRAHOEFSTALCASHIMLSURRICJSAUIE IMIDTN                 
              PENANTM A ESIUAEAEJGB  UKKEPUKMEGTOMMODEILOSAGNINEPO EI                 
                GIDEMSM NTVZMKASGKALRUUVOUWLIJNTTBALDADIGIRRDZ S O OE                 
                  BARONIEE KOKGUOELIUKTIZ IELTIOAOLAACOVGMSUEE   L V                  
                   N    TE ASUSMOOISEKSBOMPBLWTCBRUNETTEER TRN   V                    
                   C    TNMAARLETPR CHROMOPJEURHLDNEPJINNE IOOR                       
                   I    IU ILLUSIEPLACIDEBEIGEATO N NG   K L                          
                   E    PI ZAADDOOSTOPBORDRBAEWIEBELENEKNEDEB                         
                   N    SLTOORTSPRANKERNJIW ALZ DTGRGIEGAGEN                          
                          ELASTIEK TUOHKAH SLOOHCSGAENETSAAH                          
                           IT   T  PCRUISESIVEEZOIEAINNEREREV                         
                      GERRITREKVISCOLIOSEDIMSALPUUZLLAE E                             
                           SAL  LNTN VLIJTKLERKENJMEEPT D                             
                           OIA  EINESSALKOELTANKTNORBSNENAK                           
                           TNN   KEGEVATAPPENIEREODE IA O                             
                            ED   KTLAMMERENTNMOORVEP RK P                             
                            E    ETONLUSTOPSEINIE P  OM                               
                                 NERIJLESTREMMENV R  LORGIE                           
                                  EE   RPOIRMELTO O  K                                
                                   E   GIOEEEDERR T                                   
                                   DGILETVKTT GIE                                     
                                   S   RSEEN  RGI                                     
                                   TRIADEDNI  OEH                                     
                                   STEVENATAALG                                       
                                        E                                             
                                        R                                             
                                        E                                             
                                        I                                             
                                        K

[ Voor 12% gewijzigd door Serpie op 02-03-2007 18:07 ]

[Marcj]

Serpie schreef op vrijdag 02 maart 2007 @ 17:35:
Hier nog even de output van grid1, wellicht dat iemand hem even kan valideren? Dan weet ik tenminste dat ik op de goede weg ben en dat mijn eigen validator het ook doet

..

Output van mijn validator: Kan woord NAARLING niet vinden!

[zwippie]

Volgens mij staat de N van naarling verkeerd in de grid (namelijk linksbovenin). Het wordt dan het eerste woord van bovenaf gezien. Copy paste foutje misschien?

[Serpie]

zwippie schreef op vrijdag 02 maart 2007 @ 18:07:
Volgens mij staat de N van naarling verkeerd in de grid (namelijk linksbovenin). Het wordt dan het eerste woord van bovenaf gezien. Copy paste foutje misschien?

Klopt!, heb er pre tag van gemaakt ipv code en nu staat hij er goed.
Oorspronkelijke bericht geedit

[mOrPhie]

Serpie schreef op vrijdag 02 maart 2007 @ 17:35:
Hier nog even de output van grid1, wellicht dat iemand hem even kan valideren? Dan weet ik tenminste dat ik op de goede weg ben en dat mijn eigen validator het ook doet

Ik kom hierop uit:

code:

Valid grid!
Letters total: 3231
Letters used: 2533
Compression: 78,4%

[Serpie]

mOrPhie schreef op vrijdag 02 maart 2007 @ 18:45:
[...]


Ik kom hierop uit:

code:

Valid grid!
Letters total: 3231
Letters used: 2533
Compression: 78,4%

Mooi, mijn code om woorden te plaatsen werkt dus goed, en mijn validator ook.
Nu maar even kijken of ik wat intelligente manieren kan bedenken om de woorden te plaatsen.

[EdwinG]

Marcj schreef op donderdag 01 maart 2007 @ 08:44:
Dit is de uitvoer van mijn programma nu op de eerste testset. Hier staan de bestanden die daar uitkwamen. Iemand die het wil valideren is welkom!

Ik krijg de volgende fouten bij de voorbeelden (alleen set1, de andere 2 waren in orde)
Mist mijn validator (en ik, handmatig) iets, of is je script niet volledig?

code:

BLOK 1
Compleet

BLOK 2
Niet compleet:
    [541] => brouwen

BLOK 3
Niet compleet:
    [516] => custode

BLOK 4
Compleet

BLOK 5
Niet compleet:
    [209] => kopie

BLOK 6
Compleet

[mOrPhie]

Zo, finally iets wat erop lijkt:

code:

Valid grid!
Letters total: 3231
Letters used: 2194
Compression: 67,9%

Output van de grid01.txt van eerste testset 1.

M'n code needs refactoring, bigtime!

[ Voor 13% gewijzigd door mOrPhie op 02-03-2007 20:40 . Reden: paar woorden gewonnen. :P ]

[Anoniem: 3057]

WDN? reviews: Bericht van GoT: 3D-overklokcontest RobIII, tijd voor een inhaalslag qua publiciteit met deze wedstrijd?

* Anoniem: 3057 heeft overigens ondertussen het inlezen en elimineren van overbodige woorden gebouwd en gaat ergens dit weekend wat woorden plaatsen

[RobIII]

Anoniem: 3057 schreef op vrijdag 02 maart 2007 @ 18:30:
WDN? reviews: Bericht van GoT: 3D-overklokcontest RobIII, tijd voor een inhaalslag qua publiciteit met deze wedstrijd?

Wordt over gepraat

[Soultaker]

EdwinG schreef op vrijdag 02 maart 2007 @ 19:20:
Ik krijg de volgende fouten bij de voorbeelden (alleen set1, de andere 2 waren in orde)
Mist mijn validator (en ik, handmatig) iets, of is je script niet volledig?

Ik heb dezelfde resultaten. Ofwel we zijn hetzelfde vergeten (niet heel onwaarschijnlijk natuurlijk) of MarcJ's resultaten kloppen niet.

Verder zijn de scores wel best goed:

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    01        487     3231     2208    1023 (31.66%)
grid02.txt: Word "brouwen" not found!
    02        578     3779
grid03.txt: Word "custode" not found!
    03        560     3661
    04        429     2771     1852     919 (33.16%)
grid05.txt: Word "kopie" not found!
    05        487     3178
    06        731     4768     3189    1579 (33.12%)

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    01        487     3132     2116    1016 (32.44%)
    02        589     3851     2565    1286 (33.39%)
    03        902     5864     3865    1999 (34.09%)
    04        804     5190     3405    1785 (34.39%)
    05        571     3740     2491    1249 (33.40%)

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    01        359     3267     2427     840 (25.71%)
    02        378     3512     2632     880 (25.06%)
    03        469     4320     3234    1086 (25.14%)
    04        366     3399     2591     808 (23.77%)

[ Voor 14% gewijzigd door Soultaker op 02-03-2007 21:08 . Reden: Nu mét laatste grid van elke set; tnx EdwinG! ]

[EdwinG]

Soultaker schreef op vrijdag 02 maart 2007 @ 19:57:

  Grid         Words        Characters   Score        Saved
 ------------ ------------ ------------ ------------ ----------------
           1          487         3231        2208      1023 (31.66%)
grid02.txt: Word "brouwen" not found!
           2          578         3779
grid03.txt: Word "custode" not found!
           3          560         3661
           4          429         2771        1852       919 (33.16%)
grid05.txt: Word "kopie" not found!
           5          487         3178

Je vergeet Bij alle 3 de sets het laatste grid te controleren.

[Soultaker]

Erm, hee, goed punt.

Trouwens, wat scores betreft: is het niet zinniger om bij te houden hoeveel letters je bespaard hebt, zodat hoger beter is en je mensen die een ongeldig grid maken gewoon 0 punten geeft?

Dat is vergelijkbaar met wat EdwinG voorstelde (ongeldig grid geef je het aantal letters in de woordenlijst als score), maar naar mijn idee wat intuïtiever omdat een ongeldige oplossing gewoon 0 punten waard is, en hogere scores beter zijn.

Als er overigens veel verschillen zitten in de groottes/eigenschappen van woordenlijsten, kan het aardig zijn om relatieve scores te sommeren. Je deelt dan bijvoorbeeld voor elk grid de score door de best behaalde score (degene met de beste score krijgt dan 1.0 punten de anderen een getal tussen 0 en 1) en die op te tellen. Met 100 testcases is de maximumscore dus ook 100 (maar dan moet je in alle grids de beste score van alle deelnemers hebben). Het effect is dat elk grid evenveel waard is, in plaats van dat grids met meer woorden waar bijna automatisch meer te besparen valt relatief meer waard zijn.

[ Voor 95% gewijzigd door Soultaker op 02-03-2007 21:26 ]

[Arjan]

kan iemand me trouwens vertellen waarom mijn prog sneller draait op een oude AMD XP 2800+ dan op een dual core turion, terwijl wel beide cores gebruikt worden

erg vaag...

[Marcj]

EdwinG schreef op vrijdag 02 maart 2007 @ 19:20:
[...]


Ik krijg de volgende fouten bij de voorbeelden (alleen set1, de andere 2 waren in orde)
Mist mijn validator (en ik, handmatig) iets, of is je script niet volledig?

code:

..

Klopt helemaal. Ik heb nog een oude versie daar staan. Ik ga nog ff kijken of ik mijn algorithme weer werkend kan krijgen en dan zal ik er wel weer goed versie neer zetten

[NMe]

DaCoTa schreef op vrijdag 02 maart 2007 @ 16:32:
[...]

Kan de organisatie iets van een idee geven over hoeveel sets er in de contest set zitten?

Nee...

Want er zit inderdaad nogal een verschil tussen 99 lijsten en 4 a 5 zoals in de voorbeeldsets.

...want dat is de hele clou van deze contest.

Atgast schreef op vrijdag 02 maart 2007 @ 22:44:
kan iemand me trouwens vertellen waarom mijn prog sneller draait op een oude AMD XP 2800+ dan op een dual core turion, terwijl wel beide cores gebruikt worden

erg vaag...

Misschien een lib gebruikt die beter werkt op een bepaalde soort processor omdat die bijvoorbeeld sneller kan vermenigvuldigen?

[DaCoTa]

-NMe- schreef op vrijdag 02 maart 2007 @ 23:24:
[...]
Nee...
[...]
...want dat is de hele clou van deze contest.

Flauwerikken

We gooien gewoon iedere set in een thread en lekker de CPU spammen.

[Arjan]

-NMe- schreef op vrijdag 02 maart 2007 @ 22:24:

[...]

Misschien een lib gebruikt die beter werkt op een bepaalde soort processor omdat die bijvoorbeeld sneller kan vermenigvuldigen?

ok...ook sneller dan op een core 2 duo @ 1.66Ghz
dit lijkt mij niet echt gezond ?

[H!GHGuY]

zijn de woorden uniek (per groep)?

[Varienaja]

H!GHGuY schreef op zaterdag 03 maart 2007 @ 00:34:
zijn de woorden uniek (per groep)?

Ik hoop het wel, dan krijg je een goeie compressie!

[Soultaker]

H!GHGuY schreef op zaterdag 03 maart 2007 @ 00:34:
zijn de woorden uniek (per groep)?

Dat zijn ze nu al niet. (Zie 'belg' en 'leut' in set 2, grid 3 respectivelijk 4).

[Varienaja]

't Is laat genoeg nu.

Ik heb m'n implementatie versneld, en daarbij ongeveer 5% aan ruimtewinst verloren. :-/

Iemand zin om te valideren? Ik ben je zeer erkentelijk! Grid 4 is dit:

code:

---
                                                  S    G                                                              
                                       Z      D   TUOHMLAP                                                            
                                       I      A   H    O                                                              
                                       L      M   C    R                                                              
                                       V    GRASBAANWASI                                                              
                                       E S VOORBEENKAP A                                                              
                                       R T  D TKLUNENIELAB                                                            
                                     NIERRETSUL   A N  U                                                              
                                BALEINENUERDH E   V E  P                                                              
                                       G B  U N   EENIMODNEDOG                                                        
                                      NELEKKIPSOH   U  P                                                              
                                       NERAOS       E                                                                 
                                 TNEMGIPMOZMM       R                                                                 
                G                     S JVKPU       D                                                                 
                E                     P IEERS                                                                         
                V                     A RNOEIVJIDNAK                                                                  
                E  S                  A E RSC    I                                                                    
               SCHUIF                 R G BRU    Z                                                                    
               NH  LK                 KLAPBESMUIKT                                                                    
              RETHCIL                 A L IPT    S                                                                    
               LYRICUS   V  P ESUEDNOTSIP RPO    N                                                                    
               T D ON K KIBBOETS   E       IS    U                                                                    
             BERLIJNEIEONS  R   M  FV  KEOKTNAKORK                                                                    
              PAREMENTI EH  K   OG FA      N                                                                          
               MUH PE M TANKAUTOONAARD     A                                                                          
       NEOISNEPMET LWRASTAMELENETIULS      X                                                                          
              GEDOGENERIEKIESPIJNL BI      M  N            S                                                          
               NNZIH KK R NR    AE  TTADZIMASSEREN         I                                                          
                I DC R    ZZ    FID Y     DS  L LR         L                                                          
                U DN U    AI     WN       FSSNEGEILV S  G  A  D                                                       
                T OA U  GNAJAW    J       EA  R PT   T KE  R  F F                                                     
                  VR T    M       I       ICVERASSEN R RZ  U  O O                                                     
                  EB             DL  N    RR FOHNEKERO EE RLEMOCOHC                                                   
                  R              REKNEUZINGEMOMPELGRIM WLNEPMIHCS                                                     
                  A   E          AG  L FREEWAREGIETERIJSLOLLY L O                                                     
                  LS  D        FVAARGEUL TG     KN KEJSAILLANTA L                                                     
                  VF  IG      VOUWBOOTUATSOPVRETENERETSAGNETJIBNI                                                     
             ZANDLAAGSTAM N    T Z   S A OBISSCHOPTELSOMMATHIS  F                                                     
                  KAZTORATIE   STEENWEGM O     CDM VPUTOPTIERN                                                        
                  BL URFJKRZ   F B  DNATKEOH   UDA  AVALENTIEA                                                        
                  LS FIOOLOT   L       S B     LNACYRREJ   DMR                                                        
                  A  IPCRIMEISJE       A       KAZRETAW GESLOTENATAD                                                  
                  D  BAU E HSA D       G DIEHDRAHD        VERSMAAT                                                    
                  PEERTSPRENGN                 B J          DO                                                        
                     II     ND                   I        KJIRFOOL                                                    
                     LL     OH                   L          N                                                         
                      O     KI                              A                                                         
                      L      P                              A                                                         
                             H                              L   N                                                     
                             O                              B   E                                                     
                             P                              E  PDH                                                    
                             H                              S BRAT                                                    
                             E                               BLERIL                                                   
                             F                              MRONIL                                                    
                             F                              BIETTIP                                                   
                             E              GUB G            EMOMJL                                                   
                             N             KNARFOLK          LMEXPOTS                                                 
                D            A              I TROUWUOLIEBRONDGANG E                                                   
                A      O     F      B     Z LBATIKASAJ        L   G                                                   
                A      N     L      Y    HENNANHRTAALP        I   R                                                   
                R   D  WLWELFAREISDOELLIJNEVERGAANDROGYN      N   E                                                   
                M   R  AO    C           TFLESLUHMODUS        G   S                                                   
        SNETHCEREIDNO  AV   IH             OD  W  S D         A                                                       
           R  DNEDROEGORD  NUE           SKEOH                L W T                                                   
          GAZONTDOENSH DUOHEBR             DZ                 STOMN  G                                                
           C  IKEITANAF M  STZ                                D EAIRCO                                                
           KRELVOETBANKGIROTSIG                               L RGS  G                                                
              B W AICACAJ  OEE                               NEDDEB  M                                                
                  JLKIULLORKPN                            WAARVOORAFJE                                                
                      P      D                               UUGOOHPB                                                 
                        T    E                               DDROMERIG                                                
                        O    F                              DIEETRUUS                                                 
                       TV    L                               UBE UPIM                                                 
                      BEANGSTAFLID                           LEPMIWMU                                                 
                   Z R JH  T T                                 U L  T                                                 
               RUUBANO VC  H I                                 O                                                      
               ECAPABELOSNOC E                 O               C                                                      
               DNEDIERPSAE E          S        P                                                                      
               A T S BF DMTL          A     Z  W L                                                                    
              ARCADESLEMPENS          A    ZEILIMAFPERKEN                                                             
              SNAHTLAAITINIT          P   ZWI  P N                                                                    
               A CN KDTALLOOSTUPIDE   M   WIL  P K                                                                    
               A  ESUKORKEPF          L   EJP  ESR                                                                    
               G  S RLMT WT         SAAKSARGUMENTE                                                                    
               S  NTKAHEG E  G    V KOPKRAMENOZDNOVA                                                                  
               O  OS PAN  S  E F  O YKLOODERTS  AV                                                                    
               LTHCULVL  V   T O GESLAAGD NFOHLEPET                                                                   
              BWKLOKKEIRYLG  U TESTBAANVANGELEVATOR                                                                   
              RUITDELENIGENNOIPS  P BZDNC LRW   OTA                                                                   
             POOHTSEM GC CI  G PB ALMENEINIMEF  H A                                                                   
              MJCS ZZN HMHZ  EILEIDERDETP JEZ     H                                                                   
             MISSAAL EITATIC   UD  POOKTIUDTE     Y                                                                   
              D PK BOMMEN U    HU  STMEU  ETNEGEOVNI                                                                  
         ROTAREPOKMODJ NZ S     U  JS TD  NEGORDNIO                                                                   
                KOMBUIS I       SPLITPENEODNEPOJ  P                                                                   
                 GSTILERENNIW   D  LR GI    N UI                                                                      
                    MV  K          BO         PZ                                                                      
                    D               O         IS                                                                      
                    I               I         EA                                                                      
                    K               E          W                                                                      
                                    R

[Soultaker]

Hij klopt in ieder geval, en werkt best goed:

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    04        429     2771     1805     966 (34.86%)

[Dash2in1]

Met welk woord laten jullie je algoritme beginnen en waarom?

[ Voor 9% gewijzigd door Dash2in1 op 03-03-2007 06:57 ]

[Marcj]

Ik het hier nu wel een goede testset staan met een behoorlijke score

[Serpie]

Marcj schreef op zaterdag 03 maart 2007 @ 07:32:
Ik het hier nu wel een goede testset staan met een behoorlijke score

Netjes hoor, je behoudt je voorsprong
Mijn code ook wat verder geoptimaliseerd, en ook wat resultaten die er op beginnen te lijken.
Kwa tijd nog ruimte genoeg om verder te optimaliseren.

Totale parsetijd van de 6 groepen: 51 sec 735ms

Aantal over tekens in grid1: 2133
Aantal over tekens in grid2: 2412
Aantal over tekens in grid3: 2355
Aantal over tekens in grid4: 1805
Aantal over tekens in grid5: 2067
Aantal over tekens in grid6: 3008

Grappig dat mijn grid4 precies zoveel tekens heeft als die van Varienaja. Hij ziet er wel wat anders uit:

code:

---
                                                        Z                                        
                                                       SAS    R                                  
                                                       NAK    E                                  
                                                   STROOIER   T                                  
                                                       ESOOLLAT                                  
                                                      DIEHDRAHENNA                               
                                                  ROTAVELE  N N                                  
                                                     LINOU KK K  L                               
                                                        SPAARKASTOP                              
                                                        N  AE Z  O                               
                                                      AVONDZONT  D                               
                                                        C  EVGOGME                               
                                                    DUOHEB DE R  RS                              
                                                   S  MESTHOOPVRETEN                             
                                                   L ZMLK  MTEJVOSOO                             
                                                M  AEEVPALKIDMIUD RZ                             
                                                O  KFEVEN LN  R   DA                             
                                                R KROKANTKOEKNEUZING                             
                                               EITPOTUPSUDFEIRGEGRES                             
                                               MN  PSSAILIJDZAAM  D                              
                                          E    MB  AFTLOE  N  L   J                              
                                          DK F AI  KLUMEM ZEILPUNTIG                             
                                      ALVAARGEULJIMNEFPNOPWIPPEN  LE                             
                                          CARMPITTEED A CF Z M E  GHANA                          
                                       LIURMOI NE VEJFAROOVRAAWKCUPA E                           
                                          AIUN GNHABISSCHOPERSERPMOKOTSEN                        
                                        GREEPI  J N Z W CS HESUEDNOTSIP                          
                                        ESAKIESPIJN SIUBMOKC A P  P  U      G                    
                                        WANNENUERDACAPABEL A C F  HTIL      E                    
                                  RICHTENOCILIS E C W H  IHLDRAAWZEB S      T                    
                                        E HETZE M H NKJIRFOOLEKNARF  NS     E                    
                                        E    TBVOETBANKGIROO W AT  BRAT     K K                  
                                        T    SPGRASBAANVANGINETTEMREFHR T  GEOLP                 
                                        S   GNAGDNORBEILO  F  LIREGIETERIJ NNPU                  
                                          THCULVINDUTTENEMARKPOEZF NELESTIRADEN                  
                                          KLOKKENGALSDLEVUDEB  KAA  ZAPRENTT NELERROM            
                                          IYTISRAV  E  G STEOBBIKM  BRO L  IHDNAS                
                                     H    U    GAPESTBUIDURW NEMJILVREM L  S OE                  
                                  K  I BISMUT BALYKSP  NSCHAVOTDALBKAVHREIDNOEG                  
                                  WIMPEL US   RAAHYNOPXEVOORBEENLINGNOU RDRAANOOT                
                        S         A  H Y CEPPITNAX  I BLAFFENIERRETHCIL  R R ED                  
                        U     NEMMARTO RFIBRILBDTKIENSPELGRIMOTIEFIUHCS  ONTDOEN                 
                        U  K MPI ZD  P IJSLOLLYRICUSTOSM  HULPSTOF AELE  M   TG                  
                        REELPARTSORM T E UA  BEOOSTENATADZIMASSERENEDOL  E                       
               R     BIETAPIRAUA MAA E K MA MK GBAKLUCHTUOHMLAPLANDTUURKEROM                     
               O     L    UP ZILEPSJILBARSIJERRYCANKIHCSPOK  F FTAFAOWIELING                     
               TG  K I   MOD NMFIITO SNZUITKOOPNKEIRENEGNEZEWLOTIFOHLEPETG                       
               IE  RTNISBACACIAEVGARFOEKLUIDLK   IPOPULAIRCONAS E OCALJR                         
               DSPREIDEN A S MGDJMFBOMMENHN BUGMOTSAAKSARGUMENT   H KFIZ           G             
           EITNELAVLIEGENS WENENIELABMROTSIGASTMAAL   TLN  OP R  PLURALISGNOK      E             
               OO  V   LZWIJGER DNI HAERODACIPLUSTER GODENDOMKOPERATOR JJ   L      O             
               LTBEANGSTREBERLIJNTDVOUWBOOTUATSOPIM   FNPBATIKM   B LEPMOMEGIUTEG  R             
               VERASSENR R   EJ A   T ZBAGELIJNDGCP    AT  NH I  VE LIRUUBANEI     D             
                NI VISHAAKT GKM T   PC I N    EJSIEMGNIZIUSAC J BEDUUSD W  ARNESTELEN            
                 E   L MFOHNEKERK KCARTRUEDNIUTNESNOC  SLAAFSIT BROMIDEDEOWJ V     N             
                     A A VC ZILVERENNIWW R    H         P K  NNG SZ KO  LIBANONWAARD             
                    HANDDOEKEPA OPI TM U P    C         STUPIDEA MTHCELVNO WEE                   
                     GEMUDVOLSAJHLZ SE O S    E           RNORMS A DALBREOR PG                   
                     DD IDE LOSGAANRADER      R           K VOETPAD NL  MGI ME                   
                      D TIG IHS STANKAUTO                    GRETTAJSI BEROVEN                   
                    WOERDG  GNILAHMOK                        EAR IA  JIDNAK TT                   
                      B EL   TMDIEHTOZ                       NPE LR  NEGNEREV                    
                        LO  NERELITSG                          N OM     O                        
                       VERKEREN LD                             EILEIDER I                        
                        NI  UI  A                              T  E     P                        
                         A   D  N                              R        S                        
                                T                              A                                 
                                                               T

Update

Nog even een ander ideetje wat ik had geimplementeerd, nog weer wat dichter bij marcJ gekomen

Aantal tekens in grid1: 2096
Aantal tekens in grid2: 2387
Aantal tekens in grid3: 2308
Aantal tekens in grid4: 1790
Aantal tekens in grid5: 2049
Aantal tekens in grid6: 2984

[ Voor 3% gewijzigd door Serpie op 03-03-2007 11:19 ]

[mOrPhie]

Dash2in1 schreef op zaterdag 03 maart 2007 @ 06:57:
Met welk woord laten jullie je algoritme beginnen en waarom?

Ik begin met de langste woorden. Het idee (of de hoop is) is dat je dan de meeste overlap als eerste afdekt. Maar ik heb al gemerkt dat het sorteren van essentieel belang is (in elk geval in mijn algoritme) en probeer me daarom daar nu op te richten. M'n resultaten verbeteren erdoor.

[ Voor 3% gewijzigd door mOrPhie op 03-03-2007 12:25 ]

[H!GHGuY]

Mijn huidig probeersel crasht de compiler:

code:

c:\Program Files\Microsoft Visual Studio .NET 2003\Vc7\include\vector(152) : fatal error C1001: INTERNAL COMPILER ERROR
        (compiler file 'msc1.cpp', line 2701) 
         Please choose the Technical Support command on the Visual C++ 
         Help menu, or open the Technical Support help file for more information
Board.cpp
g:\BoostLibrary\boost_1_33_1\boost\multi_index\mem_fun.hpp(59) : fatal error C1001: INTERNAL COMPILER ERROR
        (compiler file 'msc1.cpp', line 2701) 
         Please choose the Technical Support command on the Visual C++ 
         Help menu, or open the Technical Support help file for more information

nou wat?

ff verderproggen, mss werkt ie op de 2005 wel...

met een resem typedefs weg te halen heeft ie er pcies wel weer zin in...

[ Voor 4% gewijzigd door H!GHGuY op 03-03-2007 16:24 ]

[twanvl]

Ik ga ook maar eens mee doen. Mijn resultaten bij de eerste poging zijn best aardig, alleen doet het programma er erg lang over.

Number of character in grid 1: 2083
Number of character in grid 2: 2388
Number of character in grid 3: 2356
Number of character in grid 4: 1772
Number of character in grid 5: 2052
Number of character in grid 6: 3012

[H!GHGuY]

twanvl schreef op zaterdag 03 maart 2007 @ 16:31:
Ik ga ook maar eens mee doen. Mijn resultaten bij de eerste poging zijn best aardig, alleen doet het programma er erg lang over.

Number of character in grid 1: 2083
Number of character in grid 2: 2388
Number of character in grid 3: 2356
Number of character in grid 4: 1772
Number of character in grid 5: 2052
Number of character in grid 6: 3012

raar dat iedereen zegt: mijn programma doet er lang over...

mijn programma zal wsch nooit eindigen, tenzij ik er een limiet op zet...
vaag

[Serpie]

twanvl schreef op zaterdag 03 maart 2007 @ 16:31:
Ik ga ook maar eens mee doen. Mijn resultaten bij de eerste poging zijn best aardig, alleen doet het programma er erg lang over.

Number of character in grid 1: 2083
Number of character in grid 2: 2388
Number of character in grid 3: 2356
Number of character in grid 4: 1772
Number of character in grid 5: 2052
Number of character in grid 6: 3012

En wat is lang? je hebt een uur de tijd immers..

Inmiddels mijn code dusdanig aangepast dat ie wat langer gaat zoeken naar goede combinaties, gevolg is dat het wel langer duurt natuurlijk maar ik vind wel betere plaatsen.

In ieder geval nu binnen 5 minuten grid 1 opgelost en 2039 tekens over gehouden, vanavond nog maar eens kijken hoever ik kom als ik hem nog langer laat zoeken.

[ Voor 3% gewijzigd door Serpie op 03-03-2007 17:04 ]

[DaCoTa]

Wil iemand mijn grid1 valideren? Mijn eerste output, maar volgens mij kloppen mijn prioriteitstellingen nog niet helemaal. (score: 2159)

              m                                              
             dagwerk                                         
             ld  v                            n              
            neruert      g                    e              
             pe  a       a         krewlet    u     d        
             sejkarts    a       lachbuilding s     a        
             skavgew     d         i f t    v b     a        
            raajnaambeeldn         mnekuehcsigeleekark       
     nestipsewlaglijgootaarefer    membraannemercatoreez     
           p  ruimte  dp ve        iketgiur windvango        
          redruelbbhypnoseivormigorgeleneknedeb     o        
           rduurloopgaan rt      deviaties  a       v        
           w  voorfilmledicalp  gnilraankomst                
           e    bdfiukeg jevormleer ir n o ia                
           r tb urednimi ps h y vpkaptaamd m                 
        tsiujno o rzwemenittobzsajremozp d t                 
          iulekjir  drob ja c notities s a h  t u            
         r witsjze beertwny lme  nnootlebahcsinoi            
     tsiroloctbiwbs  nesabekaarw leddims zbi dactylus        
tsakruuzioolheababijbelstarfaressapmim i  ol  r g            
     o   d ltelraam ltuujn  gcruhurcyprus u   v i z          
     b   nnegageigrooi  ek mesepotewmaart w  pamflet         
     s  gidnapnivpedelzriatilevendw  a cntoppingt i          
     m      s  hi kldeelkamillerdru  nedairt kupekku   c     
     a     yobyalpkeuzeevisrijkeniereizenrd  sbt netsaah     
     l  knatleokc uboeteligimi b einu  nereveloschroef u     
            i  h  tukwskirtser agnn    hpe koerierkajuittocht
           devoot gjnkn janud baaio vs upgradeeltje s  n     
            beaufortemeitluccounterminalarm nueu  rgillets   
               t  aduogg spicashklareedslemjiwzc neruzay     
               reifezorg l g cmeikbafe tks  htoopknameird    
                    e ea o a asfrusk h a y  ljnjicupak       
                   dnovm murtcelpitlumcggnoteezeppelin       
                 kakementheteropna apohertz pii   j          
                    f k chromom e  k siwoak enjh  e          
                    ffiudsobmb  t   wuljnxu ldde  d          
                    ave nmuseaalnekkuriidiu pier             
                    pimpelennataal darrzesdaagsloohcsimota   
              streduogfotseretnikanenipullahpamajyp          
                    me ht  coulomb mkc tiwkjiledrog          
                    hr sa   z pjoggen  nr    sde             
                   zoetstoffigaroognah ainwerken             
                    on ksiameestrootronlustnenrooh           
               latnegeneffunsws vgneppatm    oi              
                    valslot olispanys  annavahj              
                        vlooien  negeilebarap                
                          rflognoolekejso                    
                  reehmodeilokeend r nessalk                 
                          t cavnettipsierteov                
                        g   sneograbintrige                  
                        n   kknhhandicapj verarmen           
                       zitkuiltgciceromxk nt                 
                        n   foiednipstrekvisserij            
                     jirekkofbew eejtnolknetjirk             
                        p  herlezen   fnaalatac              
                        o   uu   g gnitjiwkazkeoh            
                    nevetsavruumrovlob neralkpo              
                             vyobtfil nelewuaw               
                             ewtouwbaans d                   
                             gidraabs  s d                   
                        tnumsapesachsucimehc                 
                             zp matmat w l                   
                             nelebeiw  f kurdleiw            
                             irednopdlaatraw                 
                          jaspisi lefatpakrewgeov            
             kalvjilgidadlab gnigohpoao                      
                       f  nemmertsruocrapookroov             
                       h laanruoj   hoppompen                
                       a   d  mlnezeived                     
                    vlekkeneiurkpo    diehgaal               
                 hechtselammereneggezmobskes                 
                       nelletfa r               f            
                        r tnedive nekeobfa     krewneeb      
                        k h nereluorevoreihgireviuh          
                     riaelcun nraatnal     l    t            
                        n aedimsalpa  boorkopanledeb         
                          m  taarojampeezreettenurb          
                         keopeorkristal   ri    so           
                   keitsalekuknimeitiram  nerutseb           
                          z      cm   s   jng  neppets       
                                 yr   tceridniespots         
                          ruelkielatsfeoh wliuneets          
                       nekkinsraagnoh neimarts   so          
                                tcepsus     rediryoj         
                           tknimrev        maarkurd          
                                  o eisullinwinneni          
                           ximdoorb         z nediudeb       
                                                w z          
                                         nekortiu            
                                      reinauodwuortegadnob   
                                         njilwuov            

[Naj_Geetsrev]

Een vraag. Mag het programma alleen de gegevens gebruiken in de woordenlijst die hij inleest, of mag hij ook gegevens van die woorden ophalen van internet??

[Rainmaker1987]

Volgens mij mag de computer geen contact maken met internet of wat dan ook. Datgene wat je inlevert moet voldoende zijn. Daarnaast, wat zou je dan willen ophalen van internet? Mij lijkt dat je toch al je gegevens kan uitlezen uit het words01.txt bestand?

Kben ook maar eens begonnen. Met tetris liep ik al heel snel vast. PHP is de taal die ik wel moet gebruiken omdat ik C++, VB etc allemaal niet ken. Hij lees nu braaf alles in en haalt de dubbele eruit. Jammer alleen dat hij er zo lang over doet. (7 sec over ontdubbelen)

[EdwinG]

DaCoTa schreef op zaterdag 03 maart 2007 @ 17:53:
Wil iemand mijn grid1 valideren? Mijn eerste output, maar volgens mij kloppen mijn prioriteitstellingen nog niet helemaal. (score: 2159)

Grid is compleet, volgens mijn validator. (Score functie heb ik nog niet ingebouwd)

[DaCoTa]

EdwinG schreef op zaterdag 03 maart 2007 @ 18:07:
[...]
Grid is compleet, volgens mijn validator. (Score functie heb ik nog niet ingebouwd)

Merci! Score functie is in principe tellen van letters, dus zou eenvoudig moeten zijn voor een validator

Geheugen is trouwens echt een issue... Met 512MB heapspace (java) kom ik ongeveer tot 500.000 grids in memory. Hoe zit dat bij de rest?

Inmiddels zit ik op 2106, alleen komt er op een of andere manier geen betere oplossing meer zodra eenmaal alle woorden geplaatst zijn. Beetje vreemd.

[ Voor 32% gewijzigd door DaCoTa op 03-03-2007 20:38 ]

[RobIII]

Naj_Geetsrev schreef op zaterdag 03 maart 2007 @ 17:53:
Een vraag. Mag het programma alleen de gegevens gebruiken in de woordenlijst die hij inleest, of mag hij ook gegevens van die woorden ophalen van internet??

RobIII in "Programming Contest Nieuwe Stijl: Contes..."

[PiepPiep]

DaCoTa schreef op zaterdag 03 maart 2007 @ 18:11:
[...]

Merci! Score functie is in principe tellen van letters, dus zou eenvoudig moeten zijn voor een validator

Geheugen is trouwens echt een issue... Met 512MB heapspace (java) kom ik ongeveer tot 500.000 grids in memory. Hoe zit dat bij de rest?

Volgens mij zijn er maximaal 99 sets en dus maximaal 99 grids, zou toch moeten passen

[The Flying Dutchman]

Leuk een programming contest!
Toevallig stuitte ik bij een zoektocht op GoT op de vorige contest. Enigzins balende dat ik daarvoor te laat was... maar gelukkig is er alweer een nieuwe .

Ik ben gelijk maar gaan schrijven (C++), het inlezen van bestanden werkt in ieder geval al (het vervelende werk ). Nu eens nadenken over de te volgen tactiek... het is nog best een lastig probleem!

[chris]

Ik ben net begonnen met een haskell-implementatie, ik heb nu iets meer tijd om er aan te werken. Ik heb 'm nu zo ver dat 'ie alle woorden er uit haalt die een subwoord van een ander woord zijn. Dit doet 'ie in 1 seconde voor alle groepen van de 1e testset. Nou nog het moeilijke gedeelte. Ik zit nu op 42 regels code, inclusief commentaar.

[Varienaja]

Gisteravond heb ik tot diep in de nacht zitten klaaien om de snelheid te verbeteren. Hierbij heb ik wat andere invul-algoritmen verzonnen, maar het hielp niet echt. De snelheid was weliswaar beter, maar de scores een stuk slechter.

Vanavond kreeg ik een nieuw idee. Ik heb het nu wat uitgewerkt, en het lijkt veelbelovend. De snelheidswinst is gebleven, maar de scores zijn weer als vanouds:

code:

Grid1: 2021
Grid2: 2304
Grid3: 2249
Grid4: 1734
Grid5: 1994
Grid6: 2891

[Soultaker]

Ook maar wat gebouwd... het zal wel ongeveer hetzelfde zijn als wat MarcJ en Varienaja bedacht hadden, want de scores zitten ook ongeveer in hetzelfde bereik (al zijn ze iets lager dan van Varienaja):

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    01        487     3231     2040    1191 (36.86%)
    02        578     3779     2330    1449 (38.34%)
    03        560     3661     2274    1387 (37.89%)
    04        429     2771     1738    1033 (37.28%)
    05        487     3178     1997    1181 (37.16%)
    06        731     4768     2911    1857 (38.95%)
 -------- -------- -------- -------- ----------------
  Total:     3272    21388    13290    8098 (37.86%)

[Serpie]

Het zit allemaal dicht bij elkaar, hier nog wat vergelijkings materiaal van mij:

code:

Grid1
Orgineel: 3231
Nieuw   : 2039
Gespaard: 36,89%

Grid2
Orgineel : 3779
Nieuw    : 2341
Gespaard : 38,05

Grid3
Orgineel: 3661
Nieuw   : 2285
Gespaard: 37,58

Grid4
Orgineel: 2771
Nieuw   : 1734
Gespaard: 37,42

Grid5
Orgineel: 3178
Nieuw   : 2019
Gespaard: 36,47

Grid6
Orgineel: 4768
Nieuw   : 2918
Gespaard: 38,80

Hoe lang doen jullie parsers erover om de grid te maken? Bovenstaande resultaten heb ik behaald in ongeveer 6 minuten. Ik heb hem even wat langer laten parsen en dan krijg ik (gelukkig) nog betere resultaten. in 16 minuten kom ik dan tot het volgende:

Grid1: 2016
Grid2: 2303
Grid3: 2253
Grid4: 1727
Grid5: 1967
Grid6: 2873

[ Voor 27% gewijzigd door Serpie op 04-03-2007 11:41 ]

[H!GHGuY]

raar dat jullie allemaal zo snel een werkend prog hebben...

ik heb mijn algo al geschreven maar moet de files nog uitlezen en nog redelijk wat implementatie doen om het ding werkend te krijgen...

mss het nadeel van in C++ te werken ?

[NMe]

Naj_Geetsrev schreef op zaterdag 03 maart 2007 @ 17:53:
Een vraag. Mag het programma alleen de gegevens gebruiken in de woordenlijst die hij inleest, of mag hij ook gegevens van die woorden ophalen van internet??

Het mag wel, maar dan alleen met een schakeloptie ofzo; het standaardgedrag moet zijn dat de zut uit de genoemde bestanden wordt ingelezen. En je krijgt er geen extra credit voor een internetimplementatie, dus waarom zou je?

PiepPiep schreef op zaterdag 03 maart 2007 @ 18:48:
[...]

Volgens mij zijn er maximaal 99 sets en dus maximaal 99 grids, zou toch moeten passen

Niet als je elk grid een paar keer uit wil rekenen om zo te kijken welke het gunstigst is.

[Serpie]

Ik heb het plaatsen van de woorden even gevisiualiseerd, het werk wel vertragend dus komt niet in de release mode. Maar wel leuk om te zien.

Voor de liefhebber even een filmpje ervan gemaakt, hier is mijn parser bezig met het parsen van de woorden voor grid 1.

http://www.smokeysoft.com/parser.avi

[The Flying Dutchman]

Ziet er gaaf uit hoor .
Ik ben nog niet zover, gisteren pas begonnen en vanochtend eerst een paar ranzige bugs uit mijn inlees functie gehaald .
Een eerste optimalisatie is natuurlijk het standaard weghalen van woorden die geheel overlapt worden door andere, dat werkt ondertussen ook.

Ik heb nog wel wat leuke ideeetjes voor algoritmen, maar daar moet eerst nog eens verder over nagedacht worden, of ze echt nuttig toepasbaar zijn en of ze niet teveel tijd kosten.

[NMe]

Serpie schreef op zondag 04 maart 2007 @ 12:29:
Ik heb het plaatsen van de woorden even gevisiualiseerd, het werk wel vertragend dus komt niet in de release mode. Maar wel leuk om te zien.

Voor de liefhebber even een filmpje ervan gemaakt, hier is mijn parser bezig met het parsen van de woorden voor grid 1.

http://www.smokeysoft.com/parser.avi

Hoeveel tekens heeft dat grid uiteindelijk?

[Varienaja]

Serpie schreef op zondag 04 maart 2007 @ 09:54:
Hoe lang doen jullie parsers erover om de grid te maken? Bovenstaande resultaten heb ik behaald in ongeveer 6 minuten. Ik heb hem even wat langer laten parsen en dan krijg ik (gelukkig) nog betere resultaten. in 16 minuten kom ik dan tot het volgende:

Het optimaal plaatsen van alle woorden is onmogelijk, er zijn teveel mogelijkheden om dit in eindige tijd te proberen. Ik (en alle anderen ook; kan niet anders ) probeer dus door aannames te doen toch in eindige tijd een grid te bouwen. De eerste testset (van 6 middelmatig grote grids) wordt bij mij uitgerekend in 10 minuten. Deze tijd moet beslist naar beneden. Ik wil het tot een seconde of 5 per grid terugbrengen (hulde aan Marcj, Atgast Glabbeek Serpie, zij zijn al zover) en daarna de resterende tijd benutten om verbeteringen te vinden.

Spannende contest zo! 't Puzzeltje ziet er lekker simpel uit, de uitvoer en processing (filmpje van Serpie, maar ook de output op m'n console) zien er leuk uit, maar toch is er de lekkere uitdaging om een onoplosbaar probleem zo goed mogelijk proberen te benaderen.

[Serpie]

-NMe- schreef op zondag 04 maart 2007 @ 13:46:
[...]

Hoeveel tekens heeft dat grid uiteindelijk?

Dit is de grid van 2039 tekens

[H!GHGuY]

na filmpje gezien te hebben:
hmm, nu snap ik waarom jullie dat in eindige tijd kunnen...

Mijn oplossing gaat precies toch iets verder...

[ Voor 12% gewijzigd door H!GHGuY op 04-03-2007 14:19 ]

[Soultaker]

H!GHGuY schreef op zondag 04 maart 2007 @ 11:32:
raar dat jullie allemaal zo snel een werkend prog hebben...

ik heb mijn algo al geschreven maar moet de files nog uitlezen en nog redelijk wat implementatie doen om het ding werkend te krijgen...

mss het nadeel van in C++ te werken ?

Ik heb mijn code nu juist ook in C++ geschreven, omdat ik een hekel heb aan datastructuren en stringmanipulatie in C. Lekker std::strings inlezen met getline() en je grid in een deque< deque<char> > representeren maakt 't juist een stuk makkelijker.

[H!GHGuY]

Soultaker schreef op zondag 04 maart 2007 @ 14:52:
[...]

Ik heb mijn code nu juist ook in C++ geschreven, omdat ik een hekel heb aan datastructuren en stringmanipulatie in C. Lekker std::strings inlezen met getline() en je grid in een deque< deque<char> > representeren maakt 't juist een stuk makkelijker.

boost::multi_index_container met de juiste indices maakt het net nog iets makkelijker

[chris]

Erg cool filmpje. Ik denk dat ik het anders aan ga pakken, maar dit is toch ook wel nice!

[maurad3r]

Ik ben ook maar eens begonnen om wat in elkaar te knutselen. Mijn eerste resultaat over de eerste set woorden. Ik weet eigenlijk niet eens wat voor score ik heb behaald . Zou iemand het even kunnen valideren?

Testset 1, grid 1:
                                                              m        
                                                              a        
                                                              r        
                                                             liftboy   
                                c                          u  thur     
                            g   h zonzijdeviatie         k k kiakug    
               g            n   e lohoclanimretnuoc  neppalk rekkne    
               n            i pimpelen  nekkelv  torpedooliedomheer    
               a            d   i m rl   z  vfk  n  ann  kupnekortiu   
               v        kurdleiwcbmoluoc e nemrarevoreih anu p untb    
               d      b     inlautopesachilikai edicalp nreklontjed    
               nessiwfaivilcull s r ztrekvisipsajin blsiameesejsium    
          kalvjilgt   b lamsbout   teerzeepke t  vdleebmaatpakrewgad   
            zr wiaab sirolk  os    jnp leddimpassei lto b s  o     f   
       mlifroovfratsiujno    ni    u p anpore l j reffobw  krewgeovi   
       n  gfrus pdtp  b i   wgetrofuaeblichtgasfemelaarmultiple    u   
       o  n glab seizoeneehmoorvlaataneffunsr   k ckazkeoh   t     k   
       l  owiebelenteelandhallt ickaaie   kaarw eitamroft   ta     e   
   zeemacht er mzz tevigerenlfehnaapmit serafdl l     p     cn  t rg   
hoofdwasspelde pw vergenoptve o tc po myznenenekahfa cruiseseksbome    
       s  enancienenohgewueinuvsergerritneirgovksooddaaz toppingouderts
       a  zeikermisuboete rei  traineeunikfeiverminktt jiressivgp i    
    vouwdeurr kierenetnakmoseneremmalkrujnevegnissapoaw kalruuvlk r    
          eut lenimed   nootlebes nnileppezab djegatsluh m isl yn y    
          kze eeis kanen ei kz utnettee ed v   t  botal  i amercator   
         haastene nererevs r ikrr t erl ne e kledderiatilezewkeem j    
          v o dsr eitces   unereedsliks db r olnekrewni in l jirekkof  
          gni aleverendtkerkerenesabnekjirsiveez reeanekuehcsinoi      
         reelmrov  opening kmawlb l onih   jprik emzram kryucral       
          wdo g      gopdriemaneprewreps   l it  wa tv  tupnhsurpyc    
         njicupak synaps etnemedaeb alaatsteven  lagaarvitn roognah    
          iusmu      d  giletwee mu beoculistremmennah  zso obd   r    
          zddr    m  n     f ebp ejmaggi hnudevootjilv   esserpxe o    
           eroneggezmoragiffots  nh  reppiwe     valslot be f     m    
           bovenarmyobyalp anlupineggojkgnitjiwkmaarlet           o    
            blp  jb     asuperelaar sg rednim     raos  p              
            mom gireviuhb   zhnraatnaltalonr     ntamtamajyp           
            lboksbaldadig eduok wgz j  keeef     j nhh dp              
            arp sraagnohoornen  zp  r negentals  i koccult             
            gup yentuhclokeend   o  e keitsalek  l ooezue              
             uo  i smedig dik       mb lsggimmickw mghurp              
             v   h fd  taarefer  indoorecic  jftnumsapule              
               smederijuaduogfotsteozt  huitgifteo tsiroloc            
               t  bouwordeeltje breyats or  iweoevvoorkoop             
               o  ohk  gn lgordelijkwitsoodiuzuogi pl ap h             
               pg p rkwuank tstrootp n  l  ubargoensi s  o             
               br k aa  veititonedalreh s  ih ejtwueeltragicus         
              voorraad nrrenuejed weu  sulytcadiud inpandig            
               rn u museaalejlp i  cu   kaptafelaa n     n             
            l  dd i  upsnl malarm  tz   oubollig t       g             
           dafboeken krstk ekinks  ri      c  v  a                     
           wauwelen   aaap knglaanruoj     h  o                        
           ugm giegagenlvocaalenl  mo      t  r                        
     galsknohucirrusnikken kb dkp   l         m                        
           reu rid  inzageevnielk             i                        
           tirotua lnd g    j bo              g                        
           edv nmmuenirep   i  b                                       
           g a irebbag w    p                                          
             sruocrap  l g                                             
             t   pohsskesixatnys                                       
                  oce bosduif                                          
                 hdsw  k r                                             
             s  kamillegaal                                            
            lekuknimajoraat                                            
             j   dxog    b                                             
             k  simthcil                                               
             a   c a                                                   
           acrobaat                                                    
         zwartingp                                                     

[Soultaker]

Je mist 't woord strakjes.
(Verder zit je op een besparing van 1086 chars, of 33.61%)

Overigens is rauwe score berekenen vrij makkelijk:

perl -npe 's/[^\w]//g' | wc -c

[ Voor 78% gewijzigd door Soultaker op 04-03-2007 22:15 ]

[The Flying Dutchman]

Hier is een idee ontstaan dat ik zal proberen uit te werken. Het is nog wel vrij ingewikkeld dus ik moet eerst eens even heel erg hard nadenken over de juiste datastructuur. Na enig beredeneren over computatie tijd ben ik in ieder geval hoopvol dat het te doen is, maar dat zal in de praktijk nog moeten blijken natuurlijk. Hopelijk deze week nog de eerste resultaten .

[Arjan]

Al mijn verzonnen optimalisaties hebben niet het beoogde effect

ze kosten veel tijd en leveren amper winst op...als ik nog een shot op de nr.1 plek wil hebben moet ik toch even een nuttige brainfart hebben

[RobIII]

Atgast schreef op zondag 04 maart 2007 @ 23:42:
Al mijn verzonnen optimalisaties hebben niet het beoogde effect

ze kosten veel tijd en leveren amper winst op...als ik nog een shot op de nr.1 plek wil hebben moet ik toch even een nuttige brainfart hebben

Er zijn meer categorieën dan enkel score

[Soultaker]

Atgast schreef op zondag 04 maart 2007 @ 23:42:
Al mijn verzonnen optimalisaties hebben niet het beoogde effect

ze kosten veel tijd en leveren amper winst op...als ik nog een shot op de nr.1 plek wil hebben moet ik toch even een nuttige brainfart hebben

Relax; je hebt nog twee maanden om je hoofd er op te breken.

[.oisyn]

Ik moet binnenkort ook eens wat in elkaar flansen. Maar even aan alle mensen die nu resultaten aan het posten zijn: is het niet handig om af te spreken om een eenduidige score output hier neer te zetten? De ene keer lees ik de pure score, de andere keer hoeveel procent er over blijft, en weer een andere keer hoeveel procent er wordt bespaard

Persoonlijk ben ik sowieso voor een percentage (geeft een wat duidelijker beeld bij verschillende grids), en dan het liefst voor het percentage dat overblijft

[Aloys]

Inderdaad, ik zat ook al te kijken dat er nu al mensen zijn die hele algoritmes af hebben en validators. Ik doe rustig aan hoor, kan ik mooi goeie tips van andere jatten . (Wie ziet er allemaal op de middelbare school? Dat zijn vast de mensen die vorige week erg hard hebben gewerkt )

[Soultaker]

.oisyn schreef op zondag 04 maart 2007 @ 23:54:
Maar even aan alle mensen die nu resultaten aan het posten zijn: is het niet handig om af te spreken om een eenduidige score output hier neer te zetten? De ene keer lees ik de pure score, de andere keer hoeveel procent er over blijft, en weer een andere keer hoeveel procent er wordt bespaard

Dat vraagt om een poll!

Poll: Hoe resultaten posten?
• Aantal letters geplaatst (score)
• Aantal letters bespaard (chars - score)
• Percentage van letters geplaatst (score/chars)
• Percentage van letters bespaard (1 - score/chars)

^{Ook een poll maken? Klik hier}

Persoonlijk ben ik sowieso voor een percentage (geeft een wat duidelijker beeld bij verschillende grids), en dan het liefst voor het percentage dat overblijft

Ik ben voor percentage bespaard, zodat geldt hoger = beter. Verder lijkt de score redelijk af te hangen van het grid, maar met een percentage is het toch wat makkelijker om te zien hoeveel je ongeveer bespaard hebt (al is het maar dat het niet direct duidelijk is hoeveel procent 21271 van 79012 is.)

[Aloys]

Ik zie liever combinatie van procenten.. i.c.m aantal geplaatste letters. Wrom staat er geen combinatie optie?? procenten is goed voor snel kijken... Maar met een vast getal is het toch een stukje duidelijker denk ik.

[Serpie]

Aloys schreef op maandag 05 maart 2007 @ 00:26:
Ik zie liever combinatie van procenten.. i.c.m aantal geplaatste letters. Wrom staat er geen combinatie optie?? procenten is goed voor snel kijken... Maar met een vast getal is het toch een stukje duidelijker denk ik.

Vind ik ook, reden dat ik nog geen procenten heb laten zien is omdat ik het nog niet heb ingebouwd in mijn parser. Stelt niets voor natuurlijk maar goed.

Verder is het aantal letters natuurlijk officeel je score, dus waarom zouden wij alleen het percentage laten zien.

De scoretelling is simpel; het aantal letters in de grid is je score. Degene met de laagste score wint

[SeeSharp.nl]

Soultaker schreef op zondag 04 maart 2007 @ 02:58:
Ook maar wat gebouwd... het zal wel ongeveer hetzelfde zijn als wat MarcJ en Varienaja bedacht hadden, want de scores zitten ook ongeveer in hetzelfde bereik (al zijn ze iets lager dan van Varienaja):

  Grid     Words    Chars    Score        Saved
 -------- -------- -------- -------- ----------------
    01        487     3231     2040    1191 (36.86%)
    02        578     3779     2330    1449 (38.34%)
    03        560     3661     2274    1387 (37.89%)
    04        429     2771     1738    1033 (37.28%)
    05        487     3178     1997    1181 (37.16%)
    06        731     4768     2911    1857 (38.95%)
 -------- -------- -------- -------- ----------------
  Total:     3272    21388    13290    8098 (37.86%)

Hoe kom je aan die aantal woorden.
Ik kom namelijk op veel minder woorden als ik alle dubbelen en alle woorden die passen en in omgekeerde vorgorde weghaal.

Dit is mijn begin situatie wat betreft de woorden die ik moet gaan plaatsen.
- 479
- 559
- 547
- 422
- 476
- 718

Gaat trouwens over testbestand 1.

[RobIII]

SeeSharp.nl schreef op maandag 05 maart 2007 @ 10:30:
Hoe kom je aan die aantal woorden.

Misschien dat Soultaker die woorden wel helemaal niet weghaalt (dubbele) maar ze gewoon slim plaatst zodat ze alsnog 'wegvallen' in reeds geplaatste woorden van het grid?

[SeeSharp.nl]

RobIII schreef op maandag 05 maart 2007 @ 10:44:
Misschien dat Soultaker die woorden wel helemaal niet weghaalt (dubbele) maar ze gewoon slim plaatst zodat ze alsnog 'wegvallen' in reeds geplaatste woorden van het grid?

Zou inderdaad heel goed kunnen ja, niet over nagedacht

Ik heb in iedergeval het makelijkste erop zitten nu.
Nu het moeilijke gedeelte.
De theorie zit wel in mijn hoofd, maar de realisatie ervan absoluut nog niet.
Ik ga er nog eens goed over nadenken.

Leuke contest, mijn complimenten.

Succes allemaal...

[zwippie]

Ook maar eens wat eerste output van mij. Mijn validator zegt dat het klopt, maar misschien wil iemand het nog eens nakijken.

Testset_I wordset 1:

code:

naarlingeventielktzrednimpassejkartsiroloccultiempiriekenieralkviesoilocs  c eno
efceodnihhgesneebsuenipulagaarvapesachromosnuffen go jatemvererenittobsgt  atlep
ztrehallsoasatvdeiuke rlerommeljldewnagky yew glijgootmfenielkirtseizoenrvocaale
eeohoatlantaarneiurkpoiekco  bmuarrdeviezenmezesdaagswiihrdleejme voorkoopgaanen
llbmcrrocgsbniipgjkupekkuog  aeinu flaeeniartbtkiemnuulgmoemvjtirregrestopbordbi
rlaolrebbagorgelenataaljkubelastiekoengneppatomischabeltoonreseneknedebetazwemen
eeadaoeuaambeeldvosel  inraajnaamlmopnadissresipsajheeeititontnksiveezoetstoffig
hntemobosrijk kpalteklorislkanenroohmagloeiendupp obalgunucvdeettentl mz superwi
baaimve  sucigartarrplasmidejeuneregivekowwvuurlakyouparabel pk oragifzoeiuhraam
radlepssawy ednipsazt vibeadementeswprnellowri anerufiaakhroppompenijpendnjolttm
orworetehoekzaklismeikeverdriemancienaoovafrbfayneiwotlamcibverdsnjuk gzag gisji
obese ujotnsuclljaierwrk tietrtbuy rjnppogoaeonbirdorlrloadrontee irw gireviuhec
dmian rsectietounwepoeielegischoolspitteneralkpondertuee lnueaivilc ibejgtrnk sk
mevgu eifeumkybsbknotzjrzo foacecgielb odwmkikoygardemirisiugnuonlustundprogtnup
imotc nusphtlloiarehueltivnettats xnwamralazeerotmuenirepllvwt ooep riveuoo iar 
xurhl emtscheukenetsalebjibzzomerjasurfk etwgre  aeoedepaoebea triadelirium zar 
 rmce r auscdsslkwnslas wuankrewletmog e oiaeic jjdlsdopmmpmraklakkoudeutwh api 
 tiia e lsiid biagaknatleokewpemranevobi kernjiwoywbsekif pokrooble rifutdo amc 
 cglijvlaknlefatpakeieh gidnieza nydeeltjestekc gpu il wl elnoinwerken zo o dir 
 e irle aioar latd sesc v  njdfareserntacruises grozwijmelzuej l umnng ic g dta 
 lmhteligfit  oiau suuegaznitoerefargsnikkensnm eov ftgstadouanierieam oh   oom 
 pacidnahf n  oraolewmhnk  wilokif ie uvletgalsknoh aeaesteczmtuobsmal ot   oo  
  takrakeele  nemgeribdin  nneruza jn meeri l smedigilletsgue  n  umni l    sp  
  mtsoodiuzg  gf fbpninpandigphrep    sdeer k t kne  rmmaialn  e  rekf       k  
  aa g  dr e  of ouxd opre  aecdnekahfaidnf   r kiribabaardig  e  ptor       n  
  tl       n klontjevthopd valslot    pc      e u o eaoilknsliftboy mo       a  
   a          fb sn anetsaahdpue       a      d r v dmrsepoth  s  c so       m  
   a             ae nekkelv nacip      l    wauwelene dpd bay       tv          
   n            hvd gm   rl apiw       p      o w r l uin eyp   w   r           
   r           maritiem  eivvgm               g r   nautogeen   a   e           
   u            kuudak   hjibreih              femelaarsr nrouleren m           
   o            hudnaabwuotsluh                 p   pnleg w s   t   m           
   j            ome wk     s tc                 s weghonenekeobfa   e           
                u b z      e i                       eo k r     a   n           
                t       nekrelk                      fp u k     l               
                           i                            i                       
                           j                            f                       
                                                        d

2080 over van de 3231 : 64%

[Marcj]

zwippie schreef op maandag 05 maart 2007 @ 13:15:
Ook maar eens wat eerste output van mij. Mijn validator zegt dat het klopt, maar misschien wil iemand het nog eens nakijken.

Testset_I wordset 1:

code:

naarlingeventielktzrednimpassejkartsiroloccultiempiriekenieralkviesoilocs  c eno
efceodnihhgesneebsuenipulagaarvapesachromosnuffen go jatemvererenittobsgt  atlep
ztrehallsoasatvdeiuke rlerommeljldewnagky yew glijgootmfenielkirtseizoenrvocaale
eeohoatlantaarneiurkpoiekco  bmuarrdeviezenmezesdaagswiihrdleejme voorkoopgaanen
llbmcrrocgsbniipgjkupekkuog  aeinu flaeeniartbtkiemnuulgmoemvjtirregrestopbordbi
rlaolrebbagorgelenataaljkubelastiekoengneppatomischabeltoonreseneknedebetazwemen
eeadaoeuaambeeldvosel  inraajnaamlmopnadissresipsajheeeititontnksiveezoetstoffig
hntemobosrijk kpalteklorislkanenroohmagloeiendupp obalgunucvdeettentl mz superwi
baaimve  sucigartarrplasmidejeuneregivekowwvuurlakyouparabel pk oragifzoeiuhraam
radlepssawy ednipsazt vibeadementeswprnellowri anerufiaakhroppompenijpendnjolttm
orworetehoekzaklismeikeverdriemancienaoovafrbfayneiwotlamcibverdsnjuk gzag gisji
obese ujotnsuclljaierwrk tietrtbuy rjnppogoaeonbirdorlrloadrontee irw gireviuhec
dmian rsectietounwepoeielegischoolspitteneralkpondertuee lnueaivilc ibejgtrnk sk
mevgu eifeumkybsbknotzjrzo foacecgielb odwmkikoygardemirisiugnuonlustundprogtnup
imotc nusphtlloiarehueltivnettats xnwamralazeerotmuenirepllvwt ooep riveuoo iar 
xurhl emtscheukenetsalebjibzzomerjasurfk etwgre  aeoedepaoebea triadelirium zar 
 rmce r auscdsslkwnslas wuankrewletmog e oiaeic jjdlsdopmmpmraklakkoudeutwh api 
 tiia e lsiid biagaknatleokewpemranevobi kernjiwoywbsekif pokrooble rifutdo amc 
 cglijvlaknlefatpakeieh gidnieza nydeeltjestekc gpu il wl elnoinwerken zo o dir 
 e irle aioar latd sesc v  njdfareserntacruises grozwijmelzuej l umnng ic g dta 
 lmhteligfit  oiau suuegaznitoerefargsnikkensnm eov ftgstadouanierieam oh   oom 
 pacidnahf n  oraolewmhnk  wilokif ie uvletgalsknoh aeaesteczmtuobsmal ot   oo  
  takrakeele  nemgeribdin  nneruza jn meeri l smedigilletsgue  n  umni l    sp  
  mtsoodiuzg  gf fbpninpandigphrep    sdeer k t kne  rmmaialn  e  rekf       k  
  aa g  dr e  of ouxd opre  aecdnekahfaidnf   r kiribabaardig  e  ptor       n  
  tl       n klontjevthopd valslot    pc      e u o eaoilknsliftboy mo       a  
   a          fb sn anetsaahdpue       a      d r v dmrsepoth  s  c so       m  
   a             ae nekkelv nacip      l    wauwelene dpd bay       tv          
   n            hvd gm   rl apiw       p      o w r l uin eyp   w   r           
   r           maritiem  eivvgm               g r   nautogeen   a   e           
   u            kuudak   hjibreih              femelaarsr nrouleren m           
   o            hudnaabwuotsluh                 p   pnleg w s   t   m           
   j            ome wk     s tc                 s weghonenekeobfa   e           
                u b z      e i                       eo k r     a   n           
                t       nekrelk                      fp u k     l               
                           i                            i                       
                           j                            f                       
                                                        d

2080 over van de 3231 : 64%

Grid: 1
Score: 2080
Percentage van max: 64

Netjes

[zwippie]

Dankje

[Serpie]

Aloys schreef op zondag 04 maart 2007 @ 23:57:
Inderdaad, ik zat ook al te kijken dat er nu al mensen zijn die hele algoritmes af hebben en validators. Ik doe rustig aan hoor, kan ik mooi goeie tips van andere jatten . (Wie ziet er allemaal op de middelbare school? Dat zijn vast de mensen die vorige week erg hard hebben gewerkt )

Ik zit niet op school, ik werk gewoon van 8 tot 5 en studeer daarnaast aan de OU.

Mijn algoritme is niet zo heel bijzonder volgens mij, en de tijd die ik er in heb zitten valt nog erg mee maar ik ben wel gelijk begonnen toen de contest bekend was .

Ik verwacht dan ook niet te winnen, de reden dat ik mee doe is vooral om ervaring op te doen. Het is heel wat anders dan wat ik dagelijks op mijn werk aan programmeer werk doe, dus ik moet op een hele andere manier gaan denken.

Ik hoop dat ik wel een beetje in de top eindig en ben zeer benieuwd naar de andere implementaties, ik kan me niet zoveel voorstellen bij een implementatie die oneindig doorgaat en met een resultaat komt als je hem stopt. Maar ik wacht het af en zal zeker de sources bekijken.

[Zyppora]

Nadat ik besloten had om mee te doen (waarschijnlijk in Python, maar misschien wordt het toch Java), was de eerste vraag die bij mij opkwam: is het ook toegestaan om in 3 dimensies te werken (dus niet alleen horizontaal en vertikaal). Maja, probeer dat maar eens in een txt file te dumpen Het idee was leuk though.

Ik zal kijken of ik hier iets nuttigs kan proggen Succes aan iedereen btw.

[DaCoTa]

Zyppora schreef op maandag 05 maart 2007 @ 16:43:
is het ook toegestaan om in 3 dimensies te werken (dus niet alleen horizontaal en vertikaal). Maja, probeer dat maar eens in een txt file te dumpen Het idee was leuk though.

Ik zie een uitdaging: een extra parameter dat het aantal dimensies aangeeft

[zwippie]

3d output gaarne aanleveren in deze vorm:

  __
 /l /|
/__/ |
| o|l|
|__|/

[DaCoTa]

Even de competitie op scherp zetten, 2009 op grid 1:

                                      n                        
                                      e                        
           e h                        m                        
           t o                        m                        
           f o                        e                        
           i r                      stramien                   
           g n                      u t                        
           t e                      c s                        
          liuneets                  i i                        
         bouwordettenurb          h m u                        
             h j    e            zomerjas                      
             gnitjiwk        pacidnahangoor                    
             e zdrukraam          g cao   e                    
             w nelebeiw      l   kanklob  i                    
             lbov   w  lepelpap maarletgiur                    
            neoziesonpyh yobyalp  r  rl j e                    
     nettatsmoknaapmit   jmurtcelpsdneekolohoclaanruoj         
         f   kset eodiehgaal s  z    pb g k                    
         t t  bii rrn   imgs t  edargpu g                      
         e n naue whonkslagtrekvisserijkelui                   
         lnezelrehechtseljireva k mduw  n                      
         lem ndk  reelmrovlobeademente                         
        bedelnap openingb eodnihr iii                          
         nak ido  e    eu tt fareskmlifroov                    
          lafwissen gimroviestarfte                            
          rk ng     vuurbolw iw fov h                          
          e  i dlepssawionemewz ofegadnob                      
          h    neruert trdma k  bfrukkepukj                    
            spindejeuneremmalj  cig h joyrider                 
             n  nd  oao ezorgiegagenopt   r                    
   n  g    reehmod  cln z rl laatan uknatleok                  
   e  l     wijnrek rtl t ea e fargetrouwdk     g              
   m  y      o egl  aau rllahds lo bmoluock     o              
   r  c      o gik  pvsmedig rukavgewek noo     r              
   a  e      l gdn zeetoheteropna neppatelfmap ng              
   r  r  f   v erebbagoogbalgbeenwerkoznkothcameez   s         
  nepmoppo n  tzaknw iprooilmarccu t ekaarw    rl    g         
kalvjilgordellimakeuzeevisrijkenierukkenhi z  neegotua         
   z n   m k srobeml bslpgim nb einu hoefstalneknedeba         
   w kaptafelyo glme skirtseraagnn j  hpat anekrelkurdleiw     
   a u   t o ntoovednepjinud baaio vs up a dbireg   rs g       
   rik   i beaufortemeitluccounterminalarmadreekejtleedicalp   
 latnegeneffapaeh mp m  ipicashklareedsl tmo eititonyz d       
 gnidliubhcalslom inzageh gccmeikb feutk auo  nellowae n       
   ni         nro u  ivocaalasfruspohoatomischabelastenaabwuot 
   gr         ihdcruisesurricimpassemggsimrekkutb jusr p       
    e         tcepsus     tv r     jofe  cicero jraroodnileppez
    c expressejsium sloohcsinoir  itsot ltltgidniespotsiluco   
    t    simthcil l  i museaalseomkantenereikje bipyda         
          f  i go a  u    rz k i   wisoevidentp aficicg        
          i  lnessalkk    eu   z    ktbsead aer besturen       
          utolslavt  t h  traineesjekelandi rno  zlezewk       
          dfiukegirtni c  nezuenkoudeolbdem p t    lemjiwz     
gnigohpohsskes etga  zpassingypekanenzym    s  s jibreih       
       g bosrijkhewtnumsap toopknameird  p  elpitlum nz        
       neebsuenacrsnuffenittobeea rlp    a  w  x     n         
      taareferrriec    p thcottiujakuudakrewletaaborca         
       v  d ltaklnh   nestipsfsrw kalruuvandaagt   u a         
       d  u kea peezreettent iai  l a    bargoens  e g         
       n  i ioj gouderts neralkpomaatpakrewgad y   f p         
       i  deevnielk   shieroverminkts gnilraan sawdfooh        
       w  e l adleebmaac rejtwueelskipia    r      i n         
          n tnarvannavahperineumeitiramb    v      k d         
             emo      huiverigz     k mn           s e         
             znb    leitnevegnippot   ij             r         
             eemf t t  nel dpoolruud  ci                       
            gilletsaanredrueltoogjilg kp                       
             veam aaa  yipimpelen                              
           krewgeovtr   mobskesoilocs                          
             du l rao   sk   z  n                              
              a a udj   arouleren                              
              w a uwassalonraatnal                             
             naarbmem   pookroovp                              
                   i     b      s                              
                   v                                          

Vraag niet na hoelang rekenen