How to decrease memory usage in codeeval Road Trip challenge

I'm solving easy CodeEval challenges in Python 2.7. Usually my solutions use around 256 bytes of memory according to CodeEval. With Road Trip however while time used is still low (30-40ms), memory is >5881866 bytes. As I'm somewhat of a beginner, is there an easy way to decrease memory usage?

For each test case, which consists of one line of input that lists cities and their locations on a line, the task is to find the incremental distances when visiting them all. Input follows the template ("city_name", distance;"city_name", distance;):

Rkbs,5453; Wdqiz,1245; Rwds,3890; Ujma,5589; Tbzmo,1303;
Vgdfz,70; Mgknxpi,3958; Nsptghk,2626; Wuzp,2559; Jcdwi,3761;
Yvnzjwk,5363; Pkabj,5999; Xznvb,3584; Jfksvx,1240; Inwm,5720;
Ramytdb,2683; Voclqmb,5236;

The data set is pretty big for this challenge:

• The route length is an integer in range [10000, 30000]

• The number of cities is in range [500, 600]

My solution is as follows:

test_cases = open(file)
for line in test_cases:
    line = line.strip()
    if line == "": continue
    line = line.replace(';', ' ').replace(',', ' ').split()
    distances = sorted(map(int, [line[i] for i in range(1, len(line), 2)]))
    result = [distances[i] - distances[i-1] for i in range(1, len(distances))]
    result.insert(0, distances[0])
    print ','.join(map(str, result))

I don't think it's a good idea to preprocess the line so much. line = line.strip() duplicates the line, for no benefit. I don't know why if line == "": continue should be needed. line = line.replace(';', ' ').replace(',', ' ').split() degrades the data, and takes two passes to do it.

Here's how I would read the input:

for line in fileinput.input():
    route = itertools.chain([0], sorted(
        int(city.group(1)) for city in re.finditer(r'[A-Za-z]+,(\d+);', line)
    ))

Using fileinput.input() will let you take input from either a file specified on the command line, or sys.stdin if no file is specified. re.finditer() will look for the pattern and capture the numbers that you need.

In Python 2, you should use xrange() instead of range(). However, if you capture just the numbers, as I've done above, then you wouldn't need to use range() or xrange() to extract every other item.

Each of your list comprehensions results in another temporary copy of the data. result.insert(0, distances[0]) is also bad for performance, since every entry must be copied to make room for one entry at the front of the list.

To finish off the solution, I would do this:

print(','.join(str(b - a) for a, b in pairwise(route)))

… using the pairwise() recipe from itertools.

StackExchange Code Review Q#135288, answer score: 5