43 lines
1.2 KiB
Ruby
43 lines
1.2 KiB
Ruby
require "set"
|
|
|
|
Words = File.open("unixdict.txt").read.split("\n").
|
|
group_by { |w| w.length }.map { |k, v| [k, Set.new(v)] }.
|
|
to_h
|
|
|
|
def word_ladder(from, to)
|
|
raise "Length mismatch" unless from.length == to.length
|
|
sized_words = Words[from.length]
|
|
work_queue = [[from]]
|
|
used = Set.new [from]
|
|
while work_queue.length > 0
|
|
new_q = []
|
|
work_queue.each do |words|
|
|
last_word = words[-1]
|
|
new_tails = Enumerator.new do |enum|
|
|
("a".."z").each do |replacement_letter|
|
|
last_word.length.times do |i|
|
|
new_word = last_word.clone
|
|
new_word[i] = replacement_letter
|
|
next unless sized_words.include? new_word and
|
|
not used.include? new_word
|
|
enum.yield new_word
|
|
used.add new_word
|
|
return words + [new_word] if new_word == to
|
|
end
|
|
end
|
|
end
|
|
new_tails.each do |t|
|
|
new_q.push(words + [t])
|
|
end
|
|
end
|
|
work_queue = new_q
|
|
end
|
|
end
|
|
|
|
[%w<boy man>, %w<girl lady>, %w<john jane>, %w<child adult>].each do |from, to|
|
|
if ladder = word_ladder(from, to)
|
|
puts ladder.join " → "
|
|
else
|
|
puts "#{from} into #{to} cannot be done"
|
|
end
|
|
end
|