Delirious Ducks

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


grid_size = 3


def nbrs(pos, grid_size=3):
    i, j = pos
    nbrs = []
    for d in [-1, 1]:
        if (i+d) >= 0 and (i+d) < grid_size:
            nbrs.append((i+d, j))
        if (j+d) >= 0 and (j+d) < grid_size:
            nbrs.append((i, j+d))
    return nbrs


neighbours = {(i, j): nbrs((i, j)) for i in range(grid_size)
              for j in range(grid_size)}


def avgTimeToMeet(ducks_start, runs=100000):
    total_t = 0
    for _ in range(runs):
        ducks = ducks_start
        t = 0
        while (True):
            ducks_t = []
            for duck in ducks:
                duck_nbrs = neighbours[duck]
                duck = duck_nbrs[randrange(len(duck_nbrs))]
                ducks_t.append(duck)
            ducks = ducks_t
            t += 1
            if all([d1 == d2 for d1, d2 in combinations(ducks, 2)]):
                break
        total_t += 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)))