D
Daniel Sheppard
Bit slow in bringing my code to market.=20
My code uses the dijkstra shortest-path algorithym. I originally
implemented by just recursing the tree - it ran reasonably well, but
once I realised that dijkstra applied, I kicked that to the kerb - I
might figure out where I put it (if I kept it?) and post it later. The
Dijkstra algorithym is built as separate module.
The big thing that sped up the program was pre-calculating the list of
"related words" as each word is created, rather than recursing the
entire word list and repeatedly comparing words. Did lots of playing
around with adjusting other things to make it run faster, but everything
that made sense to do seemed to make the thing slower. I'll investigate
some of the counter-intuitive points and discuss seperately.
The script accepts three arguments - start, end and dictionary.
Dictionary can be wildcarded to include multiple files. The linking of
differently lengthed words is implemented - the linking words are
restricted to lie between the lengths of the two ends (I thought it
looked funny to go from duck to rubys via pub).
Running the sahara-cloudy test against the debian british-english
dictionary I managed to pull out a 27 word chain (not 47 as previously
posted):
daniels@daniels ~ $ time ruby dijkstra.rb sahara cloudy british-english
sahara samara tamara tamera tamers tapers papers payers payees paynes
paines paints faints flints clints clinks blinks blinds blonds bloods
floods floors flours flouts clouts clouds cloudy
real 0m22.638s
user 0m22.057s
sys 0m0.052s
Full Code:
---------------------------------------------------------
#
# requires the implementation of an each_neighbour method which must
yield the neighbours of an object, and optionally the 'cost' of the
link.
# it doesn't require the full object list - it builds the list as it
goes. Would probably be faster if it had the whole list, but I wanted to
keep the
# code generic
#
module Dijkstra
=09class Vertex
=09 attr_reader
bject
=09 attr_accessor :distance
=09 def initialize(object, distance=3Dnil)
=09 @object =3D object
=09 @distance =3D distance
=09 end
=09 def <=3D>(other)
=09 a,b =3D distance, other.distance
=09 return 0 unless a || b
=09 return -1 unless a
=09 return 1 unless b
=09 return a <=3D> b
=09 end
=09end
=09# returns a hash where the keys are all reachable nodes and the
values are the shortest distances to those nodes
=09# yields each node and the calculated distance hash as they are
calculated
=09def find_distances()
=09 known =3D Hash.new
=09 unknown =3D Hash.new { |h,k| h[k] =3D Vertex.new(k)}
=09 unknown[self] =3D Vertex.new(self, 0)
=09 a =3D b =3D weight =3D neighbour =3D min =3D nil
=09 until unknown.empty?
=09 min =3D unknown.values.min
=09 known[min.object] =3D min
=09 yield min, known
=09 min.object.each_neighbour do |neighbour, weight|
=09 weight =3D 1 unless weight
=09 unless known.has_key?(neighbour)
=09 nd =3D unknown[neighbour]
=09 nd.distance =3D [nd.distance,
min.distance+ weight].min
=09 end
=09 end
=09 unknown.delete(min.object)
=09 end
=09 return distances
=09end
=09# finds the shortest path from the current node to the specified
end_node
=09def shortest_path(end_node)
=09 find_distances() do |found_vertex, known_vertexes|
=09 if(found_vertex.object =3D=3D end_node)
=09 return
shortest_path_internal(found_vertex, known_vertexes)
=09 end
=09 end
=09 return nil
=09end
=09private
=09def shortest_path_internal(end_vertex, known_vertexes)
=09 path =3D [end_vertex]
=09 until path[0].object =3D=3D self
=09 closest =3D min_distance =3D nil
=09 path[0].object.each_neighbour do |neighbour,
weight|
=09 weight ||=3D 1
=09 if known_vertexes[neighbour]
=09 vertex =3D
known_vertexes[neighbour]
=09 distance =3D vertex.distance +
weight
=09 if min_distance.nil? || distance
< min_distance
=09 closest =3D vertex
=09 min_distance =3D distance
=09 end
=09 end
=09 end
=09 path =3D [closest] + path
=09 end
=09 return path.collect {|x| x.object }
=09end
end
class Word
=09include Dijkstra
=09@@similar =3D Hash.new {|h,k| h[k] =3D Array.new}
=09def initialize(string)
=09 @string =3D Word.normalize(string)
=09 @similar_keys =3D []
=09 @string.length.times do |i|
=09 @similar_keys =3D String.new(@string)
=09 @similar_keys =3D "."
=09 end
=09 #allow changing word lengths - for some reason this
makes it FASTER for the same-length scenario??
=09 @similar_keys << @string[0..-2] if @string.length > 1
=09 @similar_keys << @string
=09 @similar_keys << @string + "."
=09 # ---
=09 @similar_keys.each do |key|=20
=09 words =3D @@similar[key]
=09 words << self
=09 end
=09end=09
=09def each_neighbour(&block)
=09 @nieghbours =3D @similar_keys.each do |key|
=09 @@similar[key].each {|word| yield word }
=09 end
=09end
=09def Word.read_words(word_file, size_range=3Dnil)
=09 Dir[word_file].each do |filename|
=09 warn "reading #{filename}" if $DEBUG
=09 File.open(filename) do |f|
=09 f.each do |x|
=09 x =3D normalize(x)
=09 Word.new(x) if size_range.nil?
|| size_range.include?(x.size)
=09 end
=09 end=09
=09 end
=09end
=09def <=3D>(other)
=09 @string <=3D> other.to_s
=09end
=09def to_s
=09 @string
=09end
=09private
=09def Word.normalize(string)
=09 string =3D string.downcase
=09 string.strip!
=09 string.gsub!(/[^a-z]/,"")
=09 string
=09end
end
if $0 =3D=3D __FILE__
=09start_word =3D ARGV[0] || "duck"
=09end_word =3D ARGV[1] || "ruby"
=09dictionary =3D ARGV[2] || "scowl/final/english-words.[0-3]*"
=09Word.read_words(dictionary, Range.new(*[start_word.length,
end_word.length].sort))=09
=09start_node =3D Word.new(start_word)
=09end_node =3D Word.new(end_word)
=09shortest_path =3D start_node.shortest_path(end_node)
=09puts shortest_path
end
#########################################################################=
############
This email has been scanned by MailMarshal, an email content filter.
#########################################################################=
############
My code uses the dijkstra shortest-path algorithym. I originally
implemented by just recursing the tree - it ran reasonably well, but
once I realised that dijkstra applied, I kicked that to the kerb - I
might figure out where I put it (if I kept it?) and post it later. The
Dijkstra algorithym is built as separate module.
The big thing that sped up the program was pre-calculating the list of
"related words" as each word is created, rather than recursing the
entire word list and repeatedly comparing words. Did lots of playing
around with adjusting other things to make it run faster, but everything
that made sense to do seemed to make the thing slower. I'll investigate
some of the counter-intuitive points and discuss seperately.
The script accepts three arguments - start, end and dictionary.
Dictionary can be wildcarded to include multiple files. The linking of
differently lengthed words is implemented - the linking words are
restricted to lie between the lengths of the two ends (I thought it
looked funny to go from duck to rubys via pub).
Running the sahara-cloudy test against the debian british-english
dictionary I managed to pull out a 27 word chain (not 47 as previously
posted):
daniels@daniels ~ $ time ruby dijkstra.rb sahara cloudy british-english
sahara samara tamara tamera tamers tapers papers payers payees paynes
paines paints faints flints clints clinks blinks blinds blonds bloods
floods floors flours flouts clouts clouds cloudy
real 0m22.638s
user 0m22.057s
sys 0m0.052s
Full Code:
---------------------------------------------------------
#
# requires the implementation of an each_neighbour method which must
yield the neighbours of an object, and optionally the 'cost' of the
link.
# it doesn't require the full object list - it builds the list as it
goes. Would probably be faster if it had the whole list, but I wanted to
keep the
# code generic
#
module Dijkstra
=09class Vertex
=09 attr_reader
bject=09 attr_accessor :distance
=09 def initialize(object, distance=3Dnil)
=09 @object =3D object
=09 @distance =3D distance
=09 end
=09 def <=3D>(other)
=09 a,b =3D distance, other.distance
=09 return 0 unless a || b
=09 return -1 unless a
=09 return 1 unless b
=09 return a <=3D> b
=09 end
=09end
=09# returns a hash where the keys are all reachable nodes and the
values are the shortest distances to those nodes
=09# yields each node and the calculated distance hash as they are
calculated
=09def find_distances()
=09 known =3D Hash.new
=09 unknown =3D Hash.new { |h,k| h[k] =3D Vertex.new(k)}
=09 unknown[self] =3D Vertex.new(self, 0)
=09 a =3D b =3D weight =3D neighbour =3D min =3D nil
=09 until unknown.empty?
=09 min =3D unknown.values.min
=09 known[min.object] =3D min
=09 yield min, known
=09 min.object.each_neighbour do |neighbour, weight|
=09 weight =3D 1 unless weight
=09 unless known.has_key?(neighbour)
=09 nd =3D unknown[neighbour]
=09 nd.distance =3D [nd.distance,
min.distance+ weight].min
=09 end
=09 end
=09 unknown.delete(min.object)
=09 end
=09 return distances
=09end
=09# finds the shortest path from the current node to the specified
end_node
=09def shortest_path(end_node)
=09 find_distances() do |found_vertex, known_vertexes|
=09 if(found_vertex.object =3D=3D end_node)
=09 return
shortest_path_internal(found_vertex, known_vertexes)
=09 end
=09 end
=09 return nil
=09end
=09private
=09def shortest_path_internal(end_vertex, known_vertexes)
=09 path =3D [end_vertex]
=09 until path[0].object =3D=3D self
=09 closest =3D min_distance =3D nil
=09 path[0].object.each_neighbour do |neighbour,
weight|
=09 weight ||=3D 1
=09 if known_vertexes[neighbour]
=09 vertex =3D
known_vertexes[neighbour]
=09 distance =3D vertex.distance +
weight
=09 if min_distance.nil? || distance
< min_distance
=09 closest =3D vertex
=09 min_distance =3D distance
=09 end
=09 end
=09 end
=09 path =3D [closest] + path
=09 end
=09 return path.collect {|x| x.object }
=09end
end
class Word
=09include Dijkstra
=09@@similar =3D Hash.new {|h,k| h[k] =3D Array.new}
=09def initialize(string)
=09 @string =3D Word.normalize(string)
=09 @similar_keys =3D []
=09 @string.length.times do |i|
=09 @similar_keys =3D String.new(@string)
=09 @similar_keys =3D "."
=09 end
=09 #allow changing word lengths - for some reason this
makes it FASTER for the same-length scenario??
=09 @similar_keys << @string[0..-2] if @string.length > 1
=09 @similar_keys << @string
=09 @similar_keys << @string + "."
=09 # ---
=09 @similar_keys.each do |key|=20
=09 words =3D @@similar[key]
=09 words << self
=09 end
=09end=09
=09def each_neighbour(&block)
=09 @nieghbours =3D @similar_keys.each do |key|
=09 @@similar[key].each {|word| yield word }
=09 end
=09end
=09def Word.read_words(word_file, size_range=3Dnil)
=09 Dir[word_file].each do |filename|
=09 warn "reading #{filename}" if $DEBUG
=09 File.open(filename) do |f|
=09 f.each do |x|
=09 x =3D normalize(x)
=09 Word.new(x) if size_range.nil?
|| size_range.include?(x.size)
=09 end
=09 end=09
=09 end
=09end
=09def <=3D>(other)
=09 @string <=3D> other.to_s
=09end
=09def to_s
=09 @string
=09end
=09private
=09def Word.normalize(string)
=09 string =3D string.downcase
=09 string.strip!
=09 string.gsub!(/[^a-z]/,"")
=09 string
=09end
end
if $0 =3D=3D __FILE__
=09start_word =3D ARGV[0] || "duck"
=09end_word =3D ARGV[1] || "ruby"
=09dictionary =3D ARGV[2] || "scowl/final/english-words.[0-3]*"
=09Word.read_words(dictionary, Range.new(*[start_word.length,
end_word.length].sort))=09
=09start_node =3D Word.new(start_word)
=09end_node =3D Word.new(end_word)
=09shortest_path =3D start_node.shortest_path(end_node)
=09puts shortest_path
end
#########################################################################=
############
This email has been scanned by MailMarshal, an email content filter.
#########################################################################=
############