segmentation fault, need to prevent this and reduce the run time of my program

Question

I solved a problem where I had to find sum of numbers whose digits are made of only 4, 5 and 6.. The numbers have at most x fours, at most y fives and at most z sixes. I successfully passed some of the sample tests. But, I cannot get past other test cases as i keep getting segfault errors. Also, I think my programs run time is seriously long. Any help in reducing the run time, optimizing the solution and -reventing segfault will be appreciated. Here is my code in Python:

from itertools import permutations
x , y, z = raw_input().split(' ')
x = int(x)
y = int(y)
z = int(z)
max = ''
for a in range(z):
    max += '6'
for b in range(y):
    max += '5'
for c in range(x):
    max += '4'
perms = [''.join(p) for p in permutations(max)]
chances = []
def substring(string):
    possible = []
    for x in range(len(string) + 1):
        for y in range(x, len(string) + 1):
            possible.append(string[x:y])
    return possible
for d in perms:
    chances += list(set(substring(d)))
chances = list(set(chances))
chances.remove('')
sum = 0
for nstr in chances:
    sum += int(nstr)
print sum

This is an algorithm problem. Add it as a tag. – aadarshsg Jul 08 '15 at 01:24 — aadarshsg, Jul 08 '15 at 01:24

score 0 · Answer 1 · answered Jul 08 '15 at 02:24

It would be helpful to know what part of the program is consuming the most time. Looking at the second half, after the call to permutations, I see that you are creating potentially huge lists (in chances and permutations. After building them you convert to a set (to eliminate duplicates I suppose) and back again to a list. Why not use a single set instead, like this:

chances = set()
def substring(string):
    for x in range(len(string) + 1):
        for y in range(x, len(string) + 1):
            chances.add(string[x:y])
for d in perms:
    substring(d)
chances.remove('')
sum = 0
for nstr in chances:
    sum += int(nstr)
print sum

I don't know if that will solve all your problems, but it should help.

I think that would help, but I am still getting segfault errors. — therealdev, Jul 08 '15 at 02:35
Have you looked here: http://stackoverflow.com/questions/10035541/what-causes-a-python-segmentation-fault — Paul Cornelius, Jul 09 '15 at 01:07

segmentation fault, need to prevent this and reduce the run time of my program

1 Answers1