Programming Contest Nieuwe Stijl: Contest 2 *WINNAARS LEZEN*

[RobIII]

--selecteer--IndexInhoudsopgaveInleidingDe opdrachtDetailsDe scoretellingDe regels en andere afsprakenWat kan ik eigenlijk winnen?Om je op weg te helpenTot slot...

Programming Contest Nieuwe Stijl: Contest II

Inhoudsopgave

• 1: Inhoudsopgave
• 2: Inleiding
• 3: De opdracht
• 4: Details
• 5: De scoretelling
• 6: De regels en andere afspraken
• 7: Wat kan ik eigenlijk winnen?
• 8: Om je op weg te helpen
• 9: Tot slot...

« ·^

Inleiding

Na het daverende succes van de vorige PRG Contest is hier dan eindelijk deel II. Ook in dit deel zullen wij, als crew, weer trachten een leuke contest op te zetten die:

• uitdagend is, maar niet te hoogdrempelig; iedereen moet in principe mee kunnen doen
• niet te langdradig; het blijft een leuk 'spelletje' om aan mee te doen en de uitslagen zijn niet pas in 2009 bekend
• niet platform of programmeertaal gebonden; van PHP tot ASM, van C# tot Java: iedereen is welkom
• niet te serieus; er worden geen gouden bekers of schalen uitgereikt. Wat je wél kunt winnen is eeuwig restecp van mede GoT-ters.

Ook deze contest proberen wij als crew weer te begeleiden en te sturen; we zullen ons niet te veel met de contest an sich bemoeien maar zijn wel aanspreekpunt voor vragen omtrent de opdracht, regels en uitslagen. Uiteraard zijn we zelf voor de uitslagen van deelneming uitgesloten (we winnen anders toch alleen maar ), maar het is goed mogelijk dat iemand (of meerdere iemanden ) ook een potje met jullie meespelen om te zien hoe wij ranken t.o.v. jullie

« ·^

De opdracht

We hebben ons best gedaan ook deze keer weer een leuke contest te verzinnen; wat hierna volgt is de opdracht. Lees deze aandachtig door, alle informatie die je nodig heb om aan deze contest mee te doen staat er in. Schroom niet om te vragen als je nog onduidelijkheden denkt te hebben gevonden, maar verzeker je ervan dat de informatie niet in deze opdracht staat voordat je dat doet.

De bedoeling

De bedoeling is als volgt: we gaan puzzelen met woorden. Je krijgt van ons een bestand aangeleverd met woorden; nederlandsche woorden om precies te zijn. Elk van deze woorden is puur willekeurig gekozen. Deze woorden dienen in een zo klein mogelijk vlak te worden geplaatst, horizontaal (van links naar rechts of omgekeerd) of verticaal (van boven naar beneden of omgekeerd). Daarbij dienen letters van reeds geplaatste woorden ge/herbruikt worden zodat het totale 'grid' uiteindelijk als een soort kruiswoordpuzzel in elkaar gepast is. Het is verplicht om de woorden zowel horizontaal als verticaal te plaatsen, en de bedoeling om woorden zo veel mogelijk te laten kruisen/overlappen.

De kunst

De kunst is om deze woorden in een zo klein mogelijk 'grid' te plaatsen, het uiteindelijke aantal letters in het 'grid' wordt gebruikt voor de scoretelling.

« ·^

Details

Er wordt een bestand, words.txt, aangeleverd met daarin de woorden die je in het grid dient te plaatsen. De woorden worden gescheiden door een CrLf ("enter" ofwel \r\n). Deze woorden zijn gegroepeerd middels één of meerdere lege regels, met een maximum van 99 groepen in het bestand. Met iedere groep woorden dient een grid te worden gevormd waarin alle woorden uit die groep zijn geplaatst (horizontaal dan wel verticaal, zoals beschreven in 'de bedoeling'). Iedere groep bevat minimaal 5 en maximaal 999 woorden. De output dient het grid te zijn, in een ASCII bestand, waarbij de horizontale regels worden gescheiden door CrLf. Iedere groep wordt in een eigen uitvoer bestand geplaatst, genaamd grid01.txt, grid02.txt enzovoorts. Whitespace in de in- en uitvoer bestanden wordt gerepresenteerd door een spatie. Woorden kunnen of mogen lower én uppercase karakters bevatten in zowel de in- als uitvoer bestanden. A en a zijn dus uitwisselbaar.

Eventueel 'nieuwe' woorden, die dus niet voorkomen in het aangeleverde words.txt, die worden gevormd bijvoorbeeld door het horizontaal onder elkaar plaatsen van woorden worden niet in ogenschouw genomen. Degene met de minste punten wint de contest op het vlak van de scores. Alle in- en uitvoer bestanden dienen te worden gelezen en geschreven in dezelfde directory als de executable (of het script). In- en uitvoer bestanden zijn ASCII, géén extended ASCII.

« ·^

De scoretelling

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

« ·^

De regels en andere afspraken

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

1. Inzendingen voor de contest stuur je naar [e-mail]; neem daarbij in de subjectregel de tekst "Inzending PRG Contest 2" op en vernoem in de email zelf je nickname. Zet de bestanden niet ergens publiek neer voordat de sluitingsdatum is bereikt, om het zo voor iedereen leuk te houden. Stuur bovendien geen code op waar je niet 100% achter staat. Je eerste inzending is de enige inzending die telt, een tweede inzending zullen we niet in ogenschouw nemen.
2. De sluitingsdatum van de contest is 1 mei 2007. Elke inzending die binnenkomt ná 30 april 2007 om 23:59:59 is helaas uitgesloten van deelneming, zonder uitzondering.

   We hebben bewust een datum gekozen die nog redelijk ver in de toekomst ligt, zodat niemand echt tijdsdruk zal ondervinden en zoveel mogelijk mensen mee kunnen doen. Daarnaast is het niet de bedoeling dat je werk er onder gaat lijden

3. Neem in je mailtje een zip- of rar-file op met daarin een uitvoerbare versie van je programma én je programmacode.

   In het geval van scripttalen zoals PHP is één bestand uiteraard voldoende.

4. Je mag elke programmeertaal gebruiken die je wilt, met uitzondering van Brainfuck.
5. Samenwerken mag, maar meld het wel even als je dit doet. Neem in je inzendingsmailtje de nicknames van alle programmeurs op.
6. De ingestuurde zipfiles worden na de contest publiek gemaakt, inclusief je sourcecode. Als je hiertegen bezwaar hebt, dan kun je beter niet meedoen. Uiteraard staat het je vrij om elke willekeurige opensource licentie aan je code te verbinden en de credits liggen uiteraard gewoon bij jou.
7. Het geven van foute uitvoer betekent sowieso dat je game over bent en je dus geen punten krijgt.
8. Alle genoemde tekstbestanden bevinden zich in dezelfde directory als het uitvoerbare bestand van je programma; dat betreft dus uitvoer én invoer.
9. Als je programma langer dan één uur nodig heeft om te runnen op de pc die je score berekent, dan heb je pech. Na één uur wordt je applicatie gestopt en alleen de uitvoer die op dat moment in je gridxx.txt bestand zit wordt gebruikt voor het berekenen van je score. Je kan ervan uit gaan dat de pc waarop je programma gerund wordt sneller is dan de gemiddelde consumentenpc, maar probeer je programma zo snel mogelijk te houden.
10. Het heeft geen zin om bij moderators te gaan vragen naar de uiteindelijke lijst met woorden. Deze file wordt namelijk pas ná de sluitingsdatum überhaupt gemaakt, dus we kúnnen je die files niet geven, zelfs al zouden we het willen. Natuurlijk geven we uiteindelijk wel de precieze files vrij, samen met de uitslag van de contest, en niet eerder dan dat om zo een beetje de spanning erin te houden.

Daarnaast verwachten we ook zinnig én voldoende commentaar in je code; zoals je in productiecode zou verwachten. Dit omdat wij ook de code willen/gaan beoordelen.

Behalve de winnaar in de categorie "laagste score" en "snelste code" zullen er nog winnaars zijn in diverse andere categoriën, waaronder o.a. de categorie 'beste defensive code' (code die goed tegen een stootje kan zoals bijvoorbeeld een 'beschadigd' words.txt bestand of een words.txt bestand dat niet voldoet aan de specificaties). Hierbij is het mogelijk dat één persoon in meerdere categoriën de winnaar is.

« ·^

Wat kan ik eigenlijk winnen?

Nou, dat is vrij simpel: niks. Het enige dat je mogelijk aan deze contest overhoudt is eeuwige roem en de eer om de tweede contest in dit nieuwe format gewonnen te hebben.

« ·^

Om je op weg te helpen

Om je op weg te helpen kun je hieronder 3 testbestanden downloaden welke als voorbeeld dienen van de uiteindelijke bestanden zoals wij die gaan gebruiken om jullie inzending op los te laten.

Testbestand I
Testbestand II
Testbestand III

Daarnaast ben je, net als in vorige contest, vrij om zelf een 'validator' te schrijven (en online te zetten) om te controleren of je uitvoer voldoet aan de eisen. Wij, de crew, zullen onze eigen validator inzetten om de uiteindelijke uitvoer van jullie inzendingen te controleren. Laatstgenoemde blijft, in ieder geval tot na de deadline, intern en is dus niet voor jullie beschikbaar.

« ·^

Tot slot...

...willen we jullie natuurlijk (weer) heel veel succes wensen. We hopen dat je er plezier in gaat hebben om aan deze contest mee te doen, en natuurlijk hopen we dat je niet de enige bent. Hoe meer competitie, hoe beter!

May the force be with you!

[Voor 100% gewijzigd door RobIII op 27-02-2007 10:41]

[RobIII]

--selecteer--IndexInzendingenUitslagenPrijzen?!Afsluiting

Inzendingen en uitslagen

Inzendingen

Hieronder vind je alle inzendingen die we binnen de deadline hebben ontvangen. De volgorde van deze lijst van inzendingen is alfabetisch en zegt niets over de behaalde score.

Arjan

Download: hier
Taal/omgeving: C++

Quote uit bijgaande email:

---

Bij deze mijn inzending, ik heb geen backtracing gebruikt, dus er zit een limiet aan de kwaliteit van de oplossing. Echter zou hij binnen een uur moeten stoppen wanneer blijkt dat hij langer nodig zou hebben voor de beste oplossing.

---

Arty_Shock

Download: hier
Taal/omgeving: C#

Quote uit bijgaande email:

---

De opdracht is gemaakt met behulp van Visual Studio 2005 en vereist dat de testmachine is voorzien van Microsoft.Net framework 2.0. De executable is op te starten vanaf de commandline en verwacht een words.txt bestand in de current directory. Als eerste parameter is eventueel een pad op te geven naar een ander inputbestand. Output van de gridxx.txt bestanden vindt ook in de current directory plaats. Mja, dat was het wel.

---

cobratbq

Download: hier
Taal/omgeving: Java

Quote uit bijgaande email:

---

Hier mijn oplossing. Resultaten zullen redelijk zijn, maar ik heb zeker
genoten van de opdracht.

Ik stuur een executable JAR-file mee op, gegenereerd door Eclipse, waar
zowel de gecompileerde bestanden als de sources in zitten. Ik had
begrepen uit forum-posts dat dit voldoende is voor jullie?!?

