Ruby longest path

gistfile1.rb

class LongestChain
	attr_accessor :words
	attr_accessor :longest_paths

	def initialize(words)
		self.words = words
	end

	def calculate
		@words.each do |word|
			yield word
			make_paths(word)
		end
		self.longest_paths
	end

	def make_paths(next_word, path_so_far = [])
		path = [path_so_far, next_word].flatten
		
		candidates = self.starts_with[next_word[-1]].to_a - path

		if candidates.length == 0
			if self.longest_paths.nil? || path.length > self.longest_paths.first.length
				self.longest_paths = [path]
			elsif path.length == self.longest_paths.first.length
				self.longest_paths << path
			end
		else
			candidates.each { |word| make_paths(word, path) }
		end
	end

	def starts_with
		return @starts_with unless @starts_with.nil?

		@starts_with = {}
		@words.each do |word|
			@starts_with[word[0]] ||= []
			@starts_with[word[0]] << word
		end

		@starts_with
	end
end

#words = %w{ herb bird dish }
words = %w{ sausage blubber pencil cloud moon water computer school network hammer walking violently mediocre literature chair instance two window cords musical zebra xylophone penguin home dog final ink teacher fun website banana uncle softly mega ten awesome attatch blue internet bottle tight zone tomato prison hydro cleaning telivision send frog cup book zooming falling evily gamer lid juice moniter captain bonding loudly thudding guitar shaving hair soccer water racket table late media desktop flipper club flying smooth monster purple guardian bold hyperlink presentation world national comment element magic lion negation sand crust toast jam hunter forest foraging silently tawesomated joshing pong }

puts "#{words.count} words: #{words.join(' ')}"
puts

print "Calculating..."
chain = LongestChain.new(words)

start_time = Time.now
chain.calculate { print '.' }
elapsed = Time.now - start_time

puts "#{elapsed} seconds"
puts 
puts "#{chain.longest_paths.count} longest paths found"
puts "Example: #{chain.longest_paths.first.join(' ')}"