[SOLUTION] Word Chains (#44)

(David Tran) #1

Here are my solutions. They are very slow ...
Not elegant at all, but at least they can find the solution. :slight_smile:

(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 != end_word.size

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

dictionary = 'words.txt'
if d_index = ARGV.index('-d')
聽聽ARGV.delete_at(d_index)
聽聽dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = 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 = []
File.open(dictionary) { |f|
聽聽while word = f.gets
聽聽聽聽word.chomp!
聽聽聽聽words << word if word.size == start_word.size
聽聽end
}

puts "Building chain..."
result = 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 != end_word.size
聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽聽
聽聽return [strat_word, end_word] if start_word == end_word
聽聽return nil unless dictionary.delete(start_word)
聽聽return nil unless dictionary.delete(end_word)
聽聽word_length = start_word.length

聽聽start_paths = [[start_word]]
聽聽end_paths = [[end_word]]
聽聽paths = start_paths
聽聽last_new_words = [end_word]
聽聽loop do
聽聽聽聽new_paths = []
聽聽聽聽new_words = []
聽聽聽聽paths.each do |path|
聽聽聽聽聽聽word = path.last
聽聽聽聽聽聽word_length.times do |i|
聽聽聽聽聽聽聽聽('a'..'z').each do |c|
聽聽聽聽聽聽聽聽聽聽new_word = word.dup
聽聽聽聽聽聽聽聽聽聽new_word[i] = c
聽聽聽聽聽聽聽聽聽聽if index = last_new_words.index(new_word)
聽聽聽聽聽聽聽聽聽聽聽聽if paths == 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 == start_paths
聽聽聽聽聽聽start_paths = new_paths
聽聽聽聽聽聽paths = end_paths
聽聽聽聽else
聽聽聽聽聽聽end_paths = new_paths
聽聽聽聽聽聽paths = start_paths
聽聽聽聽end
聽聽聽聽last_new_words = new_words
聽聽end
end

dictionary = 'words.txt'
if d_index = ARGV.index('-d')
聽聽ARGV.delete_at(d_index)
聽聽dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = 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 = []
File.open(dictionary) { |f|
聽聽while word = f.gets
聽聽聽聽word.chomp!
聽聽聽聽words << word if word.size == start_word.size
聽聽end
}

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

(David Tran) #2

It feels really bad when you see your solution fail on [SUMMARY] Word Chains
(#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,
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
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 != end_word.size

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

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

dictionary = 'words.txt'
if d_index = ARGV.index('-d')
ARGV.delete_at(d_index)
dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = 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 = []
File.open(dictionary) { |f|
while word = f.gets
word.chomp!
words << word.downcase if word.size == start_word.size
end
}

puts "Building chain..."
result = 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 != end_word.size

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

start_paths = [[start_word]]
end_paths = [[end_word]]
paths = start_paths
last_new_words = [end_word]
loop do
new_paths = []
new_words = []
paths.each do |path|
word = path.last
word_length.times do |i|
('a'..'z').each do |c|
new_word = word.dup
new_word[i] = c
if index = last_new_words.index(new_word)
if paths == 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 == start_paths
start_paths = new_paths
paths = end_paths
else
end_paths = new_paths
paths = start_paths
end
last_new_words = new_words
end
end

dictionary = 'words.txt'
if d_index = ARGV.index('-d')
ARGV.delete_at(d_index)
dictionary = ARGV.delete_at(d_index)
end
start_word = ARGV[0]
end_word = 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 = []
File.open(dictionary) { |f|
while word = f.gets
word.chomp!
words << word.downcase if word.size == start_word.size
end
}

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

(James Edward Gray II) #3

That's a great point. Thanks for bringing it up. It's easy to forget the call to downcase() when comparing words, but it's probably a good idea most of the time.

James Edward Gray II

路路路

On Sep 1, 2005, at 9:33 AM, David Tran wrote:

All words on the zip file are lower case. (except acronym).
And my programs work find for these dictionaries.

(Simon Kr枚ger) #4

David Tran wrote:

It feels really bad when you see your solution fail on [SUMMARY] Word Chains (#44).

Yep!

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,

dito

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.

Hmmm!

All words on the zip file are lower case. (except acronym).
And my programs work find for these dictionaries.

Yes.

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

Ohoh...

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

grrrr... thanks for figuring it out, anyway.

cheers

Simon