from collections import defaultdict as dd, deque
from random import random
import re

class MarkovTextGenerator:
    def __init__(self, depth):
        self.freq = dd(lambda: dd(int))
        self.quantity = dd(int)
        self.depth = depth
    def learn(self, text):
        words = re.split("\\s+", text)
        state = deque([None] * self.depth)
        for word in words:
            state.popleft()
            self.freq[str(state)][word] += 1
            self.quantity[str(state)] += 1
            state.append(word)
    def generate(self, size):
        state = deque([None] * self.depth)
        for i in range(size):
            try:
                state.popleft()
            except:
                break
            pick = random()
            acc = 0.0
            for p in self.freq[str(state)].keys():
                if (acc + self.freq[str(state)][p] / self.quantity[str(state)] >= pick):
                    print(p, end=" ")
                    state.append(p)
                    break
                acc += self.freq[str(state)][p] / self.quantity[str(state)]

# usage
fin = open('input.txt')

mtg = MarkovTextGenerator(4)
mtg.learn(fin.read())
mtg.generate(1000)