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:

How to use a brute force algorithm to solve the problem.
How to make better use of your guessing strategy to solve the problem more efficiently.

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.

The random string is 0010111100.
You guess 1010101010.
You are told that 6 digits match. (These digits are _0101_1__0.)

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],
)

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

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:

There are 2ⁿ strings to guess.

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

O(2ⁿ) 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 want to figure out the second digit of a 10-digit string.
I guess 0000000000 and record the matching count in a variable Z.
I guess 0100000000 and record the matching count in a variable I₁.
If Z > I₁, then the second digit is 0.
If I₁ > Z, then the second digit is 1.

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

I make one guess for Z.
I make n guesses for I₀, I₁, ..., I_n-1.

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:

1 guess is made for Z.
n guesses are made for I₀, I₁, ..., I_n-1.
1 final guess is made to assert that I got the right answer.

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?

How many guesses would the brute force solution take?

How many guesses could a quicker solution take?

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

(If you spot any errors or typos on this post, contact me via my contact page.)