Programming Contest Nieuwe Stijl: Contest 2 *WINNAARS LEZEN* Vorige deel Overzicht Volgende deel Laatste deel

Dit topic is onderdeel van een reeks. Ga naar het meest recente topic in deze reeks.

Pagina: 1 ... 7 ... 9 Laatste
Acties:
  • 5.302 views sinds 30-01-2008
  • Reageer

Onderwerpen


Acties:
  • 0 Henk 'm!

  • RedPixel
  • Registratie: Januari 2004
  • Laatst online: 15:31
veldsla schreef op dinsdag 01 mei 2007 @ 08:42:
[...]


R, zie http://www.r-project.org/

Een statistische programmeeromgeving. Ik had jammer genoeg niet voldoende tijd om echt veel dingen te implementeren. De start van de contest viel samen met de geboorte van mijn dochter O+
Gefeliciteerd! *O* Hoe heet ze? Is ze gezond, hoeveel weegt ze? ... Heeft ze al een pincode? :+

Mocht iemand mijn code willen zien:
http://wwwhizz.nl/meuk/WordGrid_5(final).rar

[ Voor 8% gewijzigd door RedPixel op 01-05-2007 10:20 ]

I see red pixels.


Acties:
  • 0 Henk 'm!

  • veldsla
  • Registratie: April 2000
  • Laatst online: 10-09 16:26
wwwhizz schreef op dinsdag 01 mei 2007 @ 10:14:
Gefeliciteerd! *O* Hoe heet ze? Is ze gezond, hoeveel weegt ze? ... Heeft ze al een pincode? :+
Ze heet Liset en weegt ondertussen al meer dan 5 kilo! Ze heeft zelfs nog geen spaarpot....Ben ik nu een slechte papa? ;)

Heb mijn scrippie ook maar even online gegooid.
Ik hoop trouwens maar dat in de uiteindelijke woordensets de ondergrens van 5 woorden niet opgezocht gaat worden. Het zou wel eens verkeerd uit kunnen pakken, maar ik had gisteravond echt geen tijd meer om het te fixen. ;(

Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Topicstarter
(overleden)
veldsla schreef op dinsdag 01 mei 2007 @ 11:00:
Ik hoop trouwens maar dat in de uiteindelijke woordensets de ondergrens van 5 woorden niet opgezocht gaat worden. Het zou wel eens verkeerd uit kunnen pakken, maar ik had gisteravond echt geen tijd meer om het te fixen. ;(
Reken maar dat we met de uiteindelijke woordensets bepaalde grenzen wel testen :Y)
Zowieso bekijken we hoe je programma omgaat met sets die niet (of gedeeltelijk niet) voldoen aan de specs :P

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
Is het mogelijk dat alle inzendingen (+ sources) alvast op de eerste pagina gezet worden?

Ik vind het wel leuk om alvast een overzichtje te hebben van de deelnemers. Er staan wel een paar exes nu online, maar het overzicht ontbreekt :)

Plus er is toch niemand meer die wijzigingen kan aanbrengen.

Acties:
  • 0 Henk 'm!

  • Marcj
  • Registratie: November 2000
  • Laatst online: 13:59
Gefeliciteerd veldsla met de kleine! *O*

Rob: hoeveel inzendingen hebben jullie nu uiteindelijk ontvangen?

Acties:
  • 0 Henk 'm!

  • Nick The Heazk
  • Registratie: Maart 2004
  • Laatst online: 07-09-2024

Nick The Heazk

Zie jij er wat in?

Mijn code kan je op deze pagina vinden.

Mijn excuses voor de rommelige code. Mensen die ze bekijken zullen duidelijk wel het verschil merken tussen de code die ik nog snel gisteren bij elkaar heb gehackt, en de beter gedocumenteerde code van een aantal weken geleden. Om mensen de code te besparen zal ik hier ook even kort de gebruikte techniek beschrijven;

1) De woorden worden gefiltered. Woorden die voorkomen in een ander woord (zowel gewoon als reversed) worden verwijderd.

2) De resterende woorden worden in een lijst gezet, gesorteerd op heuristiek. De heuristiek geeft de gewogen som weer van de letters in het woord, waarbij de gewichten gelijk zijn aan het totaal aantal voorkomens van die letter.

Info: De grid die gebruikt wordt om woorden op te zetten is een char[][]. Deze kan dynamisch groeien.

3) Het algoritme is ontworpen als een greedy brute force. Voor elk van de woorden in de lijst wordt nagegaan waar ze geplaatst kunnen worden in de grid. Dit gebeurt door middel van een concurrent horizontale en verticale scan van de grid.

Normaliter hadden alle gevonden mogelijkheden gecached moeten worden (systeem MarcJ). Zodanig dat enkel de mogelijkheden die conflicteren met het vorige geplaatste woord opnieuw gescand hoeven te worden. Helaas zaten er in de code van zaterdag een aantal fouten, waar ik niet echt de tijd meer voor vond om ze op te sporen. Dus dit is er uiteindelijk niet ingekomen.

Na het bepalen van de mogelijke plaatsen wordt het woord met de langste overlapping en de beste heuristiek geplaatst in 98,5% van de gevallen. In 1,5% van de gevallen gebeurt er een random walk; het algoritme kiest willekeurig een woord met de langste overlapping, ongeacht de heuristische waarde.

Zolang er nog woorden te plaatsen vallen, en er plaatsen gevonden zijn waar een woord geplaatst kan worden, keert het algoritme terug naar 3. (We merken hier bij op, dat het algoritme potentieel geen oplossing geeft indien het de woorden nergens meer kan schakelen aan andere woorden. Er is geen mechanisme voorzien om ergens op een lege plaats verder te gaan--tijdsgebrek :). Dat is dan ook een potentieel erg zwak punt in dit algoritme.)

Al bij al is dit een zeer rekenintensief algoritme; met de cacheing ging het weliswaar 110% sneller, maar dat werkte helaas met fouten.

Oh, en het is zo robuust als een kaartenhuisje. Er is geen enkele vorm van foutenafhandeling te vinden, met uitzondering van het printen van wat foutboodschappen (/me mompelt iets over tijdsgebrek en minder schoolwerk :))

Edit: Waar is de elementaire beleefdheid? Proficiat met je nieuwe spruit O+. Hopelijk zijn alle specs in orde :).

[ Voor 6% gewijzigd door Nick The Heazk op 01-05-2007 14:12 ]

Performance is a residue of good design.


Acties:
  • 0 Henk 'm!

  • veldsla
  • Registratie: April 2000
  • Laatst online: 10-09 16:26
RobIII schreef op dinsdag 01 mei 2007 @ 11:01:
Reken maar dat we met de uiteindelijke woordensets bepaalde grenzen wel testen :Y)
Zowieso bekijken we hoe je programma omgaat met sets die niet (of gedeeltelijk niet) voldoen aan de specs :P
Oei...net even gekeken, de woordeindoverlapmerge functie faalt als ie geen overlap kan vinden :( Had ik met 1 extra regeltje kunnen fixen. |:(

Yikes....er zitten nog een paar foutjes in die alleen de kop opsteken op die kleine setjes, de gridsize wordt ook te klein gegokt :'(

Nou ja, gelukkig is Liset een lief meisje!

[ Voor 17% gewijzigd door veldsla op 01-05-2007 11:27 ]


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Topicstarter
(overleden)
veldsla schreef op dinsdag 01 mei 2007 @ 11:19:
Nou ja, gelukkig is Liset een lief meisje!
Which reminds me: *O* Feli! :P (Vergeten in de vorige post). Heb je pics?

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Verwijderd

veldsla schreef op dinsdag 01 mei 2007 @ 08:42:
R, zie http://www.r-project.org/

Een statistische programmeeromgeving. Ik had jammer genoeg niet voldoende tijd om echt veel dingen te implementeren. De start van de contest viel samen met de geboorte van mijn dochter O+
Ziet er interessant uit, dat R.

En natuurlijk van harte gefeliciteerd met de gezinsuitbreiding. Leuk dat je desondanks toch nog de tijd hebt weten vrij te maken om aan de contest deel te nemen.

Acties:
  • 0 Henk 'm!

  • veldsla
  • Registratie: April 2000
  • Laatst online: 10-09 16:26
RobIII schreef op dinsdag 01 mei 2007 @ 11:29:
Which reminds me: *O* Feli! :P (Vergeten in de vorige post). Heb je pics?
Mag ik u voorstellen: Liset (als jpg link om het topic niet teveel te vervuilen!)

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
veldsla schreef op dinsdag 01 mei 2007 @ 12:14:
[...]


Mag ik u voorstellen: Liset (als jpg link om het topic niet teveel te vervuilen!)
Gefeliciteerd hoor, het is een prachtige baby!

Hier mijn inzending voor de contest voor de geintresseerde. Zowel executable as source (vb.net 2.0)

http://www.smokeysoft.com/Contest2.rar

[ Voor 41% gewijzigd door Serpie op 01-05-2007 13:36 ]


Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

veldsla schreef op dinsdag 01 mei 2007 @ 08:42:
...De start van de contest viel samen met de geboorte van mijn dochter O+
Dan heeft ze gelijk mee kunnnen kijken hoe dat werkt, zo'n GoT contest ;)

Maare, Gefeliciteerd. :)

Wat de tot nu toe genoemde bugjes betreft, volgens mij pakt mijn oplossing die goed op.
Sommige programma's hebben daar wat problemen mee.

Mijn uiteindelijke testset zit ook in de zip. De eerste 6 grids zijn de speciaaltjes.

Acties:
  • 0 Henk 'm!

  • cobratbq
  • Registratie: Maart 2001
  • Laatst online: 17-12-2015
Hmmm... ik ben benieuwd hoe ze naar de grenzen gaan kijken. Ik heb zelf namelijk geen check gemaakt op het aantal woorden en aantal lists, dus als ze verwachten dat woordje 1000 en verder niet meegenomen worden, dan gaat mijn programma tegenvallen :D.

One ring to rule them all, one ring to find them, one ring to bring them all, and in darkness bind them...


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Topicstarter
(overleden)
cobratbq schreef op dinsdag 01 mei 2007 @ 16:46:
Hmmm... ik ben benieuwd hoe ze naar de grenzen gaan kijken.
Je moet het niet alleen zoeken in de grenzen. We zouden het programma ook een gerenamede JPG kunnen voeren om te zien wat er gebeurt >:)

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

Dat heb ik ook niet duidelijk gekregen.
Je zou ook nog kunnen zeggen, dit is een ongeldig grid, die slaan we over.

Mijn programma plaatst ze gewoon als is het wel op het snelst mogelijke algoritme om geen tijd te verliezen met feitelijk onjuiste grids.

Edit:
een gerenamede jpg... hmm
Daar maakt hij ook gridjes van die er best wel apart uitzien.

[ Voor 16% gewijzigd door KoW op 01-05-2007 16:53 ]


Acties:
  • 0 Henk 'm!

  • Creepy
  • Registratie: Juni 2001
  • Laatst online: 07:55

Creepy

Tactical Espionage Splatterer

De .jpg maar dan omget naar ascii? :P

"I had a problem, I solved it with regular expressions. Now I have two problems". That's shows a lack of appreciation for regular expressions: "I know have _star_ problems" --Kevlin Henney


Acties:
  • 0 Henk 'm!

  • Pete
  • Registratie: November 2005
  • Laatst online: 07-09 17:51
Creepy schreef op dinsdag 01 mei 2007 @ 17:32:
De .jpg maar dan omget naar ascii? :P
Is het de volgende contest omdat zo realistisch mogelijk te realiseren?

