From: shane.emmons@...
Date: 2006-04-10T22:42:04+09:00
Subject: [SOLUTION] Markov Chain (#74)

--=_alternative 004B40AD8525714C_=
Content-Type: text/plain; charset="US-ASCII"

# Author: Shane Emmons
#
# Quiz 74: Markov Chains
#
# This is based off of the classic Mark V. Shaney program. The
# basic algorithm only looked at the previous two words. I have
# changed it, so that it can check the previous four, previous three,
# previous two, or the previous word(s) to find the next reasonable
# choice. I also added some smarter end of phrase checks along with
# the standard rubifying.
#
# I was thinking, but have not tried, what would happen if you
# sent source code through the algorithm? Obviously some things
# would need to be changed for "phrase_breaks", but I wonder if
# anything would actually sucessfully run.

class MarkovChain

    attr_reader :phrase_breaks, :phrases

    def initialize( book )
        @book = book
        @phrases = Array.new( 4 ).fill( Hash.new )
        @phrase_breaks = Array.new
    end

    def read( book = @book )
        prev = [ '', '', '', '' ]
        words = File.open( book ).read.split
        words.each do |word|
            word.gsub!( /"/, '' )
            unless prev[ 0 ].eql?( '' )
                @phrases.each_index do |i|
                    prev_words = prev[ 0 .. i ].join( ' ' )
                    @phrases[ i ][ prev_words ] = Array.new unless
                        @phrases[ i ].has_key?( prev_words )
                    @phrases[ i ][ prev_words ] << word.downcase
                    @phrase_breaks << prev_words if prev_words.match( 
/[.!?]$/ )
                end
            end
            prev.pop and prev.insert( 0, word )
        end
    end

    def get_chain( num_want = 5 )
        chain = Array.new
        num_made = 0
        prev = [ '', '', '', '' ]
        prevs = Array.new( 4 )
        prev.each_index { |i| prevs[ i ] = prev[ 0 .. i ].join( ' ' ) }
        while num_made < num_want do
            until @phrases[ 3 ].has_key?( prevs[ 3 ] ) or
                  @phrases[ 2 ].has_key?( prevs[ 2 ] ) or
                  @phrases[ 1 ].has_key?( prevs[ 1 ] ) or
                  @phrases[ 0 ].has_key?( prevs[ 0 ] )
                prev = @phrase_breaks[ rand( @phrase_breaks.length ) 
].split
                prev.each_index { |i| prevs[ i ] = prev[ 0 .. i ].join( ' 
' ) }
            end
            words = Array.new
            @phrases.each_index do |i|
                prev_words = prev[ 0 .. i ].join( ' ' )
                words = @phrases[ i ][ prev_words ] if
                    @phrases[ i ].has_key?( prev_words )
            end
            word = words[ rand( words.length ) ]
            chain << word
            prev.shift and prev.push( word )
            prev.each_index { |i| prevs[ i ] = prev[ 0 .. i ].join( ' ' ) 
}
            num_made += 1 if prev[ -1 ].match( /[.!?]$/ )
        end
        chain
    end
 
end

mChain = MarkovChain.new( ARGV[ 0 ] )
mChain.read
print mChain.get_chain.join( ' ' ), "\n"
--=_alternative 004B40AD8525714C_=--