News for hackers. Stuff that matters.
Re:ITA Software's Hiring Puzzles by jules on Thursday April 22, 2010 @09:00AM (#1284922)
What do you mean by anagram solver? Find anagrams for a given word? Isn't that trivial by indexing words by the sorted version of the word? E.g. {"aep" -> ["ape", "pea"], ...}
Re:ITA Software's Hiring Puzzles by chime on Thursday April 22, 2010 @10:35AM (#1285174)
I'm trying to built a better multi-word anagram solver. If you input a 32 character string, you'll end up with hundreds of thousands of potential anagrams and most of them are pretty useless. For example, "Florence Nightingale" returns 52k results on:

http://wordsmith.org/anagram/anagram.cgi?anagram=Florence+Ni...

And most of them are pretty lame e.g. "A Fleecer Tingling Hon", "A Fleecer Longing Hint" etc. It'll take hours before you come across "Flit on, cheering angel" - I want to make this process faster/easier.

Re:ITA Software's Hiring Puzzles by pwk on Thursday April 22, 2010 @11:50AM (#1285411)
It's a fun project! I built one several years ago, after playing around with a bunch of different approaches. I wound up with a human-guided tool that seems to work pretty well for coming up with interesting ones:

http://anagramlogic.com/

Re:ITA Software's Hiring Puzzles by jules on Thursday April 22, 2010 @01:48PM (#1285820)
Ah, interesting! This problem is NP-complete even in if you don't specifically want anagrams that are interesting to a human.

Suppose that you only have a single letter alphabet (say "a"). Now the input string can only contain a's, so it can be represented by a number n. The dictionary also consists only of words of a's, so the dictionary can be represented as a set of numbers D a subset of the natural numbers. Now the problem of finding an anagram is finding a subset of A of D such that sum(A) = n. But this is the subset sum problem, which is NP-complete!

How are you determining the interestingness of an anagram?

Re:ITA Software's Hiring Puzzles by tedunangst on Thursday April 22, 2010 @11:09AM (#1285277)
Use random partitioning? If you have more than 10 letters, randomly split into roughly equal parts. Then do that 1000 times to the input string.
Re:ITA Software's Hiring Puzzles by rimantas on Thursday April 22, 2010 @06:04PM (#1286623)
I wrote this snippet ~10 years ago when learning Perl:

  for(<>){chop;$s{join'',sort split'',lc}.=" $_"}for(sort%s){/. /&&print"$_\n"}
Running against wordlist.txt was fun (anemic cinema, bedroom boredom, etc.)
Re:ITA Software's Hiring Puzzles by asimjalis on Thursday April 22, 2010 @09:39AM (#1285006)
Yes.
Re:ITA Software's Hiring Puzzles by jjs on Thursday April 22, 2010 @09:55AM (#1285048)
Until you get to multiple-word anagrammatic phrases, when it becomes a search problem.

(You could index a list of phrases the same way, but users wouldn't be able to type in their name and find out what phrases it jumbles into.)