gistfile1.txt

#!/usr/bin/env python3

## Uses batch testing and divide-and-conquer to optimize the number of 'test' runs
## Based on the premise that test runs are a bottleneck, as appears to be the case for COVID-19 testing

## assumptions:
##  - Test is 100% accurate (incl. precision, recall)
##  - Test batching doesn't increase per-test costs very much (big if)

## concerns:
##  - Specimen dilution is proportional to test size

import random, math
import numpy as np

def test(subsamples,batch):
    testcount, positivecount = (1,0)
    positive = np.logical_or.reduce(subsamples)
    if positive and len(subsamples) > 1 and batch > 0:
        for i in range(batch):
            s = len(subsamples)//batch
            a = s*(i+0)
            b = s*(i+1)
            c, d = test(subsamples[a:b],batch)
            testcount += c; positivecount += d
    else: return testcount, 1 if positive else 0
    #print(subsamples)
    #print(testcount,positivecount)
    return testcount, positivecount

def trial(saturation,batch,levels,simulations):
    #print()
    size = pow(batch,max(1,levels)) ## levels=0 is special-case with no divide-and-conquer
    testcount,positivecount,actualpositivecount=(0,0,0)
    for i in range(simulations):
        samples = np.array(random.choices( [False,True], weights=[1-saturation/100,saturation/100], k=size ))
        (a,b) = test(samples,batch if levels>0 else 0)
        c = len(np.where(samples)[0])
        testcount += a
        positivecount += b
        actualpositivecount += c if levels > 0 else (0 if c==0 else 1)
    efficiency = math.trunc(simulations*size/testcount*100)/100
    efficient = ("!" if efficiency > 1 else "")
    print("saturation:",saturation,"%, batch:",batch,", levels:",levels,", positiveavg:",positivecount/simulations,", size:",size,", testavg:",testcount/simulations,", efficiency=",efficiency,efficient)
    #print(actualpositivecount)
    assert(positivecount==actualpositivecount)

batch=4
levels=2
simulations=1000
print("Simulations per trial:",simulations)
for saturation in range(0,30,2): trial(saturation,batch,levels,simulations)