From: Matthew Moss <matthew.moss.coder@...>
Date: 2006-04-10T22:20:47+09:00
Subject: Re: [QUIZ] Markov Chains (#74)

Here is my own solution. I had hoped to do a bit more work on this,
but alas I do not expect to have time this week to do anymore, so here
it is, as-is.

It's a quick-n-dirty solution, storing hashes of hashes. The keys were
groups of X words at a time, X being the order.


require 'enumerator'

ORDER = 3

class Markov
   def initialize
      @graph = Hash.new { |h, k| h[k] = Hash.new(0) }
      @count = Hash.new(0)
   end

   def <<(group)
      source, sink = group[0...-1].join(' '), group[-1]
      @graph[source][sink] += 1
      @count[source] += 1
   end

   def [](group)
      return '' if group.empty?

      source = group.join(' ')
      return self[group[1..-1]] if @count[source].zero?

      x = rand(@count[source])
      @graph[source].each do |sink, freq|
         return sink if x < freq
         x -= freq
      end
   end
end

m = Markov.new

length = 0
number = 0

ARGV.each do |arg|
   puts "Reading: #{arg}"

   words  = [''] * ORDER
   words += File.open(arg).read.split(/\s+/).reject { |x| x.empty? }

   words.each_cons(ORDER+1) do |group|
      m << group
      length += 1
   end
   number += 1
end

text = []
group = [''] * ORDER
(length / number).times { text << group.push(m[group]).shift }

puts text.join(' ')