koobas.hobune.stream
Match all words containing specific set of letters
I have got a wordlist text file with about 17 000 words. I have also got a randomly generated letter set, say
string[] letters = { "a", "b", "t", "e", "l", "t" };
I am looking for an efficient way for my game to find all word matches that contain three or more or ultimately all of the letters it is given in the letters array. Listing all possible combinations seems like a very slow and inefficient way to work that out, so I assume it would be best if I used Regular Expression.
So here are some of the valid matches I am supposed to get from the list above: bat, table, battle, tab, belt, able, ale, late, tale
If I exclude "l", the number of valid matches narrow down to two: "bat" and "tab" only.
So basically it's a Scrabble game and I'm working on the AI: I want the computer opponent to be able to detect when it has gotten enough letters (represented by lettered tiles) to construct a specific word(s) from the database. So it needs to find all words that are constructed with three or more of the letters available. Since a single tile represents a single letter, there must not be any matches where a letter is used more than once, unless it appears more than once in the letters array.
Example: When you have got { "a", "b", "e", "l", "t" }, "table" would be a valid match. "battle" would be an invalid match, since there is only one instance of the letter "T" available.
dude, you totally WANT SCRABBLE PROGRA$$anonymous$$$$anonymous$$ED?? !
whoa !
to be honest, that is not so much Unity3D specific you know ..
I reckon, you could try on gamedev or something like that.
good luck !!
No no, I don't need the whole game programmed. The human gameplay of my Scrabble game is almost done all I need now is this word matching (for the AI specifically) I'm talking about here.
lol for sure dude. that's the rather hard part ! enjoy !
shadedrop has given you an incredible tip
as shaedrop but with an slight variation. i would assign weights to the different letters and check for them in a db or something. like this
1st i would check the number of letters
num of letters =
2 - 100
3 - 200
4 - 300
5 - 400
6 - 500
7 - 600
8 - 800
i would a ssign a value to every letter and count the result but with the index of how many letter it has for example : the words iwth the same amout of letters and the same letters should give u the same n umber.
a - 11 roma (400) = 119+116+114+11 = 400360
b - 22 amor (400) = 11+114+116+119 = 400360
c - 33 risa (400) = 119+99+220+11 = 400449
d - 44 casa (400) = 33+11+220+11 = 400275
e - 55 raro (400) = 119+11+119+116 = 400365
f - 66 toro (400) = 221+116+119+116= 400572
g - 77 pala (400) = 117+11+113+11 = 400252
h - 88
i - 99
j - 111
k - 112
l - 113
m - 114
n - 115
o - 116
p - 117
q - 118
r - 119
s - 220
t - 221
u - 222
v - 223
w - 224
x - 225
y - 226
z - 227
idk if i explained myself but i hope u get the idea. probably u might need to test it 1st just to make sure that the values wont be the same in special cases. and test with different weights. hope i hepled :P
You are right, there are cases where values are equal (i.e. 117+221=116+222=115+223), but I get the idea and it is brilliant! Thank you very much.
I don't think regular expressions are going to help you here. One possible approach is to process the list of words into some kind of data structure, like a multi-value dictionary, where the key is the letters of the word sorted alphabetically, and the value is a list of words that match those letters.
Using your own example, you store the list of words bat, tab, belt, battle late and tale like so:
Key Values
===== ======
abt bat, tab
aelt tale, late
belt belt
abeltt battle
And so on. Then all you need to do for any list of letters is to sort them alphabetically, combine them into a string, and use that to access the dictionary.
Hope this makes sense :)
FTR this is how you do it in the major scrabble engines we are familiar with !
