6
\$\begingroup\$

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
\$\endgroup\$

2 Answers 2

4
\$\begingroup\$

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 \$.

\$\endgroup\$
2
  • \$\begingroup\$ Is +Counter a typo, or some new syntax that I've never heard of? \$\endgroup\$
    – mkrieger1
    Commented Apr 23, 2015 at 9:27
  • \$\begingroup\$ @mkrieger1: + is just the unary plus operator; see the collections.Counter documentation for what it does when applied to a Counter object. \$\endgroup\$ Commented Apr 23, 2015 at 9:33
2
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.