Text-Twist - similar to boggle problem

Question

A similar play on the boggle problem from before (some text from that has been used below, edited to fit) any code that solves the familiar "text-twist" game

Objective

7 letters are given at random, to which there is a minimum 1 word that uses all 7 letters, and multiple words using less (3 or more required)

The letters may be used in any order, however not duplicated (unless duplicates are included in the 7)

Your code should run for no more than 1 minute (60 seconds). At that time, it should have solved all results.

Final challenge score will be the character count of the program. In the event of a tie, the winner will be the fastest output, decided by an average of 3 inputs, the same being given to both. In the event there is still a tie, the winner will be whichever algorithm found more long (6+) words.

Rules / constraints

Please refer to wordlist.sourceforge.net for a word list (use ISPELL "english.0" list - the SCOWL list is missing some pretty common words). This listing may be referenced in your code any way you wish.

Answer 1

Perl, 90 chars

$_++for@q{<>=~/./g};open E,"E";while(<E>){%p=%q;$.*=$p{$_}--for/./g;y///c>3&&$.&&print}

The program takes the list of letters as a line on standard input. The word list is referenced as a file in the current directory named "E". (Presumably this falls under the umbrella of "any way you wish".)

Some other assumptions I made that were not spelled out in the problem description:

• that the goal was to produce a program (as opposed to a function);
• that the input was case-sensitive;
• that apostrophes and hyphens were not to be ignored;
• that the program was required to not match on words in the word list that were too short.

Also, I wonder if the time limit given in the original description is necessary. Even when given a huge list of letters such that every word in "english.0" matches, my program still runs to completion in under 1s.

Answer 2

Python, 158 chars

w=raw_input()
q=dict.fromkeys(w,0)
for c in w:q[c]+=1
for b in open('E'):
 p=dict(q)
 for c in b[:-1]:
    if p.get(c,0):p[c]-=1
    else:b=''
 if len(b)>3:print b,

This seems larger than it needs to be, but I'm just starting to learn Python from a golfing perspective. Hopefully someone more Python-savvy will submit a better answer.

Answer 3

bash 152

s(){
echo $1|sed -r 's/(.)/\1\n/g'|sort|tr -d "\n"
}
o=`s $1|sed -r 's/(.)/\1?/g'`
for s in `egrep "^[$1]{3,7}$" e`;do s $s|egrep -q ^$o$&& echo $s;done

The file has to be renamed to 'e' (line 1) to make it work.

Ungolfed:

Let's generate the testdata ourself:

alpha=({a..z})
word=$(for n in {1..7}; do r=$((RANDOM%26)); echo -n ${alpha[r]}; done ; echo)
echo $word
# $word=owimvhl

In above code, $word is $1 - user input.

text=$(egrep "^[$word]{3,7}$" english.0)
# t=hill him hollow how howl iii ill loom low mill mom mow oil owl vii viii vow whim who whom will willow woo wool

We take every word of len 3 to 7 from the english.0 dict, ^...$ prevent unwanted characters to slip in. We still might have unwanted duplicates, however.

sort () {
  echo $w | sed -r 's/(.)/\1\n/g' | sort | tr -d '\n'
}
# sort $w7 => hilmovw

We now split the word, to sort the characters, and rebuild the word. Now we insert a ? after every character:

optional=$(sort $word|sed -r 's/(.)/\1?/g')
# h?i?l?m?o?v?w?

This way we only use every character, which appears only once, only once.

for s in $text ; do sort $s | egrep -q "^$optional$" && echo $s; done
him
how
howl
low
mow
oil
owl
vow
whim
who
whom

Hm. Assertion that there is a match with 7 characters didn't hold. Try something else:

time ./cg-5947-text-twist.sh unknown
know
known
non
noun
now
nun
own
unknown

real    0m0.207s
user    0m0.200s
sys 0m0.052s

Answer 4

Ruby 154 152 151

require 'set'
d=Set.new(File.read(?e).split)
(3..7).each{|t|puts (0..6).to_a.permutation(t).map{|p|p.map{|i|$*[0][i]}.join}.select{|w|d.include? w}|[]}

Expects the 7 letter input as the first command line argument (ex: ruby texttwist.rb abcdefg). Dictionary is in a file called "e" in the same dir.

Answer 5

C# 412

void F(string l){
for(var i=3;i<8;i++)
foreach(var s in P(l.Length,i,new int[]{})
.Select(p=>new string(p.Select(c=>l[c]).ToArray()))
.Where(File.ReadAllLines("e").Contains)
.Distinct())
Console.WriteLine(s);
}
IEnumerable<int[]>P(int n,int r,int[]c){
if(c.Length<r)
for(var i=0;i<n;i++)foreach(var j in P(n,r,c.Concat(new[]{i}).ToArray()))yield return j;
else
if(c.Length==c.Distinct().Count())yield return c;
}

Not really the right language to golf in, but it was fun. :)

The entry point is the F method, which needs to be called with a string argument representing the 7 letters.

I tested it with the input "indents" got this output: http://pastebin.com/uBuwr50R (unfortunately I don't think it's possible to run this on ideone.com because of the dictionary file dependency).

The above test executes in about 7.5s on my machine.

If I replace File.ReadAllLines("e") with new HashSet<string>(File.ReadAllLines("e")), the execution time drops to about 1.5s, but at a pretty high character count cost.

Just like breadbox (in his Perl answer), I:

• named the dictionary file e and considered it's present in the current dir
• made the string comparisons case sensitive
• did not ignore special characters (apostrophes, hyphens) in string comparisons

Update: Here's an ungolfed (and slightly refactored for readability) version: http://pastebin.com/b1wxv4zU