[Tutor] distance between cities matrix

Dave Angel davea at davea.name
Thu Feb 21 16:42:24 CET 2013

On 02/21/2013 07:16 AM, Mara Kelly wrote:
> Hi everyone, Here is the question I was given...Consider the (20x20) array of numbers here(I wrote all of the numbers in my program). Lets say this represents a matrix A of distances (in kilometers) between cities. Note that A is symmetric A(i,j) = A(j,i) and all its diagonal elements are zero. Suppose Vladimir from city i and Petra from city j want to meet up in some third city k (i, j and k are all different). Conscious about their carbon footprint (!), they want k to be as near as possible: specifically the sum of the distances both has to travel should be minimum. Given i and j, write a program in PYTHON that determines what k should be. (In PYTHON you can store the matrix as a list of lists). Do not worry in your program about "reading in" A: Just hard-wire it in to the code. You should read in from the user the two cities (i and j) where Vladimir and Petra live. From your program, calculate the answer for1) i=5, j=112)i=10, j=13
> I think my program is correct, but I'm not sure what they want us to do with the two conditions given above. I also don't know what to enter when I run the program to test these. I am working in Python 3. Thank you!

This is a text mailing list.  By posting as html, you made it pretty 
difficult to make sense out of those two long paragraphs.  Please send 
your emails as text.

I don't know what two particular conditions you're asking about. Could 
you be explicit, instead of just saying 'given above" ?  Lots of 
conditions were given above.

Some comments on your code:
It's customary to name the file with an extension of .py

As written, the code doesn't do anything.  You define two functions, but 
never call them.  At a minimum, you need to use input() to get two 
number strings from the user, and int() to convert each to an integer. 
Then you need to call the distance() function with those two numbers. 
Then you need to test it once by having the user input the numbers 5,112 
and again with 10, 13.  The first case will get an exception of course, 
since there aren't 112 cities.

 > #Python Program to calculate the city equidistant between two given 

That's not what was in the assignment, nor is it what you did.

 > #Sort the cities by arranging the distances from greatest to least
I think you're actually sorting from least to greatest, which is fine. 
But if so, the comment is wrong.

 > #Range is a pre defined 20 by 20 matrix
No, range(0,20) builds a 1 by 20 list, not any kind of matrix.  perhaps 
you meant to refer to cities, which you are building here.

 > #For entry within the matrix if that value happens to be of type 
list, then it will append a value to that list

If you're referring to the cities matrix, all the values are of type 
list, so I'm not sure what you're trying to say here.

 >    for b in cities[i]:
 >        for c in cities[j]:
 >            sums.append(b+c)

No idea what this is supposed to accomplish.  But the code works better 
without it.

 >    sums[i] = 0
 >    sums[j] = 0

By zeroing them, you make them the minimum distance.  Instead you might 
want to make them very large.  I used a million, and that worked.

It's not at all clear to me what the numbers in the original matrix 
represented, since if they were really the tallying of the shortest 
route between each pair of cities, then the answer would already be a 
direct lookup (cities[i][j]).  But if it's the shortest distance between 
two cities that doesn't go near any other city, then this program is set 
up to calculate the shortest route that goes through exactly one 
intermediate city (the 'k' city).  It still is not necessarily the 
shortest route that might go through several intermediates.


More information about the Tutor mailing list