petersmit.eu


Acties:
  • 0 Henk 'm!

  • cobratbq
  • Registratie: Maart 2001
  • Laatst online: 17-12-2015
RobIII schreef op dinsdag 01 mei 2007 @ 16:47:
Je moet het niet alleen zoeken in de grenzen. We zouden het programma ook een gerenamede JPG kunnen voeren om te zien wat er gebeurt >:)
Had je dat niet een paar dagen eerder kunnen zeggen? :P

Edit:
Btw, hier is mijn oplossing. Verwacht er niet te veel van en stop d'r niet te veel in, zoals plaatjes enzo ;)
Download: Solver

Edit2:
Als iemand het zich afvraagt: de filter..... methode wordt niet gebruikt, omdat m'n plaatsingsalgoritme eenzelfde check ook al uithaald.

[ Voor 37% gewijzigd door cobratbq op 01-05-2007 21:22 . Reden: Additie ]

One ring to rule them all, one ring to find them, one ring to bring them all, and in darkness bind them...


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Topicstarter
(overleden)
cobratbq schreef op dinsdag 01 mei 2007 @ 18:44:
[...]

Had je dat niet een paar dagen eerder kunnen zeggen? :P
Stond / staat toch écht in de TS:
RobIII schreef op maandag 26 februari 2007 @ 19:32:
...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).
:Y)

[ Voor 16% gewijzigd door RobIII op 01-05-2007 19:11 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • Robbbert
  • Registratie: April 2005
  • Laatst online: 10-09 19:11
Hier mijn inzending: http://home.deds.nl/~robbbert/contest.rar
Zowel exe als source, zit ook validator bij.

Code werkt, maar is kwalitatief niet al te best.
Alles staat als een dikke sliert in 1 bestand, veel kopier/plakwerk i.p.v. functies en nauwelijks commentaar.

Ik had er uiteindelijk geen tijd meer voor. Voorbereiden voor me examens vind ik nu belangrijker.

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
RobIII schreef op dinsdag 01 mei 2007 @ 19:11:
[...]

Stond / staat toch écht in de TS:

[...]

:Y)
Maar ik neem aan dat de overige categorieen wel getest worden met correcte word sets?

Acties:
  • 0 Henk 'm!

  • Fiander
  • Registratie: Februari 2001
  • Laatst online: 28-05 12:35
als je der hernoemde JPG's in gaat stoppen, gaat de mijne zijn best doen om deze als strings in een grid te plaatsen, echter zal die ook keurig crashen als er te weinig woorden in dat jpg zitten.

net getest, en het plaatje werd als één string gezien, en de applicatie crashde keurig zoals gepland. ;-)

mare, als julie een klant waren geweest, had ik je een rekening gestuurt, omdat julie afwijken van de door julie opgegeven specs. en ik daarvoor onderzoek moest doen. ;)

Deze sig is een manueel virus!! Als je dit leest heb je het. Mail dit bericht naar iedereen die je kent, en verwijder alle bestanden van je computer.


Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

Robbbert schreef op dinsdag 01 mei 2007 @ 19:12:
Hier mijn inzending: http://home.deds.nl/~robbbert/contest.rar
Zowel exe als source, zit ook validator bij.
Hij is niet echt snel tevreden met mijn testset.

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
Poeh, een hoop deelnemers trouwens.
Ik heb even alle source download linkjes uit het topic verzameld, dan staan ze makkelijk bij elkaar dit zijn ze:

Marcj - JAVA
Arty_Shock - C#
Kow - Visual FoxPro
DaCoTa - JAVA
wwwhizz - JAVA
Veldsla - R
Nick The Heazk - JAVA
Serpie - VB.NET
cobratbq - JAVA
Robbbert - C

Acties:
  • 0 Henk 'm!

  • Arjan
  • Registratie: Juni 2001
  • Niet online

Arjan

copyright is wrong

Serpie schreef op dinsdag 01 mei 2007 @ 20:44:
Poeh, een hoop deelnemers trouwens.
Ik heb even alle source download linkjes uit het topic verzameld, dan staan ze makkelijk bij elkaar dit zijn ze:

Marcj - JAVA
Arty_Shock - C#
Kow - Visual FoxPro
DaCoTa - JAVA
wwwhizz - JAVA
Veldsla - R
Nick The Heazk - JAVA
Serpie - VB.NET
cobratbq - JAVA
Robbbert - C
Arjan - C++
zal er nog wat uitleg bijgeven:

Als je het programma start, laadt deze de woordenlijst in, en kijkt vervolgens of ie aangeroepen wordt met commandline opties. Zo nee, dan dient dit process als een server voor andere instanties van deze exe.
Afhankelijk van de hoeveelheid threads die er gestart mogen worden, starten er enkele threads op die allemaal afzonderlijk een grid gaan berekenen. Er wordt wat statistische data rond gegooid om te kunnen bepalen hoelang de volgende grid erover mag doen.

Het daadwerkelijke plaatsen van woorden is heel dom. Het programma zoekt naar mogelijke plaatsen om het woord neer te zetten. Hij doorloopt alle mogelijkheden, tenzij je hebt aangegeven dat je genoegen neemt met minder dan 100% overlap.
In dat geval stopt het zoeken bij de eerst gevonden mogelijkheid die voldoet aan de minimale overlap.

dit levert bijvoorbeeld bij words1.txt een behoorlijke tijdswinst op als je maar naar 20% overlap laat zoeken.

Wat doet mijn programma NIET
- caching, het zoeken door niet veranderde gedeelten van de grid is tijdrovend, maar het cachen zou me niet genoeg tijdswinst opleveren.
- sorteren van woorden, zat er eerst in, leverde ook niet genoeg winst op
- het 'wegen' van woorden, veel voorkomende letters meer gewicht geven enzo, leverde ook maar marginale winsten op en heeft de uiteindelijke versie dus ook niet gehaald.
- backtracing, mijn methode haalt maar een bepaalde score, betere scores zouden eigenlijk alleen haalbaar zijn met backtracing, maar ik had besloten dat het niet rendabel zou zijn gezien de tijdslimiet van 60min. (als de uiteindelijke testgrids maar enkele grids groot zijn piep ik wel anders natuurlijk ;))

[ Voor 43% gewijzigd door Arjan op 01-05-2007 21:09 ]

oprecht vertrouwen wordt nooit geschaad


Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 09-09 15:29
Ik ben wel benieuwd naar dat R. :) Verder natuurlijk de usual suspects. ('t Verbaast me een beetje dat de PHP programmeurs het laten afweten?)

Acties:
  • 0 Henk 'm!

  • Fiander
  • Registratie: Februari 2001
  • Laatst online: 28-05 12:35
dan kan ik niet achter blijven.
contest2_01.zip

werkt als volgt,
het grid word als één array van 22500 chars gezien, volgende regel is sprong van 150 pos, vorige regel is -150 pos. dit is efficienter dan een twee dimensionaal grid.

de woorden worden eerst gefilterd ( dubbele eruit ) en indien het een redelijke compressie oplevert, samen gevoegt. ( bij proberen, kwam ik bij één keer samenvoegen op de beste grid uit.
daarna worden de woorden gesorteerd op grote ( de langste bovenaan )

het langste woord word op het grid geplaats, en daarna word in een loop welke loopt tot alle woorden op het grid staan, er telkens door de nog niet geplaatste woorden geloopt, en door het gehele grid gezocht om het op dat moment best te plaatsten woord.

bij het plaatsen van een woord, worden de posities opgenomen in een array waarin word bijgehouden welke posities op het grid in gebruik zijn. bij het zoeken naar een plekje voor een woord, word er dus ook alleen op posities gezocht welke in deze array staan, en lege grid posities worden niet doorzocht.

Deze sig is een manueel virus!! Als je dit leest heb je het. Mail dit bericht naar iedereen die je kent, en verwijder alle bestanden van je computer.


Acties:
  • 0 Henk 'm!

  • EdwinG
  • Registratie: Oktober 2002
  • Laatst online: 09-09 16:54
RobIII schreef op dinsdag 01 mei 2007 @ 16:47:
Je moet het niet alleen zoeken in de grenzen. We zouden het programma ook een gerenamede JPG kunnen voeren om te zien wat er gebeurt >:)
Als ik het goed heb, geeft mijn programma in deze situatie een hele lijst met foutmeldingen.
Om precies te zijn, er komt een foutmelding als een niet-ascii-teken gebruikt wordt.
Per niet-ascii-teken een regel dus :P

Bezoek eens een willekeurige pagina


Acties:
  • 0 Henk 'm!

  • EdwinG
  • Registratie: Oktober 2002
  • Laatst online: 09-09 16:54
Soultaker schreef op dinsdag 01 mei 2007 @ 21:42:
('t Verbaast me een beetje dat de PHP programmeurs het laten afweten?)
* EdwinG meld zich
Af laten weten? Volgens mij was ik de eerste/enige met een onine validator. Ok, zegt nog niets over mijn script:
woordpuzzel_edwing.zip

Mijn idee was vrij eenvoudig, zoek vanaf X posities vanaf de rand naar woorden die vanaf daar richting rand & verder geplaatst kunnen worden. Uiteraard eerst overbodige woorden er uit halen, en woorden combineren.

Het combineren van worden gaat in de eerste plaats op de grootste overlapping tussen de woorden. Dit in meerdere ronden, om een beter resultaat te halen.

Helaas had ik te weinig tijd om mijn 'X' posities idee te implementeren. Nu zoekt mijn script eigenlijk steeds de rand af, om vanaf daar nieuwe woorden te plaatsen. (Met telkens 1 teken overlapping)

[ Voor 3% gewijzigd door EdwinG op 01-05-2007 23:22 . Reden: Quote gespecifieerd ]

Bezoek eens een willekeurige pagina


Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
Ik kom er net achter dat mijn prog een vervelende bug bevat die eventueel op invloed kan zijn op de scores van anderen.

Als je het programma afsluit, voordat hij klaar is met het parsen van de woorden dan gaat hij gewoon door op de achtergrond. Het is dus beter om hem gewoon te killen via taakbeheer.
Hopenlijk gaat alles goed, of kunnen de mods hier rekening mee houden.

Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

Bij mij is de user interface een extraatje die los staat van de threads die het eigenlijke werk doen.
Sluit je de userinterface dan wordt een stop message gestuurd naar de threads maar voordat die gestopt zijn ben je al gauw een seconde of wat verder.

Acties:
  • 0 Henk 'm!

  • zwippie
  • Registratie: Mei 2003
  • Niet online

zwippie

Electrons at work

Serpie schreef op woensdag 02 mei 2007 @ 07:20:
Ik kom er net achter dat mijn prog een vervelende bug bevat die eventueel op invloed kan zijn op de scores van anderen.

Als je het programma afsluit, voordat hij klaar is met het parsen van de woorden dan gaat hij gewoon door op de achtergrond. Het is dus beter om hem gewoon te killen via taakbeheer.
Hopenlijk gaat alles goed, of kunnen de mods hier rekening mee houden.
Diskwalificatie! :+


Een 'tactiek' in mijn programma was overigens om voor het hele alfabet bij te houden op welke positie in het veld elke letter voorkomt, een lookup table. Dat scheelt een hoop iteraties als je op zoek bent naar een karakter in het veld, je hoeft dan niet het hele veld door te zoeken maar weet direct de posities.
Van elk woord dat wordt geprobeerd worden de eerste x karakters genomen, de locaties van deze karakters opgezocht, het woord in alle richtingen geprobeerd en de score berekend.
Verder is mijn inzending niet zo geavanceerd. Geen multithreading, geen cache, geen branching.

How much can you compute with the "ultimate laptop" with 1 kg of mass and 1 liter of volume? Answer: not more than 10^51 operations per second on not more than 10^32 bits.


Acties:
  • 0 Henk 'm!

Verwijderd

Soultaker schreef op dinsdag 01 mei 2007 @ 21:42:
[...]

Ik ben wel benieuwd naar dat R. :) Verder natuurlijk de usual suspects. ('t Verbaast me een beetje dat de PHP programmeurs het laten afweten?)
R - Ruby?

Acties:
  • 0 Henk 'm!

  • veldsla
  • Registratie: April 2000
  • Laatst online: 10-09 16:26
zwippie schreef op woensdag 02 mei 2007 @ 09:48:
Een 'tactiek' in mijn programma was overigens om voor het hele alfabet bij te houden op welke positie in het veld elke letter voorkomt, een lookup table. Dat scheelt een hoop iteraties als je op zoek bent naar een karakter in het veld, je hoeft dan niet het hele veld door te zoeken maar weet direct de posities.
Van elk woord dat wordt geprobeerd worden de eerste x karakters genomen, de locaties van deze karakters opgezocht, het woord in alle richtingen geprobeerd en de score berekend.
Hee, zoiets heb ik ook, maar dan neem ik alle karakters :). Sterker nog, als je dan elke gevonden karakterpositie voor alle vier de printrichtingen omrekent naar het start karakter en dan het voorkomen van de startposities telt dan weet je ook meteen de potentiele overlap voor dat woord! Hoef je alleen nog maar te kijken of er nog mismatch karakters zijn in aflopende volgorde van overlap!
Nee, R als in R zie http://www.r-project.org

[ Voor 7% gewijzigd door veldsla op 02-05-2007 10:47 ]


Acties:
  • 0 Henk 'm!

  • Robbbert
  • Registratie: April 2005
  • Laatst online: 10-09 19:11
zwippie schreef op woensdag 02 mei 2007 @ 09:48:
Een 'tactiek' in mijn programma was overigens om voor het hele alfabet bij te houden op welke positie in het veld elke letter voorkomt, een lookup table. Dat scheelt een hoop iteraties als je op zoek bent naar een karakter in het veld, je hoeft dan niet het hele veld door te zoeken maar weet direct de posities.
Van elk woord dat wordt geprobeerd worden de eerste x karakters genomen, de locaties van deze karakters opgezocht, het woord in alle richtingen geprobeerd en de score berekend.
Verder is mijn inzending niet zo geavanceerd. Geen multithreading, geen cache, geen branching.
Ik heb ook zoiets met score berekenen, maar bij mij zoekt het programma het hele veld af.

Eerst had ik het zo dat een woord werd geplaatst op de positie met de beste score. Net voor de deadline heb ik snel nog gemaakt dat telkens van alle woorden van alle posities de score wordt berekend en dat dan het woord met de beste score voor de positie wordt geplaatst. Alleen dit is niet zo snel :P

Acties:
  • 0 Henk 'm!

  • DaCoTa
  • Registratie: April 2002
  • Laatst online: 05-09 23:19
Robbbert schreef op woensdag 02 mei 2007 @ 10:55:
[...]
Eerst had ik het zo dat een woord werd geplaatst op de positie met de beste score. Net voor de deadline heb ik snel nog gemaakt dat telkens van alle woorden van alle posities de score wordt berekend en dat dan het woord met de beste score voor de positie wordt geplaatst. Alleen dit is niet zo snel :P
Dit is ook mijn taktiek. Alleen is bij mij de berekening van 'beste' het verschil in percentage over 2 woorden. Op deze manier worden haakse overlappen beter geplaatst. Dit systeem werkt goed tot ongeveer de helft van de te plaatsen woorden, het percentage zit dan vaak onder de 50%. Helaas gaat dit weer hard omhoog om de tweede helft van de woorden te plaatsen.

Verder heb ik geen grid, alleen lettersoep in twee arrays, een waar de positie in staat en een waar de letter in staat. Bij ieder te plaatsen woord onthou ik alleen de nieuwe letters en een verwijzing naar het voorlaatst geplaatste woord. Op deze manier is een grid heel goedkoop qua geheugenbelasting, ik kwam tot ruim 700.000 grids in memory met een heap van 500MB. Het doorzoeken van al deze grid was alleen een probleem ;)