Ik stop er geen readme bij, want er valt niet meer te doen dan de
JAR-file te starten in de map waar ook de 'words.txt' file staat. (Zoals
in de opdracht omschreven.) En er zit, naar mijn idee, voldoende
code-documentatie tussen ze source files om de werking uit te leggen.

---

DaCoTa

Download: hier
Taal/omgeving: Java

EdwinG

Download: hier
Taal/omgeving: PHP

Quote uit bijgaande email:

---

Hierbij mijn inzending voor de 2e programmeer contest. Net zoals vorige keer weer geschreven in php. Gemaakt en getest op Linux, maar werkt ook prima onder Windows. Helaas door tijdgebrek een erg eenvoudig systeem geworden.

Als bij het uitvoeren blijkt dat bestanden met de naam gridXX.txt al bestaan, zullen deze aan het begin verwijderd/geleegd worden. Informatie over fouten verschijnen gewoon in het scherm, en wordt niet opgeslagen.

---

Fiander

Download: hier
Taal/omgeving: C#

Quote uit bijgaande email:

---

DotNetFramework 2 zou voldoende moeten zijn.

---

H!GHGuY

Download: hier
Taal/omgeving: C++

Quote uit bijgaande email:

---

Ik was eerst niet van plan om mijn programma in te zenden (het is ook niet helemaal af)
maar omdat het anders zonde van de tijd zou zijn...

In bijlage zit een rar-file (hernoemd voor eventuele attachment blockers).
Wanneer je de file unpackt zitten er 2 .sln files in voor VS.NET 2003 en VS.NET 2005.
Ik heb het programma ook geport naat linux, maar die versie heb ik op deze PC niet bij.

In de rar-file zitten ook GoTWords.exe en een run.bat script.
De reden is dat de exe volgende commandline opties heeft:
GoTWords.exe <file> [<set nummer>]
(ik was te lui om multi-threading en timing support in mijn prog te steken)

De run.bat laat toe om een words.txt file met een maximum van 40 sets
tegelijk te starten. (mochten er meer zijn dan kan de eenvoudige structuur van
run.bat aangepast worden).

Het programma stopt na 10000 iteraties wat voor 1 set soms wel een kwartier kan duren.
Daarom ook dat het run.bat script meerdere instanties tegelijk opstart.
Jullie zullen waarschijnlijk het programma moeten stoppen als het de
toegestane tijd overschrijdt.

---

hij

Download: hier
Taal/omgeving: C++

Quote uit bijgaande email:

---

Hierbij treffen jullie mijn inzending aan bovengenoemde contest. Bijgevoegd
is een .zip file met daarin twee Win32/W2K executables en wat C++ code.
File _README.TXT geeft een beschrijving hoe het programma te gebruiken is.

---

KoW

Download: hier
Taal/omgeving: Visual FoxPro

Quote uit bijgaande email:

---

Onderstaande link bevat mijn inzending voor deze contest.
Op de valreep is het toch nog gelukt om mijn oorspronkelijke routine terug op te bouwen. Dat brengt natuurlijk ook weer wat bugs met zich mee.
Het had wel als extra voordeel dat ik nu ook code heb ingebouwd om in geval van gecrashte threads dat grid door een andere thread nogmaals te laten berekenen.

De zip bevat een mapje source met de code en een mapje Distribution met de executables. In de root staat een omschrijving van het programma.

Het is op zich heel simpel, plaats het geheel in een mapje waar het proces schrijfrechten op heeft, zet een words.txt over mijn testbestand heen en start GoT.exe
Het programma zal zelf een mapstructuurtje aanmaken en wat hulptabellen genereren. De grid01 t/m grid99 bestanden worden in de hoofdmap geplaatst.
In het bestand log.txt is te zien hoe het programma "loopt" De laatste regels daarvan worden in een formpje getoond.

De resterende tijd die wordt weergegeven is indicatief al zal hij ovr het algemeen eerder te negatief zijn dan dan hij extra tijd neemt.
Wanneer tijdens de uitvoer de systeemtijd wordt aangepast negeert het programma dat en gaat gewoon verder tot zijn tijd op is.

Door op het kruisje te drukken geef je een abort commando waarmee de threads stoppen.

Het programma is alleen getest op Windows XP. Helaas heb ik geen Vista tot mijn beschikking.

---

MarcJ

Download: hier
Taal/omgeving: Java

Quote uit bijgaande email:

---

Hierbij mijn inzending voor the tweede programmeercontest. De source zit deze keer wel goed in de jar ingepakt. Het makkelijkste is echter gewoon een word.txt bij deze jar in de map zetten en dan de jar starten. Dit kan makkelijk met "java -jar WordGrid.jar".

---

Nick The Heazk

Download: hier
Taal/omgeving: Java

Quote uit bijgaande email:

---

bij deze mijn inzending voor de programming contest. Ik zou jullie graag willen waarschuwen. Wegens het tijdgebrek heb ik de code niet meer kunnen oppoetsen. Normaliter ging ik ze voor deze reden niet insturen--echt het is afschuwelijk :) .

De jar bevat de source bestanden en is zo uitvoerbaar. Het programma stopt niet uit zichzelf, maar ik denk dat het bij deze implementatie sowieso niet op een paar seconden zal steken :) . Het lijkt me aangeraden om de jar in een console of IDE te draaien, zodanig dat men toch nog enige vorm van I/O heeft (buiten het schrijven van de bestanden natuurlijk). Het programma aanvaardt geen invoerargumenten en is zo robuust als de gemiddelde kaartentoren :+. Het programma vereist dat het words.txt bestand in dezelfde directory staat als de executable zelf. De output wordt ook in deze directory geplaatst.

---

Robbbert

Download: hier
Taal/omgeving: C

Quote uit bijgaande email:

---

Ik heb uiteindelijk te weinig tijd gehad om van de code nog wat fatsoenlijk leesbaars van te maken.
De code werkt, maar daar is dan ook alles mee gezegd :P

Compilen kan met GCC, ik heb zelf DevC++ gebruikt.

---

Serpie

Download: hier
Taal/omgeving: VB.NET 2.0

Quote uit bijgaande email:

---

Hierbij de inzending voor Serpie

De zip bevat 2 mappen, source waar de source in zit en in de map inzending zit de exe voor de contest.
Het is geschreven in vb.net 2.0, je hebt dus het dotnet 2.0 framework nodig om hem te runnen, daarnaas geen vereisten.

---

Soultaker

Download: hier
Taal/omgeving: C++

Quote uit bijgaande email:

---

Bij deze mijn inzending voor Programming Contest nummer 2! Executables voor 32-bits Windows zijn bijgevoegd:
- checker.exe: berekent score voor grids in huidige directory
- player.exe: single-threaded player (GCC 3.4)
- player-mt.exe: multi-threaded player (ICC 9.1)
- player-mt-sse3.exe: multi-threaded player voor Pentium 4 met SSE3 instructies (ICC 9.1)

