# Help Mr Jones to enjoy his bicycle round-trip

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 (B|C). A is a city's name, B and 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

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.

# J, 357 288

m=:>:>./c=:>1{"1 p=:([:<([:<1-~[:".;._1'|',}:);._1'(',]);._2(1!:1)3
'n c'=:|:o=:p/:12 o.j./"1 c-"1(+/%#)c
C=:<"1 c
L=:u:65+i.#o
g=:<"1;c([:<@|:0.5<.@+[+>@])"1(-~/"2(<@:*]%~i.@>:@])"0([:>./|@-/)"2)>C,"0(1|.C)
echo(u:48+10|i.>:0{m),|:(u:48+10|>:i.1{m),L C}'*'g}m$' ' echo' ',L,.':',.' ',.n  This is just a quick squeezing of the original (see below). A lot of golfing is probably still possible to eliminate lots of useless rank manipulation and boxing. Only caveat: Ruler is just the last digit unlike example output. Edit: Bug fix - Cities had wrong labels (and were not in alpha order on map). Edit 2: Removed all sorts of horseplay and tomfoolery for a savings of 69 characters. Output (Verbatim, from test script): First example: 01234567 1 B 2 ** 3 * * 4 A * 5 * * 6 * * 7 * C 8 * ** 9* ** 0D* A: ACity B: Home C: Wherever D: SomeTown Second example: 012345678901234567890123456789012 1 D F 2 * * *** 3 * ** * * 4 * * ** * 5 * E * 6 * * 7 C * *I 8 ** * ***** 9 * * *H* * 0 ** * ** * 1 ** G* ** 2 A*********B * 3 ** * 4 * J 5 ** * 6 Q * 7 ** * 8 ** K 9 ** * 0P* * 1 * N * 2 * ** * L 3 * ** * ** 4 * ** * ** 5 O* M* A: great bridge B: supermarket C: home D: beach E: park F: little island G: friend's house H: SO building I: forest J: tea-shop K: cinema L: restaurant M: airport N: old castle O: museum of code-golf P: riverside Q: new plaza End Second  Ungolfed original: coords =: > 1 {" 1 parsed =: ([:<([:<[:".;._1'|',}:);._1'(',]);._2 (1!:1)3 center =: (+/%#) coords max =: >:>./ coords angles =: 12 o. j./"1 coords -"1 center ordered =: parsed /: angles paths =: >(],"0(1)|.]) 1 {" 1 ordered path_grid_lengths =: ([:>./|@-/)"2 paths path_grid_interval =: ([:<]%~i.@>:@|)"0 path_grid_lengths path_grid_distances =: -~/"2 paths path_grid_steps =: path_grid_distances ([:<[*>@])"0 path_grid_interval path_grid_points_sortof =: (> 1{"1 ordered) ([:<0.5<.@+[+>@])"0 path_grid_steps path_grid_points =: <"1;([:<>@[,.>@])/"1 path_grid_points_sortof graph_body =: }."1}. (u:65+i.#ordered) (1{"1 ordered) } '*' path_grid_points} max$ ' '

axis_top =: |:(":"0)10|}.i. 1{max
axis_side =: (":"0)10|i. 0{max

echo |:(axis_side) ,"1 axis_top, graph_body
echo ''
echo (u:65+i.#parsed),.':',.' ',.(> 0{"1 ordered)

• You know, the question states, that the output is mostly freeform, so you don't have to keep a specific order of the labels. – FUZxxl Apr 2 '11 at 8:10
• @FUZxxl: It's not the order, it's that the cities were labeled wrong (wrong positions) – Jesse Millikan Apr 2 '11 at 17:46
• You win. (15 chars) – FUZxxl Apr 19 '11 at 16:40
• A comment has to have at least 15 chars. Since I wanted to tell you, that you won my task, and the plain message »You win.« is shorter then 15, I had to add this text. – FUZxxl Apr 19 '11 at 16:44
• Well, I'm glad we had this little talk. – Jesse Millikan Apr 19 '11 at 16:47

import List
c n=n>>=(++" ").show.(*3)
(x&y)l="<text x='"++c[x]++"' y='"++c[y]++"'>"++l++"</text>"
f%p=[a-1,b+2,(a+b)/2]where n=map(f.fst)p;a=minimum n;b=maximum n
s p=concat["<svg xmlns='http://www.w3.org/2000/svg' viewBox='",c[i,m-1,j,n],"'><polygon fill='none' stroke='#c8c' points='",c$snd=<<(sort$map a p),"'/><g font-size='1' fill='#bbb'>",(\x->(x&m$show x)++(i&x$show x))=<<[floor(iminm)..ceiling(jmaxn)],"</g><g font-size='2'>",snd=<<p,"</g></svg>"]where a((x,y),_)=(atan2(x-q)(y-r),[x,y]);[i,j,q,m,n,r]=fst%p++snd%p
w(l,s)=((x,y),(x&y)l)where(x,r)=v s;(y,_)=v r
main=interact\$s.map(w.break(=='(')).lines


Rather longish for code-golf, but produces a lovely SVG map:

Or, if your browser can't handle SVG, a PNG of that image:

• Edit: (648 -> 633) in-line coordinate drawing, and possibly draw more than needed, letting them be clipped by the viewBox; also a few golf-tricks here and there.
• How about stripping the xmlns stuff? Some viewers don't need it. – FUZxxl Apr 3 '11 at 11:36
• No browser I have will display the SVG w/o the xmlns declaration. – MtnViewMark Apr 3 '11 at 16:58
• Hm... at least eyes of gnome will do. (Though it isn't a browser) – FUZxxl Apr 3 '11 at 17:36

## Python, 516 476 bytes

#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
i,j,K=L.find('('),L.find('|'),'%c'%k
n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
H=max(H,h);V=max(V,v);T+=[(K,h,v)];k+=1;print K+':',n
V=V+1&~1
for s in zip(*['%3d'%(i+1)for i in range(H)]):print'   '+''.join(s)
C=H*V*[u'─']
C[0::H]=u'│'*V
C[1::H]=V/2*u'└┌'
C[H-1::H]=V/2*u'┐┘'
C[0:2]=u'┌─'
C[-H:-H+2]=u'└─'
for K,h,v in T:C[v*H-H+h-1]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*H:i*H+H])


(Note: I didn't include the first two lines in the byte count, I consider them "interpreter parameters". But I did charge myself for the utf-8 length of the program in bytes.)

On your second example I produce:

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

11111111112222222222333
12345678901234567890123456789012
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─────────────┐
26└──────────────────────────────┘


Yay, Unicode glyphs!

• Ooo... that's not how i'd like my bicycle trip. Originally, I planned to allow the shortest route between two cities only, but I forgot this restriction. If you agree, I'd like to rewrite the question, so that only direct routes between two cities are allowed. – FUZxxl Mar 31 '11 at 19:24
• Sure, that would be fine. It's not a cash prize :) – Keith Randall Mar 31 '11 at 20:06
• Thanl you very much. I am very sorry for making your entry wrong, you get a special price instead. – FUZxxl Mar 31 '11 at 20:09

## Python, 1074 bytes

Ok, spent way too many bytes (and time) getting reasonable paths to work.

#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
R=1000
i,j,K=L.find('('),L.find('|'),'%c'%k
n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
H=max(H,h);V=max(V,v);T+=[(v*R-R+h-1,K)];k+=1;print K+':',n
for s in zip(*['%3d'%(i+1)for i in range(H+1)]):print'   '+''.join(s)
T.sort()
U=reduce(lambda a,x:a[:-1]+[(a[-1][0],x)]if x/R==a[-1][0]/R else a+[(x,x)],[[(T[0][0],T[0][0])]]+map(lambda x:x[0],T))
C=R*V*[' ']
r=0
for x,y in U:C[x:y]=(y-x)*u'─'
for (a,b),(c,d)in zip(U,U[1:]):
if r:
if d%R>b%R:x=b/R*R+d%R;C[b:x]=(x-b)*u'─';C[x:d:R]=(d-x)/R*u'│';C[x]=u'┐'
else:x=d/R*R+b%R;C[d:x]=(x-d)*u'─';C[b:x:R]=(x-b)/R*u'│';C[x]=u'┘'
else:
if c%R<a%R:x=a/R*R+c%R;C[x:a]=(a-x)*u'─';C[x:c:R]=(c-x)/R*u'│';C[x]=u'┌'
else:x=c/R*R+a%R;C[a:x:R]=(x-a)/R*u'│';C[x:c]=(c-x)*u'─';C[x]=u'└'
r^=1
p=U[0][1];C[p:H]=(H-p)*u'─'
if r:p=U[-1][1];C[p:R*V]=(R*V-p)*u'─'
else:V+=1;C+=[' ']*R;p=U[-1][0]+R;C[p:R*V]=(R*V-p)*u'─';C[p]=u'└'
C[H::R]=u'┐'+u'│'*(V-2)+u'┘'
for p,K in T:C[p]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*R:i*R+H+1])


Makes nice paths, though:

A: SomeTown
B: ACity
C: Wherever
D: Home

12345678
1  ┌─D──┐
2  │    │
3  │    │
4  B───┐│
5      ││
6      ││
7┌─────C│
8│      │
9│      │
10A──────┘


and

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

111111111122222222223333
123456789012345678901234567890123
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─────┘        │
26     └──────────────────────────┘

• That one is nice, though it doesn't use the shortest connection possible`between two cities. – FUZxxl Apr 1 '11 at 14:25