[SOLUTION] Word Chains (#44)

David_Tran1 · 29 August 2005 19:55

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

(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_Tran1 · 1 September 2005 14:33

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 · 1 September 2005 14:42

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_Kroger · 1 September 2005 16:00

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

Topic		Replies	Views
[QUIZ] Word Chains (#44) ruby-talk	41	318	31 August 2005
[QUIZ] Word Chains (#65) ruby-talk	6	61	3 February 2006
[SOLUTION] Word Chains (#44) ruby-talk	0	80	30 August 2005
Review of code please ruby-talk	7	73	28 January 2007
[QUIZ] Solution #2 ruby-talk	0	67	3 January 2007

[SOLUTION] Word Chains (#44)

Related Topics