Purposes of this assignment

• To give you more practice pair programming
• To give you some experience with dictionaries and sets
• To give you more practice with writing tests
• To get you started thinking about how to solve problems with programs

General idea of the assignment

Suppose there are a number of "cities," as in Figure 1 below. The distance between any two cities is the standard Euclidian distance, that is, √((x₁-x₂)²+(y₁-y₂)²). There are two problems to be solved.

Figure 1, Cities.	Figure 2. A circuit.	Figure 3. A spanning tree.

Problem 1: Travelling salesman

A travelling salesman wishes to visit every city exactly once, then return to his starting point. (It doesn't matter what city is the starting point.) Such a path is called a circuit, as in Figure 2. However, the salesman also wishes to minimize the total distance that must be travelled.

Problem 2: Telegraph lines

A telegraph company wishes to put telegraph lines between cities, such that every city is connected (however indirectly) to every other city, with no circuits. Such a set of connections is called a spanning tree, as in Figure 3. To keep costs down, the company wishes to minimize the total distance that it must put wires.

(If you don't like telegraphs, call it electric power lines, or road building, or fiber optic cables.)

Solutions from the web

These are classic computer science problems, known as the Travelling Salesman problem and the Minimum Spanning Tree problem. You can find algorithms for solving them on the web, and you are welcome to look at those algorithms. However, I want you use a hill climbing approach, where you start with "any" solution, and try to progressively improve it until you can't improve it any more.

This should require you to think about how to solve the problem, rather than just copying some algorithm you may or may not understand. Your final solution is unlikely to be the optimal (best possible) solution, but that's okay, so long as it isn't obviously terrible.

Specific requirements

Data representation

There will be from 1 to 26 cities, with names "a", "b", "c", etc. Each city will have an x-y location, which is a 2-tuple of floating point numbers, such as (743.02, 215.53), where each number is between 0.0 and 1000.0. When I use the term directory in the function descriptions below, it will refer to a dictionary whose keys are city names and whose values are the corresponding x-y locations.

To represent either a circuit or a spanning tree, use a dictionary whose keys are city names, and whose values are a set of the names of the directly connected cities. In the function descriptions below, I will call this kind of dictionary a road_map. For a circuit, each set will contain exactly two city names; for a spanning tree, each set will contain one or more city names.

While I will require these particular data representations as function parameters and function results, this does not imply that you have to work with these representations as you solve the problems. Python makes it easy to convert from one kind of sequence to another.

Required functions (file cities.py)

def create_cities(how_many)

Given a number between 1 and 26, inclusive, creates that many cities, and returns them as a directory.

def print_cities(directory)

Prints a list of cities, along with their locations. Print only one or two digits after the decimal point.

def create_cycle(directory)

Returns a road_map that describes an initial (probably not very good) cycle.

def create_spanning_tree(directory)

Returns a road_map that describes an initial (probably not very good) spanning tree.

def compute_cost(road_map, directory)

Returns, as a floating point number, the sum of the distances of all the connections in the road_map.

def improve_cycle(road_map, directory)

Tries to modify the road_map to be slightly better (have a lower cost) and returns True if it succeeds, False if no further improvement can be found. This may involve trying many small changes, until one is found that reduces the total cost of the cycle. It is your job to figure out how to do this. (You do not have to return the road_map; since it is an object, any changes you make will be seen in the calling function.)

def improve_spanning_tree(road_map, directory)

Tries to modify the road_map to be slightly better (have a lower cost) and returns True if it succeeds, False if no further improvement can be found. This may involve trying many small changes, until one is found that reduces the total cost of the spanning tree. It is your job to figure out how to do this. (You do not have to return the road_map; since it is an object, any changes you make will be seen in the calling function.)

def find_best_cycle(road_map, directory)

Improves the given road_map until you can find no further improvements. This does not need to be the best possible solution; it only needs to be "reasonably good." (You do not have to return the road_map; since it is an object, any changes you make will be seen in the calling function.)

def find_best_spanning_tree(road_map, directory)

Improves the given road_map until you can find no further improvements. This does not need to be the best possible solution; it only needs to be "reasonably good." (You do not have to return the road_map; since it is an object, any changes you make will be seen in the calling function.)

def print_map(road_map, directory)

Prints, in an easily understandable format, the cities and their connections, along with the cost for each connection and the total cost.

def main()

Creates some number of cities (ask the user how many) and prints them out, creates the "best" cycle and prints it out, and creates the "best" spanning tree and prints it out.

Required tests (file cities_test.py)

All functions, except the main, print_cities, and print_map, should be tested. This includes any additional functions you might write.

TDD, Test Driven Design, really is a good idea. Here is the general approach:

1. Write a stub for each function. (A stub is a function that does nothing or, if it must return a value, returns a value that is unlikely to be correct.)
2. Pick a function--if possible, one that does not depend on any other functions you haven't yet written--and write a test for it. Run the test and make sure it fails.
3. Improve the function just enough to make it pass the test.
4. If the function needs to do more, then expand the test (or add another test) to test the new functionality. Run the test and make sure it fails. Then return to step 3. Repeat as many times as necessary until the function is complete.
5. If any functions remain to be written, return to step 2.

Division of labor

Put both names (yours and your partner's) in a comment at the top of both files. You may, if you wish, put your name in a comment in the major functions you have written; but you will both get the same grade for the assignment.

This assignment has been written to have a common part, and two easily separable problems. You should work with your partner as much as possible; but if you must work apart, one of you should work on the travelling salesman problem, and the other should work on the spanning tree problem.

In the past, some students have tried the following: One partner writes the functions, and the other partner writes the test. Those students have told me, in no uncertain terms, that this is a bad idea. Learn from their mistakes. Whoever writes a function should also write the tests for that function.

Programming hints

• Import random at the top of your program; then number = 1000 * random.random() will give you a floating-point number in the range 0.0 <= number < 1000.0.
• Figure out what happens when you convert a dictionary to a list.
• The % operator (check your textbook) is a good way to print out floating-point numbers, for example, with the format %6.2f.
• ord('a') is 97; chr(97) is 'a'; and similarly for other letters.
• If you haven't yet read my Unit testing and TDD handout (linked to from the course home page), now would be a good time to do so.

Grading

The assignment will be graded on the basis of 100 points total. You and your partner will receive the same grade. Grading will be based on:

• Correctness. We will have our own unit tests, which your functions must pass. This means that (1) the above functions must take parameters and produce results exactly as specified, or our test will fail and cost you points, and (2) your own unit tests should be good enough to catch any errors before we do.
• Style. Use proper indentation (4 spaces) and proper spacing. Use good, self-explanatory variable and function names. Don't repeat code if you can put it in a function and just call the function. Don't use "magic numbers" (unexplained constants in your code); give them names. Try to avoid redundancy (such as the beginner's if better == True).

Due date