0

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?

Improve this question
5
  • 2
    Oh my God... You do know you have a 460 character long line of code? Also the indentation is clearly wrong(you can't have a return statement outside a function). I strongly suggest you to rewrite that code in a more readable manner. As it is now it's just a mess and I do not want to use hours of my life trying to get the sense of that code. So, please rewrite it, possibly using english names for variables/functions(otherwise how should we understand what the 460 characters do?) Commented Nov 21, 2012 at 12:05
  • Yes I agree with you and I apologise for the messy code. I will try to explain what I do: For every empty cell in the first line of the table I find all the combinations to the lowest row in the table. I search for a path by recursively going either down, right or left and fill the cell from which I went. The profesor told me, that this algorithm is not efficient (memory consumption) since it creates a new table for every possible move. So what I would like to know is, is there a way to solve this problem (because I spent a lot of hours writing this) without changing the algorithm? Thank you! Commented Nov 21, 2012 at 12:13
  • Then the problem is that memory consumption grows exponentially(probably). May I ask you which version of python are you using? Because I notice you are using a lot of filter/map etc. and all those would create lists that, inside the resursion tree, could take a lot of space. Commented Nov 21, 2012 at 12:18
  • To clarify - you are trying to find all ways from the X's at the top, to get down to any X's at the bottom? Commented Nov 21, 2012 at 12:26
  • I want to find all the paths from the empty cells (denoted with ' ') in the first line to the empty cells in the last line, by only moving down, right or left. You cant go to a full cell (denoted 'X'). Commented Nov 21, 2012 at 12:34

1 Answer 1

Reset to default
1

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

It is disappointing news, because I just failed this college year because of this assignment. :( Thank you for your effort and your answer.
No doubt you'll go on to be a prodigy in another field and wind up gifting this professor a low paid job because he's down on his luck.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.