129Views29Replies

Author Options:

Calling All Programmers (Yes, ALL) Answered

Every now and then in typing class, our teacher will give us a handful of letters, and we're given about 5 minutes to come up with as many words as we can from these letters. So today I thought... what if there was a program where you could input a string of letters, and it would spit out as many words as possible that can be made out of those letters. A quick Google search was less than fruitful. So, to the more techier of my fellow Iblians, how would you go about writing a program that could do this? I'm thinking something where you input a string of letters, and then it scans, say, an online dictionary, to find as many words as possible from the inputted letters. Sound doable?

29 Replies

user
Chicken2209 (author)2009-02-09

it must exist! it was in national treasure!

Select as Best AnswerUndo Best Answer

user
whatsisface (author)Lithium Rain2009-02-20

Odd, we have a pool hall called Rileys.

Select as Best AnswerUndo Best Answer

user
Lithium Rain (author)Chicken22092009-02-09

(He's the guy who is running all that equipment in the movie)

Select as Best AnswerUndo Best Answer

user
Chicken2209 (author)Lithium Rain2009-02-09

... i thought Nicholas Cage movies were jessyratfink's thing..

Select as Best AnswerUndo Best Answer

user
Lithium Rain (author)Chicken22092009-02-09

What, we can't share a thing?!

Select as Best AnswerUndo Best Answer

user
Chicken2209 (author)Lithium Rain2009-02-09

no one likes a copy cat only copy kitties

Select as Best AnswerUndo Best Answer

user
Padlock (author)2009-02-10

A program that would do that would have immense outputs. To be precise, the number of letters factorial. For example, 10 letters would have 3,628,800 different combinations. As for adding a filter to only output actual words, then you would have to use some sort of dictionary function... Which I don't recall being in any programming language I have learned. Making a commandline program wouldn't be hard, as long as you found a dictionary checking program to call. Or, possible some PHP to interface dictionary.com and use the resulting page to determine whether or not it is a word. It all depends on the lengths of the word though... loading a webpage 3,628,800 times would take a long time, not to mention processing the results.

Select as Best AnswerUndo Best Answer

user
Goodhart (author)Padlock2009-02-10

there is a CLASS in javascript called Dictionary.js which may be useful in this case.

Select as Best AnswerUndo Best Answer

user
Padlock (author)Goodhart2009-02-11

browser based languages are kinda limited in interaction with files, so it would have to be completely self contained, I'm guessing. But hey, I don't know. I don't have much experience with JavaScript.

Select as Best AnswerUndo Best Answer

user
Goodhart (author)Padlock2009-02-11

JavaScript can be Client run, or Server run and, as far as I know, it is not browser dependent (not dependent on one browser that is). Still, a language more like Perl or C# may be better for writing the "sort"

Select as Best AnswerUndo Best Answer

user
gschoppe (author)Goodhart2009-02-20

I would not reccommend JScript for this sort of thing... It has some real issues with datatypes and complicated operations... I'd do it in ANSI C, because although memory management and garbage collection are easy to mess up, the control to quickly create complicated custom data indexing methods is awesome... at the same time, for a recursive program like this, a FUNCTIONAL programming language would be a perfect fit... I've changed my opinion in mid thought... USE SML. IT WILL BLOW YOUR MIND for this sort of program.

Select as Best AnswerUndo Best Answer

user
Goodhart (author)gschoppe2009-02-20

Hmm, I had not heard about Standard ML before your mention of it.....but I see where it has great strengths in this area: SML Link

Select as Best AnswerUndo Best Answer

user
PKM (author)Padlock2009-02-11

Remember that to a computer, 3 million does not equal "immense". The computer could generate all 3,628,800 possible combinations in seconds, and check them against a 100,000 word dictionary easily. The most efficient way of making words and checking them is an interesting programming puzzle. I'd be tempted to generate the shorter combinations first (so make words like "as" and "in", then "ask" and "ink", etc.) and check those against the dictionary (looking up a word in a dictionary is a very time-efficient task if the dictionary is stored on the computer in the right way) before writing the existing words out to a list. In fact, the description I've given above is half the program already. Labot: Do you actually want to write this program? If so, what languages do you know?

Select as Best AnswerUndo Best Answer

user
Padlock (author)PKM2009-02-11

I made a program that generated all of the 3,628,800 10 letter words-- just a quick command line program-- and it took 31.28 seconds. This is just the 10 letter words- All of them would be 10! + (2)9! + (3)8! + (4)7! + (5)6! + (6)5! + (7)4! + (8)3! + (9)2! + (10)1!. The total of ALL possible combinations would be 4500244. This would take almost twice as long, and that's without even looking them up. Not to mention, I doubt there is just this 100,000 word outsourcing dictionary... It would have to be built directly into a programming language.... Like javascript (So goodhart says. Idk, I don't have any expierience in web-programming except for a little of the basic HTML)

