Calculate the less number of mice to find out two poisons from N bottles by brust force. Python >= 3.6

mice_brust_force.py

#-*- coding:utf8 -*-
from pprint import pprint
from time import time

def bottle_arrange(bottle_num, mouse_num):
    mice = list(range(0, mouse_num))
    bottle_combination = 2**bottle_num
    while True:
        for i in range(mouse_num - 1, -1, -1):
            if mice[i] < bottle_combination - mouse_num + i:
                mice[i] += 1
                for j in range(i + 1, mouse_num):
                    if mice[j] == -1:
                        mice[j] = mice[j - 1] + 1
                break
            else:
                mice[i] = -1
        if mice[0] == -1:
            return
        yield mice


def unique(s):
    """Return a list of the elements in s, but without duplicates.

    For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
    unique("abcabc") some permutation of ["a", "b", "c"], and
    unique(([1, 2], [2, 3], [1, 2])) some permutation of
    [[2, 3], [1, 2]].

    For best speed, all sequence elements should be hashable.  Then
    unique() will usually work in linear time.

    If not possible, the sequence elements should enjoy a total
    ordering, and if list(s).sort() doesn't raise TypeError it's
    assumed that they do enjoy a total ordering.  Then unique() will
    usually work in O(N*log2(N)) time.

    If that's not possible either, the sequence elements must support
    equality-testing.  Then unique() will usually work in quadratic
    time.

    Link: http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/
    """

    n = len(s)
    if n == 0:
        return []

    # Try using a dict first, as that's the fastest and will usually
    # work.  If it doesn't work, it will usually fail quickly, so it
    # usually doesn't cost much to *try* it.  It requires that all the
    # sequence elements be hashable, and support equality comparison.
    u = {}
    try:
        for x in s:
            u[x] = 1
    except TypeError:
        del u  # move on to the next method
    else:
        return u.keys()

    # We can't hash all the elements.  Second fastest is to sort,
    # which brings the equal elements together; then duplicates are
    # easy to weed out in a single pass.
    # NOTE:  Python's list.sort() was designed to be efficient in the
    # presence of many duplicate elements.  This isn't true of all
    # sort functions in all languages or libraries, so this approach
    # is more effective in Python than it may be elsewhere.
    try:
        t = list(s)
        t.sort()
    except TypeError:
        del t  # move on to the next method
    else:
        assert n > 0
        last = t[0]
        lasti = i = 1
        while i < n:
            if t[i] != last:
                t[lasti] = last = t[i]
                lasti += 1
            i += 1
        return t[:lasti]

    # Brute force is all that's left.
    u = []
    for x in s:
        if x not in u:
            u.append(x)
    return u

def find_less_mice(bottle_num):
    format_str = '{{0:0{}b}}'.format(bottle_num)
    cnt = 0
    last_time = time()
    for mouse_num in range(1, bottle_num-1):
        print('mouse number:{}'.format(mouse_num))
        correct_arrange = []
        for arrange in bottle_arrange(bottle_num, mouse_num):
            cnt += 1
            if cnt % 10000000 == 0:
                cur_time = time()
                print('cnt:{} use:{}'.format(cnt, cur_time - last_time))
                last_time = cur_time
            appeared_codes = {}
            valid_arrange = True
            for poison1 in range(0, bottle_num-1):
                for poison2 in range(poison1+1, bottle_num):
                    poison_mask = (1 << poison1) | (1 << poison2)
                    code = 0
                    for mouse_no in range(0, mouse_num):
                        if arrange[mouse_no] & poison_mask:
                            code |= (1 << mouse_no)
                    if code in appeared_codes:
                        valid_arrange = False
                        break
                    else:
                        appeared_codes[code] = 1
                if not valid_arrange:
                    break
            if not valid_arrange:
                continue
            else:
                correct_arrange.append({a:0 for a in arrange})
                break

        if correct_arrange:
            correct_arrange = [[format_str.format(n) for n in sorted(list(a.keys()))] for a in unique(correct_arrange)]
            print('Use {} mice for check {} bottles.'.format(mouse_num, bottle_num))
            print('Arrangement:')
            pprint(correct_arrange)
            return
    print('Use {} mice for check {} bottles.'.format(bottle_num - 1, bottle_num))
    


bottle_num = 7
find_less_mice(bottle_num)

