NPR Sunday Puzzle
February 19, 2013
There is a trick: either or both of the two “other” letters can also be from the set A, B, C, D, E, and F. Thus, the eight letters of the words form a multi-set, not a set. Here’s the function that determines if a word contains the letters A, B, C, D, E and F in any order:
(define (abcdef? word)
(equal? (string->list "abcdef")
(take 6 (sort char<?
(fold-right set-cons (list)
(string->list word))))))
We represent sets as lists; set-cons is like cons, except that it only adds an element to the set if it is not already present in the set:
(define (set-cons x xs)
(if (member x xs) xs
(cons x xs)))
Given abcdef?, it is easy to run through a dictionary and test all the 8-letter words:
> (with-input-from-file "dictionary"
(lambda ()
(let loop ((word (read-line)))
(when (not (eof-object? word))
(when (= 8 (string-length word))
(when (abcdef? word)
(display word) (newline)))))))
boldface
feedback
We used take and fold-right from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/m7yajoBT.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to find two words that consist of the letters A through F […]
My Haskell solution (see http://bonsaicode.wordpress.com/2013/02/19/programming-praxis-npr-sunday-puzzle/ for a version with comments):
import Data.List npr :: String -> Bool npr s = length s == 8 && null ("abcdef" \\ s) main :: IO () main = mapM_ print . filter npr . lines =<< readFile "en_US.dic"[…] Question is from here: […]
My java solution here.
Happy birthday.
grep -E -x '.{8}' /usr/share/dict/british-english |
grep a | grep b | grep c | grep d | grep e | grep f
[…] Pages: 1 2 […]
Python solution:
abcdef = set('abcdef') with open("/12dicts/2of12.txt", "rt") as f: lines = (line.strip() for line in f) words = [w for w in lines if len(w) == 8 and abcdef.issubset(w)]Happy Birthday! Your efforts are most appreciated. :)
Here’s a quick Racket version: NPR Sunday Puzzle
; find all words containing _chars_ with _length_ characters (define (words-containing chars [length (length chars)]) (with-input-from-file DICTIONARY (lambda () (for/list ([word (in-lines)] #:when (and (= length (string-length word)) (andmap (lambda (c) (string-contains? word c)) chars))) word))))I’ll admit to being a fan of Racket’s
forfamily of macros. They certainly make things like this much easier.in python, not as pretty as Mike’s version
def npr_sunday(): with open("..\wordsEn.txt", "rt") as wordlist: for word in wordlist: word = word.strip() reqs = 'abcdef' extratwo = '' for ch in word: if ch in reqs: reqs = reqs.replace(ch, '') elif len(extratwo) < 2: extratwo = extratwo + ch else: break if reqs == '' and len(extratwo) == 2 and len(word) == 8: yield wordargv = sys.argv
fPtr = open(sys.argv[1], ‘r’)
content = map(lambda x: x.replace(‘\n’,”), fPtr.readlines())
content = filter(lambda x:len(x)==8, content)
for i in range(ord(‘a’),ord(‘g’)):
content = filter(lambda x:chr(i) in x, content)
print content
Here’s my solution in C# (Hopefully the link works this time!)
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.ArrayList;
public class FindWord {
public static void main(String[] args){
printCorrectWords(getEigthLetterWords());
}
private static void printCorrectWords(ArrayList words) {
for(int i=0;i<words.size();i++){
char[] sepChar = words.get(i).toCharArray();
Arrays.sort(sepChar);
sepChar = removeDoubles(sepChar);
if(sepChar[0]=='a')
if(sepChar[1]=='b')
if(sepChar[2]=='c')
if(sepChar[3]=='d')
if(sepChar[4]=='e')
if(sepChar[5]=='f')
System.out.println(words.get(i));
}
}
private static char[] removeDoubles(char[] sep) {
boolean[] map = new boolean[26];
char[] result = new char[20];
int j=0;
for(int i=0;i<sep.length;i++)
map[((int) sep[i]-97)] = true;
for(int i=0;i<25;i++)
if(map[i])
result[j++] = (char) (i+97);
return result;
}
private static ArrayList getEigthLetterWords() {
ArrayList eigthLetterWords = new ArrayList();
try{
FileInputStream fstream = new FileInputStream(“dictionary.txt”);
DataInputStream in = new DataInputStream(fstream);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String str;
while ((str = br.readLine()) != null)
if(str.length()==8)
eigthLetterWords.add(str);
in.close();
}catch (Exception e){}
return eigthLetterWords;
}
}
cat /usr/share/dict/american-english | grep -E “^.{8}$” | grep -E “a+” | grep -E “b+” | grep -E “c+” | grep -E “d+” | grep -E “e+” | grep -E “f+”
perl -nle ‘print if /^\w{8}$/ and /a/ and /b/ and /c/ and /d/ and /e/ and /f/ ‘ /usr/share/dict/linux.words
C# solution using bitwise logic. Since A-F is a contiguous, we can use simple arithmetic to quickly check whether a word has all the required letters + 2 others.
public static void FindWords(string dictPath) { if (dictPath == null) throw new ArgumentNullException ("dictPath"); int found = 0; using(var reader = new StreamReader(dictPath)) { string word; while ((word = reader.ReadLine()) != null) { if (word.Length == 8) { int flags = 0; int other = 0; foreach (char c in word.ToLower()) { if (other > 2) break; int rem = 'f' - c; if (rem >= 0 && rem <= 5) { int newFlags = flags | (1 << rem); if (newFlags == flags) other++; else flags = newFlags; } else { other++; } } if (other == 2 && flags == 63) { found ++; Console.WriteLine ("Found: " + word); if (found == 2) return; } } } } }