Nine letter word riddle

It's not too common that I get forwards nowadays. With the advent of social news, all the stupid links have migrated there. But on occasion, I'll get one from the older crowd. This one was a riddle with a movie of the answer attached.

What common English word is 9 letters long, and each time you remove a letter from it, it still remains an English word... from 9 letters all the way down to a single remaining letter?

It was only one answer, however, which it gave as "startling". I ended up wondering if there were more than one, so I wanted to see how fast I could write something to give me the answer. It'd be good practice, since most web programming is design and architectural hard, rather than algorithms hard. Besides, it's been a while since I wrote a recursive function.

Embarrasingly, it took 2.5-3 hours. I thought I'd be able to knock it out in one. I had some problems first removing a single letter from a word. Ever since I came to Ruby, I hardly ever deal with indicies, so finding those methods took a bit of time. Then, the recursion is always a bit of a mind bender when you don't do it often.

I also spent some time looking up what were considered one letter words, but then found out that there's a whole dictionary of one letter words. So I only considered "i" and "a" as valid one letter words. I also threw out all contractions.

See if you can write shorter/faster/better code. It's certainly a better workout than fizzbuzz. Seeing how it took me a bit, and I didn't clean up the code, I set the bar pretty low to beat. There were other things that would optimize it. I didn't throw out shorter words to check in the dictionary if I already checked them in a longer word--ie. I just ran down the list of dictionary words. Try it out yourself, in whatever language. (This sounds like a good beginning problem to write in Arc.) Go ahead. I'll wait.


Got it?


Here's the list I came up with along with their chains. You'll notice that it's actually a tree that branches.

cleansers
[["cleanses", ["cleanse", ["cleans", ["clean", ["clan", ["can", ["an", ["a"]]]], ["lean", ["lea", ["la", ["a"]]]]], ["clans", ["clan", ["can", ["an", ["a"]]]], ["cans", ["can", ["an", ["a"]]]]], ["leans", ["lean", ["lea", ["la", ["a"]]]], ["leas", ["lea", ["la", ["a"]]]]]]]], ["cleanser", ["cleanse", ["cleans", ["clean", ["clan", ["can", ["an", ["a"]]]], ["lean", ["lea", ["la", ["a"]]]]], ["clans", ["clan", ["can", ["an", ["a"]]]], ["cans", ["can", ["an", ["a"]]]]], ["leans", ["lean", ["lea", ["la", ["a"]]]], ["leas", ["lea", ["la", ["a"]]]]]]]]]

discusses
[["discuses", ["discuss", ["discus", ["discs", ["disc", ["dis", ["is", ["i"]]]], ["diss", ["dis", ["is", ["i"]]]]]]]]]

drownings
[["drowning", ["downing", ["owning", ["owing", ["wing", ["win", ["in", ["i"]]]]]]]]]

paintings
[["painting", ["paining", ["pining", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

piercings
[["piercing", ["piecing", ["pieing", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

prickling
[["pickling", ["picking", ["piking", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]], ["pricking", ["picking", ["piking", ["piing", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

restarted
[["restated", ["restate", ["estate", ["state", ["sate", ["sat", ["at", ["a"]]], ["ate", ["at", ["a"]]]]]]]]]

scrapping
[["crapping", ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

sparkling
[["sparking", ["sparing", ["spring", ["sprig", ["prig", ["pig", ["pi", ["i"]]]]]]]]]

splatters
[["platters", ["platter", ["latter", ["later", ["late", ["ate", ["at", ["a"]]]]]]]], ["splatter", ["platter", ["latter", ["later", ["late", ["ate", ["at", ["a"]]]]]]]]]

splitting
[["slitting", ["sitting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]], ["spitting", ["spiting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]], ["sitting", ["siting", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

stampeded
[["stampede", ["stamped", ["tamped", ["tamed", ["tame", ["tam", ["am", ["a"]]]]]]]]]

stampedes
[["stampede", ["stamped", ["tamped", ["tamed", ["tame", ["tam", ["am", ["a"]]]]]]]]]

startling
[["starling", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]], ["starting", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]], ["stating", ["sating", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

starvings
[["starving", ["staring", ["string", ["sting", ["sing", ["sin", ["in", ["i"]]]], ["ting", ["tin", ["ti", ["i"]], ["in", ["i"]]]]]]]]]

strapping
[["trapping", ["tapping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]], ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

stringers
[["stingers", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]], ["singers", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]], ["singes", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]], ["sings", ["sing", ["sin", ["in", ["i"]]]], ["sins", ["sin", ["in", ["i"]]], ["sis", ["is", ["i"]]], ["ins", ["in", ["i"]], ["is", ["i"]]]]]]]], ["stringer", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]]]

stringier
[["stingier", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]], ["stringer", ["stinger", ["singer", ["singe", ["sing", ["sin", ["in", ["i"]]]], ["sine", ["sin", ["in", ["i"]]]]]]]]]

trampling
[["tramping", ["tamping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]], ["amping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

trappings
[["trapping", ["tapping", ["taping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]], ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]

whittlers
[["whittler", ["whitter", ["whiter", ["white", ["whit", ["wit", ["it", ["i"]]], ["hit", ["hi", ["i"]], ["it", ["i"]]]], ["wite", ["wit", ["it", ["i"]]]]]]]]]

wrappings
[["wrapping", ["rapping", ["raping", ["aping", ["ping", ["pin", ["pi", ["i"]], ["in", ["i"]]], ["pig", ["pi", ["i"]]]]]]]]]


And here's my code:

#!/usr/bin/ruby

class Array
  def one_less
    total = [self[1..-1]]
    self.each_with_index do |e, i|
      total << self.values_at(0..i, (i+2)..-1)
    end
    return total[0..-2]
  end
end

def sub_words(word)
  result = word.split("").one_less.map { |word_array| word_array.join }.uniq
  result == [""] ? [] : result
end

def find_sub_word_chain(word)
  return nil unless @@dict.include?(word)
  return [word] if word.length == 1 && @@dict.include?(word)
  valid_sub_words = sub_words(word).reject { |w| !@@dict.include?(w) }
  word_chain = valid_sub_words.map do |sub_word|
    chain = find_sub_word_chain(sub_word)
    if chain.nil?
      nil
    else
      if sub_word.length == 1
        chain
      else
        (chain << sub_word).reverse
      end
    end
  end.compact
  word_chain.empty? ? nil : word_chain
end

@@dict = {}
ARGV[0] ||= "/etc/dictionaries-common/words"
words = File.readlines(ARGV[0]).map { |w| w.chomp }
words.each do |word|
  if word.length == 1
    next unless ["a", "i"].include?(word)
  end
  @@dict[word] = word
end

words.reject { |e| e.length != 9 }.reject { |word| word =~ /'/ }.map do |word|
  chain = find_sub_word_chain(word)
  next if chain.nil?
  puts word
  puts chain.inspect
  puts
end