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. 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?
3. 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
4. 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.
5. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jul 2013
Location
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.
6. 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.
7. 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.
8. 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.....
9. 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.
10. 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.
11. 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....