Acties:
  • 0 Henk 'm!

  • Marcj
  • Registratie: November 2000
  • Laatst online: 13:59
Ik zal het idee achter mijn algoritme ook proberen uit te leggen.

Het idee is om alle mogelijke plaatsingen die tenminste 1 letter overlap hebben te onthouden. Zo hoef ik nooit te controleren waar een woord past. Als ik dan een nieuw woord op het veld plaats moet ik eerst de huidige plaatsingen controleren, omdat sommige niet meer passen, en zal ik nieuwe plaatsingen kunnen maken, omdat er mogelijk nieuwe letters aan de grid zijn toegevoegd.

Uiteraard worden deze plaatsingen op een zodanige manier opgeslagen dat ik eenvoudig alle mogelijk plaatsingen van een woord, of juist alle plaatsingen door een bepaalde plek op de grid, kan doorzoeken. Dit gebeurt allemaal in een HashMatrix (dubbele HashTable).

Wanneer ik een nieuwe woord probeer te plaatsen zoek ik dus een plaatsing van een woord die er nog niet in zit en die zoveel mogelijk overlap heeft. Als er meerdere zijn met dezelfde hoeveelheid overlap, gaat hij ook nog kijken hoeveel plaatsingen niet meer kunnen als ik dat woord zou neerzetten. Degene die de minste andere woorden blokkeert, wordt dan neergezet.

Daarnaast is mijn grid helemaal dynamisch en bestaat uit een heleboel GridNode objecten die ieders een pointer naar de GridNode boven, rechts, onder en links ervan hebben. Zo kan de GridNode eigenlijk oneindig groeien zonder dat er veel speciale dingen gebeuren moeten.

Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

Bijzonder :)
Dat is wat mijn algoritme ook doet, alleen doet die van jou het stukken sneller.

Wegens tijdsgebrek is het "Degene die de minste andere woorden blokkeert, wordt dan neergezet." onderdeel niet geimplementeerd. (Staat wel in de code file als optimalisatieoptie omschreven)

Ik heb ook geen echt grid, maar een tabel met daarin alle geplaatste letters.

Mijn oorspronkelijke, snellere, algoritme heeft een dubbele weergave van zijn grid in 2 arrays, eentje voor horizontale weergave en eentje voor vertikale weergave.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 09-09 15:29
Mijn algoritme komt er op neer dat ik een grid heb, en van alle mogelijke woorden op alle mogelijke plaatsen, plaats ik het woord dat de meeste letters overlap heeft met het huidige grid. Meestal zijn er meerdere mogelijkheden, en dan kies ik de plaatsing zo dicht mogelijk in het midden.

Ik doe dus N iteraties en bij elke iteratie ga ik alle woorden op alle posities af. Vrij lomp; efficientie is O(M x N3) met M de gemiddelde woordlengte en N het aantal woorden, maar het is redelijke geoptimaliseerd waardoor het in de praktijk snel gaat.

Ik had grootse plannen voor het clusteren van woorden en dan groepen met grotere gelijkenis apart plaatsen (een beetje zoals Arjan ook beschreef) maar dat leek in de praktijk weinig winst op te leveren (hoewel ik 't ook niet heel geavanceerd geïmplementeerd had).

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
Soultaker schreef op woensdag 02 mei 2007 @ 12:58:
Mijn algoritme komt er op neer dat ik een grid heb, en van alle mogelijke woorden op alle mogelijke plaatsen, plaats ik het woord dat de meeste letters overlap heeft met het huidige grid. Meestal zijn er meerdere mogelijkheden, en dan kies ik de plaatsing zo dicht mogelijk in het midden.
Hmm das mijn algoritme :P, bij gelijke letters overlap plaats ik echter het woord welke de meeste letters heeft die het minst voorkomen (Q, Y, X etc) deze leken me moeilijker te plaatsen.

Hij sorteert de woordenlijst ook eerst zodat deze woorden eerst geplaatst worden (als we niet zo diep zoeken).

Ik kon niet altijd zoeken door alle woorden, bij een grid van 999 woorden deed hij er dan 20 minuten over. Ik bepaal het aantal te controleren woorden aan de hand van de tijd die ik heb en hoeveel woorden er in de lijst zitten.

Bij start deel ik de totale tijd door het aantal grids voor de tijd per grid, dat gebruik ik om te bepalen hoe diep ik moet zoeken. Ad-hoc heb ik op het laatst nog even toegevoegd dat hij dat na elke grid opnieuw bepaald, kom ik op het eind dus tijd te kort dan bouwt hij grids heel snel af met een zoekdiepte van 1.

Mijn grid is een multidimensionale chararray, ik wilde eigenlijk dit nog vervangen door een jagged array omdat dat performanter is maar daar kwam ik helaas ook niet meer aan toe.

Acties:
  • 0 Henk 'm!

  • maleadt
  • Registratie: Januari 2006
  • Laatst online: 09-09 20:06
Door dat weekje in Tsjechië deze contest helemaal uit het oog verloren :'( Anyway, in de categorie van snelheid of kleinste grid zou toch ik niet vermeld staan, maar ik had wel mn best gedaan voor een goed begrijpbare en enigszinds robuste code... Och ja, als het iemand intereseert: mijn Perl-brouwsel is hier te bezichtigen. (Voor het geval iemand mijn code uitprobeert: "generator.pl words.txt" leest het hele bestand, split dus nog niet op newlines voor een volgend grid)

Volgende contest beter, moge de besten winnen :)
maleadt

Acties:
  • 0 Henk 'm!

Verwijderd

Soultaker schreef op woensdag 02 mei 2007 @ 12:58:
Mijn algoritme komt er op neer dat ik een grid heb, en van alle mogelijke woorden op alle mogelijke plaatsen, plaats ik het woord dat de meeste letters overlap heeft met het huidige grid. Meestal zijn er meerdere mogelijkheden, en dan kies ik de plaatsing zo dicht mogelijk in het midden.

Ik doe dus N iteraties en bij elke iteratie ga ik alle woorden op alle posities af. Vrij lomp; efficientie is O(M x N3) met M de gemiddelde woordlengte en N het aantal woorden, maar het is redelijke geoptimaliseerd waardoor het in de praktijk snel gaat.