Gek genoeg is de performance van de eerste lokaal verreweg het beste (Intel's binary is maar liefst 30% trager!), maar die is helaas niet multithreaded (aangezien ik GCC 4.2 met OpenMP niet gecompileerd kreeg onder Windows). Gebruik dus bij voorkeur de multi-threaded versies op een multicore systeem (die met SSE3 zou het snelste moeten zijn, maar kan ik lokaal niet testen), en de single-threaded versie op een singlethreaded (en/of niet-Intel) systeem.

Ik kwam er net achter dat er een stomme bug in m'n inzendig zit. Hij doet niet
zoveel zinnigs als de uitvoerbestanden ("gridXX.txt" enzo) niet aanwezig
zijn. Gelieve die dus van te voren aan te maken, om er ueberhaupt resultaten
uit te krijgen. Ze worden dan vanzelf overschreven met een oplossing.

Verder niets bijzonders; gewoon starten in de goede directory en afwachten maar.

---

veldsla

Download: hier
Taal/omgeving: R-Project

Quote uit bijgaande email:

---

Mijn inzending! Hij runt in R, dat is dus een taal! Er zit een README
bij waar hopelijk duidelijk in staat hoe je het moet runnen.

---

wwwhizz

Download: hier
Taal/omgeving: Java

Quote uit bijgaande email:

---

Hierbij mijn inzending voor de programming contest deeltje 2. Het is geschreven in java, en zal dus ook moeten worden uitgevoerd in java... Ik heb geprobeerd er een .jar van te maken maar dat gaf allerlei foutmeldingen en toen had ik er geen zin meer in... Dan maar een .rar :+

Wat ik heb gedaan:
- Ik zorg eerst er voor dat overlap binnen het begin en eind van een woord wordt weggefilterd (dmv een trie)
- Vervolgens sorteer ik de woorden die dat oplevert op lengte en begin met de grootste (in een arraylist)
- Dan ga ik dat lijstje af en zoek voor elk woord de positie met de meeste overlap en zet ze dan in een tweedimensionaal array (die eventueel wordt vergroot)
- Aan het eind van het lijstje maak ik er een bestand van en ga verder met de volgende
- Steeds worden wat leuke stats gemeld over het zojuist gemaakte grid (kan er eventueel wel uit om het nog íetsje sneller te maken)
- Aan het eind wordt nog even vermeld hoelang hij er mee bezig is geweest...
Zie ook readme.txt.

Het opstarten kan gewoon in een console/Command Window dmv het commando 'java WordGrid' (zonder quotes natuurlijk); ik heb het in Windows XP gemaakt met de Java SDK 6.0 en Eclipse.

---

zwippie

Download: hier
Taal/omgeving: Java

« ·^

Uitslagen

And the votes are in! We hebben alle inzendingen één keer volledig laten lopen met deze woordenlijst.

Na het runnen van de tests, wat overigens op -NMe-'s pc gebeurd is, zijn Creepy, -NMe- en ik ieder voor zich in de code van alle inzendingen gedoken, en hebben daar scores aan gehangen. We hebben daarbij onder andere gelet op coding style, de aanwezigheid of afwezigheid van goed, duidelijk commentaar, en de kwaliteit van het gebruikte algoritme. We hebben hier voor iedereen punten aan toegekend, en op basis daarvan nog wat categoriën gevuld met scores.

En dan nu, zonder verder uitstel: de scores!

Scores

1. Soultaker met 331 punten.

   Hoewel deze inzending in de eerste instantie gediskwalificeerd werd omdat Soultaker er vanuit ging dat de grid-bestanden van tevoren al bestonden, bleek al snel dat het wél de beste oplossing was. Na veel gediscussiëer werd besloten hem te diskwalificeren, tot we erachter kwamen dat we eigenlijk nergens in de regels hadden gesteld dat het die bestanden door het programma aangemaakt moesten worden. Soultaker heeft dus toch gewonnen, maar is wel door het oog van de naald gekropen.

   Run-tijd: 52 minuten.

2. KoW met 448 punten.

   KoW wist nét binnen de tijd alle grids te voltooien en weg te schrijven, met een zeer mooie score. Een verdiende tweede plaats.

   Run-tijd: 57 minuten.

3. zwippie met 470 punten.

   zwippie's oplossing volgt die van KoW op de voet, maar was wel iets sneller klaar. Nek aan nek, maar toch derde.

   Run-tijd: 51 minuten.

4. wwwhizz met 626 punten.

   Bijzonder snelle inzending die bovendien een zeer respectabele score wist neer te zetten.

   Run-tijd: 1½ minuut.

5. Arjan met 694 punten.

   Slimme oplossing die tijdens de run kijkt hoeveel tijd er nog is en daar het verdere programmaverloop op aanpast. Mooi geprogrammeerd!

   Run-tijd: 54 minuten.

6. MarcJ met 714 punten.

   De winnaar van onze vorige contest wist het dit keer niet klaar te spelen om alle grids af te krijgen. Hoewel hij een respectabele score neerzet, kreeg hij maar 67 grids af, waarna het programma gecancelled werd.

   Run-tijd: 1 uur.

7. Arty_Shock met 757 punten.

   Degelijke, snelle oplossing. Goede middenmoter wat betreft score, toppertje wat betreft tijd.

   Run-tijd: 2 minuten.

8. Fiander met 764 punten.

   Deze app wierp meteen een foutmelding op, maar bleef toch doorlopen en wist uiteindelijk 81 grids aan te maken voordat de applicatie na een uur gecanceled werd.

   Run-tijd: 1 uur.

9. EdwinG met 899 punten.

   In dit script werd, net als bij de vorige contest, de uitvoer pas op het allerlaatste moment weggeschreven. Erg riskant, maar ook dit keer pakte het niet verkeerd uit. EdwinG's inzending wist alle grids te maken binnen de gestelde tijd.

   Run-tijd: 45 minuten.

10. cobratbq met 1282 punten.

    cobratbq wist 48 grids te parsen binnen een uur, waarna de applicatie gestopt werd.

    Run-tijd: 1 uur.

11. H!GHGuY met 1453 punten.

    Deze inzending was creatief in de zin dat de applicatie 40 verschillende processen (en vensters) opende die ieder voor zich een eigen grid op gingen lossen. Helaas betekende die creativiteit niet meteen ook een voordeel, aangezien er maar 26 grids gemaakt waren voordat de applicatie na een uur gestopt werd.

    Run-tijd: 1 uur.

12. hij (buiten mededinging) met 1673 punten.

    Omdat hij in zijn eerste inzending vergeten was een debugwaarde aan te passen kregen we twee inzendingen van hem. Aangezien de eerste inzending geldt kan deze inzending niet meetellen voor een prijs, maar we noemen hem wel in de scores. Helaas kreeg deze inzending het ook niet klaar om meer dan 12 grids te maken binnen de gestelde tijd.

    Run-tijd: 1 uur.

13. Nick The Heazk met 1728 punten.

    Ook Nick's inzending wist na een uur niet meer dan 12 grids te produceren.

    Run-tijd: 1 uur.

14. hij met 1780 punten.

    Dit is hij's eerste inzending, waarin hij slechts 6 grids af kreeg door een fout ingestelde waarde in zijn programma.

    Run-tijd: 1 uur.

15. DaCoTa met 1864 punten.

    DaCoTa's script had na een uur gedraaid te hebben geen grids voltooid; wel was er een half geplaatst grid, waar nog score aan verbonden is.

    Run-tijd: 1 uur.

16. Robbbert met 1881 punten.

    Na nog geen seconde gedraaid te hebben wist dit programma ons te vertellen dat groep 17 te weinig woorden bevatte, en daarom stopte wegens een foute woordenset. Nou bevatte groep 17 exact 5 woorden, dus dat lijkt op een klein foutje. Aangezien het programma meteen afsloot in plaats van verder te gaan met de andere groepen werden er geen grids aangemaakt.

    Run-tijd: 1 seconde.

17. Serpie met 1881 punten.

    Ook Serpie's inzending gaf er na een minuutje de brui aan. Er zou een exception zijn geweest die niet afgehandeld werd. Ook voor deze inzending was er dus geen grid-uitvoer.

    Run-tijd: 1 minuut.

18. veldsla met 1881 punten.

    Ook veldsla's inzending, die geschreven was in/voor het minder bekende R-Project, gaf helaas vrijwel direct een foutmelding. Wederom geen grids en dus de maximale score.

    Run-tijd: 1 seconde.

Java-inzendingen werden uitgevoerd met JRE 6.0 (non-server) en de PHP-inzending met PHP 5.2.0.

Beoordeling van de snelheid

Het beoordelen van de snelheid van een programma is natuurlijk vrij lastig aangezien het vergelijken van twee applicaties die geschreven zijn in verschillende talen nogal wat weg heeft van appels met peren vergelijken. Gelukkig was er wel een overduidelijke winnaar in deze categorie, zoals je in het schema hierboven ook kunt zien.

Arty_Shock en wwwhizz liggen wat tijd betreft dicht bij elkaar, maar wwwhizz had toch nét iets snellere code en bovendien een lagere (en dus betere) score.

Beoordeling van de robuustheid

Zoals gezegd hebben we ook de robuustheid van de code bekeken. Daarvoor hebben we bekeken wie er het beste omging met onverwachte problemen zoals het niet bestaan van invoerbestanden of het aanwezig zijn van corrupte invoer. Lang niet iedereen hield daar evenveel rekening mee (aangezien dat ook niet hoefde), maar vooral EdwinG, MarcJ, Robbert en KoW hielden wel rekening met het onverwachte.

KoW was degene die er met kop en schouders bovenuit stak en de meeste onverwachte problemen wel opving en heeft dus deze categorie gewonnen.

Beoordeling van de code

Onderstaande punten zijn berekend door het gemiddelde te nemen van de jury-beoordelingen. De punten zijn uitgedeeld op een schaal van 1 tot en met 10. Wanneer twee personen dezelfde score hadden bepaalde de score in de categorie "meest defensieve code" de exacte volgorde.

De precieze motivatie blijven we jullie schuldig, maar voor de scores hebben we gekeken naar leesbaarheid en netheid en de aanwezigheid van zinnig commentaar.

1. Soultaker met een 9.
2. MarcJ met een 8.
3. cobratbq met een 8.
4. zwippie met een 8.
5. Arjan met een 8.
6. KoW met een 7.
7. EdwinG met een 7.
8. Nick The Heazk met een 7.
9. Serpie met een 7.
10. Arty_Shock met een 7.
11. wwwhizz met een 7.
12. veldsla met een 7.
13. Robbbert met een 6.
14. hij met een 6.
15. Fiander met een 6.
16. H!GHGuY met een 6.
17. DaCoTa met een 5.

« ·^

Prijzen?!

Ik weet dat we gezegd hadden dat er geen prijzen te vergeven waren voor de winnaars. Echter, in de loop van de contest werd de Devschuur crew benaderd door de redactie van de Frontpage. P_de_B wilde een artikel schrijven over de contest en de redactie wilde daar voor de winnaars prijzen aan verbinden. Dit is echter éénmalig voor deze contest; de volgende contest zal weer, net als contest 1, prijzenloos zijn.

Onze winnaars nog eens op een rijtje:

• Soultaker in de categorie "laagste score"; als winnaar van de hoofdcategorie wint hij ook de hoofdprijs: een 22" breedbeeldmonitor van Samsung. Soultaker, gefeliciteerd!
• wwwhizz in de categorie "snelste code"; als winnaar van één van de subcategoriën krijgt wwwhizz een jaarabonnement op Tweakers.net.
• KoW krijgt voor zijn winst in de categorie "meest defensieve code" ook een jaarabonnement op Tweakers.net.
• Soultaker krijgt, omdat hij naast de meest effectieve code ook de meest nette code heeft, óók een jaarabonnement op Tweakers.net.

« ·^

Afsluiting

We willen jullie graag ook dit keer bedanken voor het tot een succes maken van deze contest. Wij als crew hebben ons erg vermaakt met de organisatie, en we hopen dat dat ook voor jullie geldt voor wat betreft het meedoen. We hopen jullie allemaal weer terug te zien bij de derde contest, die zometeen van start gaat!

[Voor 146% gewijzigd door RobIII op 23-05-2007 15:24]

[Dido]

Leuk! Ik hoop dat ik deze keer wat meer tijd vrij kan maken om ook daadwerkelijk wat af te krijgen

Twee vraagjes:

Eventueel 'nieuwe' woorden, die dus niet voorkomen in het aangeleverde words.txt, die worden gevormd bijvoorbeeld door het horizontaal onder elkaar plaatsen van woorden worden niet in ogenschouw genomen.

Wat betekent dit? Dat je woorden "over elkaar heen mag plakken", en dat dat geen consequenties heeft?
Of dat het juist niet mag?

Karakters kunnen of mogen lower én uppercase karakters bevatten in zowel de in- als uitvoer bestanden.

Dat betekent dat een "A" een ander karakter is dan een "a", en dat ze dus niet uitwisselbaar zijn?
(Lijkt me inderdaad het geval, maar just 2b sure ).

[Glabbeek]

Leuk! Weer een contest

En ik heb gelijk een vraag: Er staat

Karakters kunnen of mogen lower én uppercase karakters bevatten in zowel de in- als uitvoer bestanden.

Ten eerste: Ik neem aan dat het eerste woord 'Woorden' moet zijn;
ten tweede: Betekent dit dat het case-sensitive is? M.a.w: is 'a' iets anders dan 'A' of worden deze gelijk aan elkaar gesteld?

edit:
@Dido: Great minds think alike

[Voor 6% gewijzigd door Glabbeek op 26-02-2007 19:57]

[RobIII]

Dido schreef op maandag 26 februari 2007 @ 19:54:
Twee vraagjes:

Potver! en ik maar denken dat we duidelijk waren

Dido schreef op maandag 26 februari 2007 @ 19:54:
Wat betekent dit? Dat je woorden "over elkaar heen mag plakken", en dat dat geen consequenties heeft?

Jep.

Dido schreef op maandag 26 februari 2007 @ 19:54:
Dat betekent dat een "A" een ander karakter is dan een "a", en dat ze dus niet uitwisselbaar zijn?
(Lijkt me inderdaad het geval, maar just 2b sure ).

A en a zijn wél uitwisselbaar; het gaat er om dat in de in/uitvoer bestanden niet naar de casing wordt gekeken of gekeken moet worden. TS is aangepast wat dat betreft.

[Arjan]

en als er woorden zijn als 'aap' en 'schaapje' mag ik dan schaapje schrijven en claimen dat er ook aapje staat ?

[RobIII]

Atgast schreef op maandag 26 februari 2007 @ 20:05:
en als er woorden zijn als 'aap' en 'schaapje' mag ik dan schaapje schrijven en claimen dat er ook aapje staat ?

RobIII schreef op maandag 26 februari 2007 @ 19:32:

Het is verplicht om de woorden zowel horizontaal als verticaal te plaatsen, en om woorden zo veel mogelijk te laten kruisen/overlappen.

Ja dus

[Voor 38% gewijzigd door RobIII op 26-02-2007 20:09]

[NMe]

Atgast schreef op maandag 26 februari 2007 @ 20:05:
en als er woorden zijn als 'aap' en 'schaapje' mag ik dan schaapje schrijven en claimen dat er ook aapje staat ?

Het zal in de praktijk niet gaan voorkomen, eerder een case als "eierwekker" en "wekkerradio". Maar in theorie mag dat inderdaad.

[Dricus]

Allereerst complimenten voor het idee! Echt een leuke uitdaging. Ik ga proberen om iets moois te devven .
Nog 1 vraagje en dan is mij alles duidelijk:
Wordt het bestand words.txt in een bepaalde directory (dezelfde als de EXE) geplaatst of moet je in je progsel een mogelijkheid maken om een bestand te selecteren?
* Dricus moet es leren lezen .

[Voor 7% gewijzigd door Dricus op 26-02-2007 21:03]

[Arjan]

misschien vergis ik me, maar ik heb ook bij deze contest het idee dat het veel brute-forcen wordt, ik zie iig als ik er zo over nadenk niet echt mogelijkheden om te optimaliseren

Het wordt iig ontzettend veel zoekwerk voor de arme pc...nu is daar wel aardig wat te optimaliseren natuurlijk.
Voor mij zal deelname er vooral vanaf hangen of ik een 'orginele' optimalisatie kan bedenken

[Sjoerd]

Ik vind deze opdracht een stuk toegankelijker dan de vorige eigenlijk, mooi zoè

[EdwinG]

MrHuge schreef op maandag 26 februari 2007 @ 20:18:
Nog 1 vraagje en dan is mij alles duidelijk:
Wordt het bestand words.txt in een bepaalde directory (dezelfde als de EXE) geplaatst of moet je in je progsel een mogelijkheid maken om een bestand te selecteren?

Begint al goed, welk onderdeel van

Schroom niet om te vragen als je nog onduidelijkheden denkt te hebben gevonden, maar verzeker je ervan dat de informatie niet in deze opdracht staat voordat je dat doet.

Was niet duidelijk?

Alle in- en uitvoer bestanden dienen te worden gelezen en geschreven in dezelfde directory als de executable (of het script).

---

Ik heb wel nog een vraagje over de scores:

het aantal letters in de grid is je score. Degene met de laagste score wint

Op die manier zouden er maximaal 99 scorelijsten bijgehouden moeten worden.
Natuurlijk is het mogelijk die bij elkaar op te tellen, maar wat wordt er dan gedaan met inzendingen die niet alle grids afkrijgen? (Mijn idee: Geef die per volgend grid een score gelijk aan het aantal letters in de invoer (minst optimale grid dus))

(Gemiddelde gaat niet werken, want als het laatste grid ook de meeste woorden bevat, komt dat nadelig uit voor iedereen die de lijst af heeft, t.o.v. de overige deelnemers.)

[Voor 33% gewijzigd door EdwinG op 26-02-2007 21:01]

[Dricus]

EdwinG schreef op maandag 26 februari 2007 @ 20:55:
[...]

Begint al goed, welk onderdeel van

[...]

Was niet duidelijk?


[...]

Allemachtig, meteen al zo aangebrand? We zijn nog maar net begonnen...
Maareeh, je hebt gelijk, die heb ik echt falikant gemist ... XQses...

[EdwinG]

MrHuge schreef op maandag 26 februari 2007 @ 21:01:
[...]

Allemachtig, meteen al zo aangebrand? We zijn nog maar net begonnen...
Maareeh, je hebt gelijk, die heb ik echt falikant gemist ... XQses...

Als ik aangebrand was, had ik die smiley er niet achter gezet

(Sorry, kwam iets harder over dan ik bedoeld had)

[RobIII]

EdwinG schreef op maandag 26 februari 2007 @ 20:55:
Op die manier zouden er maximaal 99 scorelijsten bijgehouden moeten worden.
Natuurlijk is het mogelijk die bij elkaar op te tellen, maar wat wordt er dan gedaan met inzendingen die niet alle grids afkrijgen?

Die hadden maar harder moeten rekenen

[EdwinG]

RobIII schreef op maandag 26 februari 2007 @ 21:41:
[...]

Die hadden maar harder moeten rekenen

Efficiënter in plaats van harder, lijkt mij

Maar waar het meer om gaat, als je minder 'grids' af hebt, heb je (waarschijnlijk) een kleinder totaal aantal letters.

[Dido]

Je zou inderdaad eenvoudig met een "positieve" score kunnen werken (meer=beter) door het worst-case scenario mee te nemen (geen kruisingen, dus het aantal letters van de input = aantal letters in de output). Vervolgens 1 punt per overlap, oftewel 1 punt per letter minder dan het maximum.

Je kunt echter ook iedereen die niet genoeg output genereert keihard diskwalificeren: het is niet moeilijk om voor iedere set een output te genereren met een max. score. Dan heb je alle outputs klaar, en kun je gaan rekenen om ze te verbeteren. Misschien loont het in tijdnood wel om een van de eerste sets "over te slaan" om meer te scoren op een grote of makkelijkere set aan het eind...

[Gerco]

Deze contest klinkt als een excuus om prolog weer eens af te stoffen. Leuk!

[Dido]

Moeten eigenlijk alle woorden "met elkaar verbonden" zijn, of mag je ook de facto losse grids maken?

[Janoz]

Dido schreef op maandag 26 februari 2007 @ 22:13:
Moeten eigenlijk alle woorden "met elkaar verbonden" zijn, of mag je ook de facto losse grids maken?

Staat nergens in de opdracht dat dat moet en ook de score wordt er niet door beinvloed. Ik zou zeggen: trek je conclusie .


We hebben redelijk lang over de opdracht gesteggeld. We hebben over veel dingen nagedacht. De regels zijn imho redelijk uitgekristaliseerd. Natuurlijk kan het zijn dat we nog een foutje gemaakt hebben, maar er staat duidelijk aan welke eisen je oplossing moet voldoen. Alle woorden gebruiken, richting maakt niet uit zolang het horizontaal of verticaal is. Er moet minimaal 1 woord verticaal staan en minimaal 1 woord horizontaal. Als iemand een loophole vindt dat voor een betere score zorgt zonder dat het de in de topicstart gestelde regels overtreed dan is dat mooi gevonden en zou ik dat vooral uitbuiten.

[thomahawks]

Erg leuk initiatief. Ik was te laat om aan het vorige contest mee te doen, maar ik ga zeker proberen deze te doen. Na mijn eigen sudoku solver te hebben gemaakt in Java is het tijd voor dit.

Gelukkig wordt de score niet bepaald aan de hand van de grote van het grid (als ik het goed begrepen heb), dat zou een behoorlijk pittig algoritme opleveren.

Nog 1 vraagje, hoe willen jullie de java code krijgen? In een zip bestand met de java files die jullie zelf compileren of willen jullie liever een .exe file? Zo ja, heeft iemand een tip om dit makkelijk om te zetten?

[Pete]

RobIII schreef op maandag 26 februari 2007 @ 19:32:Het is verplicht om de woorden zowel horizontaal als verticaal te plaatsen, en om woorden zo veel mogelijk te laten kruisen/overlappen.

Wat houdt deze eis concreet in? Moet er in ieder grid een woord verticaal en een woord horizontaal geplaatst worden? <- dank je Janoz

Trouwens, het is natuurlijk zoiezo de bedoeling van het spel om zo veel mogelijk te kruisen/overlappen. Als je het goed leest staat er dat je prog de meest ultieme oplossing moet geven. Anders voldoet hij niet aan de spec.


(trwns, complimenten voor de contest )

[Pete]

thomahawks schreef op maandag 26 februari 2007 @ 22:40:
...

Nog 1 vraagje, hoe willen jullie de java code krijgen? In een zip bestand met de java files die jullie zelf compileren of willen jullie liever een .exe file? Zo ja, heeft iemand een tip om dit makkelijk om te zetten?

Als je met eclipse werkt bijvoorbeeld, kun je een ant-build file en een outputjar maken.

[Dido]

Janoz schreef op maandag 26 februari 2007 @ 22:37:
Staat nergens in de opdracht dat dat moet en ook de score wordt er niet door beinvloed. Ik zou zeggen: trek je conclusie .

Ok, is duidelijk

Ik was alleen de regel

Het is verplicht om [...] woorden zo veel mogelijk te laten kruisen/overlappen.

aan het over-interpreteren, denk ik.

Op zich is het wel vaag om dat verplicht te stellen, aangezien de oplossing waar de woorden het meest kruisen/overlappen simpelweg de beste score krijgt. Dat is dus het hele doel van de contest.
Als ik zou gaan mierenneuken zou het betekenen dat elke sub-optimale oplossing gediskwalificeerd wordt

(En het is vast aantoonbaar dat waarschijnlijk iedere oplossing sub-optimaal is - ik vermoed dat handmatige optimalisatie nog mogelijk is, zelfs bij een erg goed algoritme.)

Ik ga echter niet mierenneuken, dus ga ik vrolijk brainstormen over de opdracht

(phsmit: gmta )

[Blackspot]

Leuk idee, als ik wat tijd over heb dan zal ik zeker een poging doen.

[NMe]

thomahawks schreef op maandag 26 februari 2007 @ 22:40:
Nog 1 vraagje, hoe willen jullie de java code krijgen? In een zip bestand met de java files die jullie zelf compileren of willen jullie liever een .exe file? Zo ja, heeft iemand een tip om dit makkelijk om te zetten?

Een executable jar-file met daarin ook de source was bij de vorige Java-inzenders vrij populair en dat werkte wel fijn, dus indien mogelijk, graag.

[DaCoTa]

Even ter recap, de maximale score is dus het aantal letters in een woordenset, onafhankelijk van hoe groot het grid daadwerkelijk is. Zodra er van 2 woorden een overlap is, is de score een punt lager en dus beter.

Oh en for the record: erg leuk idee! Bij voorbaat al dank aan de organisatoren voor de inzet en moeite en tijd in de contest!

Prolog is aanlokkelijk, of wellicht de JProlog implementatie die ergens rondzweeft...

Hmmm.... Op eerste gezicht nog geen heel duidelijk idee over wat slim is. Niet qua zoektechniek en ook nog niet qua representatie... Tricky... Ook de gigantisch exploderende combinatiemogelijkheden, dat is bijna gemeen!

[Voor 53% gewijzigd door DaCoTa op 27-02-2007 00:34]

[Anoniem: 3057]

* Anoniem: 3057 grijnst

Mooi! Weer eens iets te doen voor de regenachtige zondagmiddagen. Ik ga hier vrijwel zeker een lapje code voor breien.

[thomahawks]

-NMe- schreef op maandag 26 februari 2007 @ 20:10:
[...]

Het zal in de praktijk niet gaan voorkomen, eerder een case als "eierwekker" en "wekkerradio". Maar in theorie mag dat inderdaad.

Vergis je niet. Mijn programma filtert inmiddels de "overbodige" woorden (m.a.w. woorden die door een ander woord volledig overlapt worden, zowel normaal geschreven als achterstevoren) en dat zijn er voor het eerste tekstbestandje al 8 135, wat het aantal letters al verminderd met 33 zo'n 450 in dit geval.

EDIT: programmeerfoutje, loop eindigde te snel, zijn er zelfs veel meer dan ik verwacht had .

En over de te controleren grids voor de mods, daar valt natuurlijk makkelijk een programmaatje voor te schrijven die checkt of elk woord voorkomt en hoeveel letters diegene gebruikt heeft per grp etc.

[Voor 7% gewijzigd door thomahawks op 27-02-2007 08:37]

[Serpie]

thomahawks schreef op dinsdag 27 februari 2007 @ 07:56:
[...]


Vergis je niet. Mijn programma filtert inmiddels de "overbodige" woorden (m.a.w. woorden die door een ander woord volledig overlapt worden, zowel normaal geschreven als achterstevoren) en dat zijn er voor het eerste tekstbestandje al 8, wat het aantal letters al verminderd met 33 in dit geval.

Dat zag ik ook al direct in de voorbeeldbestanden terug, ik heb nog geen code getyped maar wel diverse stappen voor mezelf opgeschreven.

Ik ga deze keer ook proberen mee te doen, ik heb weinig tijd naast werk én studie maar een klein projectje moet toch te maken zijn in korte tijd.

[Voor 12% gewijzigd door Serpie op 27-02-2007 08:14]

[Marcj]

Ik ga hier hopelijk ook nog wat tijd voor vrijmaken, ook al heb ik het wel druk. Dit is weer een leuke opdracht die denk ik ook wel goed te doen is voor vrijwel elke programmeur.

[Anoniem: 108943]

ik zal hier ook een poging op wagen.

[Nick The Heazk]

Aangezien deze contest niet in de examenperiode valt, ga ik ook deelnemen . Straks na de les eens beginnen met een paar ideeën vast te leggen.

[RobIII]

Dido schreef op maandag 26 februari 2007 @ 22:45:
[...]

Ok, is duidelijk

Ik was alleen de regel

[...]

aan het over-interpreteren, denk ik.

Op zich is het wel vaag om dat verplicht te stellen, aangezien de oplossing waar de woorden het meest kruisen/overlappen simpelweg de beste score krijgt. Dat is dus het hele doel van de contest.
Als ik zou gaan mierenneuken zou het betekenen dat elke sub-optimale oplossing gediskwalificeerd wordt

Die zinsnede was inderdaad wat raar en nog een overblijfsel uit een 'ander regelstelsel' dat we eerst hadden. Ik heb het inmiddels (ietwat) aangepast:

Het is verplicht om de woorden zowel horizontaal als verticaal te plaatsen, en de bedoeling om woorden zo veel mogelijk te laten kruisen/overlappen.

[Vaan Banaan]

Kunnen er ook woorden voorkomen met bijvoorbeeld een trema?
Zo ja, mag ja dan bijvoorbeeld ë als e gebruiken?
Note to self: beter lezen

[Voor 12% gewijzigd door Vaan Banaan op 27-02-2007 13:12]

[Aloys]

Vaan Banaan schreef op dinsdag 27 februari 2007 @ 13:03:
Kunnen er ook woorden voorkomen met bijvoorbeeld een trema?
Zo ja, mag ja dan bijvoorbeeld ë als e gebruiken?

Volgens mij komt dat niet voor, omdat er in de TS stond dat er geen extended ASCII (oid) werdt gebruikt.

Ik ben nu ook begonnen met code schrijven, voor mezelf al helemaal op papier gezet wat ik ga doen. Alleen zit ik nog te denken hoe ik voor me zelf een goed snel grid bijhoud. Die ik ook uiteraard kan vergroten (daar zit het probleem ), en dit alles ga ik in elkaar proberen te zetten in delphi. Ben zelf wel benieuwd of me dat gaat lukken.

Modjes alvast bedankt voor de nieuwe contest..

[Blackspot]

Vaan Banaan schreef op dinsdag 27 februari 2007 @ 13:03:
Kunnen er ook woorden voorkomen met bijvoorbeeld een trema?
Zo ja, mag ja dan bijvoorbeeld ë als e gebruiken?

In- en uitvoer bestanden zijn ASCII, géén extended ASCII.
http://www.idevelopment.i...RAMMING_ascii_table.shtml

[mOrPhie]

Leuk! * mOrPhie gaat zich er ook aan wagen

Na wat schelden op buggy output van m'n Depth Of Field voor een raytracer, denk ik dat ik me heerlijk zal vermaken met gewoon wat ascii.

[PiepPiep]

De kunst is om deze woorden in een zo klein mogelijk 'grid' te plaatsen, het uiteindelijke aantal letters in het 'grid' wordt gebruikt voor de scoretelling.

Degene met de minste punten wint de contest op het vlak van de scores.

De grootte van het grid maakt dan toch niet uit? alleen het aantal letters zorgt voor punten, de lege ruimte ertussen doet niets met je score als ik het goed begrijp?

Verder, moeten de woorden van 1 groep allemaal aan elkaar verbonden zijn of mogen het ook losse eilandjes zijn?

[RobIII]

PiepPiep schreef op dinsdag 27 februari 2007 @ 13:52:
Verder, moeten de woorden van 1 groep allemaal aan elkaar verbonden zijn of mogen het ook losse eilandjes zijn?

Het mogen prima losse eilandjes zijn, maar of dat je score ten goede komt is een tweede
Als je maar zorgt dat iedere groep in z'n eigen bestand (gridxx.txt) terecht komt.

[Arjan]

Ik heb gister even een stukje code geschreven dat de input parsed naar groepen, dat duurt bij testset1 zo'n 15ms. Ik werk nu met vectoren, maar ivm met performance moet ik misschien naar lists overstappen, zouden jullie een indicatie kunnen geven van de uiteindelijke words.txt grootte?

[Dido]

Atgast schreef op dinsdag 27 februari 2007 @ 14:07:
Ik heb gister even een stukje code geschreven dat de input parsed naar groepen, dat duurt bij testset1 zo'n 15ms. Ik werk nu met vectoren, maar ivm met performance moet ik misschien naar lists overstappen, zouden jullie een indicatie kunnen geven van de uiteindelijke words.txt grootte?

Die staat toch in de TS? 99 groepen van 999 woorden max.

RobIII schreef op dinsdag 27 februari 2007 @ 14:01:
Het mogen prima losse eilandjes zijn, maar of dat je score ten goede komt is een tweede

Dit lijkt me aardig geoptimaliseerd, anders

code:

BAL BAR
ABO ALU
KUL SOL

[RobIII]

Dido schreef op dinsdag 27 februari 2007 @ 14:09:
Dit lijkt me aardig geoptimaliseerd, anders

code:

BAL BAR
ABO ALU
KUL SOL

code:

BAL_
ABO_
ROS_
KULA

^^ Zelfde woorden. Dat is geoptimaliseerd
18 tekens in jouw geval, 13 in mijn geval.
( _ = Spatie in dit voorbeeld)

[Voor 69% gewijzigd door RobIII op 27-02-2007 14:25]

[Dido]

Ik mis BAK, LOL, ABU, OLA, RUL en BAS in ieder geval

[RobIII]

Dido schreef op dinsdag 27 februari 2007 @ 14:25:
Ik mis BAK, LOL, ABU, OLA, RUL en BAS in ieder geval

Dat zijn geen woorden ghehe
Blijkt dus dat ik je post verkeerd heb gelezen en begrepen
In dat geval heb je dus helemaal gelijk. Je mag er losse eilandjes van maken, maar je kunt ze net zo goed tegen elkaar aan zetten.

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

[Voor 32% gewijzigd door RobIII op 27-02-2007 14:30]

[Arjan]

Is dit eigenlijk niet gewoon een kwestie van nesting?

Als ik me niet vergis is daar niet echt een beste algoritme voor, dus de uitslag zou best wel eens sterk aan de uiteindelijke words lijst kunnen liggen

[RobIII]

Atgast schreef op dinsdag 27 februari 2007 @ 14:52:
Is dit eigenlijk niet gewoon een kwestie van nesting?

Als ik me niet vergis is daar niet echt een beste algoritme voor, dus de uitslag zou best wel eens sterk aan de uiteindelijke words lijst kunnen liggen

Volgens mij is nesting meer een (soort van) knapsack probleem, in deze contest kun je letters hergebruiken (overlappen); dat gaat met onderdelen die je uitsnijdt een beetje moeilijk

[Voor 6% gewijzigd door RobIII op 27-02-2007 14:58]

[.oisyn]

Atgast schreef op dinsdag 27 februari 2007 @ 14:52:
Is dit eigenlijk niet gewoon een kwestie van nesting?

Nee, ongebruikte ruimte doet er namelijk niet toe. Daarnaast maken de gelimiteerde set letters en het vaste grid het probleem een stuk makkelijker.

Als ik me niet vergis is daar niet echt een beste algoritme voor, dus de uitslag zou best wel eens sterk aan de uiteindelijke words lijst kunnen liggen

Maar goed ook, anders was het gewoon een kwestie van dat algoritme implementeren

[Arjan]

.oisyn schreef op dinsdag 27 februari 2007 @ 15:00:
[...]

Nee, ongebruikte ruimte doet er namelijk niet toe. Daarnaast maken de gelimiteerde set letters en het vaste grid het probleem een stuk makkelijker.

maar je wil wel zo min mogelijk 'materiaal' gebruiken, in tegenstelling tot het knapsack probleem waarbij je een vaste grid-size hebt en er zoveel mogelijk shit in probeert te proppen

[...]

Maar goed ook, anders was het gewoon een kwestie van dat algoritme implementeren

wat ik meer bedoel is dat 3 verschillende words.txt bestanden 3 verschillende winnaars zouden kunnen opleveren, misschien een leuk idee om met verschillende sets te testen? (al hebben jullie misschien ook nog daadwerkelijk wat nuttigs te doen met jullie tijd )

[Anoniem: 37526]

Mag er ook menselijke interactie zijn?

[.oisyn]

Atgast schreef op dinsdag 27 februari 2007 @ 15:06:
wat ik meer bedoel is dat 3 verschillende words.txt bestanden 3 verschillende winnaars zouden kunnen opleveren, misschien een leuk idee om met verschillende sets te testen? (al hebben jullie misschien ook nog daadwerkelijk wat nuttigs te doen met jullie tijd )

Het idee is toch ook dat je een grid per groep woorden levert, en dat er in een set meerdere groepen zitten?

[RobIII]

Anoniem: 37526 schreef op dinsdag 27 februari 2007 @ 15:25:
Mag er ook menselijke interactie zijn?

Als het over 'een keer op enter rammen' is om door te gaan wel... Maar ik zie niet hoe je het anders had voorgesteld; je weet dat je je uiteindelijke app moet inzenden en dat wij je app gaan gebruiken voor de uiteindelijke contest?

[DaCoTa]

Anoniem: 37526 schreef op dinsdag 27 februari 2007 @ 15:25:
Mag er ook menselijke interactie zijn?

Ja, mits beperkt tot het afleveren van kratjes bier en flessen wodka bij de organisatie.

[Janoz]

RobIII schreef op dinsdag 27 februari 2007 @ 15:43:
[...]

Als het over 'een keer op enter rammen' is om door te gaan wel... Maar ik zie niet hoe je het anders had voorgesteld; je weet dat je je uiteindelijke app moet inzenden en dat wij je app gaan gebruiken voor de uiteindelijke contest?

Nou, ook 'een keer op enter drukken' zie ik (en ik hoop wij) liever niet. Eigenlijk is het de bedoeling dat we je appje gewoon kunnen starten. Dit laten we een tijdje draaien en als ie klaar is gooien we het resultaat door onze score berekenaar en zien we hoe goed je het gedaan hebt. Als je app vervolgens 2uur op een enter gaat lopen wachten schiet het niet op.

[Anoniem: 37526]

RobIII schreef op dinsdag 27 februari 2007 @ 15:43:
[...]

Als het over 'een keer op enter rammen' is om door te gaan wel... Maar ik zie niet hoe je het anders had voorgesteld; je weet dat je je uiteindelijke app moet inzenden en dat wij je app gaan gebruiken voor de uiteindelijke contest?

Dat als je het programma draait, dat de woordenlijsten naar een internet-database worden gesubmit, dat een chineesje dat voor 11 eurocent per uur op gaat zitten lossen en het resultaat terug in de database stopt? Uiteraard binnen het uur.

[RobIII]

Anoniem: 37526 schreef op dinsdag 27 februari 2007 @ 16:02:
[...]


Dat als je het programma draait, dat de woordenlijsten naar een internet-database worden gesubmit, dat een chineesje dat voor 11 eurocent per uur op gaat zitten lossen en het resultaat terug in de database stopt? Uiteraard binnen het uur.

Nope; sterker nog: ga er maar vanuit dat er geen verbinding met de buitenwereld is.
En wat Janoz zegt.

[Voor 9% gewijzigd door RobIII op 27-02-2007 16:04]

[Creepy]

DaCoTa schreef op dinsdag 27 februari 2007 @ 15:52:
[...]

Ja, mits beperkt tot het afleveren van kratjes bier en flessen wodka bij de organisatie.

Eindelijk iemand die het snapt

[Dricus]

Atgast schreef op maandag 26 februari 2007 @ 20:30:
misschien vergis ik me, maar ik heb ook bij deze contest het idee dat het veel brute-forcen wordt, ik zie iig als ik er zo over nadenk niet echt mogelijkheden om te optimaliseren

De vorige contest leende zich goed tot brute forcen omdat er sprake was van een aantal vast omlijnde factoren (grootte speelveld, voorgedefinieerde blokjes, volgorde van de blokjes voorgedefinieerd). Het begin en het einde van de te-brute-forcen data was duidelijk. Alle te-testen mogelijkheden waren gemakkelijk in een soort boompje te plaatsen en op die boom kon dan weer geoptimaliseerd worden.

Bij deze contest is dat volgens mij heel anders. Je krijgt een ongestructureerde bak met woorden en ga maar een grid bedenken waar ze allemaal in terug te vinden zijn. Het aantal mogelijke grids voor een groep woorden is oneindig en een brute-force is volgens mij alleen maar zinvol als je een eindig aantal mogelijke oplossingen af te testen hebt.

De uitdaging van deze contest vind ik om echt een slim algoritme te vinden en dat op een slimme, maar ook inzichtelijke, manier te implementeren.

[Arjan]

.oisyn schreef op dinsdag 27 februari 2007 @ 15:35:
[...]

Het idee is toch ook dat je een grid per groep woorden levert, en dat er in een set meerdere groepen zitten?

je hebt helemaal gelijk, ik had mezelf verward door enkele test sets te creëren die aan te specifieke eigenschappen voldeden

[EdwinG]

thomahawks schreef op dinsdag 27 februari 2007 @ 07:56:
Vergis je niet. Mijn programma filtert inmiddels de "overbodige" woorden (m.a.w. woorden die door een ander woord volledig overlapt worden, zowel normaal geschreven als achterstevoren) en dat zijn er voor het eerste tekstbestandje al 8 135, wat het aantal letters al verminderd met 33 zo'n 450 in dit geval.

Ik kom maar tot 10 overbodige woorden, houd je er wel rekening mee dat de woorden PER GRID bekeken moeten worden, en dus ook vergeleken, en niet met het gehele bestand in 1x?
(of zie ik iets over het hoofd?)

[Arjan]

EdwinG schreef op dinsdag 27 februari 2007 @ 18:08:
[...]

Ik kom maar tot 10 overbodige woorden, houd je er wel rekening mee dat de woorden PER GRID bekeken moeten worden, en dus ook vergeleken, en niet met het gehele bestand in 1x?
(of zie ik iets over het hoofd?)

code:

Het lezen van words.txt duurde 16ms.
Het verwijderen van 18 overbodige woorden uit grid 1/6 duurde 47ms.
Het verwijderen van 32 overbodige woorden uit grid 2/6 duurde 62ms.
Het verwijderen van 23 overbodige woorden uit grid 3/6 duurde 63ms.
Het verwijderen van 13 overbodige woorden uit grid 4/6 duurde 47ms.
Het verwijderen van 18 overbodige woorden uit grid 5/6 duurde 31ms.
Het verwijderen van 29 overbodige woorden uit grid 6/6 duurde 109ms.

dit zijn mijn resultaten van testset1

[EdwinG]

Ah, ik doe dus iets niet goed

edit:

Ah, gevonden, het enige wat mijn script deed, wat woorden als 'sms' er uit halen, aangezien het omgekeerde van dat woord ook aanwezig was

[toevoeging 2]
En ondertussen heb ik dat ook weer opgelost. Mijn script vind nu 20 resultaten in grid 1, en die kan ik allemaal handmatig terugvinden. (Jouw script mist er dus nog 2. Toevallig ook het aantal dat alleen achterstevoren gevonden kon worden)

Voorbeeld: kiem -> meikever

[Voor 115% gewijzigd door EdwinG op 27-02-2007 19:55]

[Marcj]

MrHuge schreef op dinsdag 27 februari 2007 @ 17:25:
[...]

De vorige contest leende zich goed tot brute forcen omdat er sprake was van een aantal vast omlijnde factoren (grootte speelveld, voorgedefinieerde blokjes, volgorde van de blokjes voorgedefinieerd). Het begin en het einde van de te-brute-forcen data was duidelijk. Alle te-testen mogelijkheden waren gemakkelijk in een soort boompje te plaatsen en op die boom kon dan weer geoptimaliseerd worden.

Bij deze contest is dat volgens mij heel anders. Je krijgt een ongestructureerde bak met woorden en ga maar een grid bedenken waar ze allemaal in terug te vinden zijn. Het aantal mogelijke grids voor een groep woorden is oneindig en een brute-force is volgens mij alleen maar zinvol als je een eindig aantal mogelijke oplossingen af te testen hebt.

De uitdaging van deze contest vind ik om echt een slim algoritme te vinden en dat op een slimme, maar ook inzichtelijke, manier te implementeren.

Dit probleem is zeker ook wel eindig, echter veel te groot om te berekenen. Dit was echter bij het tetris ook zo. Het probleem van deze ten op zichte van de vorige opdracht is dat de vorige opdracht slecht een berekenbaar aantal opties per stap had (maximaal ~60), waar deze juist een heel groot aantal mogelijkheden hebben (In een grid van 10x10 heb je al 100 plekken om te beginnen en 4 richtingen, dus maximaal 400 mogelijkheden om te testen). Dus je hebt wel gelijk dat er een slimmere manier gevonden moet worden.

[Arjan]

EdwinG schreef op dinsdag 27 februari 2007 @ 19:23:
Ah, ik doe dus iets niet goed

edit:

Ah, gevonden, het enige wat mijn script deed, wat woorden als 'sms' er uit halen, aangezien het omgekeerde van dat woord ook aanwezig was

[toevoeging 2]
En ondertussen heb ik dat ook weer opgelost. Mijn script vind nu 20 resultaten in grid 1, en die kan ik allemaal handmatig terugvinden. (Jouw script mist er dus nog 2. Toevallig ook het aantal dat alleen achterstevoren gevonden kon worden)

Voorbeeld: kiem -> meikever

negeer je eerder gevonden resultaten wel?

ik bedenk me net dat ik nog niet alles omgezet heb naar lower-case, zou me niks verbazen als het daar in zit...
DoMmE vAuD

[Voor 38% gewijzigd door Arjan op 27-02-2007 20:27]

[cobratbq]

Dit keer ga ik zeker ook mee doen. Sterker nog... ik ben al bezig

[Salandur]

ik ga nu een serieuzere poging ondernemen dan bij de vorige contest. net begonnen

[Voor 10% gewijzigd door Salandur op 27-02-2007 21:10]

[thomahawks]

EdwinG schreef op dinsdag 27 februari 2007 @ 19:23:
Ah, ik doe dus iets niet goed

edit:

Ah, gevonden, het enige wat mijn script deed, wat woorden als 'sms' er uit halen, aangezien het omgekeerde van dat woord ook aanwezig was

[toevoeging 2]
En ondertussen heb ik dat ook weer opgelost. Mijn script vind nu 20 resultaten in grid 1, en die kan ik allemaal handmatig terugvinden. (Jouw script mist er dus nog 2. Toevallig ook het aantal dat alleen achterstevoren gevonden kon worden)

Voorbeeld: kiem -> meikever

Ik kom op precies dezelfde resultaten als AtGast. In de eerste serie filtert mijn programma:
per, raam, kiem, bord, baan, rijk, ski, rest, gat, zeet, bar, klei, drie, wis, klare, hop, met en mille.
Hierbij dus ook kiem wat achterstevoren gevonden wordt. Toch maar eens controleren of alles goed wordt ingelezen bij jou.
Hoe ik het controleer: ik stop alle woorden in een string array. Ik maak 2 for loops die 2 woorden combineren. Deze worden op wat dingen gecontroleerd (dat ze niet hetzelfde zijn bijv) vervolgens gebruik ik een if-statement die met de methode contains (JAVA) de 2 elementen vergelijkt. Ook heb ik een reverse-string methode geschreven die ik gebruik om 1 element om te draaien en weer met contain de 2 woorden te vergelijken. (genoeg verklapt)

Gezien de resultaten, de vele woorden die verwijderd worden is dit de meest logische start. Ik heb een soort van tactiek al klaar, die inderdaad niet gebaseerd is op brute forcen. Stel dat je 999 woorden moet combineren in een grid van 400x400, dan heb je max zo'n 320000^999 (2 (omgekeerd en normaal)x400x400) combinaties.

[Arjan]

thomahawks schreef op dinsdag 27 februari 2007 @ 21:47:
[...]

check even of je niet net als ik de lower/upper case vergeten was

verder nog een vraag aan de organisatie: gaan deze programmatjes op een multicore machine draaien?
aangezien het natuurlijk erg makkelijk per grid in een thread te stoppen is

[EdwinG]

Atgast schreef op dinsdag 27 februari 2007 @ 21:55:
check even of je niet net als ik de lower/upper case vergeten was

verder nog een vraag aan de organisatie: gaan deze programmatjes op een multicore machine draaien?
aangezien het natuurlijk erg makkelijk per grid in een thread te stoppen is

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)

