Wednesday, September 15, 2010

\$100 Words

My eleven year old daughter came home with a homework problem. The task is to find \$100 words. A \$100 word is a word whose letters, when assigned values, sum to 100. Each one she finds is worth "\$100" in their little game at school. Okay cool! But the values are assigned like this:


  • a = 1

  • b = 3

  • ...
  • m = 25

  • n = 26

  • o = 24

  • ...
  • z = 2



This is not exactly the most intuitive way to number the alphabet, and it certainly makes it hard to evaluate a given word as the typical mapping we're used to (a=1, b=2...) doesn't help. I gave up after a few minutes and told her she should learn to program to solve the problem.

She wasn't too thrilled with that idea, but here's my simple Haskell solution:


import Char (isUpper)

values :: [(Char, Int)]
values = zip (interleave ['a'..'m'] ['z','y'..'n']) [1..26]
where
interleave :: [a] -> [a] -> [a]
interleave (x:xs) (y:ys) = x : y : interleave xs ys
interleave _ _ = []

charValue :: Char -> Int
charValue c = case lookup c values of
Nothing -> 0
Just v -> v

wordValue :: String -> Int
wordValue = foldl (\s c -> s + charValue c) 0

goodWord :: String -> Bool
goodWord word@(x:_) = (not $ isUpper x) && wordValue word == 100
goodWord [] = False

main :: IO ()
main = interact (unlines . filter goodWord . lines)


Just feed it a list of words, like the handy /etc/dictionaries-common/words and away it goes...


$ ./DollarWords < /etc/dictionaries-common/words
abductor's
abductors
abidings
...

$ ./DollarWords < /etc/dictionaries-common/words | wc -l
652



So, if I was to unleash this on her poor unsuspecting teachers, her team would rocket ahead with \$652,000! But I guess that wouldn't be fair since she didn't write the program...

I'd love to see other versions of solutions for this problem.

5 comments:

  1. I would write something, but it would cost you $652,000...

    ReplyDelete
  2. Great problem. Haskel seems to be the first programming language that I cannot somewhat understand at a quick scan.

    ReplyDelete
  3. Hi Michael,

    So, if you come at haskell from a typical programming mindset, yes, it's hard to read. But with a couple of tricks, it get's easier. I'll do up a post that explains the above code in detail for you.

    ReplyDelete
  4. hi daddy!
    cool program i wish i could use the program but i guess that would be unfair, although everyone has stopped trying and kinda has forgotten about it.... :( oh well..............

    ReplyDelete