import java.util.Random
 
trait MarkovChain[T <: MarkovChain[T]] { self: MarkovChain[T] =>
  type State
 
  protected def random: Random
 
  protected def possibleTransitions: Iterable[(Double, State)]
 
  def state: State
 
  protected def withState(state: State): T
 
  def transition = {
  	val target = random.nextDouble()
  	val iterator = possibleTransitions.iterator
  	def go(n: Double, lastState: => State): State =
      if (n >= target) {
        lastState
      } else {
        assert(iterator.hasNext)
        val (probability, state) = iterator.next()
        go(n + probability, state)
      }
    withState(go(0.0, ???))
  }
}
 
case class NonsenseGenerator(table: Map[String, Set[String]], state: String) extends MarkovChain[NonsenseGenerator] {
  override type State = String
 
  protected override val random = new Random()
 
  protected override def possibleTransitions = {
    val states = table(state)
    states.map{ state => (1.0 / states.size, state) }
  }
 
  protected override def withState(state: State) =
    copy(state = state)
}
 
object NonsenseGenerator {
  def apply(input: String): NonsenseGenerator = {
    var table = Map[String, Set[String]]().withDefaultValue(Set.empty)
    val words = input.split(" ")
    for ((word, nextWord) <- words zip (words.tail :+ words(0))) {
      table = table + (word -> (table(word) + nextWord))
    }
    new NonsenseGenerator(table, words(0))
  }
}
 
object Main extends App {
  val input = """A spark plug (sometimes, in British English, a sparking plug, and, colloquially, a plug) is a device for delivering electric current from an ignition system to the combustion chamber of a spark-ignition engine to ignite the compressed fuel/air mixture by an electric spark, while containing combustion pressure within the engine. A spark plug has a metal threaded shell, electrically isolated from a central electrode by a porcelain insulator. The central electrode, which may contain a resistor, is connected by a heavily insulated wire to the output terminal of an ignition coil or magneto. The spark plug's metal shell is screwed into the engine's cylinder head and thus electrically grounded. The central electrode protrudes through the porcelain insulator into the combustion chamber, forming one or more spark gaps between the inner end of the central electrode and usually one or more protuberances or structures attached to the inner end of the threaded shell and designated the side, earth, or ground electrode(s)."""
  val ng = NonsenseGenerator(input)
  val result = new StringBuilder
  (1 to 200).foldLeft(ng) { case (ng, _) =>
    val newNG = ng.transition
    result.append(' ')
    result.append(newNG.state)
    newNG
  }
  println(result.result())
}
 

