Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his holidays. As he really loves cycling, the length of his route is completely irrelevant, but he dislikes to drive around the landscape without a target. The route he likes is from on city in a straight line to another, without any detour.
As Mr Jones is a passionated code golfer, he wants you to find a program, that plans a round trip for him, given a set of cities. The input has the form
A is a city's name,
C are its coordinates. You may assume, that the coordinate are positive and less than 1000. The data sets for the cities are line-separated. Here is an example, of how an example input might look like:
SomeTown (1|10) ACity (3|4) Wherever (7|7) Home (5|1)
Mr Jones isn't pedantic, he just wants to have a useful program. Thus, you may decide by your self how the output is looking like, as long as it mets these criteria:
- The output is a map of the cities, with the route drawn between them. If anything is correct, the route shouldn't overlap itself and should end where it started
- The coordinates are like in usual programming: (1|1) is in the NW corner. Add kind of a ruler to the maps border, to ease reading it
- The cities names have to be written down on the map, but feel free to use abbreviations which is explained somewhere else on the map
- The map can be both ASCII-art or an image
- Keep the output readable
An output might look like this:
1234567 1 D 2 * * 3 * * 4 B * 5 * * 6 * * 7 * C 8* ** 9* * 10A** A: SomeTown B: ACity C: Wherever D: Home
The program with the smallest char count wins. I don't count parameters to the compiler / interpreter, if they are needed for compiling, but please don't abuse this rule. Usual code golf rules apply.
Here is another testcase. You output doesn't have to match mine, nor do you have to choose the same path as me. The output is drawn by hand and shows a possible output. Input:
home (5|7) supermarket (13|12) park (15|5) new plaza (9|16) friend's house (20|11) old castle (14|21) riverside (1|20) beach (10|1) cinema (21|18) forest (23|7) little island (21|1) museum of code-golf (6|25) airport (18|25) tea-shop (24|14) restaurant (24|22) great bridge (3|12) SO building (25|9)
And this is an example output:
1111111111222222 1234567890123456789012345 1 H* *K 2 * * * * 3 * * * * 4 * * ** * 5 * C * 6 * * 7 A J 8 * * 9 * Q 10 * * 11 * ***E * 12 P B*** * * 13 * * * * 14 * * * N 15 * * * * 16 * D * * 17 * * * * 18* * I * 19* * * * 20G * * * 21 * F * * 22 * ** * O 23 * ** * ** 24 * ** * * 25 L** M** A: home B: supermarket C: park D: new plaza E: friend's house F: old castle G: riverside H: beach I: cinema J: forest K: little island L: museum of code-golf M: airport N: tea-shop O: restaurant P: great bridge Q: SO building
I am not an English native speaker. Feel free to correct my language and grammar, if necessary.