Ik had grootse plannen voor het clusteren van woorden en dan groepen met grotere gelijkenis apart plaatsen (een beetje zoals Arjan ook beschreef) maar dat leek in de praktijk weinig winst op te leveren (hoewel ik 't ook niet heel geavanceerd geïmplementeerd had).
Leuk, mijn eerste opzet ging ook uit van het maken van clusters. Ik probeerde clusters van zoveel mogelijk woorden (3/4/5) horizontaal te maken, en dan daarop zoveel mogelijk woorden vertikaal te plaatsen met overlap 3(/4/5). De gevonden clusters wilde ik dan (in eerste instantie) als een ketting aan elkaar knopen.
Eerste probleem was dat de benodigde rekentijd voor het vinden van een goede cluster wel erg groot was. Maar dat heb ik voor clusters met 4 horizontale woorden op weten te lossen.
Tweede en vervelender probleem was dat ik hiermee met wordset01 (testset I) met geen mogelijkheid onder de 2011 kon komen, terwijl MarcJ al op de 1952 zat. De belangrijkste reden was dat het steeds moeilijker wordt om met de overgebleven woorden vergelijkbare clusters te maken. De grootste cluster die ik met wordset01 kon vinden met 4 woorden horizontaal, had er 8 vertikaal. De gemiddelde opbrengst was dan (4*8)/(4*8) = 2,67 chars per geplaatst woord. En dat is bij een ketting-methode veel te weinig, omdat je met de overblijvende woorden vrijwel alleen maar kleinere clusters maakt, en uiteindelijk teveel losse woorden overhoudt. En een cluster van 4x4 heeft al gemiddelde 2.Terwijl een winnende oplossing (wordset01) op basis van een 4x@ cluster toch een gemiddelde van rond de 2.5 moet halen met de op de cluster te plaatsen woorden. En dat is best veel.

Uiteindelijk heb ik dat clusteren-van-clusters links laten liggen, en ben overgegaan op het zoeken van één zo'n cluster, om daarop te gaan itereren.

Wat dat itereren betreft: Soultaker doet kennelijk een depth-1 search. Ik doe een search van (afhankelijk van de situatie) 2-5 diep, waarbij ik adhv. diverse criteria in de zoekboom snijd. Zo kon ik het itereren op 2-diep in bijvoorbeeld grid01uitvoeren in een acceptabele 5 seconden.
De winst hierbij zit in het feit dat het niet per definitie voordeliger is om een woord te plaatsen met overlap 3, als je in plaats daarvan met het plaatsen van een woord met overlap 2 later een woord met overlap 5 kunt plaatsen, terwijl je met het plaatsen van dat woord van 3 die mogelijkheid elimineert... Uit mijn tests bleek dat bij wordset01 het verschil tussen alleen al 1-diep en 2-diep zoeken iets van 20 cellen was.

Overigens levert naar mijn ervaring het zo dicht mogelijk in het midden plaatsen van de woorden niet per definitie de beste oplossing (laagste score). Welliswaar begin je lekker compact, maar daardoor verminder je juist het maken van aanknopingspunten waar je later mogelijk meer kan scoren. Iets in die geest.
Mijn gevoel wordt ondersteund met het feit dat de beste vorm die ik voor grid01 gevonden heb (wat overigens 2h15m kostte, maar dan heb je ook wat), visueel gezien aanzienlijk minder compact is dan een paar oplossingen met wat slechtere scores.

Ik probeer vanavond of morgenavond tijd vrij te maken voor een meer uitgebreide uitleg (het zit kwa details redelijk ingewikkeld in elkaar), en zet die dan online tesamen met de code, exes, de resultaten op de drie test sets, en de beste grids die ik gevonden heb.

Acties:
  • 0 Henk 'm!

  • Soultaker
  • Registratie: September 2000
  • Laatst online: 09-09 15:29
Verwijderd schreef op woensdag 02 mei 2007 @ 15:39:
Wat dat itereren betreft: Soultaker doet kennelijk een depth-1 search. Ik doe een search van (afhankelijk van de situatie) 2-5 diep, waarbij ik adhv. diverse criteria in de zoekboom snijd. Zo kon ik het itereren op 2-diep in bijvoorbeeld grid01uitvoeren in een acceptabele 5 seconden.
Dan plaats je woorden gewoon op volgorde, neem ik aan? (Dus in stap N plaats je altijd woord N uit je lijst, ongeacht of andere woorden misschien beter zouden passen) Mijn ervaring was dat alle mogelijke woorden tegelijk als mogelijkheid zien (met 1 ply diep) een grote verbetering oplevert, maar dan is het echt onmogelijk om meer dan 1 ply te doen (was al lastig genoeg omdat een beetje vlot te krijgen).
Overigens levert naar mijn ervaring het zo dicht mogelijk in het midden plaatsen van de woorden niet per definitie de beste oplossing (laagste score). Welliswaar begin je lekker compact, maar daardoor verminder je juist het maken van aanknopingspunten waar je later mogelijk meer kan scoren. Iets in die geest.
Dat had ik ook bedacht, maar een omgekeerde heuristiek (woorden zo ver mogelijk weg van het zwaartepunt plaatsen) leverde eigenlijk slechtere scores op, omdat je nooit een goede dichtheid krijgt om meerdere letters overlap te krijgen. De reden dat ik uiteindelijk maar voor 'dicht bij het midden' gegaan ben, is dat het gewoon beter werkte dan random, en andere simpele heuristieken niet beter werkten.

Acties:
  • 0 Henk 'm!

Verwijderd

Soultaker schreef op woensdag 02 mei 2007 @ 15:47:
Dan plaats je woorden gewoon op volgorde, neem ik aan? (Dus in stap N plaats je altijd woord N uit je lijst, ongeacht of andere woorden misschien beter zouden passen).
Als ik zoek op bijvoorbeeld 4-diep, dan bepaal ik een 'beste' score van minimaal 1 en maximaal 4 woorden op basis van de volgende criteria: als

1) de gemiddelde (!) opbrengst per te plaatsen woord in de 'current' iteratiestap beter is dan in de 'beste' tot nu toe in deze iteratie gevonden oplossing,
of
2) het gemiddelde gelijk is, maar de nieuwe oplossing minder woorden heeft,

dan vervang ik mijn beste oplossing door de nieuwe. Voorbeeld van wat er tijdens het itereren kan gebeuren:
code:
1
2
3
4
5
Found better UW match with 12 ( 2 2 3 5) - removing previous matches
Found better UW match with 6 ( 2 4) - removing previous matches
Found better UW match with 3 ( 3) - removing previous matches
Found better UW match with 10 ( 3 3 4) - removing previous matches
[339] Placing 'kieren' at (130,124) UW profit=3

Criterium 1) wordt demonstreerd op regels 2 en 4, en criterium 2) op regel 3.

Uiteindelijk besluit ik dan om of alle woorden in de beste oplossing te plaatsen, of alleen het eerste. Plaats ik er meer dan een, dan maakt de volgorde uiteraard niet uit.
Soultaker schreef op woensdag 02 mei 2007 @ 15:47:
Mijn ervaring was dat alle mogelijke woorden tegelijk als mogelijkheid zien (met 1 ply diep) een grote verbetering oplevert, maar dan is het echt onmogelijk om meer dan 1 ply te doen (was al lastig genoeg omdat een beetje vlot te krijgen).
Als je dieper dan 1 wilt gaan zoeken, dan zijn er twee voor de hand liggende aspecten waar je je op kunt richten.

1) Bepaal criteria om zoveel mogelijk in de zoekboom te kunnen snijden, zonder 'teveel kinderen met het badwater weg te gooien' (;)) .

Ik heb nogal wat lopen uitproberen, en wat bij mij erg goede resultaten opleverde, was het alleen dieper de recursie ingaan als een porentieel te plaatsen woord as-is een winst van tenminste twee karakters opleverde. Daarmee werd de grote bulk iteraties van woorden met overlap 1 weggesneden, en kon ik tamelijk probleemloos 2-diep gaan zoeken. Daarnaast heb ik nog wat extra criteria, zoals een vergelijking van de 'current' beste oplossing met de verwachting van de maximale winst die bereikt kan worden met de 'current' iteratie.

Aardig aspect is dat het zoeken sneller gaat, naarmate er minder woorden over zijn. Bij zoeken op 2-diep gaat bij mijn implementatie het laatste deel dermate snel, dat ik als ik nog 200 woorden over heb, ik over ga op 3-diep, en bij minder dan 100 woorden 4-diep. Dit kost (iig met wordset 01) maar weinig extra tijd, doch leverde wel weer een aantal karakters winst op.

2) Bepaal gegeven een bordsituatie, efficient welke van de nog niet geplaatste woorden matchen met opbrengst >= 2. Dat kan ik per interessant vakje (*) in O(n), waarbij n het aantal in theorie passende woorden (dus met overlap 2 of meer) is. Het misschien wel leukste deel van mijn aanpak is dat het vinden van de verzameling van in theorie passende woorden bij mij O(1) is. En hiervoor hoef ik helemaal niet naar de verzameling met alle overgebleven woorden te kijken...

Tesamen met een heleboel middels profilen bepaalde micro-optimalisaties werd het mogelijk om per seconde 10^5 of zo iteratie-stappen uit te voeren.

(*) dat zijn de vakjes die door een zojuist geplaatst woord bedekt zijn
Soultaker schreef op woensdag 02 mei 2007 @ 15:47:
De reden dat ik uiteindelijk maar voor 'dicht bij het midden' gegaan ben, is dat het gewoon beter werkte dan random, en andere simpele heuristieken niet beter werkten.
Er zijn veel variaties waarop je kunt testen: zoveel mogelijk in het centrum, zoveel mogelijk aan de rand, horizontale woorden in het centrum en verticale aan de rand, zoveel mogelijk boven en rechts, enzovoort. Ik constateerde op basis van de gegeven testsets dat dit met mijn aanpak door de bank genomen niet zoveel uit maakte, en het leek me zinvoller me op andere aspecten te richten.

Meer over m'n aanpak is straks wel op m'n website te vinden.

Acties:
  • 0 Henk 'm!

  • Arjan
  • Registratie: Juni 2001
  • Niet online

Arjan

copyright is wrong

Wat ik erg opvallend vond tijdens het programmeren, was dat mijn code verrassend ongevoelig was voor statistisch 'slimmere' plaatsingen :)

Ik heb alles in SVN staan voor de liefhebber, maar op een gegeven moment had ik dus stats voor alle strings in m'n grid. Zo hoefde ik alleen maar in een boolean array te kijken of een letter er in zat en vervolgens de juiste plek te zoeken. echter was dit niet/nauwelijks sneller dan gewoon een string.find uit te voeren op alle strings. Dat had ik echt niet verwacht.

Ik heb meer van dat soort testjes gedaan, maar uiteindelijk kon ik voor mijn code alleen maar concluderen dat al die kleine slimmigheidjes niks substantieels gingen bieden. Ik heb me dan ook gefocused op het profilen van m'n bestaande code :)

oprecht vertrouwen wordt nooit geschaad


Acties:
  • 0 Henk 'm!

  • RedPixel
  • Registratie: Januari 2004
  • Laatst online: 15:31
Hoe lang duurt het voordat het is "nagekeken"?

I see red pixels.


Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

wwwhizz schreef op woensdag 02 mei 2007 @ 19:30:
Hoe lang duurt het voordat het is "nagekeken"?
Gezien het hoge aantal inzendingen denk ik dat we er wel even mee bezig zijn. Ik doe net als de vorige keer geen toezeggingen, maar ik denk dat er wel een uitslag moet kunnen zijn binnen 2 weken van nu. :)

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • maxtrash
  • Registratie: Augustus 2002
  • Laatst online: 10-09 23:28
Misschien kunnen jullie nu je testset publiceren. Maakt nu toch niet meer uit...Kan iedereen zelf alvast zijn progje erop loslaten

Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

Topicstarter
(overleden)
maxtrash schreef op woensdag 02 mei 2007 @ 21:32:
Misschien kunnen jullie nu je testset publiceren. Maakt nu toch niet meer uit...Kan iedereen zelf alvast zijn progje erop loslaten
Die testset is nog nat achter de oren >:) Ik denk dat we 'm nog (in ieder geval even) voor ons zelf houden.

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
RobIII schreef op woensdag 02 mei 2007 @ 21:37:
Die testset is nog nat achter de oren >:) Ik denk dat we 'm nog (in ieder geval even) voor ons zelf houden.
Dan doe je een deel, dat jpgtje ofzo >:). of de nieuwe contest, dan hebben we alvast 2 weken wat te doen :+

Nee hoor, Success met testen. ;)

[ Voor 5% gewijzigd door Serpie op 02-05-2007 22:18 ]


