find_min.py

def find_next(urinals):
    occupied = [i for (i, x) in enumerate(urinals) if x]
    if not occupied:
        return 0

    cur = 0
    cur_max = (None, None)
    for i, u in enumerate(urinals):
        p, n = occupied[cur], occupied[cur + 1] if cur + 1 != len(occupied) else None
        if i == n:
            cur += 1
            continue
        elif i == p:
            continue
        elif cur_max[0] is None:
            d = i - p if n is None else min(i-p,n-i)
            cur_max = (d, i)
        else:
            d = i - p if n is None else min(i-p,n-i)
            if d > cur_max[0]:
                cur_max = (d, i)
    if cur_max[0] == 1:
        return None
    return cur_max[1]

def works_for_size(n, j):
    urinals = [False]*j
    for _ in range(n):
        i = find_next(urinals)
        if i is None:
            return False
        urinals[i] = True
    return True

def find_min(n):
    # absolute minimum is 2n-1, start from there
    cur = 2*n - 1
    while not works_for_size(n, cur):
        cur += 1
    return cur

if __name__=='__main__':
    print("N\tM")
    for n in range(1000):
        print("%s\t%s" % (n, find_min(n)))