aW1wb3J0IGphdmEudXRpbC5SYW5kb20KCnRyYWl0IE1hcmtvdkNoYWluW1QgPDogTWFya292Q2hhaW5bVF1dIHsgc2VsZjogTWFya292Q2hhaW5bVF0gPT4KICB0eXBlIFN0YXRlCgogIHByb3RlY3RlZCBkZWYgcmFuZG9tOiBSYW5kb20KCiAgcHJvdGVjdGVkIGRlZiBwb3NzaWJsZVRyYW5zaXRpb25zOiBJdGVyYWJsZVsoRG91YmxlLCBTdGF0ZSldCgogIGRlZiBzdGF0ZTogU3RhdGUKCiAgcHJvdGVjdGVkIGRlZiB3aXRoU3RhdGUoc3RhdGU6IFN0YXRlKTogVAoKICBkZWYgdHJhbnNpdGlvbiA9IHsKICAJdmFsIHRhcmdldCA9IHJhbmRvbS5uZXh0RG91YmxlKCkKICAJdmFsIGl0ZXJhdG9yID0gcG9zc2libGVUcmFuc2l0aW9ucy5pdGVyYXRvcgogIAlkZWYgZ28objogRG91YmxlLCBsYXN0U3RhdGU6ID0+IFN0YXRlKTogU3RhdGUgPQogICAgICBpZiAobiA+PSB0YXJnZXQpIHsKICAgICAgICBsYXN0U3RhdGUKICAgICAgfSBlbHNlIHsKICAgICAgICBhc3NlcnQoaXRlcmF0b3IuaGFzTmV4dCkKICAgICAgICB2YWwgKHByb2JhYmlsaXR5LCBzdGF0ZSkgPSBpdGVyYXRvci5uZXh0KCkKICAgICAgICBnbyhuICsgcHJvYmFiaWxpdHksIHN0YXRlKQogICAgICB9CiAgICB3aXRoU3RhdGUoZ28oMC4wLCA/Pz8pKQogIH0KfQoKY2FzZSBjbGFzcyBOb25zZW5zZUdlbmVyYXRvcih0YWJsZTogTWFwW1N0cmluZywgU2V0W1N0cmluZ11dLCBzdGF0ZTogU3RyaW5nKSBleHRlbmRzIE1hcmtvdkNoYWluW05vbnNlbnNlR2VuZXJhdG9yXSB7CiAgb3ZlcnJpZGUgdHlwZSBTdGF0ZSA9IFN0cmluZwoKICBwcm90ZWN0ZWQgb3ZlcnJpZGUgdmFsIHJhbmRvbSA9IG5ldyBSYW5kb20oKQoKICBwcm90ZWN0ZWQgb3ZlcnJpZGUgZGVmIHBvc3NpYmxlVHJhbnNpdGlvbnMgPSB7CiAgICB2YWwgc3RhdGVzID0gdGFibGUoc3RhdGUpCiAgICBzdGF0ZXMubWFweyBzdGF0ZSA9PiAoMS4wIC8gc3RhdGVzLnNpemUsIHN0YXRlKSB9CiAgfQoKICBwcm90ZWN0ZWQgb3ZlcnJpZGUgZGVmIHdpdGhTdGF0ZShzdGF0ZTogU3RhdGUpID0KICAgIGNvcHkoc3RhdGUgPSBzdGF0ZSkKfQoKb2JqZWN0IE5vbnNlbnNlR2VuZXJhdG9yIHsKICBkZWYgYXBwbHkoaW5wdXQ6IFN0cmluZyk6IE5vbnNlbnNlR2VuZXJhdG9yID0gewogICAgdmFyIHRhYmxlID0gTWFwW1N0cmluZywgU2V0W1N0cmluZ11dKCkud2l0aERlZmF1bHRWYWx1ZShTZXQuZW1wdHkpCiAgICB2YWwgd29yZHMgPSBpbnB1dC5zcGxpdCgiICIpCiAgICBmb3IgKCh3b3JkLCBuZXh0V29yZCkgPC0gd29yZHMgemlwICh3b3Jkcy50YWlsIDorIHdvcmRzKDApKSkgewogICAgICB0YWJsZSA9IHRhYmxlICsgKHdvcmQgLT4gKHRhYmxlKHdvcmQpICsgbmV4dFdvcmQpKQogICAgfQogICAgbmV3IE5vbnNlbnNlR2VuZXJhdG9yKHRhYmxlLCB3b3JkcygwKSkKICB9Cn0KCm9iamVjdCBNYWluIGV4dGVuZHMgQXBwIHsKICB2YWwgaW5wdXQgPSAiIiJBIHNwYXJrIHBsdWcgKHNvbWV0aW1lcywgaW4gQnJpdGlzaCBFbmdsaXNoLCBhIHNwYXJraW5nIHBsdWcsIGFuZCwgY29sbG9xdWlhbGx5LCBhIHBsdWcpIGlzIGEgZGV2aWNlIGZvciBkZWxpdmVyaW5nIGVsZWN0cmljIGN1cnJlbnQgZnJvbSBhbiBpZ25pdGlvbiBzeXN0ZW0gdG8gdGhlIGNvbWJ1c3Rpb24gY2hhbWJlciBvZiBhIHNwYXJrLWlnbml0aW9uIGVuZ2luZSB0byBpZ25pdGUgdGhlIGNvbXByZXNzZWQgZnVlbC9haXIgbWl4dHVyZSBieSBhbiBlbGVjdHJpYyBzcGFyaywgd2hpbGUgY29udGFpbmluZyBjb21idXN0aW9uIHByZXNzdXJlIHdpdGhpbiB0aGUgZW5naW5lLiBBIHNwYXJrIHBsdWcgaGFzIGEgbWV0YWwgdGhyZWFkZWQgc2hlbGwsIGVsZWN0cmljYWxseSBpc29sYXRlZCBmcm9tIGEgY2VudHJhbCBlbGVjdHJvZGUgYnkgYSBwb3JjZWxhaW4gaW5zdWxhdG9yLiBUaGUgY2VudHJhbCBlbGVjdHJvZGUsIHdoaWNoIG1heSBjb250YWluIGEgcmVzaXN0b3IsIGlzIGNvbm5lY3RlZCBieSBhIGhlYXZpbHkgaW5zdWxhdGVkIHdpcmUgdG8gdGhlIG91dHB1dCB0ZXJtaW5hbCBvZiBhbiBpZ25pdGlvbiBjb2lsIG9yIG1hZ25ldG8uIFRoZSBzcGFyayBwbHVnJ3MgbWV0YWwgc2hlbGwgaXMgc2NyZXdlZCBpbnRvIHRoZSBlbmdpbmUncyBjeWxpbmRlciBoZWFkIGFuZCB0aHVzIGVsZWN0cmljYWxseSBncm91bmRlZC4gVGhlIGNlbnRyYWwgZWxlY3Ryb2RlIHByb3RydWRlcyB0aHJvdWdoIHRoZSBwb3JjZWxhaW4gaW5zdWxhdG9yIGludG8gdGhlIGNvbWJ1c3Rpb24gY2hhbWJlciwgZm9ybWluZyBvbmUgb3IgbW9yZSBzcGFyayBnYXBzIGJldHdlZW4gdGhlIGlubmVyIGVuZCBvZiB0aGUgY2VudHJhbCBlbGVjdHJvZGUgYW5kIHVzdWFsbHkgb25lIG9yIG1vcmUgcHJvdHViZXJhbmNlcyBvciBzdHJ1Y3R1cmVzIGF0dGFjaGVkIHRvIHRoZSBpbm5lciBlbmQgb2YgdGhlIHRocmVhZGVkIHNoZWxsIGFuZCBkZXNpZ25hdGVkIHRoZSBzaWRlLCBlYXJ0aCwgb3IgZ3JvdW5kIGVsZWN0cm9kZShzKS4iIiIKICB2YWwgbmcgPSBOb25zZW5zZUdlbmVyYXRvcihpbnB1dCkKICB2YWwgcmVzdWx0ID0gbmV3IFN0cmluZ0J1aWxkZXIKICAoMSB0byAyMDApLmZvbGRMZWZ0KG5nKSB7IGNhc2UgKG5nLCBfKSA9PgogICAgdmFsIG5ld05HID0gbmcudHJhbnNpdGlvbgogICAgcmVzdWx0LmFwcGVuZCgnICcpCiAgICByZXN1bHQuYXBwZW5kKG5ld05HLnN0YXRlKQogICAgbmV3TkcKICB9CiAgcHJpbnRsbihyZXN1bHQucmVzdWx0KCkpCn0K