Je kan ervan uit gaan dat de pc waarop je programma gerund wordt sneller is dan de gemiddelde consumentenpc, maar probeer je programma zo snel mogelijk te houden.

Beste optie is natuurlijk om je programma zo te maken, dat deze het aantal core's telt.

----

Naast 2 omgedraaide woorden, waren er inderdaad ook 2 met hoofdletter verschillen. Al kon ik dat niet zien, aangezien bij het inlezen alles lowercase gemaakt wordt.

[The Fox NL]

Ik ga ook weer meedoen. Dit keer ga ik het doen in Delphi ipv C++.

Nu ik weet dat de code ook beoordeeld gaat worden zal ik daar wat beter mijn best op doen. Mijn vorige project was nogal een zooitje wat dat betreft .

[thomahawks]

Atgast schreef op dinsdag 27 februari 2007 @ 21:55:
[...]

check even of je niet net als ik de lower/upper case vergeten was

verder nog een vraag aan de organisatie: gaan deze programmatjes op een multicore machine draaien?
aangezien het natuurlijk erg makkelijk per grid in een thread te stoppen is

Ah, inderdaad. Bedankt voor de tip.

Over het systeem zou ik mij geen zorgen maken, omdat brute force hier eigenlijk geen keus is, moet je op een slimme manier gaan zoeken. Natuurlijk komt hier wel wat rekenwerk bij kijken, maar bij lange na niet wat nodig is voor brute force. Ik denk dat mijn programma hooguit een paar minuten nodig heeft om een resultaat te bereiken, al kan ik mij hier uiteraard in vergissen. Hoe slimmer het algoritme, hoe minder het rekenwerk zullen we maar zeggen.

