.gitignore

randomly

randomly.go

package main

import (
	"bufio"
	"fmt"
	"math/rand"
	"os"
	"strings"
	"time"
)

const NumChars = 'z' - 'a' + 2

type Prefix [2]int
type CountTable map[Prefix][]int64
type Chain map[Prefix][]int64

func (ct CountTable) AddWord(word string) {
	word = strings.ToLower(word)
	var last Prefix
	for _, char := range word {
		elem := int(char - 'a' + 1)
		if elem < 1 || elem >= NumChars {
			continue
		}
		if ct[last] == nil {
			ct[last] = make([]int64, NumChars)
		}
		ct[last][elem] += 1
		last = Prefix{last[1], elem}
	}
	if ct[last] == nil {
		ct[last] = make([]int64, NumChars)
	}
	ct[last][0] += 1
}

func (ct CountTable) Chain() Chain {
	ch := make(Chain, len(ct))
	for i := range ct {
		var cumsum int64
		ch[i] = make([]int64, NumChars)
		for j := range ct[i] {
			cumsum += ct[i][j]
			ch[i][j] = cumsum
		}
	}
	return ch
}

func (ch Chain) Next(p Prefix) int {
	X := rand.Int63n(ch[p][NumChars-1] + 1)
	for i, x := range ch[p] {
		if X <= x {
			return i
		}
	}
	return 0
}

func (ch Chain) Walk() string {
	var s []rune
	var p Prefix
	for elem := ch.Next(p); elem != 0; elem = ch.Next(p) {
		s = append(s, rune(elem+'a'-1))
		p = Prefix{p[1], elem}
	}
	return string(s)
}

func exit(v interface{}) {
	fmt.Fprintln(os.Stderr, v)
	os.Exit(1)
}

func main() {
	rand.Seed(time.Now().UnixNano())
	ct := make(CountTable)
	scanner := bufio.NewScanner(os.Stdin)
	for scanner.Scan() {
		ct.AddWord(scanner.Text())
	}
	if err := scanner.Err(); err != nil {
		exit("error reading standard input")
	}
	ch := ct.Chain()
	for i := 0; i < 10; i++ {
		fmt.Println(ch.Walk())
	}
}