Word Cube

July 13, 2010

Our solution is a straight forward statement of the problem:

(define (wordcube puzzle)
  (let* ((ltrs (string->list puzzle))
         (must (string-ref puzzle 4))
         (sign (sort char<? ltrs)))
    (with-input-from-file "/usr/share/dict/words"
      (lambda ()
        (let loop ((word (read-line)) (words '()))
          (if (eof-object? word) (reverse words)
            (let ((ws (sort char<? (string->list word))))
              (if (and (< 3 (length ws))
                       (member must ws)
                       (subset? ws sign))
                  (loop (read-line) (cons word words))
                  (loop (read-line) words)))))))))

We “sign” each word by sorting its letters into ascending order. Member assures that the central letter is part of the solution, and subset? compares two signatures to ensure that the first is a subset of the second:

(define (subset? s1 s2)
  (let loop ((s1 s1) (s2 s2))
    (cond ((null? s1) #t) ((null? s2) #f)
          ((char<? (car s1) (car s2)) #f)
          ((char<? (car s2) (car s1))
            (loop s1 (cdr s2)))
          (else (loop (cdr s1) (cdr s2))))))

Here’s an example:

> (wordcube "ncbcioune")
("bonnie" "bunion" "coin" "concubine" "conic" "cubic" "ennui" "icon" "nice" "nine" "nuncio" "union")

We used read-line and sort from the Standard Prelude. You can see the entire program at http://programmingpraxis.codepad.org/E61ALT0i.

About these ads

Pages: 1 2

13 Responses to “Word Cube”

  1. [...] Praxis – Word Cube By Remco Niemeijer In today’s Programming Praxis exercise our task is to write a program to solve Word Cube puzzles, in which you [...]

  2. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2010/07/13/programming-praxis-word-cube/ for a version with comments):

    import Data.Char
    import Data.List
    
    solve :: String -> [String] -> [String]
    solve c = filter (\w -> length w > 3 && elem (c !! 4) w && null (w \\ c))
    
    wordcube :: String -> IO ()
    wordcube cube = mapM_ putStrLn . solve cube .
                    lines . map toLower =<< readFile "words.txt"
    
  3. karijes said

    Here is my attempt in clojure:

    http://pastebin.com/gVf0DZV9

  4. matías said

    A bit of python:

    def words_in_cube(cube):
    return filter(lambda word: 3 < len(word) < 10 and \
    cube[4] in word and
    all(word.count(x) <= cube.count(x) for x in word),
    (word.strip() for word in open('/usr/share/dict/words').xreadlines()))

  5. Gary Johnson said
    ;; My clojure solution.
    ;; The previous one forgets to compare the distribution
    ;; of characters between the words from the word list
    ;; and the characters from the word cube.
    
    (ns wordcube
      (:use [clojure.contrib.duck-streams :only (read-lines)]))
    
    (defn count-chars [chars] (apply merge-with + (for [char chars] {char 1})))
    
    (defn solve [chars words-file]
      (let [middle-char #{(get chars 4)}
            char-counts (count-chars chars)]
        (filter #(and (> (count %) 3)
                      (some middle-char %)
                      (every? (fn [[char reps]] (<= reps (char-counts char 0))) (count-chars %)))
                (read-lines words-file))))
    
    ;; Usage
    (solve "ncbcioune" "words.txt")
    
  6. Mac said

    Here’s a version in LUA:

    http://pastebin.com/vBeDvup9

    @matias: The python version misses the words with upper case characters.

  7. [...] is my first solution for a Programming Praxis assignment, the Word Cube [...]

  8. Jebb said

    I’d appreciate any well-versed criticism of the regex I used:

    def cubewords(word_cube):
        import re
        center = word_cube[4]
        f = open('/usr/share/dict/words', 'r')
        str = f.read()
        f.close()
        pattern1 = "(?mi)(?=^\w{4,}$)(?=^[" + word_cube + "]+$)^\w*" + center + "\w*$"
        return re.findall(pattern1, str)
    
  9. Gary Johnson said

    @Jebb

    The character set match ^[ncbcioune]+$ just validates that your dictionary word only consists of characters from the cube. However, like some of the other answers here, it doesn’t account for the distribution of these characters in the cube and the dictionary word. Therefore, your algorithm gives incorrect answers like “bobbin”, “innocence”, “niece”, and “onion”.

  10. [...] that finds all matching words for a given word cube. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments [...]

  11. Jebb said

    @ Gary: OK, looks like I’d completely misunderstood the assignment. I’m beginning to suspect regexes are not the right tool here…

  12. [...] in my recent set of Word Games from Programming Praxis, today we’re tasked with finding all words made from a grid of [...]

  13. JP said

    Here’s a version written in Racket that generalizes to any size grid (although the minimum length of 4 is hard-coded) and seems to work pretty well:
    Word Cubes

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 616 other followers

%d bloggers like this: