1. Just For Fun Contest #1: Word Squares
- Posted by euphoric (admin) Jun 21, 2009
- 1811 views
If anybody's been bored lately or wants to have some programming challenge fun, try this out: Word Squares Contest.
2. Re: Just For Fun Contest #1: Word Squares
- Posted by useless Jun 21, 2009
- 1787 views
- Last edited Jun 22, 2009
If anybody's been bored lately or wants to have some programming challenge fun, try this out: Word Squares Contest.
What is the point of the grid, if all you want is the most words that can be made of x amount of letters?
useless
3. Re: Just For Fun Contest #1: Word Squares
- Posted by euphoric (admin) Jun 22, 2009
- 1780 views
If anybody's been bored lately or wants to have some programming challenge fun, try this out: Word Squares Contest.
What is the point of the grid, if all you want is the most words that can be made of x amount of letters?
But that's not what I want and I never said it was. The example I gave only applies to the size 2 grid. Basically, you have four letters to use in that case, all of them touching and so the combinations are as simple as finding a set of four letters that form the most words. On a size 3 grid, there are nine letters, and they aren't all adjacent to one another. You can't just pick and choose. You have to follow a path from one letter to the next adjacent letter (either straight or diagonal). An example size 4 board:
SVAT OUTR LIDO BIUA
While the letters 's' 't' 'a' and 'b' are in this grid and form the word "stab," they are not adjacent to each other and so the word doesn't count.
However, with the upper right quadrant, you could form ART, RAT, TAR. Some five letters word in there are SOLID and AUDIO.
So, you have a limited set of letters and a limited way in which they can be joined.
I hope that's clear. Have you never seen or played Boggle?!
4. Re: Just For Fun Contest #1: Word Squares
- Posted by useless Jun 22, 2009
- 1810 views
If anybody's been bored lately or wants to have some programming challenge fun, try this out: Word Squares Contest.
What is the point of the grid, if all you want is the most words that can be made of x amount of letters?
But that's not what I want and I never said it was. The example I gave only applies to the size 2 grid. Basically, you have four letters to use in that case, all of them touching and so the combinations are as simple as finding a set of four letters that form the most words. On a size 3 grid, there are nine letters, and they aren't all adjacent to one another. You can't just pick and choose. You have to follow a path from one letter to the next adjacent letter (either straight or diagonal). An example size 4 board:
SVAT OUTR LIDO BIUA
While the letters 's' 't' 'a' and 'b' are in this grid and form the word "stab," they are not adjacent to each other and so the word doesn't count.
However, with the upper right quadrant, you could form ART, RAT, TAR. Some five letters word in there are SOLID and AUDIO.
So, you have a limited set of letters and a limited way in which they can be joined.
I hope that's clear. Have you never seen or played Boggle?!
No, never played Boggle. Social and cultural games require society and a culture, things i am legally (as in a court of law) not allowed to have.
useless
5. Re: Just For Fun Contest #1: Word Squares
- Posted by euphoric (admin) Aug 24, 2009
- 1665 views
I've posted an update to this challenge.
6. Re: Just For Fun Contest #1: Word Squares
- Posted by mindwalker Mar 06, 2011
- 1510 views
Quote from the contest:
This next contest is just for fun: using a standard dictionary (words.txt (Google it), or a Euphoria database dictionary of words) and given a square grid with sides of length x (from 2 to X), with a letter in each grid square, determine all possible words in the grid using adjacent letters, each letter used only once, and with word length at least 3 characters.
Yes, this is a Boggle solver. But, there's a twist! For each grid size, determine what combination of letters will give the highest possible score. ...
Notes
- The score for any grid is completely dependent on the dictionary used. To see this most clearly choose a dictionary with no words. Then every grid no matter its size or the letters it contains scores zero. Now add just one word to that dictionary, say "dog" and all grids will fall into one of two possibilities; those that can form "dog" and those that can not. Of course the ones that can will have their scores go up. By extension take any standard dictionary and add one new word and all grids will fall into one of two possibilities, where the ones that can form the new word will have their scores go up with the possibility that that increase will push some grid into top spot.
A perfect real life example of this, I used to play boggle on pogo.com and one day I was playing a grid that contained the words 'european' and 'europeans'. But Pogo's dictionary apparently does not include the plural, so I wasted a lot of time trying to enter this word over and over thinking I was mistyping it in my hurry.
My point is that if people start with different dictionaries they probably will arrive at different solution grids for the second portion of the contest. In order to determine the best program you would need to establish one dictionary to be used (Google returns many different "words.txt" dictionaries), so that you are comparing apples to apples.
- Even with a specific dictionary established a brute force program that returns the best grid of size x is going to require a super computer or many computers dividing the task for grids of size greater than 3.
To see this lets examine how many different grids of size x can be formed. If x is 1 there are 26 possibilities. When x = 2, there are 26 to the 4th power possibilities (456976), still small enough for a standard computer. But when x = 3 there are 26 to the 9th power grids to evaluate (5429503678976). If a computer was able to score 1,000,000 grids per second (and I don't believe a standard computer can even do this), it would take about two months to process them all. Obviously any larger x would be beyond a standard computer's abilities.
So for anybody who is looking to solve the second half of the contest, you will need to be able to eliminate whole classes of grids without evaluating them directly. Otherwise you will need to develop a genetic algorithm that keeps looking for a better solution until some criterion is met. There is no guarantee the solution found will be the best.
As an example of the elimination of classes of grids, grids with 80 percent or more of the same consonant letter won't be the best grid.
One thought for a genetic algorithm, analyze the dictionary to determine the frequency that each letter appears adjacent to each of the letters. Then the algorithm will take the best grid so far (start with any random grid) and pick one letter to be replaced. It will use the sum of the frequencies of the grid letters adjacent to the cell being replaced to set a probability for each letter being the one picked.
I have taken a boggle solver (written in Euphoria version 3.1.1) that I had developed previously and modified it to read/write files (as per the contest rules). My solver treats the letter Q in the grid as a QU something many boggle games do. It incorporates a 51k+ word dictionary. If I can figure out how, I'll pass a shrouded copy of my solver to be posted on the http://UsingEuphoria.com website so that you can give it a try.
Can you write a faster solver?
Some examples (minus the found words list) of grids solved
BKNA
MAPU
OTRI
TDDG
Solved time: 0.005 seconds
words found: 80
QITM
ETJU
GEBW
NARO
Solved time: 0.004 seconds
words found: 83
IRNE
ONKO
TUAO
PEIO
Solved time: 0.003 seconds
words found: 50
SORE
DETW
IIUM
EOES
Solved time: 0.003 seconds
words found: 101
TEKU
DAOG
VBEL
REPI
Solved time: 0.003 seconds
words found: 91
RODE
ADSL
AOOE
OSRY
Solved time: 0.004 seconds
words found: 86
DWHE
OPSE
RERN
GTGE
Solved time: 0.005 seconds
words found: 91
INTHEBEGINNINGGODCRE
ATEDTHEHEAVENANDTHEE
ARTHANDTHEEARTHWASWI
THOUTFORMANDVOIDANDD
ARKNESSWASUPONTHEFAC
EOFTHEDEEPANDTHESPIR
ITOFGODMOVEDUPONTHEF
ACEOFTHEWATERSANDGOD
SAIDLETTHEREBELIGHTA
NDTHEREWASLIGHTANDGO
DSAWTHELIGHTTHATITWA
SGOODANDGODDIVIDEDTH
ELIGHTFROMTHEDARKNES
SANDGODCALLEDTHELIGH
TDAYANDTHEDARKNESSHE
CALLEDNIGHTANDTHEEVE
NINGANDTHEMORNINGWER
ETHEFIRSTDAYANDGODSA
IDLETTHEREBEAFIRMAME
NTINTHEMIDSTOFTHEWAT
Solved time: 0.576 seconds
words found: 3619
CALLMEISHMAELSOMEYEARSAGONEVERMINDHOWLONGPRECISELY
HAVINGLITTLEORNOMONEYINMYPURSEANDNOTHINGPARTICULAR
TOINTERESTMEONSHOREITHOUGHTIWOULDSAILABOUTALITTLEA
NDSEETHEWATERYPARTOFTHEWORLDITISAWAYIHAVEOFDRIVING
OFFTHESPLEENANDREGULATINGTHECIRCULATIONWHENEVERIFI
NDMYSELFGROWINGGRIMABOUTTHEMOUTHWHENEVERITISADAMPD
RIZZLYNOVEMBERINMYSOULWHENEVERIFINDMYSELFINVOLUNTA
RILYPAUSINGBEFORECOFFINWAREHOUSESANDBRINGINGUPTHER
EAROFEVERYFUNERALIMEETANDESPECIALLYWHENEVERMYHYPOS
GETSUCHANUPPERHANDOFMETHATITREQUIRESASTRONGMORALPR
INCIPLETOPREVENTMEFROMDELIBERATELYSTEPPINGINTOTHES
TREETANDMETHODICALLYKNOCKINGPEOPLESHATSOFFTHENIACC
OUNTITHIGHTIMETOGETTOSEAASSOONASICANTHISISMYSUBSTI
TUTEFORPISTOLANDBALLWITHAPHILOSOPHICALFLOURISHCATO
THROWSHIMSELFUPONHISSWORDIQUIETLYTAKETOTHESHIPTHER
EISNOTHINGSURPRISINGINTHISIFTHEYBUTKNEWITALMOSTALL
MENINTHEIRDEGREESOMETIMEOROTHERCHERISHVERYNEARLYTH
ESAMEFEELINGSTOWARDSTHEOCEANWITHMETHERENOWISYOURIN
SULARCITYOFTHEMANHATTOESBELTEDROUNDBYWHARVESASINDI
ANISLESBYCORALREEFSCOMMERCESURROUNDSITWITHHERSURFR
IGHTANDLEFTTHESTREETSTAKEYOUWATERWARDITSEXTREMEDOW
NTOWNISTHEBATTERYWHERETHATNOBLEMOLEISWASHEDBYWAVES
ANDCOOLEDBYBREEZESWHICHAFEWHOURSPREVIOUSWEREOUTOFS
IGHTOFLANDLOOKATTHECROWDSOFWATERGAZERSTHERECIRCUMA
MBULATETHECITYOFADREAMYSABBATHAFTERNOONGOFROMCORLE
ARSHOOKTOCOENTIESSLIPANDFROMTHENCEBYWHITEHALLNORTH
WARDWHATDOYOUSEEPOSTEDLIKESILENTSENTINELSALLAROUND
THETOWNSTANDTHOUSANDSUPONTHOUSANDSOFMORTALMENFIXED
INOCEANREVERIESSOMELEANINGAGAINSTTHESPILESSOMESEAT
EDUPONTHEPIERHEADSSOMELOOKINGOVERTHEBULWARKSOFSHIP
SFROMCHINASOMEHIGHALOFTINTHERIGGINGASIFSTRIVINGTOG
ETASTILLBETTERSEAWARDPEEPBUTTHESEAREALLLANDSMENOFW
EEKDAYSPENTUPINLATHANDPLASTERTIEDTOCOUNTERSNAILEDT
OBENCHESCLINCHEDTODESKSHOWTHENISTHISARETHEGREENFIE
LDSGONEWHATDOTHEYHEREBUTLOOKHERECOMEMORECROWDSPACI
NGSTRAIGHTFORTHEWATERANDSEEMINGLYBOUNDFORADIVESTRA
NGENOTHINGWILLCONTENTTHEMBUTTHEEXTREMESTLIMITOFTHE
LANDLOITERINGUNDERTHESHADYLEEOFYONDERWAREHOUSESWIL
LNOTSUFFICENOTHEYMUSTGETJUSTASNIGHTHEWATERASTHEYPO
SSIBLYCANWITHOUTFALLINGINANDTHERETHEYSTANDMILESOFT
HEMLEAGUESINLANDERSALLTHEYCOMEFROMLANESANDALLEYSST
REETSANDAVENUESNORTHEASTSOUTHANDWESTYETHERETHEYALL
UNITETELLMEDOESTHEMAGNETICVIRTUEOFTHENEEDLESOFTHEC
OMPASSESOFALLTHOSESHIPSATTRACTTHEMTHITHERONCEMORES
AYYOUAREINTHECOUNTRYINSOMEHIGHLANDOFLAKESTAKEALMOS
TANYPATHYOUPLEASEANDTENTOONEITCARRIESYOUDOWNINADAL
EANDLEAVESYOUTHEREBYAPOOLINTHESTREAMTHEREISMAGICIN
ITLETTHEMOSTABSENTMINDEDOFMENBEPLUNGEDINHISDEEPEST
REVERIESSTANDTHATMANONHISLEGSSETHISFEETAGOINGANDHE
WILLINFALLIBLYLEADYOUTOWATERIFWATERTHEREBEINALLTHA
Solved time: 16.262 seconds
words found: 12756