[Aloys]

Ik vind er nu ook 20 ... Was eerst wel heel enthousiast met mijn 347 ofzo. Was alleen vergeten dat dat over verschillende grids ging, ik zal straks eens een poging doen om alle grids automatisch bij langs te werken.

Over de preformace ben ik op dit moment ook nog wel te spreken, alhoewel delphi niet eens een standaard ReverseString functie heeft .

[Marcj]

Waarom zijn jullie nu al direct met een vrij kleine optimalisatie bezig? Als je je algoritme goed ontwerpt zou die automatisch op die plekken terecht moeten komen. Dit soort dingen zou ik aan het einde toevoegen als extra, maar eerst zou ik een grid maken waarin je woorden kan plaatsen. En daarna een AI die de woorden dan vervolgens ook daadwerkelijk slim plaatst.

[Anoniem: 50683]

Aloys schreef op dinsdag 27 februari 2007 @ 22:54:
Ik vind er nu ook 20 ... Was eerst wel heel enthousiast met mijn 347 ofzo. Was alleen vergeten dat dat over verschillende grids ging, ik zal straks eens een poging doen om alle grids automatisch bij langs te werken.

Over de preformace ben ik op dit moment ook nog wel te spreken, alhoewel delphi niet eens een standaard ReverseString functie heeft .