Acties:
  • 0 Henk 'm!

  • ArtyShock
  • Registratie: Juli 2002
  • Laatst online: 05-09 13:45
Hee, hier even een snelle reply vanuit een Internet cafe in Londen. Ik was even benieuwd of er al iets van uitslagen waren, maar dat gaat nog even duren begrijp ik. :P

Ik heb even doorgekeken wat anderen voor algoritmes hadden en ik herkende erg veel terug van methodes die ik van plan was te implementeren. Ik heb nu niet de tijd uit te leggen wat het uiteindelijke doel was, maar de basis van mijn datastructuur bestaat uit het matchen van indices van woorddelen. Als je voor elke letter 5 bits neemt, kun 12 letters indexeren met een 64-bits long. De hele datastructuur cached zowel gevonden indices als alle indices die in alle woorden zitten. Daardoor is het geheel vrij snel, kan er makkelijk gesorteerd worden etc. Maar ja, ik was nog lang niet klaar alle statistische uitkomsten te interpreteren voor de beste uitkomst. Eindresultaat is iets wat alleen maar matched op woorden met de mooiste lettercombinaties en het langst plaatsbare woordonderdeel in de grid.

Goed, ik kom zaterdag nog wel een keertje checken. :w

Acties:
  • 0 Henk 'm!

  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

Mijn algo gaat pcies nog verder...

Je moet mijn grid zien als een dynamische matrix. Een element kan al dan niet aanwezig zijn (je kan bvb van (2,3) springen naar (2,8).
Elk element van de matrix is dan ook nog eens een container van letters (uiteraard dezelfde letter als er overlap is) Een woord is dan weer een array van letters. Elk woord kan dus geplaatst worden in de grid en die waar nodig dynamisch vergroten. (lang leve de boost multi-index container) Aangezien ik van een woord zijn plaats en richting weet kan ik ook het woord weer weghalen...

Het algo gaat dus zo:
Woorden inlezen en daarna overlap zowel forward als backward eruithalen van minstens 3 karakters. (omvatte woorden worden dus auto uitgefilterd). Daarna worden volgens een wegingscoefficient (afh van % voorkomen van de letters) de woorden gesorteerd.

In een 2de fase wordt het eerste woord op (0,0); rechts geplaatst. Van dan of wordt er woord per woord de best overlap gezocht door:
- per letter in het woord
--- per overeenkomstige letter in het grid
----- per richting
te controleren of het woord past en een grotere overlap heeft dan een vorig mogelijkheid.
Dit hele proces wordt 1maal gedaan voor de hele wordenset.
Daarna wordt voor alle woorden een 2de maal geprobeerd. Lukt het dan nog niet dan zet ik het woord maar ergens neer zonder overlap.

Voor testset 1 grid 1 haal ik hiermee 2007 letters.

Dan begint het echte werk pas.
Per iteratie ga ik een aantal random woorden (ongeveer 15%) van de grid plukken en opnieuw proberen te plaatsen. Met hopelijk een betere score dan voorheen. Om alles in beweging te houden verkies ik een nieuwe plaatsing met minstens even veel overlap boven een oude.

Door meer dan 1 woord van de grid te plukken kan het gebeuren dat je score omhoog gaat ipv omlaag doordat je andere woorden niet meer kan plaatsen. Die worden alsnog geplaatste. Doordat we natuurlijk itereren komt alles over het algemeen wel weer goed.

Dat is ook de reden waarom mijn scores moeilijk te reproduceren zijn. Eenmaal had ik rond de 1950 letters over. Ik was dan ook onprettig verrast door een bug in de code om de grid op te slaan. Jammer genoeg heeft deze aanpak redelijk wat processing power nodig. Voordeel is dan weer dat het programma op een uit de kluiten gewassen PC net niet in de cache kan passen.

Ik zal proberen om binnenkort (weekend?) de code te posten en misschien nog wat correcties en aanvullingen op bovenstaand verhaal.

ASSUME makes an ASS out of U and ME


Acties:
  • 0 Henk 'm!

  • Swaptor
  • Registratie: Mei 2003
  • Laatst online: 17-06 07:31

Swaptor

Java Apprentice

Serpie schreef op woensdag 02 mei 2007 @ 22:18:
Dan doe je een deel, dat jpgtje ofzo >:). of de nieuwe contest, dan hebben we alvast 2 weken wat te doen :+
Die jpeg is natuurlijk gewoon henk!
Afbeeldingslocatie: http://tweakers.net/ext/i.dsp/1122302426.gif

Ontdek mij!
Proud NGS member
Stats-mod & forum-dude


Acties:
  • 0 Henk 'm!

  • Pete
  • Registratie: November 2005
  • Laatst online: 07-09 17:51
Swaptor schreef op woensdag 02 mei 2007 @ 23:23:
[...]


Die jpeg is natuurlijk gewoon henk!
[afbeelding]
Alleen is deze jpeg een gif :)

petersmit.eu


Acties:
  • 0 Henk 'm!

  • Swaptor
  • Registratie: Mei 2003
  • Laatst online: 17-06 07:31

Swaptor

Java Apprentice

Like it matters.
Renamen en voeren die hap ;)

Goede spot overigens phsmit :+ Niet goed gekeken 8)7

Ontdek mij!
Proud NGS member
Stats-mod & forum-dude


Acties:
  • 0 Henk 'm!

  • HawVer
  • Registratie: Februari 2002
  • Laatst online: 03-09 19:59
Hé, jammer dat ik deze contest gemist heb. Misschien ga ik alsnog wel voor de lol een algoritme en programmatje schrijven.

http://hawvie.deviantart.com/


Acties:
  • 0 Henk 'm!

  • The Flying Dutchman
  • Registratie: Mei 2000
  • Laatst online: 29-07 21:57
Misschien interessant voor anderen om even te vertellen met wat voor algoritme ik bezig ben geweest (maar wat dus niet af is gekomen).

Ik begin vrij standaard zoals vele anderen: woorden inlezen, lowercase, sorteren op lengte en op alfabet (waarbij lengte belangrijker was) vervolgens dubbele woorden eruit halen.
Daarna was mijn plan om een soort van kohonen map algoritme toe te passen, dat ging ongeveer als volgt in zijn werk:

1. Dump alle woorden op een random plek en met random rotatie in de grid. Het gevolg is een grid waar (waarschijnlijk) niets op de juiste plek staat en waarbij vele coordinaten meer dan 1 karakter bevatten.
2. Reken uit per coordinaat hoeveel van elke karakters zich daar bevinden, het idee is dat het meest voorkomende character 'wint' van de andere karakters.
3. Ga alle woorden bijlangs om ze te verplaatsen. Dit gaat per woord als volgt:
a. bekijk 36 (geloof ik) mogelijke woordposities in de grid rondom de huidige positie van het woord (dat is inclusief allerlei mogelijke orientaties)
b. verplaats het woord naar de best passende nieuwe positie (die dus altijd dichtbij de oude positie ligt) of blijf op de oude positie als deze de beste score gaf

Ga daarna weer verder met stap 2.

Het idee hierachter is dat ieder woord bij iedere iteratie op een net iets beter plekje komt te liggen en dat dit uiteindelijk naar een oplossing itereerd.

Helaas werkte het in de praktijk iets minder mooi, er kwam nooit een oplossing, ook niet na 1000 of meer iteraties. Misschien was dit een kwestie van tweaken (bijvoorbeeld: hoe bereken je de woordpositie scores? en hoe groot neem je de grid in eerste instantie?), maar misschien was het hele idee wel gewoon onwerkbaar. Anyway, de methode heeft nooit gewerkt ook niet voor kleine grids (het grid kwam dan in een staat terecht waar niets meer veranderde, of waarbij een stuk van de grid zich steeds verder van een ander stuk af bewoog).

In eerste instantie hoopte ik dat ik per grid hooguit zo'n 500 iteraties nodig zou hebben om een oplossing te vinden. Op mijn dual athlon 1 Ghz zou het programma dan (ongeveer) een uur nodig hebben als ik de grootte en het aantal grids ruim zou inschatten. Maar helaas ontbrak de tijd om te proberen of dit idee echt vruchtbaar was.

Nu maar afwachten tot de volgende contest, wellicht kan ik daar een ander mooi algoritme uitdenken dat in de praktijk ook werkt ;)
(btw: ik studeer KI, vandaar mijn interesse in dit soort KI oplossingen)

The Flying Dutchman


Acties:
  • 0 Henk 'm!

  • MiezeL
  • Registratie: Augustus 2002
  • Laatst online: 04-03 12:39
jaaa nieuwe contest!!!:D:D:D:D

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
MiezeL schreef op donderdag 03 mei 2007 @ 12:10:
jaaa nieuwe contest!!!:D:D:D:D
Heb je nu uiteindelijk nog een versie ingeleverd voor deze contest, of is het niet gelukt?

Je laatste reactie voor deze was namenlijk, dus was eigenlijk wel benieuwd
Misschien lever ik het nog wel in hoor:P Hoeft er maar 1 crashen en sta ik er nog boven ^_^

[ Voor 28% gewijzigd door Serpie op 03-05-2007 12:18 ]


Acties:
  • 0 Henk 'm!

  • HawVer
  • Registratie: Februari 2002
  • Laatst online: 03-09 19:59
The Flying Dutchman schreef op donderdag 03 mei 2007 @ 10:43:
Misschien interessant voor anderen om even te vertellen met wat voor algoritme ik bezig ben geweest (maar wat dus niet af is gekomen).

* knip *

Nu maar afwachten tot de volgende contest, wellicht kan ik daar een ander mooi algoritme uitdenken dat in de praktijk ook werkt ;)
(btw: ik studeer KI, vandaar mijn interesse in dit soort KI oplossingen)
Komt bij KI ook (veel) programmeren om de hoek kijken?

http://hawvie.deviantart.com/


Acties:
  • 0 Henk 'm!

  • MiezeL
  • Registratie: Augustus 2002
  • Laatst online: 04-03 12:39
Serpie schreef op donderdag 03 mei 2007 @ 12:14:
[...]
Heb je nu uiteindelijk nog een versie ingeleverd voor deze contest, of is het niet gelukt?
[...]
Nee :'( Ik kwam erachter omdat ik halverwege was enzo het niet meer compileerde. Had nmlk wat dingen omgezet ivm mijn nieuwe ideëen.

Iig dat is dus ook wrom ik zo graag een nieuwe wil, omdat ik nu eindelijk best wel tijd heb en misschien een keer kan afmaken wat ik bedacht heb. Bij tetris was dit nmlk ook niet op tijd gelukt.

Acties:
  • 0 Henk 'm!

  • The Flying Dutchman
  • Registratie: Mei 2000
  • Laatst online: 29-07 21:57
HawVer schreef op donderdag 03 mei 2007 @ 12:51:
[...]

Komt bij KI ook (veel) programmeren om de hoek kijken?
offtopic:
Het hangt er een beetje vanaf waar je KI studeert en wat je keuzes zijn tijdens je studie (keuzevakken en welke master ga je doen). De KI opleiding aan de RuG in Groningen (doe ik ook) staat erom bekend vrij technisch te zijn. Om je een idee te geven:
1e jaar 2 programmeervakken (java)
verder in je bachelor nog 'logisch programmeren' en een aantal vakken waarbij practica gedaan worden waar je niet om programmeren heen kunt.
In je keuzeruimte kun je nog een (heel erg goede, maar ook zware) C++ cursus volgen die 3/4 jaar duurt (hoewel je helaas slechts een gedeelte van die punten mee mag tellen, maar ach, als je programmeren echt leuk vind, dan ga je er gewoon voor :)).

