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)))))))

We used take and fold-right from the Standard Prelude. You can run the program at

Pages: 1 2

15 Responses to “NPR Sunday Puzzle”

  1. […] today’s Programming Praxis exercise, our goal is to find two words that consist of the letters A through F […]

  2. My Haskell solution (see 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"
  3. Jussi Piitulainen said

    Happy birthday.

    grep -E -x '.{8}' /usr/share/dict/british-english |
    grep a | grep b | grep c | grep d | grep e | grep f

  4. Mike said

    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)]
  5. jpverkamp said

    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)))

    I’ll admit to being a fan of Racket’s for family of macros. They certainly make things like this much easier.

  6. 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
                if reqs == '' and len(extratwo) == 2 and len(word) == 8:
                    yield word
  7. Rafa said

    argv = 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

  8. Here’s my solution in C# (Hopefully the link works this time!)

  9. Scott said

    import java.util.Arrays;
    import java.util.ArrayList;

    public class FindWord {
    public static void main(String[] args){

    private static void printCorrectWords(ArrayList words) {

    for(int i=0;i<words.size();i++){
    char[] sepChar = words.get(i).toCharArray();
    sepChar = removeDoubles(sepChar);


    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++)
    result[j++] = (char) (i+97);

    return result;

    private static ArrayList getEigthLetterWords() {
    ArrayList eigthLetterWords = new ArrayList();
    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)
    }catch (Exception e){}

    return eigthLetterWords;

  10. James said

    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+”

  11. gulden said

    perl -nle ‘print if /^\w{8}$/ and /a/ and /b/ and /c/ and /d/ and /e/ and /f/ ‘ /usr/share/dict/linux.words

  12. brooknovak said

    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)
    					int rem = 'f' - c;
    					if (rem >= 0 && rem <= 5) {
    						int newFlags = flags | (1 << rem);
    						if (newFlags == flags) 
    							flags = newFlags;
    					} else { 
    				if (other == 2 && flags == 63) {
    					found ++;
    					Console.WriteLine ("Found: " + word);
    					if (found == 2)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 695 other followers

%d bloggers like this: