Apr 2006
1 / 4
Apr 2006
Nov 2006
spiffy
Apr '06

Can anyone give me any "clues" to speed up my solution(s) for palin as they all timeout, do I need to change the way input is gathered or the way I calculate the palindromes ?

One example of a slow solution:

!/usr/local/bin/python

import sys

def calc(arg):
nines = {'99':'101','999':'1001','9999':'10001','99999':'100001','999999':'1000001'}
if arg in nines: print nines[arg]
if int(arg) < 11:
print "11"
else:
ls = []
for i in arg:ls.append(i)
le = len(ls)
sm = int(arg)
if le == 2:
ls[1] = ls[0]
if int(''.join(ls)) <= sm:
ls[0] = str(int(ls[0])+1)
ls[1] = ls[0]
print ''.join(ls)
if le == 3:
ls[2] = ls[0]
if int(''.join(ls)) <= sm:
ls[1] = str(int(ls[1])+1)
print ''.join(ls)
if le == 4:
ls[3] = ls[0]
ls[2] = ls[1]
if int(''.join(ls)) <= sm:
ls[1] = str(int(ls[1])+1)
ls[2] = str(int(ls[2])+1)
print ''.join(ls)
if le == 5:
ls[4] = ls[0]
ls[3] = ls[1]
if int(''.join(ls)) <= sm:
ls[2] = str(int(ls[2])+1)
print ''.join(ls)
if le == 6:
ls[5] = ls[0]
ls[4] = ls[1]
ls[3] = ls[2]
if int(''.join(ls)) <= sm:
ls[2] = str(int(ls[2])+1)
ls[3] = str(int(ls[3])+1)
print ''.join(ls)

iter = sys.stdin.readline().strip()
args = []
for i in xrange(0,int(iter)):
args.append(sys.stdin.readline().strip())
map(calc,args)
sys.exit(0)

I've also tried for loops, array.array as solutions, with psyco, all too slow .

Any tips on how to speed up python solutions would be good ...

Cheers smile

spiffy
Apr '06

Hi,

Here's my latest attempt, again it times out, I'm stumped as how to improve it. I submitted a solution that just read the input and that seemed to completed in 0.17s and errored, so it seems to be related to my algorithm, rather than I/O:

#!/usr/local/bin/python
import sys
iter = raw_input()
ls = []
ans = ""
for i in xrange(0,int(iter)):
  arg = raw_input()
  next = {'0':'1','1':'2','2':'3','3':'4','4':'5','5':'6','6':'7','7':'8','8':'9','9':'0'}
  nines = {'99':'101','999':'1001','9999':'10001','99999':'100001','999999':'1000001'}
  if int(arg) < 1 or int(arg) > 999999:continue
  if arg in nines:
    ls = nines[arg]
    ans = ans + (''.join(ls))+'\n'
    continue
  if int(arg) < 11:
    ls = "11"
    ans = ans + (''.join(ls))+'\n'
    continue
  else:
    ls = list(arg)
    le = len(ls)
    sm = int(arg)
    if le == 2:
      ls[1] = ls[0]
      if int(''.join(ls)) <= sm:
        ls[0] = next[ls[0]]
        ls[1] = ls[0]
      ans = ans + (''.join(ls))+'\n'
      continue
    if le == 3:
      ls[2] = ls[0]
      if int(''.join(ls)) <= sm:
        ls[1] = next[ls[1]]
      ans = ans + (''.join(ls))+'\n'
      continue
    if le == 4:
      ls[3] = ls[0]
      ls[2] = ls[1]
      if int(''.join(ls)) <= sm:  
        ls[1] = next[ls[1]] 
        ls[2] = next[ls[2]] 
      ans = ans + (''.join(ls))+'\n'
      continue
    if le == 5:
      ls[4] = ls[0]
      ls[3] = ls[1]
      if int(''.join(ls)) <= sm:  
        ls[2] = next[ls[2]] 
      ans = ans + (''.join(ls))+'\n'
      continue
    if le == 6:
      ls[5] = ls[0]
      ls[4] = ls[1]
      ls[3] = ls[2]
      if int(''.join(ls)) <= sm:  
        ls[2] = next[ls[2]] 
        ls[3] = next[ls[3]] 
      ans = ans + (''.join(ls))+'\n'
      continue
print '\n'+ans

Any ideas ?
Cheers

12 days later
spiffy
Apr '06

I really should have read the problem definition more carefully, much wasted time trying to solve the wrong thing ... but finally a solution once I realised my idiocy... smiley

7 months later