# 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 2
^{n}strings to guess.

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

O(2

^{n}) 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`_{1}. - If
`Z`>`I`_{1}, then the second digit is`0`

. - If
`I`_{1}>`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`_{0},`I`_{1}, ...,`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`_{0},`I`_{1}, ...,`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!