"Recycled numbers" challenge

Question

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

Answer 1

  f=open('C-large.in')

Don't sue single letter variable names, its really hard to read

    noi=int(f.readline().rstrip('\r\n'))

Since the default is already to remove whitespace, why both with the \r\n parameter?

    i=1
    ou=open('jam.out','w')
    while i<=noi:

Use for loops, not while loops to count

      re=f.readline().rstrip('\r\n')

re is a really bad name because its the same as the regular expression module

      rs=re.split()
      a=int(rs[0])
      b=int(rs[1])

I'd use a,b = map(int, re.split())

      ans=0
      c=[x for x in range(a,b+1)]

Use c = list(range(a,b+1))

      for ind,x in enumerate(c):
          for y in c[ind+1:]:

That's gonna be inefficient. Firstly, you can easily express it using simple ranges

for x in range(a, b+ 1):
    for y in range(x + 1, b + 1):

and therefore avoid the slices.

But you can do much better. You are only interested in values of y which are recyclings of x. Instead of generating the rather large number of possible second numbers, try just generating the fairly small number of possible ways to recycle x.

              n=str(x)
              m=str(y)

Converting all your numbers to strings will be expensive. See if you can keep them as integers and just do math operations on them

              if len(n)==len(m) and len(n)>1 and len(m)>1:
                 ki=1 
                 while ki <len(n):

Again, use for loops to count

                     temp=n[-1:-(ki)-1:-1][::-1]+n[:-(ki)]

temp should be banned variable name. All variables are temporary, use a more helpful name.

                     if temp[0]!='0':
                      if temp==m:
                         ans+=1
                         break
                     ki+=1   
              else :
                  break



      print("Case #%s:"%(i),ans,file=ou)

Normally, we use %d for numbers

      i+=1
    ou.close()
    f.close()

Answer 2

The correct solution here is to change the logic. Your code runs in O(n^2) (where n is b-a), but the correct solution runs in O(n d) (where d is the number of digits). Because d is most likely much smaller than n, this is much faster.

For more details, see the official analysis of the problem.

Answer 3

You're calculating n and len(n) more times than you need to. I got a 25% speed increase simply by:

• moving n=str(x) up into the for idx,x... loop
• storing n's length in that same loop (eg. length_n = len(n))
• replacing all the instaces of len(n) with length_n.

I'm sure that principle will apply to whichever solution you end up going with.

Answer 4

Not sure if my comparison method is as efficient - I've not benchmarked the tow against each other, but I'd expect the rest of this code to be better. It would be more efficient to avoid the convenience function (extra function calls), however I've split it out this way to enhance readability, and make it easier to switch your comparison method.

As I say - the comparison is completely unoptimised, but then again I usually find that standard library objects are fairly efficient.

def main():
    """ Conventionally this it the function run when the script starts """
    from collections import Counter
    with open('C-large.in') as input_file: 
        # using 'with' is recommended as it will cause the file to be closed automatically
        # when you exit this block (think try/catch/finally)
        def is_recyclable(x,y):
            """ Convenience function for readability """
            X,Y = str(x), str(y)
            if len(X) == len(Y) and len(X) > 1:
                return Counter(X) == Counter(Y)
            return False
        with open('jam.out','w') as output_file:
            line_ending = '\r\n'
            i = 1
            for line in input_file: #This will do your readline calls for you. Not sure what your 'noi' was doing, it crashed for me...
                (a,b) = (int(x) for x in line.rstrip(line_ending).split())
                ans = 0
                for x in range(a, b+1): # In python 3.x this is a generator
                    for y in range(x+1, b+1): # In python 2.x use xrange
                        # You should now have a <= x < y <= b
                        if is_recyclable(x,y):
                            ans += 1
                output = "Case #%s: %s%s"%(i, ans, line_ending)
                #print output debug line
                output_file.write(output)
                i += 1

if __name__ == "__main__":
    main()