Finding the number which satisfies specific conditions

Question

I saw this question somewhere:

There is an 8-digit number. The first digit from left to right determines how many zeroes are in the number. The second digit tells you how many 1s are in the number, the third digit tells you how many 2s are in the number and so on, until the 8th digit, which tells you how many 7s are in the number. Find the number.

I wrote a piece of code in Python to find out the digit. Apart from the conditions mentioned above, I have a few additional checks like 'sum of digits should be 8' and 'no 8 or 9 should be present in the number'. This is just brute force since I take every number and check for conditions. I was curious to know if there is any better way of solving the problem.

def returnStat(number, digit, count):
    number = str(number)    
    digit = str(digit)
    print "Analysing for ",digit," to see if it appears ",count, " times in ",number,"."        
    actCnt = number.count(digit)
    count = str(count)
    actCnt = str(actCnt)
    if (actCnt == count):
        return 1
    else:
        return 0
def validateNum(number):
    numList = str(number)
    if '8' in numList:
        print "Skipping ",number, " since it has 8 in it"
        return (-1)
    elif '9' in numList:
        print "Skipping ",number, " since it has 9 in it"
        return (-1)
    elif (sum(int(digit) for digit in numList) != 8):
        print "Skipping ",number, " since its sum is not equal to 8"
        return (-1)
    index = 0
    flag = 0
    for num in numList:
        if (returnStat(number,index,num)) :
            index = index+1
            continue
        else:
            flag = 1
            break 
    if (flag == 1):
        return (-1)
    else:
        return number

for num in range(0,80000000):
    number = '{number:0{width}d}'.format(width=8,number=num)
    desiredNum = "-1"
    desiredNum = validateNum(number)
    if (desiredNum == -1):
        print number," does not satisfy all "
        continue
    else:
        print "The number that satisfies all contition is ",number
        break

Answer 1

Testing for self-descriptiveness is easy if you use the built-in collections.Counter to do the counting for you:

from collections import Counter

def self_descriptive(n):
    """Return True if n is self-descriptive, that is, if n is made up of
    digits d0 d1, ..., then d0 of them are 0, d1 are 1, and so on.

    >>> self_descriptive(1210)
    True
    >>> self_descriptive(310100)
    False

    """
    digits = [int(d) for d in str(n)]
    return Counter(digits) == +Counter(dict(enumerate(digits)))

And then the solution is a one-liner:

next(filter(self_descriptive, range(10**7, 8*10**7)))

But this takes so long that it's faster to solve the problem by hand:

Consider how many zeroes there are. It's easy to rule out 8, 7, and 6, so could there be 5? This would require the number to be \$ 5abcd100 \$, with \$ a ≥ 1 \$ and \$ b = c = d = 0 \$, but this doesn't work: either \$ a = 1 \$ but there are two 1's, or \$ a > 1 \$ and there is only one 1. There can't be 3 (or fewer) zeroes, because that leaves 4 (or more) non-zeroes, adding up to at least 1 + 2 + 3 + 4 = 10 other digits, which is too many. So that leaves 4 zeroes. This requires the number to be \$ 4abc1000 \$ with \$ a ≥ 1 \$ and either \$ b = 0 \$ or \$ c = 0 \$ (but not both). If \$ b = 0 \$ then \$ c ≥ 1 \$ but this is not possible because that would require 3 of some digit, so it must be \$ c = 0 \$ and the (only) answer is \$ 42101000 \$.

Answer 2

• A presence of a variable called flag raises a red flag immediately. Consider instead an early return.

  A pattern

  if condition:
      continue
  else:
      break
  

  suggests testing for not condition. That said, the core part of validateNum should look like

  for num in numList:
      if (not returnStat(number,index,num)) :
          return -1
      index = index+1
  return number
  

• A pattern

  if condition:
      return 1
  else:
      return 0
  

  is redundant. Consider instead a simple

  return condition
  

  (in your case,

  return actCnt == count
  

• There is no need to convert actCnt and count to strings. You may (and should) compare them directly as numbers.

• There are too many number to string transformations. I recommend to represent the number as a list of digits, and either manually increment it, or use itertools to generate all necessary combinations.