From: Joern Dinkla <joern@...>
Date: 2006-04-09T22:59:17+09:00
Subject: [QUIZ][SOLUTION] Markov Chains (#74)

--------------020800050408020303020208
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Hi all,

Here's my solution for the quiz No 74. It generates text with a first 
order Markov Chain. Because the matrix of a Markov chain for native 
language tests is sparse, the chain is stored in a hash of hashes for 
better memory usage.

I attached a tar archive for all the files and the main classes for easy 
reading.

There are some open issues i think, but i did not had the time to implement
them
- for usage of higher order markov chains one should add a list of 
previous elements in the method MarkovChain#add_elems(). But this breaks 
other parts of the code and these parts have to be adapted to this.
- better performance of the MarkovChain#rand() method
- and of course there are a lot of open issues with respect to natural 
language processing, the code does not produce grammatical valid 
sentences, no quotes, no comma, etc.

I programmed it to learn Ruby and to improve my coding skills, because i 
have less than 2,5 weeks of experience with Ruby. I bought the 
Programming Ruby" book  by Dave Thomas et. al. and started to read it 
two weeks and two days ago and i used it a lot the last 48 hours. I 
think there are some parts of the code where there are better solutions 
or could be better expressed in a more "rubyish" way.

I used Java and Perl a lot in the last years and i will use Ruby now 
instead of Perl. I can remember my experiences with hashes of hashes in 
Perl. This was awkward and often a pain. And on friday as i started 
coding for this quiz i suddenly realized that i had none of this issues 
in Ruby. Wow ! Because i know the functional language Haskell i am used 
to iterators, map's, lambda's etc. and i tried to use iterators and 
block in the program, but i think i have to get more experience here in 
Ruby.

If you have any comments, i will be glad to receive and answer them.

Extract the archive

$ tar xzf joern_dinkla_quiz_74.tar.gz

Call the program and print the command line syntax.

$ cd net.dinkla.ruby.quiz.74/lib
$ ruby main-markov-chain.rb --help

Best regards,

Joern Dinkla

-- 
Joern Dinkla, http://www.dinkla.net



--------------020800050408020303020208
Content-Type: application/x-gzip;
 name="joern_dinkla_quiz_74.tar.gz"
Content-Transfer-Encoding: base64
Content-Disposition: inline;
 filename="joern_dinkla_quiz_74.tar.gz"

H4sICLz3OEQCA2pvZXJuX2RpbmtsYV9xdWl6Xzc0LnRhcgDtPGt32ziu+br6FazTndhbR7Fs
J96TNu2kbdrJ3Gkzm6bbD4mPD2Uxtjay5BWlOJmk97dfACT18Ku5Mz093R2xrSKRIAiAIACC
TEOR2J4fXgXcjlP31v536v9m97o7p0eHr98d2clNsvGHSwvKXre70TLf+me31eoYGKfVdfac
nrPb3d1wurvdFmOstfENSioTHgOJYeRG3u1quC+1/4eWs7EvmefHYphE8S0bRmHC/VCyCb57
gl1GMUvGgp2CcrB/gHKw9xHrdZlVZ+Mkme7v7MxmM1Id0pxhNNlp2JZ1nLCRCEXMEyFZIm4S
NvOTMePs0o9lwqLYEzF7x+Or6Jq9GsOINnsphjyVgkab8CT2b1h0CT0sDTZEMKIn5Il/LVjA
w1HKR9BDyEQy4ENOeSxFk1AocKwExoTH4ANwjbkcI1r8CZQhNlckCRAzERMUQCoBIzBwNhax
YBz+yWgiWDQViEym0MkH/LBimsxNE/jwfI+FUQIoPRo48QE+iZg/mQZiIsLEgtqJ9ZdtGo3w
EwX+CIbQkpgUWJQsCmHUcZQGHuMe/GOBLxPrLwy7TWNx7UepZEIhl8gYiUwk48jTMiWRbkLn
AYLJegPEC8QC3RLxuLHgVzBOghSAzAALoCap4ZzzkDiBuVBtY35NHLnQ5PFpAtKEL0SECG1k
TQtxKmJgcsLDoTAYiwTFgLne0KRiNxwJ4IZRGquZ1zIHlkGi0FKUO2lQLOQUdBUJADVIYx4w
i1HJ1GEaR0MhpR+OmjlPXgQYcJqg1UuBvFHMJ6Bm/hAwXPMAJlHjkSBVAQzIJsCzf6dRol9B
tye8yUQyRAVHRIQDdYvoCQSPQ7VQSIKkAnEEslOLCQhi8soPAkDnamX3YbKDW9RLAGs3O2wm
xBXNhrgBYfpIiGIc8drsmLlROhonxFjtV00CYsb2GrRGV8wCCl4jwrNxNOGgKonNeGATVWjt
9ASCEijSZ5EelsiGL4/fwscoogrLB6VVTKppwaEDDqu4+3c2xplDsmhJFGaQVs2ialkzgsjh
tOLIKEgTP0Llj1EdQPXdrBFEAdMuzSKGdQqIamhzfDmusRm/pQkhKn/m15zI/lXEgSZYrxCi
+RYmSTHqg1yDAHupOQujGUDKBKViAc2IADkb8hBEBebBxYV6W5gYrZLaluRWBcZTncm4zmAG
LD67mvHY0woP+gWkTcnsHWIN2LXYB6kzjubFzJHWGWWCARNaWGi2ZOp5AtUGZjDwf8PZHHM0
RWiCQrQeJHJfZhYr1OrzCXh8lFlaQHWFXKNwLtNwiBMAqyFbSD9xeSVARD7jEyVd1OkErXoU
gxJP+HQLfgR84np8C7jEpaFlC/ZbwdNApg81ukE0vDKToleRMaZKjXy9IKD7SCRqwgvrgZTH
8AQzf8luo1RZKR7e0jpFy9g0UwyaNAq41vmh8K+VieOhnAnybhPAcnSTxHyotJvHwzFAWdZj
BlPBbn67ZP+KRBwOVKQ0wIkY9Lo2NNqj3yzrFYdRCtwQ+mnsh4nWfDAcUBP4aNhvwcPe2Ih7
CLO1IvwKfBcAsAqk7IfbykFsk4OwY5dtb49FMLUs6yX4PuBqBMolm5b1M5LJXhPGJntGVP+o
B4CxnjfZzz9E6SR4mkFZ1kZV/rxljQLuLGieBNX7ivF/p9t15uL/Vqfb2XB6e22niv+/Sdl8
tJPKeAdMMg92XD/cIZuzPbOsWIAugKHdAhMcTZMgCkdbeSVG1bfbOsaP4kJLUWEK1TOIdOWW
ZW2yX9Ewgr9MlXUEgxhNJcaRm5YnLrPvegMCsmkKkLXldhC1kZ0rS9jHlzBFHz2ILgc0GHt/
vx2y99Q08z3w1J/ut2fsE1Vci9iNpLjfvu7T/uTSD4SsWSL0kEQV/aYj8LGjIHIpRIx97gIM
RS3kDNEvk5FHJ224IQ8AwYr1y8nbwZvjX44GuJMevP/4jh0wBxYCNXw6OX39Ia/EIUtOAuQN
vphZj/95dPry5MMRgIV+YD2GHi+PTgcnbxQG3fvxp+PXZz/BR+/vlgVdJby+pUn7BSYN7P6s
DqI8rylR1Zqstj2GZw6yv//+ZHB4+vbju6P3Z6zf1NBz8qSOWEkv4RyG06N/fDw+PXq9BA8J
nzrNHt5JTxB1u15HrdVQTNuCD8cQ57N7+GrCNI3uAdWQSxInvELoGTIjBAr2S6rGIMTwk3qr
UQCdlwCBLZmFY9gyjERch0GL3Q0Pqls+l0mcigKYko8CMlM5h1FgIE7KSYoKACCAf1qWf8mo
wg5EOErGsLk6OGAt6PDh7PXR6amN66deO4rjKN5n73zaFaFoUoyQaoi5JAOSgNMwywCXHPyA
GJ920bcsW++WHAENH7DyrakjRWsA/KWA1WFCIkUvrBIMHRX1+UzhJ86SHNm4WcXPOj6IAsZo
XfBgmAY8EWZ5udz1Az/xhUTu67lcc3vxSvdBZks9mG3bNSWdk49n9mWQSpAZsQskTIY2xIfQ
dwDEQzWMbpIYylIhuysH1XKAMdcMQlI8QH7ptT6vSzRoHj3CngsNC+2pYSvkWX7oiRuGU0y7
GXyRUw4xMb7NxiA6pkCeKWozvQB6NvNtTLYdgt0CQ9U26QScC41P4SFuCdU5VTSZ02cH/8t2
zllz/+mjF3Z/hzWeQjcEVF22FWpQRK3NanXF3IelWFOJFdibcDVwANqoKFIbArUY1LgGD5H0
xNGISNyKJASwbWruU5uRD1VZKi1AclJcPWGOWkyWAX0CJpSmZgHrttOH+Nr6U8d/pU3H18//
7rW65fhvr7frtDacvd12lf/9RvEfA4NzWErF5klgjlmy6RgclQ8GW3gjHf4E3AV74an0R8nA
QhDHYIXrfnn2lUtKLKkESZMynCazzF1K/hRtewFEBWNguQKV9C2PRmOFkSeyLJMaeBjFmCiM
VBoO66/EbQajqMB4UxFbSksi0WCYwGhQ6HBSDxtNolVO0KVhKlaa5AqLdBZYEUqmTENAKM3B
1EuBuYQsDaETWif1YMRCcJXWEGyNLOZIweehpT4OgUFK7sgSydAG/zBM9jMIHb38mAnygN19
VlWZ2PIqmU4GaibzOs+Pk1vzrawjUfGHpJuTSijKNNrYozzYIaa6Q9IydhlHE+oGKoiZXnxz
iyghWqhzkP0c6+e8z+7vkRG20HDuqrbW0hbyA2UBGWStJfU5OMkOq7KwjoInzZHU2XvK6JqM
/ZT78Qycoa2EfPL6JFMoVDR1JAAD2OwNfBYPCoroFk4CCFuWOwUJUcJUzxDOitJVGkopJB4D
rDoFyAWtzxDoqeTN9X6EgmaspogOlhDGdO69TqRnc6ScOdfuW3V3VWea/kxgJm5DM6PDx0yD
h+kkXWoDClpRit7mF0Cue146nW8nBgY4McQDA7rpqMjwojDXOfGSzfkcD1qRC1z8Tg5gHEIN
PTCws1tlYpW2FTW4wJKkPmVt/Rvo0iKOeZ7dJh6EpMLwrEbH5xOYPmpiO4TfTGQRGy4igi4I
xSwP2wMtSYRhq9itLLq32ZkhJ6sMVkCmQzzNwXVxaUwCH4IJoty41u5ykE8HMcJTKMmUIIy4
4Xgip04LSzJH869JWzPPUMFt0PoXYBTKclxaqQJvsx1TuJM0DgsLR+IYy/s45T4lKDSd562+
QSI06GZmRDglEXhsvA/m+MlVL/g1sj1BNIKPssfSONWkH7D/ESDQwFaO0qgHfPgeTdZBmUAJ
sz1M2B3YgiZNzT092XON73OZuRwRcJUxVrQMOEtJNJB6imQaYEh/3i9+P3vGagU/WpvzN3O6
DjJcWOEZms07aP68zw5ffthnm3f5QoPqvo2E1BufYZtzevQLtWe8F9trpXWgsNv/ivywXrsI
aw3DHD6+1/h/Lsf3u7cAK/O/TqdXiv9b7V6r1dtwep1Wlf/9ZvH/qtQtbQyy2VcxMLxQ3P3G
1/65dDmDjEx+GUFSCIAZIeia5XcalN/IEitcp5bm+qraesPOguRysgnNAk+SeICn2BC/7E+G
xokUYucVAfNkqAKYBjOWfTIkK278GgEUrIlObc1ZXAUGj2WxDAV/lNCgXLR2VAWcc9EsgWmC
ALGdB16qZUlgieJcgnguTi5k1VieP6mdgtzodBmRbN7hj8867VJKbjHNwAH7hD9tumJTzNRp
CS50Kw6Ep7Wbd4RIO7nPCq1dK8Eeh1LEyQJZGmYuoVaKM1ZLrBhaCB1bFFQu1PzVazbmmps1
uuCBcbRK7HOTqSLpGbkq7QwbeQgMAjI6XQ8BkV1TjSp3l0fPK6IdRVEWrJT246BhEPvo4CCk
5aN25HRRQN9C4ISyFC0h1UVlKNJHHKkEmbjxYcePThxXAe7V6vnEQ7UGOCfvrz/0LDb6OPU0
TrZ8jDS0e6aHY6fTJMIoA72vb3yuHgDHJeQ5UciLj/GeglF7cq/JEn4l8tiQcgRGZJoy3X2B
rJw02Ludw/T0s+qH8KmBjb4ZXBAuYO980Drz2V/Z3BkPxIDshx8WF8hc6hhC1s07P1sZLINa
ovg5KdlPJKisYG9I95QZMrvEokLM6yZTV/UO9KZORSusljfZI5m6j+o7F+zcbj568bR/wXaa
bOvCYVs50PcS2lTlD8Z/Sg//QOL3C/Ff21m4/9va24X4b7fd263iv28U/x0ycukqwMP1S/fF
5u7YSpUDNXtoMIqBjzdpY3AqeN8T877w90i178MrY7UzujIKBe/sRnRHEoorwOlj6tUkRWn4
QqqKxzG/JYhzQIFO2aVj4CjGJyDCH0mhAW25iRIpSFkIDkmTjVU8pW1nMTije8YYahSN49Jw
J+QTE/Iws0vnQTAwMZJ2em8QF95dzTupfSeFNcb90Yi0McX9uk6f4et97prmAq86NufuI0Rz
ja5Olh1dThI4u5nM6n1KXOaOpeSw5m4rLDitvJvxW4xRcEdOCwkrOa0VbqvkQ+dcWEZ2Mdhd
MV043orpKggJzzynAR79QQSP1Srkwb7GlcUXIfqwLZMAMkkaFA4BzmdyIMoSU715AQ3G+8iw
r8AtEF4gxCSte8tcWDlXcmG0+nnz6aMX+3a/gWOy3HHS4SzeFU5DulyyiHUB13lt62L7ycFF
gizUG33AmDlroHEa+PquLt4oodVlZJvH9ISPQAEf6z/ZaRSyN7N7NjPcPwdt+Jx3rXz8f7n/
xyzpTjIcfI0z4JXnv93uXjn/43TajrPh9LqtXuX/v43/z7M/NOVp6CdbazJC4HCE+vUQphyu
ihok7pUXTzPn/bDJpDbZvkmawmt2VgHvlHLX9480vjPAXjwhfUY1+/sfgdT9fXx/xaUweWIJ
Bjw73pkMnZWJHGhsr23EhELdabbzpExnHXxnCTxVdZrdApA+YehkVd11SLuLSLsLSA1QZ6Fm
PczccVm2caR0O4h1sHDGDI5nQC0Ss2t1lG+TtbK/xSRVEQ9mZkCgK5G0m0zhgaezHklnJZJO
kyk87S8i6a5E0qXu6m9ruVCMDmscoKEiTgawYHhQv/vcJKWzDdAyGOfg+V374LnzWQG3Hwbc
ZB147eb9Og/q14RewEt3KYpuCUXxsAUZNSt0LaMGaDVMey3MAlPrgDVTLbu9i3y17N6uYs1u
LWOuiGpxHsnSrOWNIFbQgWf9hr+HwXVWwxmCM4BFajMbuZbiDGopNezgOXMM0Q8AJZE6hvov
d+gWO3TLHZYtxsJxYkhXmedyhXdmEIjG60rbsAcm7hs6GP0icO2mtg5Ykd82ioo9nIfCdx4M
3y3Cdxbg/1YiP1IsnLebYOP7Nl1TrCt91sN9mXkN234oad1VpC2i1lLqalCzdSvmxstWdTJs
4nUKt8ngxVuiPNCI2XtzUmturC6BdAkyu7OxBnJIkJkGrgP1CFTdUyiC6TVIivvnjf+/xhnw
qvi/t5f9+o85/21hShCfe1X8/z3E/wu/5rPk11fKkXr5mPb/E6zLkbPqdwpMOwWx5zVOuT98
DPHBszdbffYfGM7OmVwaYTJcFgtlR2flEz/qkbU5rRYNr2P1/GYcJfayrJ4adZENu2asvWg0
ll0ty4MBdTZePLEhSlQ9kGGSQEnkRetN2ZfW/9c4A1i1/p3dXm8h/9/b23D22k6nWv/fw/o3
v7WXr2/Ks35hWZOSqlTsyisE9drZT0cYK6SxixndPGvMLy/jKGTl8ivskNliqdHvnsx59HNE
jStKYaezg0t8atT4ivhqfXUODgHqQ6i0jxPmy6abJo8ePXRcMkjHdGLhS3W/ANd8SjWP1OP3
U/E25i7zkxdfkxp4IFqCofoXDyJwe/vQ3s6L2xw+9fbF2eX29tEK6g4zityMFLKDT/Hh4WMf
H4AEfxw9iIzDi/DlRQh/4ovw1bqBX+Lj1YNw0rXKuvpPUeiCZWMFYmwmBxQS9eYTnqVhvqvA
cr39l4Ov8Ovfq89/O7tz8Z/T7rbbG05vt12d/34r+2893rfTUI79y0SdW9K1D3qDTRGeXdYH
6mxw0MAVS0s28N1aw1rvO0z0UK5a8evhi1uNrep/pqhKVapSlapUpSpVqUpVqlKVqlSlKlWp
SlWqUpWqVKUqValKVapSlapUpSpVqUpVqlKVqlSlKlWpSlXmyv8BQBrqLQB4AAA=
--------------020800050408020303020208
Content-Type: text/plain;
 name="markov-chain.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="markov-chain.rb"

# 
# A Markov Chain contains a graph which edges are labeled with probabilities.
# The graph is stored as two hashes, one for the absolute probabilites, one for
# the relative probabilities. The nodes of the graph correspond to the keys of the hashes.
#
# The rand() method is worst case O(n), for small lists this is ok, but for
# large lists binary search will be better O(lg n)
#
class MarkovChain 

  # Initializes the hashes.
  #
  def initialize()
    @absolute = {}
    @relative = {}
    @sum_edges = {}
    @dirty = {}
  end
  
  # The nodes of the graph correspond to the keys of the hashes.
  #
  def nodes
    @absolute.keys
  end
  
  # Add an edge from node a to node b.
  #
  def add(a, b)
    @absolute[a] ||= {} 
    @absolute[a][b] ||= 0
    @absolute[a][b] += 1
    @sum_edges[a] ||= 0
    @sum_edges[a] += 1
    @dirty[a] = true
  end

  # Adds a list of elements pairwise.
  # TODO this is for order = 1. For higher orders a list of previous elements
  # could be added into the hash, but this will break other parts of the code
  def add_elems(elems)
    a = nil
    elems.each() do |b|
      add(a, b) if ( a )
      a = b
    end
  end

  # Calculates all the relative cumulative probabilities.
  #
  def recalc_all()
    @relative = @absolute.dup()
    @relative.each_pair do | a, hash |
      recalc(a) if @dirty[a]
    end
  end
  
  # Calculates the relative cumulative probabilities.
  #
  def recalc(a)
    cum = 0.0
    @relative[a] = @absolute[a].dup()
    sum = @sum_edges[a] * 1.0
    @relative[a].each_pair do | b, value|
      cum = cum + ( value / sum )
      @relative[a][b] = cum
    end
    @dirty.delete(a)
    @relative[a]
  end
  
  # Generates a random successor of node a according to the probabilities learned 
  # from the example tests.
  #
  def rand(a)
    recalc(a) if @dirty[a]
    if a.nil? || @relative[a].nil? || @relative[a].length == 0
      return nil
    elsif @relative[a].length == 1
      return @relative[a].keys[0]
    else
      # this is a linear search now with worst case O(n), TODO log(n) binary search
      value = Kernel.rand()
      candidates = @relative[a].select { |b, prob| prob > value }
      return candidates[0][0]
    end
  end

  def to_s
    result = []
    result << "MarkovChain"
    @absolute.each_pair do | key, hash |
      result << "#{key}: ABS: #{@absolute[key].to_s()} - REL: #{@relative[key].to_s()}"
    end
    result.join("\n")
  end

end

--------------020800050408020303020208
Content-Type: text/plain;
 name="story-generator.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="story-generator.rb"

# 

require 'markov-chain'

# A generator for stories. Fill the Markov chain with the methods add()
# or add_file() and generate a story with the method story().
#
class StoryGenerator

  attr_reader :mc
  
  # Initializes.
  #
  def initialize(mc = nil) 
    if mc.nil?
      @mc = MarkovChain.new()
    else
      @mc = mc 
    end
  end

  # Adds the words to the MarkovChain
  #
  def add(words) 
    @mc.add_elems(words)
  end

  # Adds a file to the MarkovChain.
  #
  def add_file(file) 
    puts "Reading file #{file}" if ( $VERBOSE )
    words = Words.parse_file(file)
    if ( $VERBOSE )
      puts "Read in #{words.length} words."
      puts "Inserting file #{file}"
      STDOUT.flush()
    end
    @mc.add_elems(words)
  end
  
  # Genereates a story with n words (".", "," etc. counting as a word) 
  #
  def story(n)
    elems = generate(n, ".")
    format(elems)
  end
  
  # Generates a story from the Markov Chain mc of length n and which starts with a
  # successor of word.
  #
  def generate(n, word)
    lexicon = @mc.nodes()
    word = lexicon[rand(lexicon.length)] if word.nil?
    elems = []
    
    1.upto(n) do |i|
      word = @mc.rand(word)
      # if no word is word, take a random one from the lexicon
      if word.nil?
        elems += ["."]
        word = lexicon[rand(lexicon.length)]
      end
      elems << word
      if ( i % LOG_WORDS_NUM == 0 && $VERBOSE )
        puts "Generated #{i} words." 
        STDOUT.flush()
      end
    end
    elems
  end
  
  # Formats the elements.
  #
  def format(elems)
    text = elems.join(" ")
    text.gsub!(/\ [.,!?;]\ /, '\1 ')
    text
  end

end

--------------020800050408020303020208
Content-Type: text/plain;
 name="words.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="words.rb"

# A parser for texts in native languages, for example english or german.
# 
# Example:
#   "To be    or not to    be."
#
# will be parsed into the array
#
# ["To", "be", "or", "not", "to", "be", "."]
#
class Words

  attr_reader :words
  
  # Returns the words of a file.
  #
  def Words.parse_file(filename)
    i = 1
    all_words = []
    File.open(filename) do | file |
      file.each_line() do |line|
        ws = Words.parse(line)
        next if ws.nil?
        all_words += ws
        i += 1 
        if ( i % LOG_FILE_READ_NUM == 0 && $VERBOSE ) 
          puts "  Read #{i} lines." 
          STDOUT.flush()
        end
      end
    end
    all_words
  end

  # Returns the words of a line.
  #
  def Words.parse(line)
    # replace newline
    line.gsub!(/\r\n/, '')
    return nil if line.length == 0
    # seperate all special characters by blanks
    line.gsub!(/([,;!?:.])/, ' \1 ')
    # remove unused special characters
    line.gsub!(/["'\-+=\t\r\n()]/, " ")
    # split the line into words
    words = line.split(/[ ]+/).select { |w| w.length > 0 }
    words
  end

end

--------------020800050408020303020208
Content-Type: text/plain;
 name="main-markov-chains.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="main-markov-chains.rb"

#!/usr/local/bin/ruby -w

require 'getoptlong'
require 'story-generator'
require 'markov-chain'
require 'words'

# Prints out the synopsis.
#
def synopsis()
  puts "ruby main-markov-chains.rb [--help] [--number_of_words N|-n N] [--width W|-w W] [--verbose|-v] textfiles"
end

# these ugly global variables are used for printing out the progress
LOG_FILE_READ_NUM = 1000
LOG_WORDS_NUM = 100

# command line option 
$VERBOSE = nil
$NUMBER_OF_WORDS = 100
$WIDTH = 78

opts = GetoptLong.new(
  ["--help", "-h", GetoptLong::NO_ARGUMENT ],
  ["--number_of_words", "--num", "-n", GetoptLong::REQUIRED_ARGUMENT ],
  ["--width", "-w", GetoptLong::REQUIRED_ARGUMENT ],
  ["--verbose", "-v", GetoptLong::NO_ARGUMENT ]
)

opts.each do |opt, arg|
  case opt
  when "--help"
    synopsis()
    exit(0)
  when "--number_of_words"
    $NUMBER_OF_WORDS = Integer(arg)
  when "--verbose"
    $VERBOSE = true
  when "--width"
    $WIDTH = Integer(arg)
  end 
end

files = ARGV

if files.length() == 0
  STDERR.puts("Error: Missing argument")
  synopsis()
  exit(1)
end

# main
# our story generator
sg = StoryGenerator.new()
# feed all the files into it
files.each do |file|
  sg.add_file(file)
end  

# calculate the probabilities
if ( $VERBOSE )
  puts "Calculating probabilities ..."
  STDOUT.flush()
end
sg.mc.recalc_all()

# generate the story
if ( $VERBOSE )
  puts "Generating..."
  STDOUT.flush()
end
story = sg.story($NUMBER_OF_WORDS)

# and print it out formatted
index = 0
last = 0
space = 0
while index < story.length()
  # remember the last non word element
  space = index if ( story[index, 1] =~ /[ ,:;!?.]/ );
  if (index - last == $WIDTH )
    raise "There is a word larger then the width" if ( last == space+1 )
    puts story[last..space]
    index = space
    last = space + 1
  end
  index += 1
end
puts story[last..-1]




--------------020800050408020303020208--