Problem
After a long night of frivolous quackery, two delirious ducks are having a difficult time finding each other in their pond. The pond happens to contain a 3×3 grid of rocks.
Every minute, each duck randomly swims, independently of the other duck, from one rock to a neighboring rock in the 3×3 grid — up, down, left or right, but not diagonally. So if a duck is at the middle rock, it will next swim to one of the four side rocks with probability 1/4. From a side rock, it will swim to one of the two adjacent corner rocks or back to the middle rock, each with probability 1/3. And from a corner rock, it will swim to one of the two adjacent side rocks with probability 1/2.
If the ducks both start at the middle rock, then on average, how long will it take until they’re at the same rock again? (Of course, there’s a 1/4 chance that they’ll swim in the same direction after the first minute, in which case it would only take one minute for them to be at the same rock again. But it could take much longer, if they happen to keep missing each other.)
Extra credit: What if there are three or more ducks? If they all start in the middle rock, on average, how long will it take until they are all at the same rock again?
Solution
from random import randrange
from itertools import combinations
= 3
grid_size
def nbrs(pos, grid_size=3):
= pos
i, j = []
nbrs for d in [-1, 1]:
if (i+d) >= 0 and (i+d) < grid_size:
+d, j))
nbrs.append((iif (j+d) >= 0 and (j+d) < grid_size:
+d))
nbrs.append((i, jreturn nbrs
= {(i, j): nbrs((i, j)) for i in range(grid_size)
neighbours for j in range(grid_size)}
def avgTimeToMeet(ducks_start, runs=100000):
= 0
total_t for _ in range(runs):
= ducks_start
ducks = 0
t while (True):
= []
ducks_t for duck in ducks:
= neighbours[duck]
duck_nbrs = duck_nbrs[randrange(len(duck_nbrs))]
duck
ducks_t.append(duck)= ducks_t
ducks += 1
t if all([d1 == d2 for d1, d2 in combinations(ducks, 2)]):
break
+= t
total_t return total_t/runs
for ducks in [[(1, 1)]*2, [(1, 1)]*3]:
print("Average time for %d ducks to meet: %f" % (len(ducks), avgTimeToMeet(ducks)))