From: Brian Ardrey <brian.ardrey@...>
Date: 2006-04-10T11:35:44+09:00
Subject: Re: [QUIZ][SOLUTION] Markov Chains (#74)

------=_Part_32547_16008079.1144636541192
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Here is my first ruby quiz solution submission. Thanks for posting
this one, it provided a fun break from my school projects.

I tried to make the code as general as possible, with variable order
of both words and letters. It uses a hash of arrays for storage. I was
planning on unifying the MarkovWords and MarkovLetters classes into
one, but decided against it, mostly to keep them simpler. These
examples use an english translation of The Odyssey to derive the text.


  Usage...

[brian@spica] [~/rubyquiz]
$ ruby markov.rb -h
Usage: ruby markov.rb [options] <filename>
  -h, --help         show this usage message
  -o, --order        set markov chain order
  -s, --sentences    set number of sentences to print
  -w, --words        set number of words to print
  -l, --letters      use letters as the basic unit


  Print 5 sentences of order 2, using words as the base unit...

[brian@spica] [~/rubyquiz]
$ ruby markov.rb -s 5 -o 2 ../etext/dyssy10.txt
My men came out of your wits? If Apollo and the whole world, neither
rich nor poor, who is handsome and clean built, whereas I am so lost
in a beautiful golden ewer, and poured it over with a lie; 'Neptune,'
said I, 'of escaping Charybdis, and at the base of her maids brought
the heifer down with my tears during the darkness of death itself. A
poor unfortunate tramp has come to pass." And Penelope answered,
"Stranger, you must have gone off to bring the contest to an end."
Melanthius lit the fire for her, but she wishes to hear the enchanting
sweetness of their grey hair.


  Print 1 sentence of order 1, using words as the base unit...

[brian@spica] [~/rubyquiz]
$ ruby markov.rb -s 1 -o 1 ../etext/dyssy10.txt
Proserpine had got into a mission to be scandalised at last of them,
and lay a hard task, no more fond of wind blew a man talked and will
leave their sport known that stalks about his wife, and the store for
he stretched out their own house, which I shall be willing to the
house to you, Telemachus.


  Print 50 words of order 3, using letters as the base unit...

[brian@spica] [~/rubyquiz]
$ ruby markov.rb -w 50 -o 3 -l ../etext/dyssy10.txt
the of it into beautiful nose kill as did ther people the wood and him
all the meanthrountry stilltrese ffere peak the the the eleide oly
with blooked ent back the himself over s his hey glarge tood welcomind
where and mannot been spoke aloud valitterince one of his


  Print 50 words of order 2, using letters as the base unit, with text
  from The Aeneid (latin version)...

[brian@spica] [~/rubyquiz]
$ ruby markov.rb -w 50 -o 2 -l ../etext/anidl10.txt
quora desi aras ta acerummarmallenstos es mihinus vade imurbethinc
plia caum turnit que re et sum fuit ade re restaeteri invicaviam
ceuctitur hos aectalisubsillo parmeis suntereffunc meo que
clachilliaeque mul rut moropula sonitotuspiumque terrequebraherautras
nos ad la ciem atque part dubstra repononibus comet ad num undo cisque
retrangeneferat simas obla




[brian@spica] [~/rubyquiz]
$ cat markov.rb
#!/usr/bin/ruby

class MarkovWords

  def initialize(filename, order)
    @order =3D order
    @words =3D Hash.new
    @state =3D Array.new(@order)
    previous =3D Array.new(@order)
    File.foreach(filename) do |line|
      line.split(/\s+/).each do |word|
        unless previous.include?(nil)
          p =3D previous.join(' ')
          unless @words.has_key?(p)
            @words[p] =3D Array.new
          end
          @words[p] << word
        end
        previous.shift
        previous.push(word)
      end
    end
  end

  def print_words(n =3D 50)
    word =3D next_word(true)
    1.upto(n) do |i|
      print word, i =3D=3D n ? "\n" : " "
      word =3D next_word()
    end
    print "\n"
  end

  # sentences start with a capital or quoted capital and end with
  # punctuation or quoted punctuation
  def print_sentences(n =3D 5)
    sentences =3D 0
    word =3D next_word(true)
    while word !~ /^['"`]?[A-Z]/
      word =3D next_word()
    end
    begin
      print word
      if word =3D~ /[?!.]['"`]?$/
        sentences +=3D 1
        if sentences =3D=3D n
          print "\n"
        else
          print " "
        end
      else
        print " "
      end
      word =3D next_word()
    end until sentences =3D=3D n
  end

  def next_word(restart =3D false)
    if restart or @state.include?(nil)
      key =3D @words.keys[rand(@words.length)]
      @state =3D key.split(/\s+/)
    end
    key ||=3D @state.join(' ')
    # restart if we hit a dead end, rare unless text is small
    if @words[key].nil?
      next_word(true)
    else
      word =3D @words[key][rand(@words[key].length)]
      @state.shift
      @state.push(word)
      word
    end
  end

end

class MarkovLetters

  def initialize(filename, order)
    @order =3D order
    @letters =3D Hash.new
    @state =3D Array.new(@order)
    previous =3D Array.new(@order)
    File.foreach(filename) do |line|
      line.strip!
      line << ' ' unless line.length =3D=3D 0
      line.gsub!(/\s+/, ' ')
      line.gsub!(/[^a-z ]/, '')
      line.split(//).each do |letter|
        unless previous.include?(nil)
          p =3D previous.join('')
          unless @letters.has_key?(p)
            @letters[p] =3D Array.new
          end
          @letters[p] << letter
        end
        previous.shift
        previous.push(letter)
      end
    end
  end

  # words begin after a space and end before a space
  def print_words(n =3D 50)
    letter =3D next_letter(true)
    while letter !=3D ' '
      letter =3D next_letter()
    end
    letter =3D next_letter()
    words =3D 0
    while words < n
      words +=3D 1 if letter =3D=3D ' '
      print letter
      letter =3D next_letter()
    end
    print "\n"
  end

  def next_letter(restart =3D false)
    if restart or @state.include?(nil)
      key =3D @letters.keys[rand(@letters.length)]
      @state =3D key.split(//)
    end
    key ||=3D @state.join('')
    # restart if we hit a dead end, rare unless text is small
    if @letters[key].nil?
      next_letter(true)
    else
      word =3D @letters[key][rand(@letters[key].length)]
      @state.shift
      @state.push(word)
      word
    end
  end

end

if $0 =3D=3D __FILE__
  require 'getoptlong'

  def usage()
    $stderr.puts "Usage: ruby #{$0} [options] <filename>",
                 "  -h, --help         show this usage message",
                 "  -o, --order        set markov chain order",
                 "  -s, --sentences    set number of sentences to print",
                 "  -w, --words        set number of words to print",
                 "  -l, --letters      use letters as the basic unit"
  end

  order =3D 2
  sentences =3D 5
  words =3D nil
  letters =3D false

  opts =3D GetoptLong.new(["--help",      "-h", GetoptLong::NO_ARGUMENT],
                        ["--order",     "-o", GetoptLong::REQUIRED_ARGUMENT=
],
                        ["--sentences", "-s", GetoptLong::REQUIRED_ARGUMENT=
],
                        ["--words",     "-w", GetoptLong::REQUIRED_ARGUMENT=
],
                        ["--letters",   "-l", GetoptLong::NO_ARGUMENT])

  opts.each do |opt, arg|
    case opt
    when "--help"
      usage
      exit 0
    when "--order"
      order =3D arg.to_i
    when "--sentences"
      sentences =3D arg.to_i
      words =3D nil
    when "--words"
      words =3D arg.to_i
      sentences =3D nil
    when "--letters"
      letters =3D true
      words =3D 50 if words.nil?
    end
  end

  if ARGV.length < 1
    usage
    exit 1
  end

  ARGV.each do |arg|
    begin
      if letters
        m =3D MarkovLetters.new(arg, order)
        m.print_words(words)
      else
        m =3D MarkovWords.new(arg, order)
        m.print_words(words) unless words.nil?
        m.print_sentences(sentences) unless sentences.nil?
      end
    rescue
      $stderr.puts $!
    end
  end
end

------=_Part_32547_16008079.1144636541192
Content-Type: application/octet-stream; name=markov.rb
Content-Transfer-Encoding: 7bit
X-Attachment-Id: 0.1
Content-Disposition: attachment; filename="markov.rb"

#!/usr/bin/ruby

class MarkovWords

  def initialize(filename, order)
    @order = order
    @words = Hash.new
    @state = Array.new(@order)
    previous = Array.new(@order)
    File.foreach(filename) do |line|
      line.split(/\s+/).each do |word|
        unless previous.include?(nil)
          p = previous.join(' ')
          unless @words.has_key?(p)
            @words[p] = Array.new
          end
          @words[p] << word
        end
        previous.shift
        previous.push(word)
      end
    end
  end

  def print_words(n = 50)
    word = next_word(true)
    1.upto(n) do |i|
      print word, i == n ? "\n" : " "
      word = next_word()
    end
    print "\n"
  end

  # sentences start with a capital or quoted capital and end with
  # punctuation or quoted punctuation
  def print_sentences(n = 5)
    sentences = 0
    word = next_word(true)
    while word !~ /^['"`]?[A-Z]/
      word = next_word()
    end
    begin
      print word
      if word =~ /[?!.]['"`]?$/
        sentences += 1
        if sentences == n
          print "\n"
        else
          print " "
        end
      else
        print " "
      end
      word = next_word()
    end until sentences == n
  end

  def next_word(restart = false)
    if restart or @state.include?(nil)
      key = @words.keys[rand(@words.length)]
      @state = key.split(/\s+/)
    end
    key ||= @state.join(' ')
    # restart if we hit a dead end, rare unless text is small
    if @words[key].nil?
      next_word(true)
    else
      word = @words[key][rand(@words[key].length)]
      @state.shift
      @state.push(word)
      word
    end
  end

end

class MarkovLetters

  def initialize(filename, order)
    @order = order
    @letters = Hash.new
    @state = Array.new(@order)
    previous = Array.new(@order)
    File.foreach(filename) do |line|
      line.strip!
      line << ' ' unless line.length == 0
      line.gsub!(/\s+/, ' ')
      line.gsub!(/[^a-z ]/, '')
      line.split(//).each do |letter|
        unless previous.include?(nil)
          p = previous.join('')
          unless @letters.has_key?(p)
            @letters[p] = Array.new
          end
          @letters[p] << letter
        end
        previous.shift
        previous.push(letter)
      end
    end
  end

  # words begin after a space and end before a space
  def print_words(n = 50)
    letter = next_letter(true)
    while letter != ' '
      letter = next_letter()
    end
    letter = next_letter()
    words = 0
    while words < n
      words += 1 if letter == ' '
      print letter
      letter = next_letter()
    end
    print "\n"
  end

  def next_letter(restart = false)
    if restart or @state.include?(nil)
      key = @letters.keys[rand(@letters.length)]
      @state = key.split(//)
    end
    key ||= @state.join('')
    # restart if we hit a dead end, rare unless text is small
    if @letters[key].nil?
      next_letter(true)
    else
      word = @letters[key][rand(@letters[key].length)]
      @state.shift
      @state.push(word)
      word
    end
  end

end

if $0 == __FILE__
  require 'getoptlong'

  def usage()
    $stderr.puts "Usage: ruby #{$0} [options] <filename>",
                 "  -h, --help         show this usage message",
                 "  -o, --order        set markov chain order",
                 "  -s, --sentences    set number of sentences to print",
                 "  -w, --words        set number of words to print",
                 "  -l, --letters      use letters as the basic unit"
  end

  order = 2
  sentences = 5
  words = nil
  letters = false

  opts = GetoptLong.new(["--help",      "-h", GetoptLong::NO_ARGUMENT],
                        ["--order",     "-o", GetoptLong::REQUIRED_ARGUMENT],
                        ["--sentences", "-s", GetoptLong::REQUIRED_ARGUMENT],
                        ["--words",     "-w", GetoptLong::REQUIRED_ARGUMENT],
                        ["--letters",   "-l", GetoptLong::NO_ARGUMENT])

  opts.each do |opt, arg|
    case opt
    when "--help"
      usage
      exit 0
    when "--order"
      order = arg.to_i
    when "--sentences"
      sentences = arg.to_i
      words = nil
    when "--words"
      words = arg.to_i
      sentences = nil
    when "--letters"
      letters = true
      words = 50 if words.nil?
    end
  end

  if ARGV.length < 1
    usage
    exit 1
  end

  ARGV.each do |arg|
    begin
      if letters
        m = MarkovLetters.new(arg, order)
        m.print_words(words)
      else
        m = MarkovWords.new(arg, order)
        m.print_words(words) unless words.nil?
        m.print_sentences(sentences) unless sentences.nil?
      end
    rescue
      $stderr.puts $!
    end
  end
end


------=_Part_32547_16008079.1144636541192--