Spelling words from "Merry Christmas"

Meghan's second-grade class had a project yesterday to see who could come up with the most (hopefully real!) words using only the letters from the phrase Merry Christmas.

Last night, Meghan (who has taken to calling my PowerBook "Sofia" for some reason unbeknownst to me), wondered how many words Sofia would be able to make. So, I whipped up a quick Tcl program to find words that could be made up from just the letters m, e, r, y, c, h, i, s, t, & a,

Macintosh OS X (like most *nix systems) has various word lists available. I decided to use the list of words from Webster's Second International Dictionary found in /usr/share/dict/web2.

set fp [open /usr/share/dict/web2]

# The frequencies of letters in "Merry Christmas"
array set max {m 2 e 1 r 3 y 1 c 1 h 1 i 1 s 2 t 1 a 1}

# Each word in the Webster's word list is on a line of its own
while {[gets $fp line] != -1} {
    set word [string tolower [string trim $line]]

    # If it has letters not in Merry Christmas we can't spell it
    if {[regexp {[^merrychristmas]} $word]} then continue

    # Meghan says she's learned that every word must have at least one vowel
    if {![regexp {[eia]} $word]} then continue

    # And, the letter e alone, while probably in the dictionary, doesn't
    # meet her teachers definition of a "word"
    if {$word == "e"} then continue

    array set remaining [array get max]
    set abort_p 0
    foreach letter [split $word ""] {
        # Have we prematurely run out of letters to use?
        # first version had a continue here—to continue the while loop
        # but that'd give us buggy behavior since it would continue the foreach instead
        # (thanks to trev for noticing the problems that caused!)
        if {[incr remaining($letter) -1] == -1} then {
            set abort_p 1
            break
        }
    }
    unset remaining
    if {$abort_p} then continue

    # If we get this far then we know $word is spelled entirely with letters
    # from "Merry Christmas"!
    puts $word
}

Sofia found 1,300 words in 4 seconds. Meghan decided that it might be unfair if we printed the word list for her to take to school on Wednesday. In the end Meghan tied a boy named Spencer today for the most words: 137 total—more than 10% of what Sofia found—pretty awesome for 2nd-graders IMNSHO.

Merry Christmas!

— Michael A. Cleverly
Thursday, December 23, 2004 at 19:34
356 comments | Printer friendly version

My "bloginality" == INTP

As a weblogger, you might not be as concerned about popularity, but more with the ideas and theories that you strive to understand. Because routines aren't your strong point, you might be more likely to work on the concept of how to do a blog, but not be as excited to keep it up.

— Michael A. Cleverly
Thursday, December 30, 2004 at 19:38
255 comments | Printer friendly version