Return to Blog

Solving the Binary Guess Problem in Python

By John Lekberg on May 08, 2020.


This week's post is about solving the "Binary Guess Problem". You will learn:

Problem Statement

You are given a random binary string with n digits. E.g.

0010111100

You can't examine the string directly. But, you can make a guess and be told how many digits match. E.g.

You goal is to correctly guess the random string.

How I represent the data in the problem

I represent a binary string as a list of 0s and 1s. E.g.

[0, 0, 1, 0, 1, 1, 1, 1, 0, 0]

I generate a random string using random.choices:

import random

def random_binary_string(n):
    return random.choices([0,1], k=n)

random_binary_string(10)
[1, 0, 1, 1, 1, 1, 1, 0, 0, 1]

I have a function, count_matching, that counts the number of matching digits in a guess:

def count_matching(bstring, guess):
    matching = 0
    for x, y in zip(bstring, guess):
        if x == y:
            matching += 1
            
    return matching

count_matching(
    [0, 1, 0, 1, 0, 1, 0, 0, 1, 1],
    [0, 1, 0, 1, 0, 1, 0, 0, 1, 1],
)
10
count_matching(
    [0, 1, 0, 1, 0, 1, 0, 0, 1, 1],
    [0, 0, 1, 1, 1, 1, 0, 1, 0, 1],
)
5

Creating a brute force solution

An easy brute force solution will guess every n-digit string:

import functools
import itertools


def binary_guess_bf(*, n, make_guess):
    """Solve the Binary Guess problem using brute force.
    
    n -- the length of the string.
    make_guess -- a function for making a guess and
        getting the number of matching elements.
    """
    every_bstring = itertools.product([0, 1], repeat=n)
    for bstring in every_bstring:
        n_correct = make_guess(bstring)
        if n_correct == n:
            return bstring

bstring = [0, 1, 0, 1, 0, 1, 0, 0, 1, 1]
binary_guess_bf(
    n = 10,
    make_guess = functools.partial(count_matching, bstring),
)
(0, 1, 0, 1, 0, 1, 0, 0, 1, 1)
bstring = [0, 0, 1, 1, 1, 1, 0, 1, 0, 1]
binary_guess_bf(
    n = 10,
    make_guess = functools.partial(count_matching, bstring),
)
(0, 0, 1, 1, 1, 1, 0, 1, 0, 1)

This uses itertools.product to generate every n-digit binary string and uses functools.partial to create the make_guess function.

What is the time complexity of this solution? For an n-digit binary string:

As a result, the overall time complexity of the brute force algorithm is

O(2n) guesses

Keeping track of the guesses to create a faster solution

How can I make fewer guesses?

One way to make fewer guesses is to determine one digit of the string at a time. E.g.

I can determine all the digits this way in n+1 guesses:

Here's a function, binary_guess_quick, that implements this algorithm:

def binary_guess_quick(*, n, make_guess):
    """Solve the Binary Guess problem in n+1 guesses.
    
    n -- the length of the string.
    make_guess -- a function for making a guess and
        getting the number of matching elements.
    """
    Z = make_guess([0] * n)
    
    answer = []
    
    for i in range(n):
        bstring = [0] * n
        bstring[i] = 1
        
        I = make_guess(bstring)
        if I > Z:
            answer.append(1)
        else:
            answer.append(0)
    
    assert make_guess(answer) == n
    
    return answer

bstring = [0, 1, 0, 1, 0, 1, 0, 0, 1, 1]
binary_guess_quick(
    n = 10,
    make_guess = functools.partial(count_matching, bstring),
)
[0, 1, 0, 1, 0, 1, 0, 0, 1, 1]
bstring = [0, 0, 1, 1, 1, 1, 0, 1, 0, 1]
binary_guess_quick(
    n = 10,
    make_guess = functools.partial(count_matching, bstring),
)
[0, 0, 1, 1, 1, 1, 0, 1, 0, 1]

What is the time complexity of this solution? For an n-digit binary string:

As a result, the overall time complexity of this algorithm is

O(n) guesses

In conclusion...

In this week's post, you learned how to solve the "Binary Guess Problem". You learned how to use itertools.product to create a brute force solution that generates every possible string. You also learned how to improve the runtime efficiency by isolating the digits, one at a time.

My challenge to you:

How would you solve this problem for a ternary string, where the digits are 0, 1, and 2?

If you enjoyed this week's post, share it with your friends and stay tuned for next week's post. See you then!