CODEWITHSUNDEEP
pythonout-of-memory
TheAptKid
TheAptKid

Reputation: 1571

Python Memory Exception

I wrote a function that find all the paths through a table.

#'X' is a full cell, ' ' is an empty cell
test1 = ["  X  X XX ",
         " X   XX  X",
         " X X X   X",
         "     X X  ",
         "  X  X    "]

def numAllPercs(table, numStreams):
    indeksiInVrsticeSplittani = [map(lambda x,y:(x,y), sorted(range(0,len(table))*len(table[0])),range(0,len(table[0])) * len(table))[i:i+len(table[0])] for i in range(0,len(map(lambda x,y:(x,y), sorted(range(0,len(table))*len(table[0])),range(0,len(table[0])) * len(table))),len(table[0]))]

def Poti(tockaX,seznamPoti,table,vejitveniSeznam):
    if(tockaX[0]+1>=len(table) or table[tockaX[0]+1][tockaX[1]] == 'X') and (tockaX[1]+1>=len(table[0]) or table[tockaX[0]][tockaX[1]+1] == 'X') and (tockaX[1]-1<0 or table[tockaX[0]][tockaX[1]-1] == 'X') :
        return (seznamPoti if len(vejitveniSeznam)==0 else seznamPoti.append(vejitveniSeznam.pop()))

    if(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X') and (tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    elif(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X') and (tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
        vejitveniSeznam.append(seznamPoti[-1])

    if(tockaX[0]+1<len(table) and table[tockaX[0]+1][tockaX[1]] != 'X'):
       seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]]])
       Poti(indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]][:indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]][indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]+1][tockaX[1]][0]+1:],vejitveniSeznam)

    if(tockaX[1]+1<len(table[0]) and table[tockaX[0]][tockaX[1]+1] != 'X'):
        seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1]])
        Poti(indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]][:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]][indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]+1][0]+1:],vejitveniSeznam)

    if(tockaX[1]-1>=0 and table[tockaX[0]][tockaX[1]-1] != 'X'):
       seznamPoti.append(seznamPoti[len(seznamPoti)-1]+[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1]])
       Poti(indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1],seznamPoti,table[:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]] + [table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]][:indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][1]] + "X" + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]][indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][1]+1:]] + table[indeksiInVrsticeSplittani[tockaX[0]][tockaX[1]-1][0]+1:],vejitveniSeznam)

    return seznamPoti

def resujem(table,seznami):
    vsePoti = filter(lambda x:x[-1][0]==len(table)-1,filter(lambda x:x[0][0]==0,reduce(lambda x,y:x+y,map(lambda x: Poti(x,[[x]],[table[0][:x[1]]+"X"+table[0][x[1]+1:]]+table[1:],[]),map(lambda x: (0,x), map(lambda x:x[1],filter(lambda x:x[0]==' ',map(lambda x,y: (x,y), map(lambda x: list(x), table)[0], range(0,len(table[0]))))))))))
    vsePoti.sort()

    def mojPresek(kombinacija):
        return (0 if len(set(reduce(lambda x,y:x+y,kombinacija))) != len(reduce(lambda x,y:x+y,kombinacija)) else 1)

    return (len(list(vsePoti for vsePoti,_ in itertools.groupby(vsePoti))) if (numStreams == 1) else  sum(map(lambda x:mojPresek(x),[list(x) for x in itertools.combinations(list(vsePoti for vsePoti,_ in itertools.groupby(vsePoti)), numStreams)])))

return (0 if numStreams <= 0 else
        0 if len(filter(lambda x: x == 'X'*len(table[0]),table)) != 0 else
        0 if numStreams >  len(map(lambda x:x[1],filter(lambda x:x[0]==' ',map(lambda x,y: (x,y), map(lambda x: list(x), table)[0], range(0,len(table[0])))))) else
        resujem(table,[]))

The parameters of the function are: the table in which we search for all possible paths and the number of streams which can concurrently flow through the table.

The program works fine for the value of streams0-4, but returns a memory exception if the parameter numStreams is 5.

Is there a solution for this problem that does not require me to change my algorithm?

Upvotes: 0

Views: 170

Answers (1)

John Mee
John Mee

Reputation: 52323

No. There is not a solution this way. Change your algorithm. Well, ok, maybe there is if you add enough memory, but really. You could just change the algorithm. My condolences if this is disappointing news.

Upvotes: 1

Related Questions