ook niet in de strutils unit ?
Hou voor de snelheid ook rekening met het feit dat pascal strings, sneller zijn dan de tegenwoordige strings (vermoed ik, zal morgen ff een benchmarkje draaien).

[Voor 13% gewijzigd door Anoniem: 50683 op 27-02-2007 23:27]

[The Fox NL]

Marcj schreef op dinsdag 27 februari 2007 @ 23:20:
Waarom zijn jullie nu al direct met een vrij kleine optimalisatie bezig? Als je je algoritme goed ontwerpt zou die automatisch op die plekken terecht moeten komen. Dit soort dingen zou ik aan het einde toevoegen als extra, maar eerst zou ik een grid maken waarin je woorden kan plaatsen. En daarna een AI die de woorden dan vervolgens ook daadwerkelijk slim plaatst.

Waarschijnlijk omdat die kleine optimalisatie het eenvoudigste is om te doen en waarschijnlijk ook het eerste wat in iedereen opkomt. Ik zat even over dit probleem te denken en dit was het eerste wat er in me opkwam. Trouwens, met deze kleine optimalisatie hoeft je AI zich weer over een paar woordjes minder te buigen, en dat is altijd meegenomen.

Anoniem: 50683 schreef op dinsdag 27 februari 2007 @ 23:23:
[...]

