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

-

Popular posts from this blog

c# - ODP.NET Oracle.ManagedDataAccess causes ORA-12537 network session end of file -

overview i want replace oracle.dataaccess orcale. managed dataaccess, opening connection latter throws ora-12537 network session end of file exception. exception message / stack trace {oracleinternal.network.networkexception (0x000030f9): ora-12537 : netzwerksession: dateiende @ oracleinternal.network.readerstream.read(orabuf ob) @ oracleinternal.ttc.orabufreader.getdatafromnetwork() @ oracleinternal.ttc.orabufreader.read(boolean bignoredata) @ oracleinternal.ttc.marshallingengine.unmarshalub1(boolean bignoredata) @ oracleinternal.ttc.ttcprotocolnegotiation.readresponse()} i trying connect oracle 11g database , not have client installed on local machine. working test application (unmanaged) using oracle.dataaccess works fine . using system; using oracle.dataaccess.client; namespace app.odp.unmanaged { internal class program { private static void main(string[] args) { //dummy connection string...
Read more

matlab - Compression and Decompression of ECG Signal using HUFFMAN ALGORITHM -

i want compress , decompress ecg signal stored text message text file , find out file size, cr,prd ratio,and qs. here code compression , decompression of ecg signal using huffman algorithm. i'm trying find out file size, compression ratio,prd ratio,qs. but error i'm getting the ecg file in text format. %clearing variables , screen enter code here clear all; close all; clc; [file1]=uigetfile('*.txt'); %fprintf('enter ecg file name :%s',file1); p=file1; t=sprintf('%s',p); b1=dlmread([file1]); len=length(b1); lead=input('enter lead number :'); %lead=str2double(lead); col2=b1(1:end,lead); e=fix(sqrt(len)); m=1; i=1:e j=1:e g2(i,j)=fix(col2(m)*1000); %amplifying 1000 m=m+1; end end g3=g2; i=1:e j=1:e ...
Read more

utf 8 - split utf-8 string into bytes in python -

i trying split utf-8 string bytes in python 3. problem is, when use bytearray, byte, encode etc functions array size of element 14 bytes, not 1 byte expected. need split text file sequence of bytes , send them byte after byte using sockets. tried this: infile = open (file, "r") str = infile.read() byte_str = bytes(str, 'utf-8') print("size of byte_str",sys.getsizeof(byte_str[0])) print gives me 14, need 1... suggestion? quoting official documentation : sys.getsizeof(object[, default]) return size of object in bytes. object can type of object. built-in objects return correct results, not have hold true third-party extensions implementation specific. only memory consumption directly attributed object accounted for, not memory consumption of objects refers to. if given, default returned if object not provide means retrieve size. otherwise typeerror raised. getsizeof() calls object’s __sizeof__ method , adds ...
Read more