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.

About these ads

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

    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
                    else:
                        break
                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.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;
    }
    }

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

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: