Gamestudio Links
Zorro Links
Newest Posts
Blobsculptor tools and objects download here
by NeoDumont. 03/28/24 03:01
Issue with Multi-Core WFO Training
by aliswee. 03/24/24 20:20
Why Zorro supports up to 72 cores?
by Edgar_Herrera. 03/23/24 21:41
Zorro Trader GPT
by TipmyPip. 03/06/24 09:27
VSCode instead of SED
by 3run. 03/01/24 19:06
AUM Magazine
Latest Screens
The Bible Game
A psychological thriller game
SHADOW (2014)
DEAD TASTE
Who's Online Now
3 registered members (Edgar_Herrera, VoroneTZ, Akow), 973 guests, and 4 spiders.
Key: Admin, Global Mod, Mod
Newest Members
sakolin, rajesh7827, juergen_wue, NITRO_FOREVER, jack0roses
19043 Registered Users
Previous Thread
Next Thread
Print Thread
Rate Thread
Longest word from array of letters #435676
01/10/14 16:00
01/10/14 16:00
Joined: Jan 2006
Posts: 968
EpsiloN Offline OP
User
EpsiloN  Offline OP
User

Joined: Jan 2006
Posts: 968
For a side project, I have to make a function search through a list of all words (80k or more).

I have an array of letters arranged like this:
abcd
efgh
ijkl
mnop

The user can go from "a" to its neighbours "b" "e" or "f". Crossing is allowed (eg. "b" to "e" to "a" and to "f").

My logic: Get all possible combinations of 3+ letters up to 16, then match every combination to the word list and remove anything that isnt a word, then sort by length.

But I dont even know where to begin! frown

I could hard-code all possible moves between letters, but that would be a LOT of combinations and time.

Anyone have any ideas?


Extensive Multiplayer tutorial:
http://mesetts.com/index.php?page=201
Re: Longest word from array of letters [Re: EpsiloN] #435677
01/10/14 16:09
01/10/14 16:09
Joined: Apr 2007
Posts: 3,751
Canada
WretchedSid Offline
Expert
WretchedSid  Offline
Expert

Joined: Apr 2007
Posts: 3,751
Canada
I don't really understand the problem, care to elaborate a bit more on that? In theory it sounds like you want to build a trie out of your word dictionary and then check all permutations of your input against that trie.


Shitlord by trade and passion. Graphics programmer at Laminar Research.
I write blog posts at feresignum.com
Re: Longest word from array of letters [Re: EpsiloN] #435678
01/10/14 16:10
01/10/14 16:10
Joined: Jun 2009
Posts: 2,210
Bavaria, Germany
Kartoffel Offline
Expert
Kartoffel  Offline
Expert

Joined: Jun 2009
Posts: 2,210
Bavaria, Germany
brute-force?

use a 2d-array, write some lines of code which check every possible direction (shouldn't be too hard if it's a recursive function) and iterate through the whole array.


POTATO-MAN saves the day! - Random
Re: Longest word from array of letters [Re: WretchedSid] #435679
01/10/14 16:22
01/10/14 16:22
Joined: Jan 2006
Posts: 968
EpsiloN Offline OP
User
EpsiloN  Offline OP
User

Joined: Jan 2006
Posts: 968
I need to get all possible combinations out of those letters, so I can compare them to the word list and display the real words to the user. But, its not like cracking a password, where you may have all symbols at any space, here you got adjacent nodes wich you have to connect, so the resulting combinations are limited.

I have no idea how to make a function to get all possible combinations between the letters. I dont want to hard-code the possible combinations so I can compare the resulting letters to the word list.

I cant even explain it well grin
I just saw its called Boggle solver in google.



*EDIT*
Quote:
use a 2d-array, write some lines of code which check every possible direction (shouldn't be too hard if it's a recursive function) and iterate through the whole array.

OK. You got me thinking laugh
I can define the rules - from wich node you can go to wich node , and 16 temp variables to check if a node has been 'visited'...And generate all possible 'paths' for each node to every other,right?

Last edited by EpsiloN; 01/10/14 16:25.

Extensive Multiplayer tutorial:
http://mesetts.com/index.php?page=201
Re: Longest word from array of letters [Re: EpsiloN] #435682
01/10/14 16:46
01/10/14 16:46
Joined: Apr 2007
Posts: 3,751
Canada
WretchedSid Offline
Expert
WretchedSid  Offline
Expert

Joined: Apr 2007
Posts: 3,751
Canada
Aha!
Now we are talking. And while we are talking, you probably don't want to brute force this, it's going to be slow as hell!

Again, put your word dictionary into a trie! Tries are perfect to match prefixes, which is exactly what you want to do. Next up create a list of all prefixes and their end positions, ie, at the beginning you have an n x n sized list one for each letter (and the matched prefix then becomes a letter). Each of these triplets looks something like this: (x, y, s) where x and y are the coordinates in the letter matrix and s is the already found prefix.

Now, go over every in the list and for each entry go over all adjacent letters (l) in the letter matrix and check s + l against the trie.
if s + l is a word, add it to the found word list
if s + l is a prefix to a word, add a new entry to the list with x and y being the position of l in the letter matrix and s being s + l

Rinse and repeat until you are done.

The rest is just iterating over the output to find the longest match, and tada you are done.
I would like to add that this idea isn't mine but comes from this StackOverflow question, which also contains some more possible solutions. You'll see a lot of tries there, which is due to the fact that tries are the perfect data structure for this sort of thing. Know your data structures wink


Shitlord by trade and passion. Graphics programmer at Laminar Research.
I write blog posts at feresignum.com
Re: Longest word from array of letters [Re: WretchedSid] #435683
01/10/14 17:04
01/10/14 17:04
Joined: Jan 2006
Posts: 968
EpsiloN Offline OP
User
EpsiloN  Offline OP
User

Joined: Jan 2006
Posts: 968
I do hope my GF will reward me for all this tonight grin

I know answers to this already exist in all sorts of languages and methods, but there arent any in Bulgarian alphabet laugh

Thanks, gonna look up all this info now and try to imagine the whole thing before jumping in.


Extensive Multiplayer tutorial:
http://mesetts.com/index.php?page=201

Moderated by  HeelX, Lukas, rayp, Rei_Ayanami, Superku, Tobias, TWO, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de

Powered by UBB.threads™ PHP Forum Software 7.7.1