Select as Best AnswerUndo Best Answer

user
PKM (author)Padlock2009-02-12

"unabr.dict" at this site is a 2.2MB file that is simply a text file containing a list of every word from an unabridged dictionary separated by newline characters. Just the words, not the definitions- exactly what you need for this task. From a programming perspective it would be trivial to read that into your program into a large array and check the words you generated against the list- many higher-level languages have a single function, called Split or similar, to do exactly that.

If you do download that file, be careful with it- I loaded the file into Word 2007 and tried to do a word count. The word count crashed Word, and that's on my work machine with a Core2 Quad and 4GB of RAM O_O

Select as Best AnswerUndo Best Answer

user
PKM (author)PKM2009-02-12

With a bit of cajoling I found out it's about 345,000 words- don't try dealing with that using javascript or a command line program...

Select as Best AnswerUndo Best Answer

user
Padlock (author)PKM2009-02-14

I used "type" from the command line and it took a good 8 minutes for it to print the entire list. If this was used, it would HAVE to be split into different files based on length, first letter, or both, etc.

Select as Best AnswerUndo Best Answer

user
PKM (author)Padlock2009-02-15

If you were going to do it with a batch file program or Windows command line stuff, yes it would be. The alternative is to use a lower-level language like C and/or a more efficient method to generate the words, and I guarantee you a well-written C program could deal with that entire dictionary as one file and generate all the possible words from ten letters in seconds, not minutes. Think about the files that Photoshop or a modern game deal with- they make a 2MB text file seem inconsequential. I'm actually tempted to write this program having spent so long discussing it. brb, coding :)

Select as Best AnswerUndo Best Answer

user
Padlock (author)PKM2009-02-14

Maybe separate it into several different text files, maybe by first letter. I tried to open it... It crashed notepad.

Select as Best AnswerUndo Best Answer

user
lemonie (author)2009-02-14

Perhaps you need an anagram solver?

Note that bumpus has posted something similar, and from the look of it possibly better.

L

Select as Best AnswerUndo Best Answer

user
jedi pen-gui-n (author)2009-02-20

http://www.franklin.com/estore/dictionary/MWD-1490&referral_code=NQYMBIO/

i have a merriam -webster mwd-1490 portable dictionary and one of the games , word builder , will make words out of up to fourteen letters. Sounds like just what you need.

Select as Best AnswerUndo Best Answer

user
gschoppe (author)2009-02-19

simple trick that cuts processing time... sort your letters alphabetically and sort your dictionary alphabetically... store your dictionary in a tree arranged such that each node has up to 26 children, identified by letter, and a value containing all words that alphabetized path from root to node contains.... then you can perform a depth first search that atempts each possible alphabetized path you can get from a subset of the letters... the cool part is that because it's depth first, and recursive, the number of operations per scan is tiny.... You could also make a strong case for hash tables... In any event, I reccomend memoising the operations, if space is not an issue... that way, once you get a subset's response once, its a single operation for every future recall. YAY... SHOUT OUT TO PROF RUDICH

Select as Best AnswerUndo Best Answer

user
Goodhart (author)2009-02-10

How many letters? If they really are only a handful, the simplest way would be to use a simple bubble sort and make as many combinations as possible and then spell check them with a good spell checker.

If there are more then say, 8-10 letters, you get into both a time bind, and an overwhelmingly large number of words to look through.

Select as Best AnswerUndo Best Answer

user
tech-king (author)2009-02-09

just google anagram programs.

Select as Best AnswerUndo Best Answer