Here is my solution.
It uses breadth first search (unidirectional) and is quite fast.
I use a trick to find all possible steps fast: While reading the words I
store them in a hash of arrays, e.g. when adding the word "dog", I
register "dog" as step for "\0og", "d\0g" and "do\0", later while look for
a step for "dot" I will use all words registered for "\0ot", "d\0t" or
"do\0". So reading the dictionary takes some time (and memory), but
afterwards finding the shortest chains is really fast. I also use symbols
instead of strings in some places for faster hash-lookup.
Of course I have also implemented my extra bonus challenge, to find a
longest shortest chain and Simon's suggestion to allow words with
different length.
Some examples:
$ time ruby word_chain.rb duck ruby
duck
luck
luce
lube
rube
ruby
real 0m1.414s
user 0m1.326s
sys 0m0.028s
$ time ruby word_chain.rb ape human
ape
are
arm
aum
hum
huma
human
real 0m2.604s
user 0m2.484s
sys 0m0.052s
$ time ruby word_chain.rb computer a
computer
compute
compote
compose
compos
compo
campo
camp
cam
aam
aa
a
real 0m12.550s
user 0m11.890s
sys 0m0.232s
The examples with words of different length take longer because much more
words from the dictionary have to be added to the hash.
$ time ruby longest_shortest.rb 3
edh
edo
ado
aho
pho
phi
poi
poa
pya
mya
real 0m4.840s
user 0m4.615s
sys 0m0.055s
$ time ruby longest_shortest.rb 6
zounds
wounds
woundy
[49 lines]
pantry
paltry
peltry
real 1m12.614s
user 1m10.113s
sys 0m0.655s
$ time ruby longest_shortest.rb 9
unpausing
unpassing
unpasting
unwasting
unwaiting
unwailing
unfailing
unfalling
unfilling
untilling
untelling
unselling
unsealing
unhealing
unhearing
unwearing
unweaving
unreaving
unreeving
unreeling
unfeeling
unfeeding
unheeding
real 0m9.252s
user 0m8.836s
sys 0m0.158s
$ time ruby longest_shortest.rb 12
modification
codification
conification
sonification
sinification
vinification
vilification
bilification
real 0m7.492s
user 0m7.127s
sys 0m0.138s
Dominik
The code:
# word_chain.rb
####################
DEFAULT_DICTIONARY = "/usr/share/dict/words"
# Data structure that efficiently stores words from a dictionary in a way,
that
# it is easy to find all words that differ from a given word only at one
# letter (words that could be the next step in a word chain).
# Example: when adding the word "dog", add_word will register "dog" as
step for
# "\0og", "d\0g" and "do\0", later each_possible_step("cat") will yield
all words
# registered for "\0at", "c\0t" or "ca\0".
class WordSteps
def initialize
@steps = Hash.new { |h, k| h[k] = [] }
@words = {}
end
# yields all words (as strings) that were added with add_word
def each_word(&block)
@words.each_key(&block)
end
# add all steps for word (a string) to the steps
def add_word(word)
sym = word.to_sym
wdup = word.dup
for i in 0...word.length
wdup[i] = 0
@steps[wdup] << sym
wdup[i] = word[i]
end
@words[word] = sym # for allow_shorter and each_word
end
# yields each possible next step for word (a string) as symbol, some
# possible steps might be yielded multiple times
# if allow_shorter is true, word[0..-2].to_sym will also be yielded if
# available
# if allow_longer is true, all words that match /#{word}./ will be
yielded
def each_possible_step(word, allow_shorter = false, allow_longer =
false)
wdup = word.dup
for i in 0...word.length
wdup[i] = 0
if @steps.has_key?(wdup)
@steps[wdup].each { |step| yield step }
end
wdup[i] = word[i]
end
if allow_shorter && @words.has_key?(tmp = word[0..-2])
yield @words[tmp]
end
if allow_longer && @steps.has_key?(tmp = word + "\0")
@steps[tmp].each { |step| yield step }
end
end
# tries to find a word chain between word1 and word2 (strings) using
all
# available steps
# returns the chain as array of symbols or nil, if no chain is found
# shorter/longer determines if shorter or longer words are allowed in
the
# chain
def build_word_chain(word1, word2, shorter = false, longer = false)
# build chain with simple breadth first search
current = [word1.to_sym]
pre = { current[0] => nil } # will contain the predecessors
target = word2.to_sym
catch(:done) do
until current.empty?
next_step = []
current.each do |csym|
each_possible_step(csym.to_s, shorter, longer) do
|ssym|
# have we seen this word before?
unless pre.has_key? ssym
pre[ssym] = csym
throw(:done) if ssym == target
next_step << ssym
end
end
end
current = next_step
end
return nil # no chain found
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
chain.reverse
end
# builds and returns a WordSteps instance "containing" all words with
# length in length_range from the file file_name
def self.load_from_file(file_name, length_range)
word_steps = new
IO.foreach(file_name) do |line|
# only load words with correct length
if length_range === (word = line.strip).length
word_steps.add_word(word.downcase)
end
end
word_steps
end
end
if $0 == __FILE__
dictionary = DEFAULT_DICTIONARY
# parse arguments
if ARGV[0] == "-d"
ARGV.shift
dictionary = ARGV.shift
end
unless ARGV.size == 2
puts "usage: #$0 [-d path/to/dictionary] word1 word2"
exit 1
end
word1, word2 = ARGV[0].strip.downcase, ARGV[1].strip.downcase
shorter = word1.length > word2.length
longer = word1.length < word2.length
length_range = if longer
word1.length..word2.length
else
word2.length..word1.length
end
# read dictionary
warn "Loading dictionary..." if $DEBUG
word_steps = WordSteps.load_from_file(dictionary, length_range)
word_steps.add_word(word2) # if it is not in dictionary
# build chain
warn "Building chain..." if $DEBUG
chain = word_steps.build_word_chain(word1, word2, shorter, longer)
# print result
puts chain || "No chain found!"
end
# longest_shortest.rb
####################
require "word_chain"
class WordSteps
# builds a longest shortest chain starting with word and returns it as
# array of symbols
# if the found chain is shorter than old_max, then it is possible to
# determine other words, whose longest shortest chain will also be not
# longer than old_max, those words will be added to not_longer, that
way
# the caller can avoid searching a longest chain for them
def longest_word_chain(word, not_longer = {}, old_max = 0)
# build chain with simple breadth first search until no more steps
are
# possible, one of the last steps is then a longest shortest chain
current = [word.to_sym]
pre = { current[0] => nil } # will contain the predecessors
target = nil
iterations = []
loop do
next_step = []
iterations << current
current.each do |csym|
each_possible_step(csym.to_s) do |ssym|
unless pre.has_key? ssym
pre[ssym] = csym
next_step << ssym
end
end
end
if next_step.empty?
target = current[0]
break
else
current = next_step
end
end
# build the chain (in reverse order)
chain = [target]
chain << target while target = pre[target]
# add words to not_longer if possible (see above)
if chain.size < old_max
(0...([old_max+1-chain.size, iterations.size].min)).each do |i|
iterations[i].each { |w| not_longer[w] = true }
end
end
chain.reverse
end
end
if $0 == __FILE__
dictionary = DEFAULT_DICTIONARY
# parse arguments
if ARGV[0] == "-d"
ARGV.shift
dictionary = ARGV.shift
end
word_length = [ARGV.shift.to_i, 1].max
# read dictionary
warn "Loading dictionary..." if $DEBUG
word_steps = WordSteps.load_from_file(dictionary, word_length)
# search chain
warn "Searching longest chain..." if $DEBUG
max = 0
chain = nil
not_longer = {}
word_steps.each_word { |w|
next if not_longer[w.to_sym]
cur = word_steps.longest_word_chain(w, not_longer, max)
if cur.size > max
chain = cur
max = cur.size
warn chain.inspect if $DEBUG
end
}
# print result
puts chain || "No chain found!"
end