Reproductive strategy of oozes can be summarized as follows:
o O 8 oo
A population of oozes at generation N is described by a string, for example:
To compute the population at generation N+1, take one character randomly, and replace it by the result of ooze evolution:
o, replace by
O, replace by
8, replace by
Generation 0 is the one-character string
o. Your program or function should get a positive number N, and output the population of oozes at generation N. At each generation, each ooze should have the same chance (to within 1% accuracy) to evolve.
Test cases (actual results may vary due to randomness):
1 -> O 2 -> 8 3 -> oo 4 -> Oo 5 -> OO 10 -> OO8 20 -> oo8oooo 30 -> oOoooOO8O 100 -> 8o8oO8OOooOo8OOoo88oOO8OOO 200 -> 88OOo8oooo8OOoooOoOOO8O8OO88o8Oo8oooOooooooOo8OooO888 1000 -> 8Ooooo88OO8o8O8oooOOoOOO88oOoO88OOoO8OOOooOOo8OO88O8OO8OO8ooo8oOO8OoooO88OooooooooOo8oooOO8OO8Oo8Oooo8O88oooOooO8Oo8ooOOOOo8OooOo8OoooooooO8oOooooOooOO8oOO8ooo8Ooooo8ooo8ooOOooO8OOoO8oO8oo88ooo8oO8OO8o888oO8OOoO8o8ooO8O88OOOoO8oooO8OoOoOo88O88oo88ooo8oO8o8oOooOo
If your solution has running time of O(n), please specify it explicitly!