6
\$\begingroup\$

For those of you who have seen the popular daytime TV show Countdown, you will know that the contestants are given 9 randomly selected letters and must then find the longest word they can in 30 seconds.

Your challenge is, given a string of 9 letters, to find the longest word that is an anagram of the largest subset of input letters, this means that you don't have to use all of the letters in the input string.

Input/output can be stdin/stdout, or whatever the equivalent in your language is.

Rules

  • Input will always a 9 letter string, all lower-case
  • You can use as few or as many of the letters from the input string
  • A word is allowed if it is found in the specified dictionary file, the dictionary file containing all the allowed words can be found here (note: I didn't compile this, credit goes to the github uploader). The file is is a .txt file which contains ~101,000 words with each word on a new line - approx 985kB.
  • You must use the dictionary file specified above, this is to ensure that all fairness across all the entries, e.g. so everyone has the same chance of finding the longest word.
  • You are allowed to manipulate the dictionary file in such a way that none of the words are edited in any way and no new ones are added, for example copying all the words to an array, making all words comma separated or copying the whole contents of the file to another file would be allowed.
  • Inputs may contain any number of vowels and consonants, e.g. 9 vowels or 8 consonants and 1 vowel
  • If there are multiple words with the same length, then you must output all of them (up to a limit of 5 - to prevent long lists of 5/6 letter words). Multiple words must be delimited, but this can be done in any way - comma, space etc.

Test Cases

Input: mhdexaspo

Output: hexapods, mopheads

Input: iesretmng

Output: regiments

Input: cmilensua

Output: masculine calumnies

Input: floiufhyp

Output: huffily puffily

Input: frtuasmjg

Output: frusta,jurats,jumars,tragus,grafts

This is , so shortest code wins!

\$\endgroup\$
  • \$\begingroup\$ Input can be stdin/stdout or whatever the equivalent for your language is. \$\endgroup\$ – Rory McPerlroy Sep 27 '14 at 11:01
  • 1
    \$\begingroup\$ Borderline dupe of Anagram Code Golf! \$\endgroup\$ – Peter Taylor Sep 27 '14 at 11:32
  • 2
    \$\begingroup\$ @PeterTaylor I don't think so as that one you are just working out whether 2 strings have the same amount of characters. Where mine you have to work out the longest anagram of a single string. \$\endgroup\$ – Rory McPerlroy Sep 27 '14 at 12:03
  • 1
    \$\begingroup\$ So yours adds a loop, changes an == to a <=, and adds some post-processing to sort by length. I haven't voted to close as a dupe, but I did consider it. \$\endgroup\$ – Peter Taylor Sep 27 '14 at 12:16
  • \$\begingroup\$ I'm a little bit in love with Rachel Riley :x \$\endgroup\$ – britishtea Feb 4 '15 at 23:35
4
\$\begingroup\$

CJam, 51 bytes

Laeas$W%{1$f++}/:A;qN/{$aA&},{,~}$5<_0=,:L;{,L=},S*

CJam has no file I/O, so I opted to read the dictionary (converted to Unix format) from STDIN and read the string of letters as a command-line argument.

Test cases

$ for w in mhdexaspo iesretmng cmilensua floiufhyp frtuasmjg
> do cjam countdown.cjam $w < dictionary.txt
> echo
> done
hexapods mopheads
regiments
calumnies masculine
huffily puffily
frusta gamuts grafts jumars jurats

How it works

La        " Push T := [ '' ].                                                         ";
eas       " Push the command-line argument (R) as a string.                           ";
$W%       " Sort its letters, then reverse.                                           ";
{1$f++}/  " Iterate over the letters; prepend them to copies of the strings in T.     ";
:A;       " Save in A and discard. A contains all sorted substrings of R.             ";
qN/       " Read from STDIN and split at linefeeds.                                   ";
{$aA&},   " Filter; keep dictionary words D such that {sort(D)} ∩ A ≠ ∅.              ";
{,~}$     " Sort by negated word length.                                              ";
5<        " Keep only the first five words.                                           ";
_0=,:L;   " Save the length of the first in L.                                        ";
{,L=},    " Filter; keep dictionary words D such that len(D) = L.                     ";
 S*       " Separate by spaces.                                                       ";
\$\endgroup\$
2
\$\begingroup\$

Python 3, 171 bytes

This requires the dictionary to be stored in a file named w with each word separated by spaces.

Thanks to @wjandrea

s=input()
z=lambda s,f:all(f>{c}and not f.remove(c)for c in s)
l=[i for i in open('w').read().split()if z(i,set(s))]
print([x for x in l if len(x)==max(len(x)for x in l)])

Examples

gbahrcswn # Input
['branch', 'whangs'] # Output

andapandamandarandaonsdf
['fandoms', 'pardons']
\$\endgroup\$
  • 1
    \$\begingroup\$ Split on whitespace (newlines) instead of commas and you can save three bytes. \$\endgroup\$ – wjandrea May 4 '17 at 4:58
  • \$\begingroup\$ @wjandrea Thanks! \$\endgroup\$ – Beta Decay May 4 '17 at 6:06
1
\$\begingroup\$

Python, 175

Instead of checking if each word in the dictionary is an anagram of the input, this program calculates all the anagrams of the input and looks for them in ths dictionary. If the dictionary is pre-sorted, this scales logarithmically, instead of linearly, with the size of the dictionary; it's probably also shorter :)

from itertools import*
s=raw_input()
n=9
J="".join
while n:
 W=[J(p)for c in combinations(s,n)for p in set(permutations(c))if J(p)+"\n"in open("d")];n-=1
 if W:print W[:5];n=0

Assumes the dictionary is in a newline-terminated file named d in the current directory.

Note that the golfed program is ridiculously slow since it re-reads d on every search. If you want to test it, add D=set(open("d")) at the beginning, and replace open("d") with D.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 165 bytes

I fear I may have gone down the wrong path with this one - it's pretty ugly! It works, but it's very resource intensive - I thought my machine might explode if I tried a combination of letters that only contained 6 (or fewer) letter words!

I was so focused on getting this to work that I didn't leave myself much time to golf it; any help would be appreciated. In particular, I'm trying to figure out why, when I pass the initial string of letters as a single element array, thus allowing me to remove the 2 splits and the join, it throws an error on y.replace()

Assumes the dictionary is already available in an array variable named d.

f=s=>(a=d.filter(w=>s.split`,`.some(n=>r(n)==r(w)),r=x=>[...x].sort()+"")).length?a.slice(0,5):s.length&&f(s.split`,`.map(y=>[...y].map(v=>y.replace(v,""))).join`,`)

Try It

As I said, this solution is resource intensive so the following Snippet uses a limited dictionary, with only the words necessary for the 2 test cases I've included. If you're brave enough to try the full dictionary and your own input, you can do so here.

d=["dapping","genipap","huffily","kepping","knapped","peaking","puffily"]
f=s=>(a=d.filter(w=>s.split`,`.some(n=>r(n)==r(w)),r=x=>[...x].sort()+"")).length?a.slice(0,5):s.length&&f(s.split`,`.map(y=>[...y].map(v=>y.replace(v,""))).join`,`)
console.log(f("floiufhyp"))
console.log(f("ingpepkad"))

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.