ook niet in de strutils unit ?

Ik kan hem niet vinden. (Delphi 5)

[Voor 10% gewijzigd door The Fox NL op 27-02-2007 23:26]

[Anoniem: 50683]

The Fox NL schreef op dinsdag 27 februari 2007 @ 23:24:
[...]
Ik kan hem niet vinden. (Delphi 5)

zoek voor InvertStrAsm

denk sowieso, dat je dit soort zaken nodig zal hebben, als je je tussen resultaat op de goede manier bijhoudt, blijf je moeten zoeken in dat resultaat of een woord al voorkomt. resultaat van je grid, kan je opslaan als woordenlijst enzo erachter komen of een woord al voorkomt (dubbel opslaan een lijst normale richting, andere lijst omgekeerde richting, lijkt me (ff gedachte spinsel)

[Voor 33% gewijzigd door Anoniem: 50683 op 27-02-2007 23:38]

[Nick The Heazk]

Heb net het eerste invoerbestand eens getest;

code:

Saved: 17
Saved: 24
Saved: 35
Saved: 20
Saved: 20
Saved: 30
Took 735 ms to process!

Detected 197173 overlaps of length 1
Detected 10596 overlaps of length 2
Detected 1608 overlaps of length 3
Detected 163 overlaps of length 4
Detected 17 overlaps of length 5
Detected 1 overlaps of length 6
Detected 0 overlaps of length 7

Mijn code zoekt naar overbodige woorden (Saved: xx), en bepaalt de lengte van een mogelijke overlapping tussen twee woorden. De volgorde van de Saved's is niet representatief (multithreaded).

[Voor 22% gewijzigd door Nick The Heazk op 28-02-2007 00:10]

[Marcj]

Ok, mijn eerste poging van mijn AI (is nog niet zo heel erg slim )

code:

Totale score: 14420
Totale percentage van max: 86
Tijd om uit te rekeken: 657ms

Ach ja, het is een score De eerste grid ziet er wel grappig uit:

code:

KAAIBAANEREBAANOPGAANKOMSTKRAKEELKOELTANKLERKENPERINEUMHOEKZAKBLOEDSCHROEF    
BAAICATALAANHEFHONGAARSMZESDAAGSTRAMIENEZEEROTVORMLEERIJLESCHABELOOIZUUR      
MAANJAARABMAATPAKJOURNAALRENETEKAKEMENTULUKLEEDMINDERULTIEMULTIPLECTRUM       
NATAALERNAASTVRAAMWETEORBMLVB VFORMATIESERAFWMJHOORNENMUURVASTHOOFDWAS        
WARTAALAATSTEAASLAVLBGPIAIIEEBANKAMILLEBIDZEEOAERUIGTEOLIEDOMOLSLAVUURBOL     
LZAPERELAARVLNCTKROAAEKTRNTRAUTORITBOETEKEUVRRSEKNEUZENZWEMENTOPPING          
AWAFEMELAARORDREACONSNLIGAEEDFRATSVENTIELRRIPEPNWEGVAKLAMSBOUTVOUWDEUR        
NAMVRAAGAL CAAONRARDETAEOLKREIMPASSEOMNNEPEDELINDIRECTUKKEROCULIST            
TAANNEMER  AAAB MCRRNARME OEMROULERENOTWUINENVSTAYERCICEROPPOMPEN             
AIRATRAINEEAMGATWAAITLEINUENEKLEINVEESRERKRNVLOOIENVISSERIJDACTYLUS           
AWEABAARDIGLABAPAOAERANNSPRANKPAPLEPELIROSUTKERMISCOLIOSEKSBOMHOOG            
RRFRILLEGAALAPTESBDMIM LPRILTHOEFSTALKGKOLIDRKOPKRUIENJOGGENBOSDUIF           
NAELTKMAJORAAT NSEOAAMWATJEMEIKEVERGENEUIEMAIKMAFWISSENVOORFILM               
MARIIAAMBEELDFDAALUNDEGUPARCOURSECTIEAGILETGJEMOMZEGGENBOSRIJK                
UKANMEMBRAANCIENLAAHERITAPPENZEIKERBBUATDZEWTNEVIJOYRIDER                     
SEAGPARABEL CGVTOSNEBEERTPLASMIDEMFEOWLROEZEEKLONTJEZONZIJDE                  
ELTKANENIER AAILNTIRONGEMPIRIENEZARSKSMOMPURNHSEKOUDECHEMICUS                 
AILBARONIEENSRAE EELMHANDICAP WVONITSPBKHPUKIOCGUNBOFFER                      
ATALNUCLEAIRHOTV NRAK GALWESPGIIMKTUBIOEEERUJNHWKJEGIMMICK                    
LANAKANTEN IAKIERENDAHETEROPNANEEPERATRNELKIPKEEEULCHROMO                     
VITANAVRANTEVKERKERENINWERKENBNZROUELTD RIATESURLICHTMIS                      
EROGELASTIEKAKLEINENTHERLEZENBEEJOSNIEUW NSGNLKK SSURF                        
RDUHALLEETTENTINTERESTEMMEN  ENNATEHINDOE TIDAE VT L                          
ARWESTATTENNNREGRESTEENUILZEEROBSMEDERIJGRAF GNZORGS                          
RUBIIAUKEERDAMSPANNINGLOEIENDBOLKNAKWEZELZITKUILN  T                          
MKADAMTLTREURENOTITIELOKEENDPLACIDELEGISCHGEKUIFD                             
ERABMTOABZIBELIEGENVOETREISJEKELJTRAGICUSUSPECT                               
NANOEAGSAEZEETBEDENKENWASSPELDSLKLORISFOKKERIJ                                
ZAGVEMESLEEDDEELTJEAXSPZEETONGEGENOPTZOETSTOFFIG                              
AMAESEEEDPNESAVERIJPPPASMUNT SPINDEVOOT VLIJT                                 
AKSNTRNNAVALSLOT RSTREMMENBELTOONLITURGBROODMIX                               
DROAACIPDHANGOORGIEAERFZEEVISOTGOUDERTSVOUWLIJN                               
DILRGA BINPANDIG SZFSWLUPINECRUISESEKSSHOP                                    
OSIMETMAGGIPASSINGEESEEWOLLENPAFFENZYM  M                                     
OTE OOGBALSTRAKJESFLERTINDOOREONLUSTOPBORD                                    
SAZWARTINGEVENEINDIGGRONDELRHDMPHYPNOSE                                       
WLINZAGERRITBONDAGESPITSENWDEOUYLIJKWIT                                       
AFHAKENSTEVENAPKGSRTWKRTRHIERBIJBEL U                                         
UAFTELLENBLLSFIROTBOEOERCEPLTUSAOCCULT                                        
WIEBELEN REWTBMOOEEPGEKIOCPIZIJMLY                                            
EVIEWDATAUVEEOPEGLDSHLVKLHEJOLEAVP                                            
LDVIGERENNERPEEPOLUEOWIAOTRKPDS OR                                            
EE GORGELENKPKLORIIINESJRSZCHILIRU                                            
NJSEIZOENTDEEEEEDGDNEGMUIEIHOND MS                                            
BEAUFORTET UNNNKEEEWN SISLJUGG                                                
KULHIEROVERZ V PLRNIPUNTT WTI                                                 
LNCULEEUWTJESUPERIGETROUWDENN                                                 
AEOPLPIJNBANKURSUBCLIVIA  GEG                                                 
PRHGUOPENING RIA D DUURLOOPY                                                  
PKORSNIKKEN  LKCVISRIJKI                                                      
ELLAIATOMISCHAKHOUTUSTOFGOUD                                                  
NEWDEMIVERMINKTVOORKOOPT                                                      
BDIEZEEMACHTKAPUCIJN   B                                                      
ODNLICHTGASMEDIGLIJGOOTO                                                      
TEDIROTOORTSNUFFEN     Y                                                      
TRVRIUWSYNAPSUITTOCHT                                                         
IUAIJNITCBOORKOPLAYBOY                                                        
NKNUKTJIIONISCHOOLS                                                           
EKGMEENSRUZUIDOOST                                                            
IELILRRKRWWCOULOMB                                                            
VNIDULEIUOI                                                                   
OHJDIAKFSRJUUT                                                                
RUVEOCWFYDM                                                                   
MILLUHIENEE                                                                   
IVAOBBJUT L                                                                   
GEKOOUTRA                                                                     
LRUNLII X                                                                     
YIKGL N I                                                                     
CGKOI G S                                                                     
EOELG                                                                         
RUPF                                                                          
ODU                                                                           
LAK

[thomahawks]

Marcj schreef op dinsdag 27 februari 2007 @ 23:20:
Waarom zijn jullie nu al direct met een vrij kleine optimalisatie bezig? Als je je algoritme goed ontwerpt zou die automatisch op die plekken terecht moeten komen. Dit soort dingen zou ik aan het einde toevoegen als extra, maar eerst zou ik een grid maken waarin je woorden kan plaatsen. En daarna een AI die de woorden dan vervolgens ook daadwerkelijk slim plaatst.

Waarom zou je niet eerst beginnen met een methode die de grootste optimalisatie heeft per woord, namelijk het volledige woord in dit geval. Ik denk dat dit puur een verschil van aanpakken is. Jij maakt eerst een grid om daarna woorden slim te plaatsen, ik maak eerst slimme woorden om die in een grid te plaatsen.
Welke methode het voordeligst is, is totaal afhankelijk van de mogelijkheid om woorden te combineren, maar zoals mijn programma nu draait verminder ik de eerste groep met zo'n 110 woorden van de 487 (ik maak daarintegen sommige woorden wel wat langer ).

EDIT: Mooie grid, alleen hoe heb je je score berekend? Ik zag dat je percentage wel overeenkomt met het aantal letters van de eerste set woorden en je grid, maar dat komt uit op 2781.

EDIT2: Zonder ook maar iets in een grid te zetten zit ik rond de 87-90% letters atm.

[Voor 11% gewijzigd door thomahawks op 28-02-2007 00:42]

[Marcj]

thomahawks schreef op woensdag 28 februari 2007 @ 00:11:
[...]
EDIT: Mooie grid, alleen hoe heb je je score berekend? Ik zag dat je percentage wel overeenkomt met het aantal letters van de eerste set woorden en je grid, maar dat komt uit op 2781.

EDIT2: Zonder ook maar iets in een grid te zetten zit ik rond de 87-90% letters atm.

De score is van alle grids. Waarschijnlijk vind mijn AI nu gewoon alle dubbele gewoon door te proberen. Het idee is nu ook om hem ietsje slimmer te laten zijn

[Anoniem: 50683]

kneep zit 'm natuurlijk om het grid zo min mogelijk te laten groeien (breedte/hoogte),

a. dus bepalen minimum breedte en hoogte (langste/hoogste woord).
b. passen en meten met de woorden.
c. indien geen woorden over naar f,
d. opnieuw bepalen grid maar nu met extra woorden (langste woord + minst langste woord ... ...)
e terug naar b.
f. volgend grid oplossen

(of zoiets, maar is al laat, morgen 's ff met een collega in conclaaf wordt overwerken ... )

hm, zat toch nog te denken
Stap 1. Vergeet de meerdere grids, doen er niet toe voor het bedenken van een algoritme.
Stap 2. Begin met leeg grid.
Stap 3. Plaats een woord (NietGeplaatsWoord[0])
Stap 4. Probeer zo veel mogelijk worden te passen
Stap 5. Bereken groei van je grid (hxb)
Stap 6. Probeer met volgend woord (NietGeplaatsWoord[1])
Stap 7. Herhaal 6 met alle overgebleven woorden.
Stap 8. Laagste score uit 6-7 bepalen te plaatsen woord
Stap 9. Schrap net geplaatst woord uit te plaatsen woorden
Stap 10. Naar Stap 3 etc.

Gedachte gang, ieder eerstvolgend te plaatsen woord (ergens in je grid) veroorzaakt een mogelijke groei. ........ ..........

[Voor 62% gewijzigd door Anoniem: 50683 op 28-02-2007 01:42]

[Aloys]

The Fox NL schreef op dinsdag 27 februari 2007 @ 23:24:
[...]
...
[...]

Ik kan hem niet vinden. (Delphi 5)

Volgens een delphi site, zou het er vanaf 7+ in moeten zitten, ik code zelf met 7 maar het is mij niet gelukt dit werkend te krijgen. Maar het kost ook maar 4 regels extra code... dus dat boeit niet echt .

[thomahawks]

Anoniem: 50683 schreef op woensdag 28 februari 2007 @ 01:00:
kneep zit 'm natuurlijk om het grid zo min mogelijk te laten groeien (breedte/hoogte)

Weet wel dat het aantal letters je score is, niet de grootte van je grid. Indien mogelijk is 1 blok tekst wat op elk punt kruist natuurlijk erg efficient, maar ik betwijfel of je dat uberhaubt tegen gaat komen. Ik denk dat ik klusters van woorden ga maken en deze op een zo efficient mogelijke manier aan elkaar koppel. Maar dit kan best een groot grid tot resultaat hebben.

Marcj schreef op woensdag 28 februari 2007 @ 00:54:De score is van alle grids. Waarschijnlijk vind mijn AI nu gewoon alle dubbele gewoon door te proberen. Het idee is nu ook om hem ietsje slimmer te laten zijn

Dus je kijkt of een woord niet al voorkomt in het grid? Dat is een manier, maar vergeet niet dat eenmaal een kleiner woord geplaatst is, met wat andere woorden eromheen, dat je de "grote" variant niet kan vervangen voor de kleine, of lastig in ieder geval.

[Voor 36% gewijzigd door thomahawks op 28-02-2007 09:00]

[Anoniem: 50683]

thomahawks schreef op woensdag 28 februari 2007 @ 08:53:
[...]
Weet wel dat het aantal letters je score is, niet de grootte van je grid. Indien mogelijk is 1 blok tekst wat op elk punt kruist natuurlijk erg efficient, maar ik betwijfel of je dat uberhaubt tegen gaat komen. denk dat ik klusters van woorden ga maken en deze op een zo efficient mogelijke manier aan elkaar koppel. Maar dit kan best een groot grid tot resultaat hebben.
[...]

ja, is ook weer zo.
had gister nog wat interessante links naar leesvoer gevonden (pdf), echter niet meer te downloaden

[MiezeL]

Oops beetje kansloze vraag, sorry.

Ben begonnen:D

[Voor 82% gewijzigd door MiezeL op 28-02-2007 17:25]

[T i M]

Mag je grid in de breedte relatief (veel) groter zijn dan in de hoogte?

[Dash2in1]

Ga hier denk ik ook maar eens mee aan de slag.

Hoewel ik me hoofd aan het breken ben op een enigszins zinnig algoritme om een leuk resultaat te krijgen, komt er niks in me op...

[zwippie]

Zo, weer wat te doen in de vrij uurtjes

Volgens mij neemt Marcj alweer de leiding in handen, dat heb je snel gedaan.

@TiM: Volgens mij is dat geen probleem.

[Marcj]

zwippie schreef op woensdag 28 februari 2007 @ 18:26:
Zo, weer wat te doen in de vrij uurtjes

Volgens mij neemt Marcj alweer de leiding in handen, dat heb je snel gedaan.

@TiM: Volgens mij is dat geen probleem.

Hoezo de leiding? Ik had gister gewoon nog ff wat tijd over. We hebben toch 2 maanden hiervoor? Dat is genoeg tijd, dus zo snel is er niet echt wat over te zeggen...

[EdwinG]

Marcj, heb je toevallig wat uitvoer-grids voor me?
Zelf heb ik nog geen resultaten, maar wel een validatie-script die ik wil testen.

[Varienaja]

thomahawks schreef op woensdag 28 februari 2007 @ 00:11:
EDIT: Mooie grid, alleen hoe heb je je score berekend? Ik zag dat je percentage wel overeenkomt met het aantal letters van de eerste set woorden en je grid, maar dat komt uit op 2781.

EDIT2: Zonder ook maar iets in een grid te zetten zit ik rond de 87-90% letters atm.

Apart grid, dat van marcj. Van boven breed, van onder smal. Het lijkt mij dat je juist een grid met zo'n klein mogelijke omtrek moet hebben. Heb je daar werkelijk 2781 letters in zitten? Ik heb 'm al tot 2403 gedrukt. 'compressie' van ~ 75%

[zwippie]

Marcj schreef op woensdag 28 februari 2007 @ 18:55:
[...]

Hoezo de leiding? Ik had gister gewoon nog ff wat tijd over. We hebben toch 2 maanden hiervoor? Dat is genoeg tijd, dus zo snel is er niet echt wat over te zeggen...

Daarom stond er ook een achter...


Het motiveert iig wel weer om zo snel al weer resultaten van meerdere mensen te zien/horen.

[RobIII]

Marcj schreef op woensdag 28 februari 2007 @ 00:10:
Ok, mijn eerste poging van mijn AI (is nog niet zo heel erg slim )

code:

Totale score: 14420
Totale percentage van max: 86
Tijd om uit te rekeken: 657ms

Hoe moet ik die score zien? Volgens mij heb je een score van 2781, of begrijpen we elkaar niet?
(oh, of is dat van alle groepen samen?)

Overigens dank voor deze set, de validator blijkt te werken (en je algo ook )
Een extra aantal grids zijn welkom op , om zo onze validator te kunnen...eh...valideren

[Voor 28% gewijzigd door RobIII op 01-03-2007 02:38]

[Varienaja]

RobIII schreef op donderdag 01 maart 2007 @ 01:21:
om zo onze validator te kunnen...eh...valideren

Je hebt er een paar extra.

BTW: Nieuw ideetje geimplementeerd; m'n eerste grid is zojuist van 2403 naar 2305 gegaan.

[Voor 20% gewijzigd door Varienaja op 01-03-2007 06:02]

[Marcj]

code:

Grid 1:
Score: 2204
Percentage van max: 68

Grid 2:
Score: 2540
Percentage van max: 67

Grid 3:
Score: 2463
Percentage van max: 67

Grid 4:
Score: 1865
Percentage van max: 67

Grid 5:
Score: 2151
Percentage van max: 67

Totale score: 11223
Totale percentage van max: 67
Tijd om uit te rekeken: 75797ms

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!

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?

edit2: Ik vind 67% eigenlijk al best laag aangezien het vrijwel onmogelijk is om onder de 50% te duiken (dan is elke letter voor minimaal twee woorden gebruikt).

[Voor 56% gewijzigd door Marcj op 01-03-2007 09:02]

[Pete]

Checkt de validator ook of er letters te veel in het grid staan?

[Marcj]

phsmit schreef op donderdag 01 maart 2007 @ 09:09:
Checkt de validator ook of er letters te veel in het grid staan?

Dat lijkt me wel de bedoeling. Of daar al aan gedacht is is natuurlijk een tweede...

Ik heb trouwens nog een kleine verbetering gevonden:

code:

Grid 1:
Score: 2135
Percentage van max: 66

Grid 2:
Score: 2404
Percentage van max: 63

Grid 3:
Score: 2374
Percentage van max: 64

Grid 4:
Score: 1792
Percentage van max: 64

Grid 5:
Score: 2066
Percentage van max: 65

Totale score: 10771
Totale percentage van max: 64
Tijd om uit te rekeken: 50906ms

[coenbijlsma]

Ik denk dat ik deze keer weer mee ga doen (maar het nu wel afmaken...) Lijkt me een leuke contest, dus moge de beste winnen!

[RobIII]

phsmit schreef op donderdag 01 maart 2007 @ 09:09:
Checkt de validator ook of er letters te veel in het grid staan?

Waarom zou 'ie? Het is jouw taak om je grid zo klein mogelijk met zo min mogelijk letters te maken. Als daar letters te veel in zitten gaat dat ten koste van je score, voor de 'validiteit' van je grid maakt het geen fluit uit.

Marcj schreef op donderdag 01 maart 2007 @ 09:18:
Dat lijkt me wel de bedoeling. Of daar al aan gedacht is is natuurlijk een tweede...

Er aan gedacht wel... geïmplementeerd nee

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!

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

[Voor 91% gewijzigd door RobIII op 01-03-2007 10:41]

[Dido]

Marcj: tel ik nou raar, of zitten er 4768 letters in invoerset 5, zodat een score van 2151 maar 45% zou zijn