# 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( * n)

for i in range(n):
bstring =  * 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!

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