group-testing.py

import math
from bisect import bisect_left
from typing import Any, Callable, List, Tuple


def generalized_binary_splitting(
    pred: Callable[[List[Any],], bool],
    candidates: List[Any],
    d: int
) -> List[Any]:
    """Generalized binary-splitting algorithm for group testing
    https://en.wikipedia.org/wiki/Group_testing#Generalised_binary-splitting_algorithm

    Arguments
    ---------
    pred : callable
        Test function. Takes a list of items, and returns True if
        _any_ of the items are defective, and False otherwise.
    candidates : list
        Candidate pool
    d : int
        Upper bound on the number of defective items in the pool.

    Returns
    -------
    defective : List
        list of defective items
    """
    n = len(candidates)
    if n == 1 or n <= 2*d - 2:
        # test items individually
        defects = []
        for c in candidates:
            if pred([c]):
                print("Found defect", c)
                defects.append(c)
        return defects
    else:
        l = n - d + 1
        alpha = math.floor(math.log2(l / 2))
        test_set = candidates[:2**alpha]
        remaining_set = candidates[2**alpha:]
        if pred(test_set):
            defect, nondefective = _binary_search(pred, test_set)
            print("Found defect", defect)
            remaining = list(set(candidates) - {defect} - set(nondefective))
            return [defect] + generalized_binary_splitting(pred, remaining, d-1)
        else:
            return generalized_binary_splitting(pred, remaining_set, d)


def _binary_search(
    pred: Callable[[List[Any],], bool],
    candidates: List[Any]
) -> Tuple[Any, List[Any]]:

    mid = 0
    start = 0
    end = len(candidates)
    nondefective = []

    while (start < end - 1):
        mid = (start + end) // 2

        test_set = candidates[start:mid]
        if pred(test_set):
            end = mid
        else:
            nondefective.extend(test_set)
            start = mid

    return candidates[start], nondefective


def main():
    import subprocess
    import functools
    with open("/home/mcgibbon/projects/nixpkgs/attrs.txt") as f:
        attrs = [a.strip() for a in f.readlines()]
    
    @functools.lru_cache()
    def test_chunk(chunk) -> bool:
        print(f"Testing {len(chunk)} attrs")
        cmd = "nix run -f /home/mcgibbon/projects/nixpkgs-hammering -c nixpkgs-hammer -f ~/projects/nixpkgs " + " ".join(chunk)
        p = subprocess.run(cmd, shell=True, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
        return p.returncode == 1
    
    def pred(attrs):  
        def chunker(seq, size):
            return (seq[pos:pos + size] for pos in range(0, len(seq), size))

        for chunk in chunker(attrs, 1000):
            if test_chunk(tuple(chunk)):
                print("  Got a failure")
                return True
        print("  No failures")
        return False

    results = generalized_binary_splitting(pred, attrs, d=100) 
    print(results)

def test_binary_search():
    candidates = list(range(100))
    for c in candidates:
        res, non_defective = _binary_search((lambda x: c in x), candidates)
        assert res == c


def test_generalized_binary_splitting():
    def pred(xs):
        # print("testing", xs)
        return any(x < 100 for x in xs)

    candidates = list(range(100000))
    import random
    random.shuffle(candidates)

    assert sorted(generalized_binary_splitting(pred, candidates, d=2)) == [0, 32]


if __name__ == "__main__":
    # main()
    test_generalized_binary_splitting()

# acl
# apostrophe
# attr
# aurulent-sans
# b612
# bash
# behdad-fonts
# binutils-unwrapped
# bzip2
# cabin
# ccacheStdenv
# clangMultiStdenv
# clangStdenv
# clangStdenvNoLibs
# coreboot-utils
# coreutils
# coreutils-full
# coreutils-prefixed
# cov-build
# dasm
# datadog-agent
# diffutils
# distccStdenv
# dosis
# dwarf-fortress-packages.cla-theme
# dwarf-fortress-packages.phoebus-theme
# dwarf-fortress-packages.themes.afro-graphics
# dwarf-fortress-packages.themes.autoreiv
# dwarf-fortress-packages.themes.dfgraphics
# dwarf-fortress-packages.themes.gemset
# dwarf-fortress-packages.themes.ironhand
# dwarf-fortress-packages.themes.jolly-bastion
# dwarf-fortress-packages.themes.mayday
# dwarf-fortress-packages.themes.meph
# dwarf-fortress-packages.themes.obsidian
# dwarf-fortress-packages.themes.rally-ho
# dwarf-fortress-packages.themes.spacefox
# dwarf-fortress-packages.themes.taffer
# dwarf-fortress-packages.themes.tergel
# dwarf-fortress-packages.themes.vettlingr
# dwarf-fortress-packages.themes.wanderlust
# elmPackages.create-elm-app
# elmPackages.elm-json
# elmPackages.elm-language-server
# elmPackages.elm-optimize-level-2
# elmPackages.elm-review
# elmPackages.elm-test
# elmPackages.elm-verify-examples
# emscriptenStdenv
# etBook
# findutils
# fira
# font-awesome
# font-awesome-ttf
# font-awesome_4
# gandom-fonts
# gawkInteractive
# gcc-unwrapped
# gcc10Stdenv
# gcc49Stdenv
# gcc6Stdenv
# gcc7Stdenv
# gcc8Stdenv
# gcc9Stdenv
# gccMultiStdenv
# gccStdenv
# gccStdenvNoLibs
# gelasio
# glibc
# gnugrep
# gnupatch
# gnused
# gnustep.stdenv
# gnutar
# go-font
# gromacsDoubleMpi
# gromacsMpi
# gzip
# holochain-go
# ia-writer-duospace
# inriafonts
# ir-standard-fonts
# javaPackages.junit_4_12
# javaPackages.mavenHello_1_0
# javaPackages.mavenHello_1_1
# kubeval-schema
# lalezar-fonts
# libcxxStdenv
# libertinus
# libgccjit
# libre-baskerville
# libre-bodoni
# libre-franklin
# linenoise
# llvmPackages.libcxxStdenv
# luajit
# luajit_2_0
# manrope
# material-design-icons
# material-icons
# montserrat
# mosdepth
# myrica
# nahid-fonts
# ne
# nika-fonts
# nim
# nim-unwrapped
# nimble-unwrapped
# nimlsp
# nimmm
# nrpl
# nuweb
# office-code-pro
# orbitron
# oxygenfonts
# parastoo-fonts
# powerline-fonts
# publicsuffix-list
# python37Packages.adblock
# python38Packages.adblock
# python39Packages.adblock
# raleway
# redhat-official-fonts
# rhodium-libre
# sahel-fonts
# samim-fonts
# shabnam-fonts
# sidequest
# stdenvNoCC
# stdenvNoLibs
# stdenv_32bit
# tt2020
# uberwriter
# vazir-fonts
# victor-mono
# vimPlugins.fruzzy
# warsow-engine
# work-sans
# x11
# xkcd-font
# xlibsWrapper
# xonotic
# xonotic-dedicated
# xonotic-glx
# zfsbackup