Verder als je geinteresseert bent in de studie, kijk eens op de website van KI in groningen (www.ai.rug.nl) daar staat ook wel ergens een online studiegids (of neem even persoonlijk contact op ofzo).

The Flying Dutchman


Acties:
  • 0 Henk 'm!

  • Creepy
  • Registratie: Juni 2001
  • Laatst online: 07:55

Creepy

Tactical Espionage Splatterer

Swaptor schreef op woensdag 02 mei 2007 @ 23:23:
[...]


Die jpeg is natuurlijk gewoon henk!
[afbeelding]
Je zit er niet ver naast :P

"I had a problem, I solved it with regular expressions. Now I have two problems". That's shows a lack of appreciation for regular expressions: "I know have _star_ problems" --Kevlin Henney


Acties:
  • 0 Henk 'm!

  • Fiander
  • Registratie: Februari 2001
  • Laatst online: 28-05 12:35
@The Flying Dutchman
Zou je wat je hebt beschikbaar willen stellen ???? je heb me heel erg nieuwschierig gemaakt naar de uitwerking. :9

Deze sig is een manueel virus!! Als je dit leest heb je het. Mail dit bericht naar iedereen die je kent, en verwijder alle bestanden van je computer.


Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

MiezeL schreef op donderdag 03 mei 2007 @ 13:35:
Iig dat is dus ook wrom ik zo graag een nieuwe wil, omdat ik nu eindelijk best wel tijd heb en misschien een keer kan afmaken wat ik bedacht heb. Bij tetris was dit nmlk ook niet op tijd gelukt.
De nieuwe contest is zo goed als af, maar hij gaat niet van start voordat deze contest in zijn geheel afgerond is, helaas. :P

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

Dat is wel snel dan :)
Ik ben benieuwd, want met de huidige contest zal ik niet zo heel hoog scoren. Toch nog eens naar dat algoritme van MarcJ kijken. Waarom krijgt hij met hetzelfde idee wel een snel resultaat

Acties:
  • 0 Henk 'm!

  • RedPixel
  • Registratie: Januari 2004
  • Laatst online: 15:31
-NMe- schreef op vrijdag 04 mei 2007 @ 00:49:
[...]

De nieuwe contest is zo goed als af, maar hij gaat niet van start voordat deze contest in zijn geheel afgerond is, helaas. :P
Oeh Oeh Oeh Oeh Oeh :+

I see red pixels.


Acties:
  • 0 Henk 'm!

  • DaCoTa
  • Registratie: April 2002
  • Laatst online: 05-09 23:19
-NMe- schreef op vrijdag 04 mei 2007 @ 00:49:
[...]

De nieuwe contest is zo goed als af, maar hij gaat niet van start voordat deze contest in zijn geheel afgerond is, helaas. :P
code:
1
2
3
O   \
  -  |
O   /
  1. Tetris
  2. Scrabble
  3. ???

[ Voor 8% gewijzigd door DaCoTa op 04-05-2007 10:34 ]


Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

DaCoTa schreef op vrijdag 04 mei 2007 @ 10:15:
[...]
code:
1
2
3
O   \
  -  |
O   /
  1. Tetris
  2. Scrabble
  3. Contest 3
:P

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • DaCoTa
  • Registratie: April 2002
  • Laatst online: 05-09 23:19
Schaken, Dammen, Go, Monopoly, Risk, Stratego, Tikkertje, Voetbal, Paintball, Marathonlopen, Triatlon, Twister, Parijs-Dakkar, Wie-kan-het-beste-vlot-bouwen. Een van deze?

Even weer ontopic: het is erg leerzaam om alle algoritmen uitgelegd te zien, heeft zeker stof tot nadenken gegeven. Is het een idee om een korte uitleg bij de inlevercriteria te stoppen voor de volgende contest?

Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

DaCoTa schreef op vrijdag 04 mei 2007 @ 12:10:
Schaken, Dammen, Go, Monopoly, Risk, Stratego, Tikkertje, Voetbal, Paintball, Marathonlopen, Triatlon, Twister, Parijs-Dakkar, Wie-kan-het-beste-vlot-bouwen. Een van deze?
Het zal in elk geval wederom geen standaardprobleem worden waarvoor je op WikiPedia zo een oplossing kan downloaden. ;)
Even weer ontopic: het is erg leerzaam om alle algoritmen uitgelegd te zien, heeft zeker stof tot nadenken gegeven. Is het een idee om een korte uitleg bij de inlevercriteria te stoppen voor de volgende contest?
Feitelijk ís dat al een criterium. We vroegen om voldoende en duidelijk commentaar. :)

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • MiezeL
  • Registratie: Augustus 2002
  • Laatst online: 04-03 12:39
hmm ik zou heel graag een soort game keertje willen doen (online?). liefst tegen elkaar ofzo, lijkt me erg vet.

[ Voor 4% gewijzigd door MiezeL op 04-05-2007 13:12 ]


Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

MiezeL schreef op vrijdag 04 mei 2007 @ 13:12:
hmm ik zou heel graag een soort game keertje willen doen (online?). liefst tegen elkaar ofzo, lijkt me erg vet.
Hoe zie je dat voor je? :P

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • IntToStr
  • Registratie: December 2003
  • Laatst online: 16:20
Ik heb een paar jaar terug wat wedstrijden gezien tussen bots die tegen elkaar risk speelden. Dit kun je met elk spel doen lijkt me. Alleen beetje lastig om het framework eromheen te maken als het spel niet hele triviale regels/omgeving heeft...

Hopelijk heb ik bij de volgende contest ook een keer tijd om mee te doen!

Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

IntToStr schreef op vrijdag 04 mei 2007 @ 14:03:
Ik heb een paar jaar terug wat wedstrijden gezien tussen bots die tegen elkaar risk speelden. Dit kun je met elk spel doen lijkt me. Alleen beetje lastig om het framework eromheen te maken als het spel niet hele triviale regels/omgeving heeft...

Hopelijk heb ik bij de volgende contest ook een keer tijd om mee te doen!
De botwars contest van een tijd terug heeft wel aangetoond dat het een leuk idee is maar nooit gerealiseerd zal worden omdat er teveel bij komt kijken. ;)

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • MiezeL
  • Registratie: Augustus 2002
  • Laatst online: 04-03 12:39
Mja online is lastig, maar misschien zou je ook iets offlines kunnen doen. bijv: bijna programma's maken een output, en 1 leest dan de output van de ander. Mocht er een fotu in zitten zeg je dat en kunnen jullie dat verifieren, dan lig je er dus uit. Kie een willekeurig spel wat je normaal ook tegen elkaar speelt, en doe dat dan dus tegen elkaar.
Enige is dat ik even geen spel zou weten.

Acties:
  • 0 Henk 'm!

  • Robbbert
  • Registratie: April 2005
  • Laatst online: 10-09 19:11
Ik heb al een paar keer ook meegedaan met CodeCup: http://www.codecup.nl

Is volgens mij een beetje hetzelfde idee.

Acties:
  • 0 Henk 'm!

  • MiezeL
  • Registratie: Augustus 2002
  • Laatst online: 04-03 12:39
hey idd, zoiets bedoel ik. al is dat wel een uitgebreide game volgens mij. ik ken dat spel trwns in eht echt, was echt vet altjid.

[ Voor 27% gewijzigd door MiezeL op 04-05-2007 16:11 ]


Acties:
  • 0 Henk 'm!

  • _js_
  • Registratie: Oktober 2002
  • Laatst online: 18-08 21:31
DaCoTa schreef op vrijdag 04 mei 2007 @ 10:15:
[...]
code:
1
2
3
O   \
  -  |
O   /
  1. Tetris
  2. Scrabble
  3. ???
  1. Bits in een grid plaatsen
  2. Bytes in een grid plaatsen
  3. Floats in een grid plaatsen, polygonen ofzo?

Acties:
  • 0 Henk 'm!

  • DaCoTa
  • Registratie: April 2002
  • Laatst online: 05-09 23:19
_js_ schreef op vrijdag 04 mei 2007 @ 17:24:
[...]
  1. Bits in een grid plaatsen
  2. Bytes in een grid plaatsen
  3. Floats in een grid plaatsen, polygonen ofzo?
Afbeeldingslocatie: http://tecfa.unige.ch/etu/LME/9899/extermann-fanac-margot/tangram.jpg

Acties:
  • 0 Henk 'm!

  • The Flying Dutchman
  • Registratie: Mei 2000
  • Laatst online: 29-07 21:57
Fiander schreef op donderdag 03 mei 2007 @ 20:33:
@The Flying Dutchman
Zou je wat je hebt beschikbaar willen stellen ???? je heb me heel erg nieuwschierig gemaakt naar de uitwerking. :9
Ik ben nu niet thuis, maar als ik daar weer ben zal ik kijken wat ik nog heb (toen het niet werkte en ik niet voldoende het idee had dat het zou gaan werken ben ik nog met iets anders begonnen, maar met wat geluk is er nog wel iets dat 'draait').

Het is overigens geschreven in C++ voor linux.
Er zit ook een template class bij die een grid representeerd, mijn eerste uitgebreide template class, was er best trots op (hoewel het vast nog een stuk beter zal kunnen). En het maakt een beetje gebruik vd boost libraries om meerdere cores/cpu's te benutten.

Ben waarschijnlijk zondag weer thuis, dan zal ik even kijken. Wat ik er verder nog over kan zeggen, in aanvulling tot eerdere uitleg:

De woordscore (van een bepaalde positie in de grid) geeft dus aan hoe goed een woord op die plek in de grid past. De woordscore heb ik op verschillende manieren bepaald, één van de manieren was bijvoorbeeld:

Kijk hoeveelste het karakter in rangorde is op een bepaald gridpunt, daarmee wil ik zeggen: stel dat punt (9, 3) in het grid de volgende karakters bevat: a, b, b, e, h, m, n, n, n, t, s (dit betekend dus dat er op dat moment 11 woorden zijn die met één karakter op gridpunt (9, 3) liggen). Stel je wilt nu het woord 'bonenstaak' plaatsen en je wilt de score uitrekenen voor dat woord op een bepaalde positie, die positie ligt zo dat de 3e letter valt op het coordinaat (9, 3). Dan is de score voor de 3e letter van het woord 'bonenstaak' voor die mogelijke positie/orientatie in het grid 3 (omdat de 'n' de 3e letter is van bonenstaak en de 'n' reeds 3x voorkomt op positie (9, 3)).

Tel de scores van alle letters van het woord (in dit geval 'bonenstaak') op en je krijgt de totaalscore voor het woord 'bonenstaak' op een bepaalde positie met een bepaalde orientatie. Zoals ik eerder al zei, dit reken je uit voor 36 posities rondom de huidige positie van het woord. Kies uit die 36 de beste positie en verplaats het woord daar naartoe.

Zodra alle woorden verplaatst zijn (eventueel zijn ze blijven staan omdat ze reeds op de beste positie stonden), ga je voor ieder mogelijk karakter voor ieder punt in het grid weer uitrekenen hoe vaak het daar voorkomt. Dan ga je weer opnieuw voor ieder woord een nieuwe beste positie (wederom de keuze uit 36 omringende posities) kiezen.

Wat zijn nou de problemen die je hierbij tegenkomt?
1. Wanneer past een woord goed op een positie? Oftewel hoe ga je de woordscores bepalen? Er zijn 1001 manieren te verzinnen, ik heb bijvoorbeeld ook geprobeerd om alleen punten uit te delen aan de letter die het meest voorkomt. In het hierboven genoemde voorbeeld zou de 'n' bijvoorbeeld 1 punt krijgen, want het is de meest voorkomende letter op positie (9, 3). Maar stel dat er een andere letter (laten we zeggen de 'o') had gestaan, dan had die letter 0 punten gekregen.

