Simon Kröçer wrote:
> William James wrote:
> > Short:
> >
> > D=IO.read('dict').split($/).grep(/^.{#{$*[0].size}}$/)
> > def rate(new,old,goal,l)
> >   t=0; v=0; new.size.times{|i|t+=1 if new[i]!=old[i]
> >     v+=1 if new[i]==goal[i] }
> >   [ 1==t && nil==l.index(new), v ]
> > end
> > def m(a,b,l)
> >   l << a.dup
> >   if a==b then p l; exit; end
> >   D.inject([]){|w,x| y,v = rate(x,a,b,l)
> >     w << [v,x] if y ; w
> >   }.sort.reverse_each{|v,x| m(x,b,l) }
> > end
> > m($*[0], $*[1], [])
>
> Using Dominik's nice idea i boiled it down to:
> (the dictionary is the optional third parameter, no -d)
>
> -----------------------------------------------------------
> dict, len = Hash.new{|h,k|h[k] = []}, ARGV[0].size
> IO.foreach(ARGV[2] || 'words.txt') do |w| w.chomp!
>    if w.size != len then next else s = w.dup end
>    (0...w.size).each{|i|s[i]=?.; dict[s] << w; s[i]=w[i]}
> end
> t, known = {ARGV[1] => 0}, {}
> while !known.merge!(t).include?(ARGV[0])
>    t = t.keys.inject({}){|h, w|(0...w.size).each{|i|
>      s=w.dup; s[i]=?.; dict[s].each{|l|h[l] = w if !known[l]}};h}
>    warn 'no way!' or exit if t.empty?
> end
> puts w = ARGV[0]; puts w while (w = known[w]) != 0
> -----------------------------------------------------------
>
> It's still quite fast.

Yours is faster and produces shorter chains.  I shortened it a
tiny bit.

dict, len = Hash.new{|h,k|h[k] = []}, ARGV[0].size
IO.foreach(ARGV[2] || 'words.txt') do |w| w.chomp!
   next if w.size != len
   s = w.dup
   (0...w.size).each{|i|s[i]=?.; dict[s] << w; s=w.dup}
end
t, known = {ARGV[1], 0}, {}
while !known.merge!(t).key?(ARGV[0])
   t = t.keys.inject({}){|h, w|(0...w.size).each{|i|
     s=w.dup; s[i]=?.; dict[s].each{|l|h[l] = w if !known[l]}};h}
   warn 'no way!' or exit if t.empty?
end
puts w = ARGV[0]; puts w while (w = known[w]) != 0