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!