2. Moet de woordscore afnemen als een woord heel lang op een positie blijft staan, maar deze positie is niet optimaal (optimaal wil zeggen: de coordinaten waarop de karakters van het woord voorkomen bevatten alleen die karakters die overeen komen met de karakters van het woord, dus er zijn geen 'concurrerende' karakters meer).

3. Wat voor score geef je aan een leeg vak (een nieuw gridpunt) waar nog geen enkel woord gebruik van maakt? Je wilt natuurlijk niet dat een leeg vak een te hoge score krijgt, want voor ieder leeg vak dat je gebruikt wordt je grid groter. Aan de andere kant... als het woord wel past als je gebruik maakt van een leeg vakje, maar anders niet... dan wil je toch wel overwegen om dat vakje te gaan gebruiken.

4. Hoe groot maak je het gebied waarin je in eerste instantie (random) je woorden dumpt? Te groot, dan wordt je grid vast niet optimaal klein. Te klein, dan is het vast te moeilijk om naar een oplossing te itereren.

Het representeren van de grid was ook nog aardig lastig omdat je voor ieder punt voor ieder mogelijk ASCII karakter moet bijhouden hoevaak ze voorkomen. Daarnaast moet je voor ieder woord bijhouden waar ze op dat moment geplaatst zijn en in welke orientatie. De grid moest natuurlijk uitbreidbaar zijn, en alles moest ook nog op een acceptabele snelheid draaien.

Ik heb verder qua optimalisaties nog overwogen om eerst alle input na te lopen en te kijken of er in verschillende grids groepen met dezelfde woorden voorkwamen. Stel dat er een set is waarin dat voorkomt, dan kun je daar misschien wat leuks mee doen.

Nouja, tot dusver de uitleg van mijn niet werkende (en niet ingeleverde) programma. Binnenkort kun je het hier ergens downloaden (als ik het nog heb liggen).

The Flying Dutchman


Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

_js_ schreef op vrijdag 04 mei 2007 @ 17:24:
[...]
  1. Bits in een grid plaatsen
  2. Bytes in een grid plaatsen
  3. Floats in een grid plaatsen, polygonen ofzo?
Contest 3 krijgt een geheel andere insteek. :P

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

grids in een byte plaatsen ?

Acties:
  • 0 Henk 'm!

  • cobratbq
  • Registratie: Maart 2001
  • Laatst online: 17-12-2015
Woorden uit een JPEG-je halen wat gerenamed is als 'words.txt'? :?

One ring to rule them all, one ring to find them, one ring to bring them all, and in darkness bind them...


Acties:
  • 0 Henk 'm!

  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

Mijn inzending (volgens de uitleg enkele posts omhoog) kan je op deze URL vinden.

Volgens de uitleg van MarcJ merk ik net dat mijn prog eigenlijk eenvoudig 2 maal zo snel zou kunnen door van de 4 richtingen er 2 af te snoepen. Waarschijnlijk zouden er dan wel enkele mogelijkheden niet gevonden worden, maar of dat zo erg zou zijn?

ASSUME makes an ASS out of U and ME


Acties:
  • 0 Henk 'm!

  • DaCoTa
  • Registratie: April 2002
  • Laatst online: 05-09 23:19
Marcj schreef op woensdag 02 mei 2007 @ 12:04:
Uiteraard worden deze plaatsingen op een zodanige manier opgeslagen dat ik eenvoudig alle mogelijk plaatsingen van een woord, of juist alle plaatsingen door een bepaalde plek op de grid, kan doorzoeken. Dit gebeurt allemaal in een HashMatrix (dubbele HashTable).
Toch nog even een vraag hierover: waar heb je de collectie van alle mogelijke plaatsingen van een woord voor nodig? Als ik het zo lees, kun je alles doen met de collectie van alle mogelijke plaatsingen op een locatie, op het verwijderen van de mogelijke plaatsingen na een daadwerkelijke plaatsing na? En zit er ook nog een weging in het stuk wat kijkt hoeveel woorden je blokkeerd?

Ik zit erover te denken om dit principe alsnog even te bouwen in mijn eigen constructie, just for the kicks.

[ Voor 44% gewijzigd door DaCoTa op 05-05-2007 01:06 ]


Acties:
  • 0 Henk 'm!

  • roy-t
  • Registratie: Oktober 2004
  • Laatst online: 08-09 11:33
Complimentje voor Arty_Shock, heb zijn C# example even gedownload en vind het een ontzettend netjes programma, die op mijn XP2400+ netjes 1 Thread spawned, ook ziet het er lekker snel uit.

*hier kan ik nog veel van leren over C#*

Mijn complimentje! Ook voor de andere Gotters mij is het niet echt gelukt behalve wat halve opzetjes, maar de C# inzending trok mijn aandacht omdat ik daarnaar aan het overstappen ben.

~ Mijn prog blog!


Acties:
  • 0 Henk 'm!

  • ArtyShock
  • Registratie: Juli 2002
  • Laatst online: 05-09 13:45
therat10430 schreef op zondag 06 mei 2007 @ 12:10:
Complimentje voor Arty_Shock, heb zijn C# example even gedownload en vind het een ontzettend netjes programma, die op mijn XP2400+ netjes 1 Thread spawned, ook ziet het er lekker snel uit.

*hier kan ik nog veel van leren over C#*

Mijn complimentje! Ook voor de andere Gotters mij is het niet echt gelukt behalve wat halve opzetjes, maar de C# inzending trok mijn aandacht omdat ik daarnaar aan het overstappen ben.
Ha ha, dank je voor het compliment en ik ben oprecht gevleid maar ik moet zeggen dat ik mijn inzending als alles behalve een net programma zou classificeren. De grote boosdoener hierin is het gebrek aan tijd geweest, wat te zien is aan een poging tot een nette opzet en vervolgens ontzettend afgeraffelde classes omdat ik koste wat kost een werkende inzending wilde insturen. Het multithreading gedeelte is er bijvoorbeeld twintig minuten vóór de deadline ingeprogrammeerd - ik moest in de MSDN zelfs nog opzoeken hoe je ook alweer threads spawned in C#. :') Ach ja, dat krijg je als je een jaar lang projecten in Java hebt gedaan.

Dus neem alsjeblieft niet mijn inzending als voorbeeld hoe C# programma's op te zetten want ik heb me aan een heleboel richtlijnen niet gehouden. Als je ziet hoe slordig er met properties en access modifiers is omgegaan... :N Onderdelen die je in een config file zou plaatsen staan gewoon als globals genoteerd... :N Gebrek aan commentaar... :N Inconsistentie in variabele benaming... :N Een slodderwerkje, maar wel één waarvan ik blij ben dat 'ie een beetje werkt.

Goed, ik ben net terug van een korte vakantie en zal vanavond nog even m'n gedachtengang oppennen bij deze programmeeropdracht. :)

Acties:
  • 0 Henk 'm!

  • roy-t
  • Registratie: Oktober 2004
  • Laatst online: 08-09 11:33
Arty_Shock schreef op zondag 06 mei 2007 @ 16:38:
Ha ha, dank je voor het compliment en ik ben oprecht gevleid maar ik moet zeggen dat ik mijn inzending als alles behalve een net programma zou classificeren
Hmmm,

*kijkt nog een keer naar zijn eigen code*

*godver*

:>

[ Voor 30% gewijzigd door roy-t op 06-05-2007 18:15 ]

~ Mijn prog blog!


Acties:
  • 0 Henk 'm!

  • ArtyShock
  • Registratie: Juli 2002
  • Laatst online: 05-09 13:45
Na van iedereen de verhalen te hebben doorgelezen lijkt mijn gedachtengang en initiële bevindingen het meest op die van "hij".

Het leuke van de opdracht is dat de optimale oplossing van een lijst van +/- 400 woorden bijna niet te bepalen is. Te veel variaties. Zelfs al denk je het optimale grid gevonden te hebben; bewijs het maar eens.

Hoe bepaal je binnen een tijdsbeperking de beste oplossing? Een aantal reeds genoemde richtingen kwamen ook in mij op:

1) Plaatsen van steeds een nieuw woord op de plek die het meeste relatieve winst oplevert. Bij gelijk spel, het mooiste (meestgebruikte letters/lettercombinaties) plaatsen.
2) Zonder al te veel optimalisaties woorden plaatsen in het grid en net zolang schuiven met woorden naar betere plekken totdat de gestelde tijd op is.
3) Proberen ideale clusters van woorden te vormen (10 à 20 per stuk afhankelijk van statistische thresholds) en die clusters weer zo gunstig mogelijk linken.
4) Beginnen met een woord (met de statistisch meestgebruikte letters) en met een alpha algoritme proberen zover mogelijk vooruit te kijken (standaard AI oplossing).

Nadelen:
1) Er blijven teveel kansen liggen. Je hebt een aantal slechtscorende plaatsingen nodig om mooie situaties te creëren.
2) Lijkt me nog steeds de meest elegante vorm van trial and error. Ook: hoe meer tijd, hoe potentieel beter het resultaat. Het optimum zal waarschijnlijk nooit gehaald worden door ‘blind spots’ bij het bepalen welk woord te herplaatsen.
3) Clusteren leek teveel lokale optimalisaties te hebben om over het geheel goed te scoren. De randen van clusters doen te weinig mee om een goede score te behalen. Een aantal dingen mee geprobeerd, maar vooral zonde van de tijd.
4) In theorie een methode op het optimum te bereiken ware het niet dat drie niveaus diep al te rekenintensief kan uitpakken. Normaliter gebruik je heuristieken om in de enorme boom van mogelijkheden te snijden, echter heb ik geen werkbare heuristiek kunnen vinden. Alles bleek te grillig. Wat wel mooi is, is dat je extra kansen evalueert en dus minder blind bent dan matchen op het op dat moment best passende woord.

Wat ik wilde bouwen voor deze contest:
Oplossing 4) op 4 à 5 niveau’s diep en in de resterende tijd oplossing 2) toepassen.

Mijn benadering:

Om woorden snel te kunnen matchen wilde ik woordonderdelen indexeren. Ik heb besloten tot 64-bit longs omdat dat de grootste eenheid is die huidige computers snel kunnen vergelijken. Een snelle rekensom (Log 2^64 / Log (26+1) ~ 13,4) leert dat er 13 letters in 64 bits te plakken zijn. Ik heb besloten om 5 bits voor iedere letter te nemen. Dan past er wel een letter minder in die 64 bits, maar het rekent al heel wat efficiënter. (Daarnaast is een match van 13 letters al niet erg waarschijnlijk. Een klein offer dus).

Bij het inlezen van de woorden wordt per woord een reeks WordParts aangemaakt. Voor APPEL wordt A, P, P, E, L, AP, PP, PE, EL, APP, PPE, PEL, APPE, PPEL, PA, EP, LE, PPA, EPP, LEP, EPPA, LEPP en APPEL aangemaakt. Alle wordparts tot een lengte van 12 komen in een grote dictionary om zeer snel gematched te kunnen worden. Van ieder WordPart wordt ook in de index vastgelegd of ze omgekeerd, vooraan aan het eind of middenin het woord staan om zodoende mismatches te voorkomen.

De WordParts dictionary bevat per index een lijst van overeenkomstige WordParts. WordParts met overeenkomstige letters kunnen tenslotte in verschillende woorden voorkomen.

