SPOJ "Pesel" challemge Here is a solution to the SPOJ's JPESEL problem. Basically the problem was to calculate cross product of 2 vectors modulo 10. If there is a positive remainder, it's not a valid PESEL number; (return D) if the remainder equals 0, it's a valid number (return N).

import re, sys
n = input()
t = [1,3,7,9,1,3,7,9,1,3,1]
while(n):
    p = map(int, re.findall('.',sys.stdin.readline()))
    # Another approach I've tried in orer to save some memory - didn't help:
    # print 'D' if  sum([int(p[0]) * 1,int(p[1]) * 3,int(p[2]) * 7,int(p[3]) * 9,int(p[4]) * 1,int(p[5]) * 3,int(p[6]) * 7,int(p[7]) * 9,int(p[8]) * 1,int(p[9]) * 3,int(p[10]) * 1]) % 10 == 0 else 'N'
    print 'D' if ( sum(p*q for p,q in zip(t,p)) % 10 ) == 0 else 'N'
    n-=1


The solution above got the following results at SPOJ:

Time: 0.03s
Memory: 4.1M

where the best solutions (submitted in Python 2.7) got:

Time: 0.01s
Memory: 3.7M

How can I optimize this code in terms of time and memory used?

Note that I'm using different function to read the input, as sys.stdin.readline() is the fastest one when reading strings and input() when reading integers.
Likely what is taking up extra time is the line:

 p = map(int, re.findall('.',sys.stdin.readline()))


There are a few things here. Firstly, regular expressions are relatively expensive. Underneath, it likely needs to compile the regular expression (which in this case is very simple, but still). Further, you don't need regular expressions to do this in python. For example, assume the string was something like '343898934'. Then this is equivalent to:

p = [int(k) for k in '343898934']


The above will likely be slightly faster.

The second place here that could be optimized (memory wise) is that map in Python 2.x returns a list as opposed to a generator. So instead we could do:

p = (int(k) for k in sys.stdin.readline())


The fact that this also removes the re import may also impact timing and memory usage, depending on how they measure.