Simulate reproduction in a population of oozes 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 by O
If O, replace by 8
If 8, replace by oo


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 -&gt; O
2 -&gt; 8
3 -&gt; oo
4 -&gt; Oo
5 -&gt; OO
10 -&gt; OO8
20 -&gt; oo8oooo
30 -&gt; oOoooOO8O
100 -&gt; 8o8oO8OOooOo8OOoo88oOO8OOO
200 -&gt; 88OOo8oooo8OOoooOoOOO8O8OO88o8Oo8oooOooooooOo8OooO888
1000 -&gt; 8Ooooo88OO8o8O8oooOOoOOO88oOoO88OOoO8OOOooOOo8OO88O8OO8OO8ooo8oOO8OoooO88OooooooooOo8oooOO8OO8Oo8Oooo8O88oooOooO8Oo8ooOOOOo8OooOo8OoooooooO8oOooooOooOO8oOO8ooo8Ooooo8ooo8ooOOooO8OOoO8oO8oo88ooo8oO8OO8o888oO8OOoO8o8ooO8O88OOOoO8oooO8OoOoOo88O88oo88ooo8oO8o8oOooOo




If your solution has running time of O(n), please specify it explicitly!
Python 3, 114 bytes



from random import*
def f(n,s=b'o'):k=randrange(len(s));return n and f(n-1,s[:k]+b'oO8o'[-~s[k]%3::3]+s[k+1:])or s


Try it online!

Interesting observation: the ascii values of oO8 are 111, 79, and 56, respectively. If you take these modulo 3, you get 0, 1 and 2.



Additional observation: you can validate the generation of your final string by substituting 'o' with 3, 'O' with 4 and '8' with 5; then taking the sum of your list and subtracting 3 from the total.

This works for all strings regardless of random variations, because each replacement in your string increases this sum by 1:

'o' (3) -&gt; 'O'  (4)
'O' (4) -&gt; '8'  (5)
'8' (5) -&gt; 'oo' (3+3 = 6)


We then just need to correct for the offset of 3.

Validate it online!