In a previous post I discussed a recent brain teaser I had come across:

Find a 10-digit number, where each digit represents the number of that ordinal number in the whole number. So, the first digit represents the number of 0's in the whole 10 digits. The second digit represents the number of 1's in the whole 10 digits. And so on. The first digit is not a 0.

As I promised at the end of the "brain only" post, we'll do better than simply finding an answer, we'll find all of them (with the aid of a computer).

Making the Problem Smaller

Without any thinking, there are 9 billion $(9 \cdot 10^9)$ total choices. This is not only intractable for the human brain, but becomes difficult for a computer too. A 3 GHz processor in the most optimal case can only perform 3 billion operations per second but there is a lot of counting, lists to create, and otherwise to find a number which fits the criteria. To start, we write our number as

Since there are 10 digits in total and each of the digits represent a subcount of occurrences, the total number of occurrences can be represented as the sum:

Additionally, (for example) since each 3 contributes a value of 3 to the digit sum, we must also have

This second equation (which requires the first to make sense) limits our choices of digits a great deal:

The last four are obvious since (for example) $2 \cdot 6 > 10$. We can also say that $d_5 < 2$. It is clearly no bigger than 2 but in the case that $d_5 = 2$ we'd also have $d_2 > 0$ meaning $2 d_2 + 5 d_5 = 2 d_2 + 10 > 10$. Thus to brute force the problem we can choose digits 5 through 9 (5 digits in total) from the 32 $(2^5)$ different possible ways to make them 0 or 1.

Listing All Choices

Now for the fun part: programming (in Python). We now have 90,000 $(9 \cdot 10^4)$ choices for our first 5 digits and 32 choices for our last 5 digits.

We can use Python's range(10**4, 10**5) to represent the 5-digit numbers between 10,000 and 99,999 (inclusive). For the 32 choices for the last 5 digits, we use itertools.product.

To see it in action on a smaller set of data:

>>> import itertools
>>> for pair in itertools.product((0, 1), repeat=2):
...   print pair
...
(0, 0)
(0, 1)
(1, 0)
(1, 1)

When we ask for 5 repeated copies of the tuple (0, 1) we get 32 possible 5-tuples as expected:

>>> len(list(itertools.product((0, 1), repeat=5)))
32

Checking Candidates

Before we can iterate through all of our combinations, we need a way to check if a given number fits the criterion. To do that we implement

def fits_criterion(digit_list):
  for i in xrange(10):
    if digit_list.count(i) != digit_list[i]:
      return False
  return True

This takes a list of digits, so as we loop over all choices, we'll turn them into lists.

Exhaustive Search

Now we can use our accumulated tools, loop through all choices and print any matches

for first5 in xrange(10**4, 10**5):
  first5_list = map(int, str(first5))
  for last5 in itertools.product((0, 1), repeat=5):
    digit_list = first5_list + list(last5)  # last5 is a tuple
    if fits_criterion(digit_list):
      print digit_list

As luck would have it, the output is simply

[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]

In other words, the only number which fits the criteria is the one we found with our brains alone:

This serves to make the interview question that much more difficult, since there is a unique solution.