Posted by
| Nick Gammon
Australia (23,133 posts) Bio
Forum Administrator |
Message
| Well, if this MUD allows it. Here is a way I thought up to detect anagrams from a list of known words.
Basically A is an anagram of B is it has the same letters with the same frequencies (eg. 2 x A, 3 x E, 2 x T). So we can take our known words and turn them into a table, like this:
"00020000100000000000000000"="Did"
"01001010000000300110010000"="borogoves"
"00000000100001000000000000"="in"
"11001000000000000000001000"="wabe"
"00001001000000000001000000"="the"
"10000000000200000000000000"="All"
"00000000100020000010000010"="mimsy"
"10010000000001000000000000"="And"
"00002000000000000100001000"="were"
"00001000000000100011010000"="toves"
"00001010000000000100000010"="gyre"
"01000010200200000100000000"="brillig"
"00001000000020100000000000"="mome"
"10000001000000000111000000"="raths"
"10000000000000000011001000"="Twas"
"00000001100100000011000010"="slithy"
"11001010000000100101100000"="outgrabe"
"01001010100110000000000000"="gimble"
The word "All" for example has 1 x A and 2 x L ("10000000000200000000000000").
So we can save them in a table, and look up a target word to see if it has the same pattern (like "LAL" would have).
-- return a string with a count for each occurrence of the letters A-Z
function calculateFrequencies (str)
-- no letters have appeared yet
local t = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }
for i = 1, #str do
local c = str:sub (i, i):upper () -- get each character (in upper case)
if c >= "A" and c <= "Z" then
local val = string.byte (c) - string.byte ("A") + 1
t [val] = t [val] + 1 -- one more occurence of this one
end -- if alphabetic
end -- for
for k, v in ipairs (t) do
if v > 9 then -- if more than 9 of one letter put an "x" there
t [k] = "x"
else
t [k] = tostring (v) -- turn into a string
end -- if
end -- for each one
return table.concat (t)
end -- calculateFrequencies
-- words we know
knownWords = {
"Twas", "brillig", "and", "the", "slithy",
"toves", "Did", "gyre", "and", "gimble",
"in", "the", "wabe", "All", "mimsy",
"were", "the", "borogoves", "And",
"the", "mome", "raths", "outgrabe",
}
-- converted into frequencies
convertedWords = { }
for k, v in ipairs (knownWords) do
convertedWords [calculateFrequencies (v)] = v
end -- for each word
-- words to test against
testWords = {
"food", "candy", "nick", "lua", -- not known
"swat", "votes", "dna", "mmoe" -- known
}
for k, v in ipairs (testWords) do
print (v)
local original = convertedWords [calculateFrequencies (v)]
if original then
print (" -->", original)
else
print (" not known.")
end -- if
end -- for
Output from test:
food
not known.
candy
not known.
nick
not known.
lua
not known.
swat
--> Twas
votes
--> toves
dna
--> And
mmoe
--> mome
|
- Nick Gammon
www.gammon.com.au, www.mushclient.com | Top |
|