python - Optimized way for finding the number which satisfies specific conditions -

i saw question somewhere. there 8 digit number. first digit left right tells how many zeroes in number. second digit tells how many 1s in number, third digit tells u how many 2 in number , on till 8th digit tells u how many 7 in number. find number. wrote piece of code in python find out digit. apart conditions mentioned above, have few additional checks 'sum of digits should 8' , 'no 8 or 9 should present in number'. i've pasted code below. brute force since take every number , check conditions. curious know if there better way of solving problem

def returnstat(number, digit, count):     number = str(number)         digit = str(digit)     print "analysing ",digit," see if 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 has 8 in it"         return (-1)     elif '9' in numlist:         print "skipping ",number, " since has 9 in it"         return (-1)     elif (sum(int(digit) digit in numlist) != 8):         print "skipping ",number, " since sum not equal 8"         return (-1)     index = 0     flag = 0     num in numlist:         if (returnstat(number,index,num)) :             index = index+1             continue         else:             flag = 1             break  if (flag == 1):     return (-1) else:     return number  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," not satisfy "     continue else:     print "the number satisfies contition ",number     break 

even if iterate on 8 digit numbers no 8s or 9s in them, there's not many possibilities (actually, 8^8 = 1<<24 ~= 17 million).

here's naive program tries them all:

import itertools  digs in itertools.product(range(8), repeat=8):     counts = [0] * 8     d in digs:         counts[d] += 1     if counts == list(digs):         print digs 

it completes (with 1 solution) in 15 seconds on machine.

to make faster, can consider 8-digit numbers digits add 8. here's same code before, uses sum_k produce possibilities. (sum_k(n, k) generates n-digit tuples digits less 8 sum k).

def sum_k(n, k):     if k < 0 or n * 7 < k: return     if n == 1:         yield k,         return     d in xrange(8):         s in sum_k(n-1, k-d):             yield (d,) + s  digs in sum_k(8, 8):     counts = [0] * 8     d in digs:         counts[d] += 1     if counts == list(digs):         print digs 

this code completes in 0.022 seconds on machine.

adapting code solve general case produces these solutions:

1210 2020 21200 3211000 42101000 521001000 6210001000 72100001000 821000001000 9210000001000