Markov Chains are a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. By analyzing a document in some way and producing a model it’s possible to use this model to generate sentences.

For example, let’s consider this quote:

Be who you are and say what you feel, because those who mind don't matter, and those who matter don't mind.

Let’s start with a seed of be, which there is only one of in this text and it’s following word is who. Thus, a 100% chance of the next state being who. From who, there are several next states: you, mind, and matter. Since there are 3 options to choose from, the next state has a 1/3 probability of each. It’s important that if there were for example two instances of who you then you would have a 2/4 probability of next state. Generate a random number and choose the next state, perhaps mind and continue until reaching a full stop. The string of states we reached is then printed and we have a complete sentence (albeit almost certainly gibberish).

Note: if we were in the state mind, our next two options would be . or don’t, in which if we hit . we would end the generation. (or not, up to you how you handle this!)

To take it a step further, you could also consider choosing the number of words to consider a state. For example, two words instead of one: those who has two possible next states: who matter or who mind. By using much longer strings of words for our states we can get more natural text but will need much more volume to get unique sentences.

This programming challenge is for you to create a Markov Chain and Text Generator in your language of choice. The input being a source document of anything you like (fun things include your favourite book, a famous person’s tweets, datasets of reddit / tildes comments), and possibly a seed. The output being a sentence generated using the Markov Chain.

Bonus points for:

• Try it a bunch of times on different sources and tell us the best generated sentences
• Using longer strings of words for the state, or even having it be variable based on input
• Not requiring a seed as an input, instead implementing that into your Markov Chain (careful as infinite loops can occur without considering the seed)
• Implement saving the Markov Chain itself, as it can take very long to generate with huge documents
• Particularly Fast, efficient, short or unique methods

Good luck!

P.S A great place to find many large plain text documents for you to play with is Project Gutenberg.

I've recently played really good game of Secret Hitler, so I wanted to let you know about it. If you don't know Secret Hitler, it's great game and I'll briefly describe it below. You can play it online, for free, without ads at secrethitler.io (opensource). You can as well buy it, or even just download pdf, print it and play with paper cards!

Secret Hitler summary

Game for 5-10 players, tabletop. Players are divided to Fascists and Liberals. One of fascists is Hitler. Fascists knows who is who, but Liberals don't know anything. There is chancellor and president, players vote them and they elect laws (president receives 3 laws, 1 discards, 2 passes to chancellor, which discards 1 law and the other one passed). Fascists win, as 6 F laws passed or Hitler was elected as chancellor with 3 or more F laws. Liberals win, if 5 L laws passed or Hitler was killed. If you want to know more, watch some gameplay at YouTube, it's really interesting game about lying to people and manipulating them. And if you will be interested in the game, we might play it together online :-)

I was a Fascist. Right on the first turn as president, I got 3 Fascists laws and I selected Hitler as chancellor - I had to because of order and it would be suspicious not to do so. So I passed him the laws and he of course had to pass Fascist law. But then, he peaked (because 3rd F law passed) at top three cards and lied about it (said FFL, was FLL). Because of this, everyone, after few turns which revealed he lied, started suspecting him. When the liberals had 4 laws passed, I tried as hard as I could to defend Hitler - he just missclicked (no, he would told us!), you know it. After about 10 minute discussion, my propose was rejected, someone else elected as Chancellor and Liberals won the game.

Leave your own stories in comments and be sure to tell, if you would like to play this with other people here, it's wonderful game. And if you would like to, I have other stories - for example when we (IRL) played Secret Hitler to 3 AM, and at the last but one turn, everyone went extremely suspicious and we played one turn almost hour and half (I don't lie about this, I started to measure it after 20 minutes of discussion).

My background: I've run a small bookkeeping business in California for the past 6 years, and worked as a bookkeeper for another 6 years before that. Over the years I've been deep in the books of dozens of businesses, both successful and not. In the process of working closely with the owners of said businesses, I've learned a lot about what makes a small business work and what means I shouldn't get too attached. I'm a generalist, working with for and non-profit businesses as well as well to do individuals (who often have financial lives more complex than my business clients.)

I'm bored and it's a smoky Sunday trapping me indoors, so if you have a question about bookkeeping or running/starting a small business, fire away.