#-*- coding:utf8 -*-
from pprint import pprint
from time import time

def bottle_arrange(bottle_num, mouse_num):
    mice = list(range(0, mouse_num))
    bottle_combination = 2**bottle_num
    while True:
        for i in range(mouse_num - 1, -1, -1):
            if mice[i] < bottle_combination - mouse_num + i:
                mice[i] += 1
                for j in range(i + 1, mouse_num):
                    if mice[j] == -1:
                        mice[j] = mice[j - 1] + 1
                break
            else:
                mice[i] = -1
        if mice[0] == -1:
            return
        yield mice


def unique(s):
    """Return a list of the elements in s, but without duplicates.

    For example, unique([1,2,3,1,2,3]) is some permutation of [1,2,3],
    unique("abcabc") some permutation of ["a", "b", "c"], and
    unique(([1, 2], [2, 3], [1, 2])) some permutation of
    [[2, 3], [1, 2]].

    For best speed, all sequence elements should be hashable.  Then
    unique() will usually work in linear time.

    If not possible, the sequence elements should enjoy a total
    ordering, and if list(s).sort() doesn't raise TypeError it's
    assumed that they do enjoy a total ordering.  Then unique() will
    usually work in O(N*log2(N)) time.

    If that's not possible either, the sequence elements must support
    equality-testing.  Then unique() will usually work in quadratic
    time.

    Link: http://code.activestate.com/recipes/52560-remove-duplicates-from-a-sequence/
    """

    n = len(s)
    if n == 0:
        return []

    # Try using a dict first, as that's the fastest and will usually
    # work.  If it doesn't work, it will usually fail quickly, so it
    # usually doesn't cost much to *try* it.  It requires that all the
    # sequence elements be hashable, and support equality comparison.
    u = {}
    try:
        for x in s:
            u[x] = 1
    except TypeError:
        del u  # move on to the next method
    else:
        return u.keys()

    # We can't hash all the elements.  Second fastest is to sort,
    # which brings the equal elements together; then duplicates are
    # easy to weed out in a single pass.
    # NOTE:  Python's list.sort() was designed to be efficient in the
    # presence of many duplicate elements.  This isn't true of all
    # sort functions in all languages or libraries, so this approach
    # is more effective in Python than it may be elsewhere.
    try:
        t = list(s)
        t.sort()
    except TypeError:
        del t  # move on to the next method
    else:
        assert n > 0
        last = t[0]
        lasti = i = 1
        while i < n:
            if t[i] != last:
                t[lasti] = last = t[i]
                lasti += 1
            i += 1
        return t[:lasti]

    # Brute force is all that's left.
    u = []
    for x in s:
        if x not in u:
            u.append(x)
    return u

def find_less_mice(bottle_num):
    format_str = '{{0:0{}b}}'.format(bottle_num)
    cnt = 0
    last_time = time()
    for mouse_num in range(1, bottle_num-1):
        print('mouse number:{}'.format(mouse_num))
        correct_arrange = []
        for arrange in bottle_arrange(bottle_num, mouse_num):
            cnt += 1
            if cnt % 10000000 == 0:
                cur_time = time()
                print('cnt:{} use:{}'.format(cnt, cur_time - last_time))
                last_time = cur_time
            appeared_codes = {}
            valid_arrange = True
            for poison1 in range(0, bottle_num-1):
                for poison2 in range(poison1+1, bottle_num):
                    poison_mask = (1 << poison1) | (1 << poison2)
                    code = 0
                    for mouse_no in range(0, mouse_num):
                        if arrange[mouse_no] & poison_mask:
                            code |= (1 << mouse_no)
                    if code in appeared_codes:
                        valid_arrange = False
                        break
                    else:
                        appeared_codes[code] = 1
                if not valid_arrange:
                    break
            if not valid_arrange:
                continue
            else:
                correct_arrange.append({a:0 for a in arrange})
                break

        if correct_arrange:
            correct_arrange = [[format_str.format(n) for n in sorted(list(a.keys()))] for a in unique(correct_arrange)]
            print('Use {} mice for check {} bottles.'.format(mouse_num, bottle_num))
            print('Arrangement:')
            pprint(correct_arrange)
            return
    print('Use {} mice for check {} bottles.'.format(bottle_num - 1, bottle_num))
    

bottle_num = 7
find_less_mice(bottle_num)