Spelling words from "Merry Christmas"

Frequency Letter
1A
1C
1E
1H
1I
2M
3R
2S
1T
1Y

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

Permanent URL for this post: http://blog.cleverly.com/permalinks/7.html