Re: [QUIZ][SOLUTION] Markov Chains (#74)

Hi again,

I wrote:
> 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.

Now i implemented higher order Markov Chains as well. I could not resist 
:-)

A first order chain, for example the following one

     @mc3 = MarkovChain.new()
     @mc3.add(1,2)
     @mc3.add(3,4)

is stored as the following hash of hashes

	{1=>{2=>1}, 3=>{4=>1}}

A higher order chain, for example the following

     @mc7 = MarkovChain.new(order = 2)
     @mc7.add_elems([20,21,20,22,21,22,20,23])

is also stored as a hash of hashes, but the keys are arrays

{[22, 21]=>{22=>1}, [22, 20]=>{23=>1}, [20, 21]=>{20=>1}, [21, 
22]=>{20=>1}, [20,22]=>{21=>1}, [21,20]=>{22=>1}}

Because i am new to Ruby, i had to learn a few things about Arrays, 
Objects and dup(). I still do not understand this fully (perhaps it is 
to late here 00:46 CET), but in the method MarkovChain.add() i need to 
dup the arrays, otherwise some keys will get overwritten.

In class MarkovChain
   # Add an edge from node a to node b.
   #
   def add(a, b)
     # this dup is needed, otherwise elements will be overwritten
     a = a.dup() if a.instance_of?(Array)
     @absolute[a] ||= {}
     @absolute[a][b] ||= 0
     @absolute[a][b] += 1
     @sum_edges[a] ||= 0
     @sum_edges[a] += 1
     @dirty[a] = true
   end

I will try to find it out tommorow. By the way, below is an example text 
i generated for order 3 after i fed 4 books of Chesterton into the 
chain. Beginning with order 3 i think the text looks like a patchwork or 
collage of some phrases and sentences of the original texts.

Best regards,

Joern

. Up to a certain point it was a wordless clamour startlingly close, and 
loud enough to be distinct if each word had not killed the other. No, 
replied Fisher. The Renaissance nobles of the Tudor time were like that. 
It is awful, I think it goes far enough! said Flambeau; but my 
information is fragmentary, and only twelve members of the Central 
Anarchist Council. The gentleman who has for some time past played, with 
propriety and general applause, the difficult part of Thursday, has died 
quite suddenly. Consequently, he was willing to go into Parliament as a 
yeoman or a gentleman or a Jacobite or an Ancient Briton, I should say 
that, Crane went on. This also tempted him, that in a more partial and 
also a more premature fashion, for his voice was colourless and sad. 
What I did next does matter: I gave him a rather wild stare, March had 
yet another unexpected emotion, for his guide hailed the man as Hoggs 
and introduced him as Sir Howard Horne, then introducing his so-called 
Socialist budget, and prepared to expound it in an interview with so
promising a penman. Harold March was to have the gold of Glengyle. So 
far the crime seemed clear enough; and while Boyle was looking into it 
he heard a thud behind him, and then a sudden stillness, as of a stone 
statue walking. He might have been firebrands. The mutinies simmered 
down; the men who must have known that particular house to be so 
accurately inaccurate. But what makes you think it a specimen. Put the 
same feather with a ribbon and an artificial flower and everyone will 
think it a wildcat, though it may have been a clever fellow, answered 
the priest. As they raced along to the gate out of which poured and 
rolled, not Roman, but very late, and that this, my successful
masquerade, might be of considerable value to the public, placed it here 
with his own pale blue ones, and said, Do you want me to tell you all 
you want to guess what he doing, keep behind him. About his life and 
fortune on the table, and went below the surface in a way that at once 
puzzled and reassured him. On the oranges was the equally clear and 
exact description, Finest Brazil nuts, 4d. a lb. M. Brun had a dark, 
handsome lady, of no little majesty, and rather like a mosaic palace, 
rent with earthquakes; or like a Dutch tulip garden blown to the stars. 
The other did not answer; he was free in free London, and drinking

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