De grid bestaat uit een enkelvoudige array van GridItems. Elk GridItem bevat de letter van die positie en twee lijsten: Een lijst met horizontale verwijzingen naar de cache en een lijst met verticale verwijzingen naar de cache.

Een item uit de cache heet een GridReference. Iedere GridReference wijst naar een index in de lijst van WordParts. Iedere GridReference wijst echter óók naar de bijbehorende positie in het grid.

Tenslotte bevat elk woord (Word) nog een referentie naar ieder WordPart dat het heeft uitstaan in de WordParts dictionary. Op deze manier is het makkelijk alle WordParts terug te trekken als een woord geplaatst wordt.

Alleen als er een nieuwe letter in het grid geplaatst wordt, worden in een straal van 12 posities (de maximale lengte van een WordPart) alle indexen herberekend. Dit kan vrij efficiënt. Alle indexen die hierdoor vervallen worden uit de cache verwijderd.

(Ik wilde hier nog een plaatje plaatsen, maar dat gaat èrg veel tijd kosten inclusief passende uitleg)

NB'tjes
- Grappig om te zien dat Fiander eenzelfde enkeldimensionale array als ingang heeft genomen als ik.
- Interessant om te zien hoe MarcJ met een clean, doeltreffend algoritme en simpele code een uitstekend resultaat behaalt. Een les voor mezelf. ;)
- Als ik naar anderen hun code kijk heb ik het mezelf wel heel ingewikkeld gemaakt. ;(

Mocht er weer zo'n tijdsintensief algoritme vereist worden dan moet ik me misschien weer eens aan C wagen (of C++ met stl) Het is lang geleden dat ik daarin wat geprogrammeerd heb, maar ik heb me mateloos geërgerd aan het gebrek aan controle wat je hebt op dingen als geheugenallocatie, array bounds checks, pointer memory walks etc.

Oh ja, in het kader beter laat dan nooit: Veldsla, gefeliciteerd met je instantiatie van je childclass! ;)

Acties:
  • 0 Henk 'm!

Verwijderd

Na het oplossen van wat hardnekkige probleempjes met betrekking tot het oploaden naar m'n hoster, is mijn inzending nu hier te vinden.

Vanuit deze pagina is niet alleen de inzending (exes + code) te vinden (sectie 9), maar ook de resultaten ervan met de drie testsets (sectie 8 ).

Tevens vinden jullie er de beste grids die ik tijdens het ontwikkelen heb gevonden. Zijn er deelnemers die betere scores hebben gehaald, dan zou ik die oplossingen graag willen zien.

In deze post meldde ik dat in de versie die ik ingezonden heb, vergeten was een zekere macro vanuit een voor een test benodigde waarde terug te zetten, waardoor het maximaal toegestane aantal woordsets in een file gelimiteerd was op 6... Waarmee mijn kansen op een plaats op het ereschavot helaas effectief geminimaliseerd werden.
Ik ben zo vrij geweest dit in de versie die vanuit bovenstaande link te vinden is, weer terug te zetten op 99. Dit is het enige verschil tussen de versie op m'n website, en de door mij ingezonden versie.

Acties:
  • 0 Henk 'm!

  • ArtyShock
  • Registratie: Juli 2002
  • Laatst online: 05-09 13:45
Oprecht jammer dat je inzending zo'n triviaal foutje bevat. Gezien de moeite die je er in gestoken hebt zou je willen dat ze (de mods, de wedstrijdleiders, de big cahuna's, jeweetwel :P ) de verbeterde versie zouden meenemen. Maar ja, regels enzo.

Ik heb je verhaal (vluchtig, gezien het tijdstip) doorgelezen en vooral het punt van pushen en poppen van de context wat je noemde viel me op. Dat was na het ontwerpen van een efficiënte datastructuur namelijk mijn grootste uitdaging. Incrementele datastructuren zijn razendsnel op de heenweg, maar een snelle terugweg vereist vaak wat meer dan een simpele stack.

Mijn bedoeling op dat punt -helaas nooit aan toegekomen- was om naast de bestaande datastructuur een tijdelijke cache op te bouwen die enige overlap had met de bestaande cache. Zolang het aantal niveau's van doorrekenen mee zou vallen (3,4 of 5), zou de mate van overlap niet dusdanig zijn dat er té veel dubbel werk verricht zou hoeven te worden, terwijl er toch aardig wat recursieve iteraties gedaan konden worden. Mja, zonder échte implementatie blijft het theorie. ;)

Teer punt in dit verhaal blijft toch een beetje dat ik niet een goede methode heb kunnen vinden de zoekboom te beperken. Ik heb nog gedacht aan de toevoeging van een mate van willekeurigheid om de kansen te vergroten, maar dat is goedbekeken een zwaktebod wat je niet goed kan praten; doe dan alles willekeurig en probeer niet met foute heuristieken je blinde vlek te vergroten.

Nu maar duimen dat er maximaal zes sets per test zijn voor de contest. :P Wat betreft je punt over C(++): Ja, het is de meest logische keuze voor de beste performance, maar ik vraag me af of ik dan überhaupt op tijd iets af had gehad.

Acties:
  • 0 Henk 'm!

  • The Flying Dutchman
  • Registratie: Mei 2000
  • Laatst online: 29-07 21:57
Hier de beloofde source van mijn programma dat nooit voltooid is (voor de geinteresseerden). Er zit wel iets van een foutje in omdat er slechts 1 iteratie gedaan wordt (vast iets mis met een check of het grid voltooid is). Ik kan zo snel even niet uitvinden wat er mis is. Maar goed, daar gaat het ook niet echt om.

Het is een beetje 'een draak van een programma' geworden naar mijn idee, dus als je het niet snapt ligt het niet aan jou :P. Maar wellicht zitten er nog wat interessante stukjes code tussen (zoals de template class, file: grid.h).

The Flying Dutchman


Acties:
  • 0 Henk 'm!

  • Marcj
  • Registratie: November 2000
  • Laatst online: 13:59
De vorige contest was na 1 week beoordeelt (1 februari inleveren, 8 februari beoordeert). Hoe schatten jullie dat met deze contest? Ik snap dat er meer deelnemers zijn, dus meer te beoordelen valt, maar is er enig zicht op hoe lang het gaat duren?

Gewoon nieuwschierig, verder niets :X

Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

Marcj schreef op dinsdag 08 mei 2007 @ 07:52:
De vorige contest was na 1 week beoordeelt (1 februari inleveren, 8 februari beoordeert). Hoe schatten jullie dat met deze contest? Ik snap dat er meer deelnemers zijn, dus meer te beoordelen valt, maar is er enig zicht op hoe lang het gaat duren?

Gewoon nieuwschierig, verder niets :X
Ik ben momenteel ongeveer halverwege met het laten runnen van de entries, dus ik heb er nog zo'n 8 of 9 te gaan. Daarnaast zijn er nog twee entries die ik buiten mededinging ga runnen, waaronder ook de tweede inzending van hij. :)

Dat is overigens maar een deel van wat er nog gedaan moet worden. Voor zover ik weet heeft er nog niemand de code ingezien en beoordeeld, dus dat komt ook nog. Het duurt allemaal wat langer dan de vorige contest, maar ik denk dat we tegen/in het weekend wel resultaten hebben, maar zoals jullie al van ons gewend zijn: geen beloftes. :P

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

Verwijderd

Ik vond deze contest ook minder leuk dan de vorige. Ik weet dat ik niet moet zeuren, want ik heb aan geen van beide meegedaan, maar als toeschouwer wil je ook wat :P . Ik hoop op een leuke (minder brute force, meer 'slim') volgende contest. Ik ben van plan mee te gaan doen...

Acties:
  • 0 Henk 'm!

  • NMe
  • Registratie: Februari 2004
  • Laatst online: 09-09 13:58

NMe

Quia Ego Sic Dico.

Verwijderd schreef op donderdag 10 mei 2007 @ 10:19:
Ik hoop op een leuke (minder brute force, meer 'slim') volgende contest. Ik ben van plan mee te gaan doen...
Deze opdracht brute force oplossen lijkt me niet echt handig. Ik heb ook al aardig wat slimme inzendingen gezien. ;) Het idee van deze contests is dat je het jezelf zo moeilijk kan maken als je zelf wil. :)

'E's fighting in there!' he stuttered, grabbing the captain's arm.
'All by himself?' said the captain.
'No, with everyone!' shouted Nobby, hopping from one foot to the other.


Acties:
  • 0 Henk 'm!

  • ArtyShock
  • Registratie: Juli 2002
  • Laatst online: 05-09 13:45
Verwijderd schreef op donderdag 10 mei 2007 @ 10:19:
Ik vond deze contest ook minder leuk dan de vorige. Ik weet dat ik niet moet zeuren, want ik heb aan geen van beide meegedaan, maar als toeschouwer wil je ook wat :P . Ik hoop op een leuke (minder brute force, meer 'slim') volgende contest. Ik ben van plan mee te gaan doen...
Deze opdracht is juist zo leuk omdat recht-toe-recht-aan alle mogelijkheden evalueren zó onmogelijk is, je automatisch wel slimme oplossingen moet gaan bedenken. Iets in de orde van grootte van 10000^400 mogelijkheden doorrekenen (bij bijvoorbeeld 400 woorden) is ettelijke malen meer dan het aantal atomen in het helaal. :P

Alleen voor de slimme oplossingen is heel veel trial en error nodig om er een vinger achter te krijgen welke vuistregels goed werken voor het samenstellen van een grid. Tijdsintensief dus.

Acties:
  • 0 Henk 'm!

  • Serpie
  • Registratie: Maart 2005
  • Laatst online: 01-07-2023
Verwijderd schreef op donderdag 10 mei 2007 @ 10:19:
Ik vond deze contest ook minder leuk dan de vorige. Ik weet dat ik niet moet zeuren, want ik heb aan geen van beide meegedaan, maar als toeschouwer wil je ook wat :P . Ik hoop op een leuke (minder brute force, meer 'slim') volgende contest. Ik ben van plan mee te gaan doen...
Het is juist leuk als het voor een grote groep toegankelijk is, een te grote uitdaging kan er voor zorgen dat het aantal deelnemers flink inzakt. Ik vind dat de modjes er goed in zijn geslaagd om iets te verzinnen wat voor veel mensen toegankelijk is (makkelijk iets werkends te krijgen), en waar toch ook een uitdaging in zit voor de gevorderden.

Ik heb de vorige niet mee gedaan, maar die had me ook erg leuk geleken en ik ga de volgende zeker ook weer meedoen. Deze contest had ik eigenlijk wat te weinig tijd, naast mijn werk doe ik een studie aan het OU en ben pas bij mijn P. Laatbloeier wat studie betreft, ben er ingerold zeg maar en op mijn werk doe ik alleen database programmeren en wat UI dus weinig met datastructuren en algoritmen te maken. Dus dit is een goeie oefening voor het soort opdrachten die ik normaliter niet krijg.

Mijn complimenten voor de organisatie _/-\o_

Acties:
  • 0 Henk 'm!

  • KoW
  • Registratie: Juli 2001
  • Laatst online: 17-08-2022

KoW

Parse parsed te veel

* KoW heeft eigenlijk nooit een studie of cursus programmeren gevolgd.
Gewoon via voorbeeldjes wat uitproberen.

Maar idd, deze contest is zo opgezet dat iedereen mee kan doen.
Of je goede scores haalt ligt voornamelijk aan het bedachte algoritme.

Als ik dan kijk naar de uitleg bij sommige inzendingen, kan ik alleen maar concluderen dat ik relatief simpele aanpak heb gekozen.
Pagina: 1 ... 7 ... 9 Laatste