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:
ooooo88ooOoOo8Ooooo8OOoo8Oo8Oo8oo8oooooo8OOooO88o
To compute the population at generation N+1, take one character randomly, and replace it by the result of ooze evolution:
- If
o
, replace byO
- If
O
, replace by8
- If
8
, replace byoo
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!