I wrote this program for the Google Code Jam problem, "Recycled numbers."
It took around 2 and half minutes to solve the small input set on my dual core, 1GB RAM system. But for the large input set it took around 25 minutes(processor usage was 100% for those 25 mins) to solve the problem.
Problem
Let's say a pair of distinct positive integers (\$n\$, \$m\$) is recycled if you can obtain m by moving some digits from the back of n to the front without changing their order.
For example, (12345, 34512) is a recycled pair since you can obtain 34512 by moving 345 from the end of 12345 to the front. Note that n and m must have the same number of digits in order to be a recycled pair. Neither n nor m can have leading zeros.
Given integers \$A\$ and \$B\$ with the same number of digits and no leading zeros, how many distinct recycled pairs (\$n\$, \$m\$) are there with \$A ≤ n < > m ≤ B\$?
How can I make my program fast enough to solve the large input set within 8 minutes?
f=open('C-large.in')
noi=int(f.readline().rstrip('\r\n'))
i=1
ou=open('jam.out','w')
while i<=noi:
re=f.readline().rstrip('\r\n')
rs=re.split()
a=int(rs[0])
b=int(rs[1])
ans=0
c=[x for x in range(a,b+1)]
for ind,x in enumerate(c):
for y in c[ind+1:]:
n=str(x)
m=str(y)
if len(n)==len(m) and len(n)>1 and len(m)>1:
ki=1
while ki <len(n):
temp=n[-1:-(ki)-1:-1][::-1]+n[:-(ki)]
if temp[0]!='0':
if temp==m:
ans+=1
break
ki+=1
else :
break
print("Case #%s:"%(i),ans,file=ou)
i+=1
ou.close()
f.close()
Small input:
50 156 927 167 978 484 954 160 990 135 916 160 939 103 914 173 958 100 101 124 945 181 976 101 932 101 935 170 928 171 984 126 973 283 788 667 667 384 750 153 934 173 993 185 930 100 100 178 993 21 31 178 970 168 958 170 992 104 989 34 70 162 935 289 289 185 993 10 99 120 953 184 917 179 936 108 967 6 7 160 958 115 925 137 972 188 921 10 99 118 966 100 972 167 944 136 983 107 926 118 996
Large input:
50 10000 10001 1781 7688 1007465 1919027 100000 100000 1032122 1995680 1216257 1504628 1216908 1951709 1021619 1930030 15048 53617 1007458 1962726 388 869 1067361 1995135 46739 73395 1077614 1958584 1031957 1958036 72634 74120 1063961 1954135 274937 720742 1 8 1057393 1928164 28 93 1000000 2000000 1032073 1940559 1089798 1970754 100000 999999 1434814 1780702 1072799 1964898 1059864 1967119 155569 345355 2578 4229 72 95 552 553 601415 711929 1275115 1433162 688042 856983 594203 673506 1172008 1490273 180289 925799 354653 354653 1195595 1669305 5908 5967 2083 7987 339 670 1015539 1982001 29229 96206 1006167 1522491 1117646 1117646 1021936 1950412 41215 83080 1033077 1969448
if len(m) == len(n) and len(m) > 1 and len(n) > 1
... If the first 2 expressions are true, the last one MUST be true. \$\endgroup\$