# 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],
)
``````
``````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:

• There are 2n strings to guess.

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 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 I1.
• If Z > I1, then the second digit is `0`.
• If I1 > 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 I0, I1, ..., In-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)

for i in range(n):
bstring = [0] * n
bstring[i] = 1

I = make_guess(bstring)
if I > Z:
else:

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 I0, I1, ..., In-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!