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], [])
Dominik Bathon wrote:
idol
idyl
odyl
odal
oral
orad
brad
bead
beak
beck
back
bach
each
etch
utch
utah
utas
upasAnd another challenge, explain all the words your program emits..
Yes, I also wondered what some of those mean, but they are all in /usr/share/dict/words on my system (Gentoo)...
who/what/where is utas? or utch? even 'orad' seems totaly foreign
to me - but than perhaps thats normal as i'm just a german guy.
So am I.
Back to your question, yes sounds more like a challenge (in terms
of acceptable runtime). I would like to suggest finding chains
between words of different lengths.like this:
refugees
refugee
refuges
refutes
reputes
reputed
deputed
debuted
debated
rebated
related
relayed
delayed
decayed
decoyed
decoded
decodes
decides
deciles
defiles
refiles
refile
refine
repine
rapine
raping
rating
bating
basing
basin
basis
basts
bests
beats
beams
seams
shams
shame
Good idea.
Dominik
On Sat, 27 Aug 2005 23:13:59 +0200, Simon Kröger <SimonKroeger@gmx.de> wrote:
I can redirect them separately. For example, I can throw the chain into a file, but still see the progress messages:
$ ruby -d word_chain.rb lead gold > chain.txt
Loading dictionary...
Building chain...
$ cat chain.txt
lead
load
goad
gold
Hope that makes sense.
James Edward Gray II
On Aug 28, 2005, at 11:03 AM, Gavin Kistner wrote:
On Aug 28, 2005, at 7:31 AM, James Edward Gray II wrote:
warn "Loading dictionary..." if $DEBUG
WordChain.load_words(dictionary_file, start)
warn "Building chain..." if $DEBUG
puts WordChain.new(start, finish)What's the benefit to using #warn rather than #puts here? stderr versus stdout?
I'm not sure, but there's a Ruby Quiz that gets you most of the way there:
http://www.rubyquiz.com/quiz40.html
James Edward Gray II
On Aug 28, 2005, at 11:37 AM, Levin Alexander wrote:
Is there some kind of priority queue in the stdlib or available as a gem?
There is nothing in the stdlib currently, but there is rbtree and a RCR to include it in the stdlib:
http://www.rcrchive.net/rcr/show/306
Dominik
On Sun, 28 Aug 2005 18:37:43 +0200, Levin Alexander <levin@grundeis.net> wrote:
James Edward Gray II <james@grayproductions.net> wrote:
My solution is attached or at <http://tinyurl.com/dpvot> (needs data:-url
support in your browser)I really liked how the interface turned out:
> puts WordChains.new(words).from("ruby").shortest_path_to("duck")
>
> WordChains.new(words).from("ruby").each { |path|
> puts path.join(", ")
> }Is there some kind of priority queue in the stdlib or available as a gem?
If you want to benchmark ruby scripts you could use 'benchmark'
<http://www.ruby-doc.org/core/classes/Benchmark.html>
-Levin
Alexandru Popescu <the.mindstorm.mailinglist@gmail.com> wrote:
Sorry to come in the middle of the solution postings but I was wondering if anybody can point me to an equivalent of linux 'time' for windows.
Alexandru Popescu schrieb:
#: Jannis Harder changed the world a bit at a time by saying on 8/28/2005 8:39 PM :#
Hi,
I implemented a bidirectional breadth-first search. I'm using regexps
to speed up dictionary actions.Extra features:
-v Debug output.
-s Single line output.
Morphing of more than two words.
Support for non alphabetic chars.Sorry to come in the middle of the solution postings but I was wondering if anybody can point me to an equivalent of linux 'time' for windows.
thanks in advance,
:alex |.::the_mindstorm::.|
You could use ruby's Time class to determine the duration.
Besides, time is mostly a built-in of the shell.
Kind regards.
After I posted my solution, I took a shower, scribbled a few diagrams on the foggy glass walls and figured out how to massively speed things up. I hence post my new solution. It's still a unidirectional depth-first search, but it keeps track of visitation depth on nodes, preventing it from revisiting words that were previously reached more quickly.
For long chains, it's a MASSIVE speed up. For short ones, it's "only" a 2x improvement.
Compare results to the above:
[Slim:~/Sites/Ruby] gavinkis% ruby wordchains-gk2.rb crate primp 20
Chain between 'crate' and 'primp', no longer than 20 links:
...
--> 15.59s (after loading dictionary)
[Slim:~/Sites/Ruby] gavinkis% ruby wordchains-gk2.rb crate primp 12
Chain between 'crate' and 'primp', no longer than 12 links:
...
--> 2.76s (after loading dictionary)
[Slim:~/Sites/Ruby] gavinkis% ruby wordchains-gk2.rb crate primp 10
Chain between 'crate' and 'primp', no longer than 10 links:
...
--> 2.54s (after loading dictionary)
[Slim:~/Sites/Ruby] gavinkis% ruby wordchains-gk2.rb crate primp 8
Chain between 'crate' and 'primp', no longer than 8 links:
...
--> 1.96s (after loading dictionary)
[Slim:~/Sites/Ruby] gavinkis% ruby wordchains-gk2.rb crate primp 6
Chain between 'crate' and 'primp', no longer than 6 links:
(no such chain exists)
--> 0.78s (after loading dictionary)
I've finally been able to discover the much-sought-after link between kittens and rabies! (My previous code was unable to find this chain after leaving it for about half an hour.)
[Sliver:~/Desktop/12dicts] gkistner$ ruby wordchain-gk2.rb kitten rabies 20
Searching in 8121 words with 6 letters
Chain between 'kitten' and 'rabies', no longer than 20 links:
kitten
bitten
batten
batted
tatted
totted
tooted
booted
boobed
bobbed
robbed
rubbed
rubber
rubier
rubies
rabies
--> 29.08s (after loading dictionary)
Now I actually feel like my code has a chance of competing with the 'big boys'. Yay!
James, could you run some speed comparisons of various solutions in your summary analysis?
#!/usr/local/bin/ruby
require 'set'
class String
LETTERS = ('a'..'z').to_a
# Finds and returns an array that links the current word to _dest_word_,
# where each link in the chain is a word that differs from the previous
# only by a single character.
On Aug 28, 2005, at 9:45 AM, Gavin Kistner wrote:
For example, using a pair of words that is particularly hard for my algorithm to find the chain for:
[Slim:~/Sites/Ruby] gavinkis% ruby -d wordchains.rb crate primp 12
Finding chain between crate and primp using ./12dicts-4/2of12inf.txt, going no deeper than 12
...
425.621661 seconds elapsed[Slim:~/Sites/Ruby] gavinkis% ruby -d wordchains.rb crate primp 10
Finding chain between crate and primp using ./12dicts-4/2of12inf.txt, going no deeper than 10
...
17.003073 seconds elapsed[Slim:~/Sites/Ruby] gavinkis% ruby -d wordchains.rb crate primp 8
Finding chain between crate and primp using ./12dicts-4/2of12inf.txt, going no deeper than 8
...
3.069903 seconds elapsed[Slim:~/Sites/Ruby] gavinkis% ruby -d wordchains.rb crate primp 6
Finding chain between crate and primp using ./12dicts-4/2of12inf.txt, going no deeper than 6
...
(no path found)
1.527844 seconds elapsed
#
# The _visitation_map_ parameter is a hash containing all legal words as
# keys, and that should be initialized with the values mapping to the
# deepest depth allowable.
def chain_to( dest_word, visitation_map, depth=1 )
return nil if depth > $max_length
# Find variations on myself which haven't been reached by a shorter path
# and update the visitation map at the same time
links = Set.new
0.upto( self.length-1 ){ |i|
old_char = self[ i ]
LETTERS.each{ |new_char|
if new_char != old_char
test_word = self.dup
test_word[ i ] = new_char
#Following returns nil if the word isn't in the dictionary
shortest_path = visitation_map[ test_word ]
if shortest_path && shortest_path > depth
#I've gotten to this word faster than anyone else
#Put my score in the high score board, and use this word again
visitation_map[ test_word ] = depth
links << test_word
end
end
}
}
path_from_me = nil
if links.include?( dest_word )
#Sweet, I have a direct route!
path_from_me = [ self ]
else
links.each{ |test_word|
path = test_word.chain_to( dest_word, visitation_map, depth + 1 )
if path
total_length = depth + path.length + 1
#Only use the found path if it's shorter than one found already
if total_length <= $max_length
warn "Found a chain of length #{total_length}" if $DEBUG
path_from_me = path
$max_length = total_length
end
end
}
if path_from_me
path_from_me.unshift( self )
end
end
path_from_me
end
end
start_word = ARGV[0] || 'crave'
end_word = ARGV[1] || 'primp'
$max_length = Integer( ARGV[2] || start_word.length * 3 )
dict = ARGV[3] || '/usr/share/dict/words'
#dict = ARGV[3] || '2of12inf.txt'
desired_length = start_word.length
unless end_word.length == desired_length
msg = "Error: '#{start_word}' and '#{end_word}' are not the same length"
msg << "(#{start_word.length} vs. #{end_word.length})"
raise msg
end
# Load words of the right length
avail_words = {}
File.open( dict, 'r' ){ |f|
w = f.read.split(/[\r\n]+/)
# No capital words, or words ending with % (12dicts)
w.reject!{ |word| word.length != desired_length or /[^a-z]/ =~ word }
w.each{ |word| avail_words[ word ] = $max_length }
}
avail_words[ start_word ] = 1
puts "Searching in #{avail_words.length} words with #{desired_length} letters"
unless avail_words.include?( end_word )
raise "Error: '#{end_word}' is not included in #{dict}"
end
print "Chain between '#{start_word}' and '#{end_word}', "
puts "no longer than #{$max_length} links:"
start_time = Time.new
if path = start_word.chain_to( end_word, avail_words )
puts path.join( "\n" )
puts end_word
else
puts "(no such chain exists)"
end
end_time = Time.new
puts "--> %.2fs (after loading dictionary)\n " % [ end_time-start_time ]
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.
BTW:
Is there a nice way to construct a hash, like #map does?
like:
array = (1..10).map{|i| i}
hash = (1..10).map_to_hash{|i| i => i*2}
(i always use inject in a 'not so nice' way)
cheers
Simon
I tried to build it but it fails the unit tests
The check for "rb_block_proc" and the later warnings seems to suggest that there is something wrong with my system. Any hints?
Thank You,
Levin
$ ruby -v
ruby 1.8.3 (2005-06-23) [i486-linux]
$ ruby extconf.rb
checking for allocation framework... yes
checking for rb_obj_init_copy()... no
checking for rb_block_proc()... no
checking for rb_yield_values()... no
checking for rb_marshal_dump()... no
checking for rb_marshal_load()... no
checking for inline keyword... __inline
creating Makefile
$ make
gcc -fPIC -Wall -g -O2 -fPIC -std=c89 -pedantic -Wall -Wno-long-long -I. -I/usr/lib/ruby/1.8/i486-linux -I/usr/lib/ruby/1.8/i486-linux -I. -DNDEBUG -DHAVE_OBJECT_ALLOCATE -Dinline=__inline -c dict.c
gcc -fPIC -Wall -g -O2 -fPIC -std=c89 -pedantic -Wall -Wno-long-long -I. -I/usr/lib/ruby/1.8/i486-linux -I/usr/lib/ruby/1.8/i486-linux -I. -DNDEBUG -DHAVE_OBJECT_ALLOCATE -Dinline=__inline -c rbtree.c
rbtree.c:58: warning: static declaration for `rb_block_proc' follows non-static
rbtree.c:66: warning: static declaration for `rb_yield_values' follows non-static
rbtree.c:1486: warning: static declaration for `rb_marshal_dump' follows non-static
rbtree.c:1492: warning: static declaration for `rb_marshal_load' follows non-static
gcc -shared -L"/usr/lib" -o rbtree.so dict.o rbtree.o -lruby1.8 -lpthread -ldl -lcrypt -lm -lc
$ ruby -v test.rb
Loaded suite test
Started
......................test.rb:819: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
..................test.rb:121: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:126: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:57: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:59: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:139: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:154: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
........test.rb:179: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:185: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:201: warning: block supersedes default value argument
.test.rb:564: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
....test.rb:483: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
...test.rb:574: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
..test.rb:649: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:653: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.Ftest.rb:23: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:326: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.Ftest.rb:581: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:609: warning: RBTree#readjust() uses current comparison block, use RBTree#readjust(nil) to set default comparison block
test.rb:613: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.F.test.rb:623: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
test.rb:624: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
...test.rb:145: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.test.rb:310: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
...test.rb:468: warning: rb_f_lambda() is deprecated; use rb_block_proc() instead
.......
Finished in 0.1 seconds.
1) Failure:
test_merge(RBTreeTest) [test.rb:425]:
<#<RBTree: {["a", "A"]=>nil,
["b", "B"]=>nil,
["c", "C"]=>nil,
["d", "D"]=>nil,
["e", "E"]=>nil},
default=nil,
cmp_proc=nil>> expected but was
<#<RBTree: {["e", "E"]=>nil}, default=nil, cmp_proc=nil>>.
2) Failure:
test_pp(RBTreeTest) [test.rb:664]:
<"#<RBTree: {\"a\"=>\"A\", \"b\"=>\"B\"}, default=nil, cmp_proc=nil>\n"> expected but was
<"#<RBTree: {[\"a\", \"A\"]=>nil, [\"b\", \"B\"]=>nil}, default=nil, cmp_proc=nil>\n">.
3) Failure:
test_reject(RBTreeTest) [test.rb:382]:
<#<RBTree: {["c", "C"]=>nil, ["d", "D"]=>nil}, default=nil, cmp_proc=nil>> expected but was
<nil>.
84 tests, 283 assertions, 3 failures, 0 errors
Dominik Bathon <dbatml@gmx.de> wrote:
Is there some kind of priority queue in the stdlib or available as a gem?
There is nothing in the stdlib currently, but there is rbtree and a RCR to include it in the stdlib:
An interesting chain to stress-test your algorithms is "sahara" <-> "cloudy" (46 links)
(in my dictionary at least)
$ time ruby word_chains.rb sahara cloudy
sahara
samara
tamara
tamera
tamers
tapers
capers
caters
waters
wavers
savers
severs
levers
levees
levies
bevies
belies
belied
belted
bolted
boated
coated
crated
craned
cranes
cranks
cracks
crocks
croaks
creaks
creeks
creels
cruels
cruets
crusts
crests
chests
cheats
cleats
bleats
bloats
floats
flouts
clouts
clouds
cloudy
real 0m28.984s
user 0m9.243s
sys 0m0.755s
Gavin Kistner <gavin@refinery.com> wrote:
I've finally been able to discover the much-sought-after link between kittens and rabies! (My previous code was unable to find this chain after leaving it for about half an hour.)
Dominik Bathon wrote:
On Sun, 28 Aug 2005 18:37:43 +0200, Levin Alexander
...
Is there some kind of priority queue in the stdlib or available as a gem?
There is nothing in the stdlib currently, but there is rbtree and a RCR
to include it in the stdlib:
Here's one version using rbtree:
http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/133202
--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
Did you consider making it into an iterative deepening search instead?
That would get rid of the need to test with several search depths 
On 8/28/05, Gavin Kistner <gavin@refinery.com> wrote:
things up. I hence post my new solution. It's still a unidirectional
depth-first search, but it keeps track of visitation depth on nodes,
Just the other day I needed 'time' for windows, and wrote a 3 line
ruby script I called 'rtime' Really trivial stuff.
start_time = Time.now
system ARGV.join(" ")
$stderr.puts "#{Time.now - start_time} seconds"
Of course, it just gives you the real time it took, nothing about user
time, etc. The main point is how very easy it was.
Dan
On 8/28/05, Levin Alexander <levin@grundeis.net> wrote:
Alexandru Popescu <the.mindstorm.mailinglist@gmail.com> wrote:
> Sorry to come in the middle of the solution postings but I was wondering
> if anybody can point me to an equivalent of linux 'time' for windows.If you want to benchmark ruby scripts you could use 'benchmark'
<http://www.ruby-doc.org/core/classes/Benchmark.html>-Levin
I will try, yes.
James Edward Gray II
On Aug 28, 2005, at 4:34 PM, Gavin Kistner wrote:
Now I actually feel like my code has a chance of competing with the 'big boys'. Yay!
James, could you run some speed comparisons of various solutions in your summary analysis?
Simon Kröger 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
Levin Alexander wrote:
Dominik Bathon <dbatml@gmx.de> wrote:
Is there some kind of priority queue in the stdlib or available as a
gem?There is nothing in the stdlib currently, but there is rbtree and a
RCR to include it in the stdlib:I tried to build it but it fails the unit tests
The check for "rb_block_proc" and the later warnings seems to suggest
that there is something wrong with my system. Any hints?Thank You,
Levin$ ruby -v
ruby 1.8.3 (2005-06-23) [i486-linux]
$ ruby extconf.rb
checking for allocation framework... yes
checking for rb_obj_init_copy()... no
checking for rb_block_proc()... no
checking for rb_yield_values()... no
checking for rb_marshal_dump()... no
checking for rb_marshal_load()... no
checking for inline keyword... __inline
creating Makefile
Looks like your ruby headers or libs aren't where extconf.rb expects
them. Did you build ruby from source? It might help to look at
ruby -r rbconfig -e 'p Config::CONFIG'
and see if the paths listed there are where the ruby installed files
are. (Sorry to be so vague...)
--
vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407
An interesting chain to stress-test your algorithms is "sahara" <-> "cloudy" (46 links)
(in my dictionary at least)
Mine is missing many of the words in that chain. What dictionary is yours?
On Aug 28, 2005, at 4:01 PM, Levin Alexander wrote:
$ time ruby word_chains.rb sahara cloudy
sahara
samara
tamara
tamera
tamers
tapers
capers
caters
waters
wavers
savers
severs
levers
levees
levies
bevies
belies
belied
belted
bolted
boated
coated
crated
craned
cranes
cranks
cracks
crocks
croaks
creaks
creeks
creels
cruels
cruets
crusts
crests
chests
cheats
cleats
bleats
bloats
floats
flouts
clouts
clouds
cloudyreal 0m28.984s
user 0m9.243s
sys 0m0.755s
My last email seemed to disappear in the ether, so here it is again.
Hi, one very simple (and short .. and slow) solution. --will
require 'set'
#read in every word into a hash
def read_dictionary(filename, length)
words = IO.readlines(filename).collect{ |l| l.strip.downcase }.reject{ |word| word.length != length }
Set.new(words)
end
#computes all possible neighbours of a word
def get_neighbours(word)
allneigbours = Set.new
for i in 0...word.length
for c in 97..122
neighbour = word.dup
neighbour[i] = c
allneigbours.add(neighbour)
end
end
allneigbours
end
#performs the word chain search
def compute(a, b, dict)
raise "words are different lengths" if a.length != b.length
#setup
dictionary = read_dictionary(dict, a.length)
raise b+" not in dictionary" if !dictionary.include?(b)
queue = [ [a] ]
seen = Set.new([a])
#very simple breadth first search
while queue.length > 0
solution = queue.delete_at(0)
break if solution.last == b
#get neighbours
neighbours = get_neighbours(solution.last)
neighbours &= dictionary
neighbours -= seen
seen += neighbours
#add onto queue
neighbours.each_with_index { |obj, i|
queue.push( solution.dup.push(obj) )
}
end
raise "cannot create word chain" if solution.last != b
puts solution
end
#parse options very simply
dict = "/usr/share/dict/words"
a = ARGV.shift
if a == "-d"
dict = ARGV.shift
a = ARGV.shift
end
b = ARGV.shift
#do it
compute(a, b, dict)
William James wrote:
Simon Kröger wrote:
> William James wrote:
> > Short:
> >
[ clipped ]
>
> 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.
[ clipped ]
Shorter still:
dict = Hash.new{|h,k| h[k] = }
IO.foreach($*[2] || 'words.txt') do |w| w.chomp!
next if w.size != $*[0].size
w.size.times{|i| dict[w[0,i]+"."+w[i+1..-1]] << w}
end
t, known = {$*[1], 0}, {}
while !known.merge!(t).key?($*[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=={}
end
puts w = $*[0]; puts w while (w = known[w]) != 0