From: David Tran <email55555@...>
Date: 2005-09-01T23:33:39+09:00
Subject: Re: [SOLUTION] Word Chains (#44)

------=_Part_6770_14974132.1125585215447
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

It feels really bad when you see your solution fail on [SUMMARY] Word Chain=
s=20
(#44).
Especially I claim my programs will at least find the solution.
I did do unit test my solutions before post them.

No matter what, when they fail, I would like to know what happend.

And I found the reason for it.

In fact, I am in Windows Box not Unix Box,=20
so I do not have the words (dictionary file),
and I am using this link:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/153706
to get the 12dicts-4.0.zip for dictionary.
All words on the zip file are lower case. (except acronym).
And my programs work find for these dictionaries.

Now, I just go check the Sun solaris unix box about words file,
they are mixed upper and lower case words.

That is the reason why my program fail.
Simply add downcase method to force all words in lower case and my programs=
=20
will pass the test again.

(1) simple breadth-first
------------------------------ ------------------------------------------
def search( start_word, end_word, dictionary )
# check pre-condition
raise "invalid argument" if start_word.nil? ||
end_word.nil? ||
dictionary.nil? ||
start_word.size !=3D end_word.size

return [strat_word, end_word] if start_word =3D=3D end_word
return nil unless dictionary.delete(start_word)
return nil unless dictionary.delete(end_word)

paths =3D [[start_word]]
while !paths.empty?
new_paths =3D []
paths.each do |path|
word =3D path.last
word.size.times do |i|
('a'..'z').each do |c|
new_word =3D word.dup
new_word[i] =3D c
return (path << new_word) if new_word =3D=3D end_word
next if !dictionary.delete(new_word)
new_paths << (path.dup << new_word)
end
end
end
paths =3D new_paths
end
nil
end

dictionary =3D 'words.txt'
if d_index =3D ARGV.index('-d')
ARGV.delete_at(d_index)
dictionary =3D ARGV.delete_at(d_index)
end
start_word =3D ARGV[0]
end_word =3D ARGV[1]

if start_word.nil? || end_word.nil? || dictionary.nil?
puts "Usage: ruby #$0 [ -d dictionary ] start_word end_word"
exit
end

puts "Loading dictionary..."
words =3D []
File.open(dictionary) { |f|
while word =3D f.gets
word.chomp!
words << word.downcase if word.size =3D=3D start_word.size
end
}

puts "Building chain..."
result =3D search(start_word, end_word, words)
puts( result ? result : "No solution." )
------------------------------------------------------------------------


(2) simple bidirectional breadth-first
------------------------------------------------------------------------
def search( start_word, end_word, dictionary )
# check pre-condition
raise "invalid argument" if start_word.nil? ||
end_word.nil? ||
dictionary.nil? ||
start_word.size !=3D end_word.size

return [strat_word, end_word] if start_word =3D=3D end_word
return nil unless dictionary.delete(start_word)
return nil unless dictionary.delete(end_word)
word_length =3D start_word.length

start_paths =3D [[start_word]]
end_paths =3D [[end_word]]
paths =3D start_paths
last_new_words =3D [end_word]
loop do
new_paths =3D []
new_words =3D []
paths.each do |path|
word =3D path.last
word_length.times do |i|
('a'..'z').each do |c|
new_word =3D word.dup
new_word[i] =3D c
if index =3D last_new_words.index(new_word)
if paths =3D=3D start_paths
return path.push(*end_paths[index].reverse)
else
return start_paths[index].push(*path.reverse)
end
end
next unless dictionary.delete(new_word)
new_paths << (path.dup << new_word)
new_words << new_word
end
end
end

return nil if new_paths.empty?

if paths =3D=3D start_paths
start_paths =3D new_paths
paths =3D end_paths
else
end_paths =3D new_paths
paths =3D start_paths
end
last_new_words =3D new_words
end
end


dictionary =3D 'words.txt'
if d_index =3D ARGV.index('-d')
ARGV.delete_at(d_index)
dictionary =3D ARGV.delete_at(d_index)
end
start_word =3D ARGV[0]
end_word =3D ARGV[1]

if start_word.nil? || end_word.nil? || dictionary.nil?
puts "Usage: ruby #$0 [ -d dictionary ] start_word end_word"
exit
end

puts "Loading dictionary..."
words =3D []
File.open(dictionary) { |f|
while word =3D f.gets
word.chomp!
words << word.downcase if word.size =3D=3D start_word.size
end
}

puts "Building chain..."
result =3D search(start_word, end_word, words)
puts( result ? result : "No solution." )
------------------------------------------------------------------------

------=_Part_6770_14974132.1125585215447--