Thread: Got struck

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0

    Got struck


    I am trying to write a function that finds the minimum sum from start to end in a matrix, moving only right and down. The code is working fine for small n (<10) but taking a long time for larger n. I thought recursive will be the best way to solve such problems which also reduces the computational time. But didn't expected this to take this much long time. I wanted to know the better ways of solving it or if there is some flaw in my code...

    Code:
    def path(m):
        r = len(m)
        c = len(m[0])
        if r == 1:
            return sum(m[0])
        elif c == 1:
            t = 0
            for i in m:
                t += i[0]
            return t
        else:
            j = m[r-1][c-1]
            m2 = []
            for k in m:
                m2.append(copy.copy(k))
            m2.pop()
            m1 = []
            for k in m:
                k.pop()
                m1.append(k)
            return j + min(path(m1),path(m2))
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2013
    Location
    /dev/null
    Posts
    163
    Rep Power
    19
    Originally Posted by shakti751
    finds the minimum sum from start to end in a matrix, moving only right and down
    Could you please elaborate; when you're traversing through a matrix "from start to end moving only right and down", how do you find the minimum sum? You mean add all the numbers?

    Code:
    1 2 3
    4 5 6
    7 8 9
    Sum = 1+2+3+4+5+6+7+8+9 = 45

    Is this what you're expecting?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by noobie1000
    Could you please elaborate; when you're traversing through a matrix "from start to end moving only right and down", how do you find the minimum sum? You mean add all the numbers?

    Code:
    1 2 3
    4 5 6
    7 8 9
    Sum = 1+2+3+4+5+6+7+8+9 = 45

    Is this what you're expecting?
    Ok, sorry for the missing clarity. I mean to say that we need to move from element (1,1) in the matrix to element (m,n) assuming the no. of rows and columns to be m and n respectively. In case of your example, we need to go from 1 to 9, only by moving right and bottom, and for the sum to be minimum the path will be
    1 + 2 + 3 + 6 + 9 = 21
    or in case if the matrix is
    Code:
    5 2 3 2
    3 1 8 9
    6 2 4 1
    Min sum = 5 + 2 +1 + 2 + 4 + 1 = 15

    Hope I am clear now
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Location
    39N 104.28W
    Posts
    158
    Rep Power
    3
    Originally Posted by shakti751
    Ok, sorry for the missing clarity. I mean to say that we need to move from element (1,1) in the matrix to element (m,n) assuming the no. of rows and columns to be m and n respectively. In case of your example, we need to go from 1 to 9, only by moving right and bottom, and for the sum to be minimum the path will be
    1 + 2 + 3 + 6 + 9 = 21
    or in case if the matrix is
    Code:
    5 2 3 2
    3 1 8 9
    6 2 4 1
    Min sum = 5 + 2 +1 + 2 + 4 + 1 = 15

    Hope I am clear now
    I'm not sure recursion is the best way here. I would start at the bottom right corner: m-1,n-1. There are only 2 sums here: m-1,n-1+m-1,n+m,n and m-1,n-1+m,n-1+m,n.
    Then, there are only 2 ways to get there: from m-2,n-1 and from m-1,n-2...and so on.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Location
    Canada
    Posts
    51
    Rep Power
    2
    Hey I don't have a suggestion for you code, but have you tried running it using command line. I'm not sure if it affects all code, but for something like: "for x in range(1, 10000): print(x)" I find a big difference in output speed using command line.
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,995
    Rep Power
    481
    I think a dynamic programming technique would work, and recommend this lecture: http://www.youtube.com/watch?v=EH6h7WA7sDw.

    And to good news: displaying ten thousand numbers to the terminal will be much faster than showing them via the overhead of tcl in IDLE. The display makes the time difference.
    [code]Code tags[/code] are essential for python code and Makefiles!
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by rrashkin
    I'm not sure recursion is the best way here. I would start at the bottom right corner: m-1,n-1. There are only 2 sums here: m-1,n-1+m-1,n+m,n and m-1,n-1+m,n-1+m,n.
    Then, there are only 2 ways to get there: from m-2,n-1 and from m-1,n-2...and so on.
    As far as I understood your algorithm, I think it fails if the matrix is like this
    Code:
    [ 5 2 3 2
      2 1 8 2
      4 9 1 1]
    There are two ways of reaching (m,n) that is through (m,n-1) or (m-1,n) but selecting the minimum of these two will not give the overall minimum sum. As we cannot be sure of the overall sum which might be minimum even by choosing a way that starts with a no. that is maximum.
  14. #8
  15. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by Good News
    Hey I don't have a suggestion for you code, but have you tried running it using command line. I'm not sure if it affects all code, but for something like: "for x in range(1, 10000): print(x)" I find a big difference in output speed using command line.
    I don't think it will make a difference as I am not printing any thing other than the final result. But anyway I tried it out and didn't work as of now, it's still running.....
  16. #9
  17. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2012
    Location
    39N 104.28W
    Posts
    158
    Rep Power
    3
    Originally Posted by shakti751
    As far as I understood your algorithm, I think it fails if the matrix is like this
    Code:
    [ 5 2 3 2
      2 1 8 2
      4 9 1 1]
    There are two ways of reaching (m,n) that is through (m,n-1) or (m-1,n) but selecting the minimum of these two will not give the overall minimum sum. As we cannot be sure of the overall sum which might be minimum even by choosing a way that starts with a no. that is maximum.
    Just break it into n-m square matrices first.
  18. #10
  19. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,995
    Rep Power
    481
    Code:
    # We have a directed graph.
    # Use Dijkstra's graph algorithm.
    
    a = [#  /    /    /    /  / 
        [  1, 100, 100, 100],#/
        [  1,   1, 100, 100],#/
        [100,   1,   1,   1],#/
        [100, 100, 100,   1]
        ]
    
    # find the cheapest path from a[0][0] to a[3][3]
    # look along the diagonals, in the direction marked.
    # along diagonal just store the lowest cost and path.
    
    def ga(a):
        '''
            graph algorithm.  Given a rectangular matrix of weights
            with restrictions that we can increment by one either the row or column
            start at a[0][0] end up at a[n-1][m-1] return the lowest cost and path
            Test with
            shell_prompt$ python -m doctest this_file.py
    
            >>> ga([[100, 100, 100, 100], [1, 1, 100, 100], [100, 1, 1, 1], [100, 100, 100, 1]])
            (7, [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [3, 3]])
        '''
        n = len(a)
        m = len(a[0])
    Well, sorry, gotta go to a memorial for a friend's father now.
    [code]Code tags[/code] are essential for python code and Makefiles!
  20. #11
  21. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jul 2013
    Posts
    5
    Rep Power
    0
    Originally Posted by b49P23TIvg
    Code:
    # We have a directed graph.
    # Use Dijkstra's graph algorithm.
    
    a = [#  /    /    /    /  / 
        [  1, 100, 100, 100],#/
        [  1,   1, 100, 100],#/
        [100,   1,   1,   1],#/
        [100, 100, 100,   1]
        ]
    
    # find the cheapest path from a[0][0] to a[3][3]
    # look along the diagonals, in the direction marked.
    # along diagonal just store the lowest cost and path.
    
    def ga(a):
        '''
            graph algorithm.  Given a rectangular matrix of weights
            with restrictions that we can increment by one either the row or column
            start at a[0][0] end up at a[n-1][m-1] return the lowest cost and path
            Test with
            shell_prompt$ python -m doctest this_file.py
    
            >>> ga([[100, 100, 100, 100], [1, 1, 100, 100], [100, 1, 1, 1], [100, 100, 100, 1]])
            (7, [[0, 0], [1, 0], [1, 1], [2, 1], [2, 2], [2, 3], [3, 3]])
        '''
        n = len(a)
        m = len(a[0])
    Well, sorry, gotta go to a memorial for a friend's father now.
    Yea will try this one...
    Also now I am able to solve it, thank for the previous video. I just realized the difference between recursive function and dynamic programming. It made a lot of difference....

IMN logo majestic logo threadwatch logo seochat tools logo