Assignment 15 - Travelling Saleman Problem

You can download this homework and set the permissions with the commands 
      cd ~/public_html
      wget http://www.comp.nus.edu.sg/~gem1501/assignment15.html
      chmod 755 *.html
Outline
The travelling saleman problem asks for the shortest tour to find visit all cities. Or, if formulated as a decision problem, it asks whether there is a tour shorter than a given constant distance visiting all cities.

What has to be done in detail
Within this exercise, it is not a task to find a tour but just to check it. For this a user input is given in form of an alphabetical code for a tour (representing each station by an initial from "A" to "L") and the following should be checked by the evaluating function:
  1. Is every place visited? That should happen.
  2. Is some place visited twice? That should not happen.
  3. What is the length of the tour? Also the distance from the last place to the first has to be counted.
The coordinates are only roughly related to the real position of the palces but should be used for this homework. You might consult an MRT map for a more realistic picture of the subway. Java Script has also associative arrays, this permits to store all data under the first letter of the word it uses as done in this implementation; for "Changi Airport" and "City Hall" the first letter of the second word is taken.
The function "analyzetour" should analyze the given tour. It should print out a report on the tour including the overall distance and all irregularities found like double or not visited places. Furthermore, instead of having a fixed tour in advance, the use should be asked for a tour using the prompt-command. It should be checked that all letters in the input are from "A" to "L" and no nonexisting station is polled. It can be assumed that all entries mrt["A"].visited to mrt["L"].visited are 0 before the calling the function analyzetour; therefore use the "reload" button to call the routine again.
The function "printtour" might used as a model how to access the variables used in this homework. The basic data model is a field "mrt" having entries "A" to "L" such that for each entry there is a record of four values. For example, 
      mrt["A"].name    == "Changi Airport"
      mrt["A"].x       == 9;
      mrt["A"].y       == 4;
      mrt["A"].visited == 0.
Similar entries exist for mrt["B"], mrt["C"], mrt["D"], mrt["E"], mrt["F"], mrt["G"], mrt["H"], mrt["I"], mrt["J"], mrt["K"], mrt["L"]. A function distance calculates the distance between two MRT stations given by their alphabetical code. So distance("A","B") computes the distance between "Changi Airport" and "Buona Vista". One can also use the function printdistance("A","B") to get the value printed out. The distances are rounded 3 decimal digits after the dot.

Java Script starts here.

Java Script ends here.