18
\$\begingroup\$

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
  • 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.

\$\endgroup\$
9
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ You know, the question states, that the output is mostly freeform, so you don't have to keep a specific order of the labels. \$\endgroup\$ – FUZxxl Apr 2 '11 at 8:10
  • \$\begingroup\$ @FUZxxl: It's not the order, it's that the cities were labeled wrong (wrong positions) \$\endgroup\$ – Jesse Millikan Apr 2 '11 at 17:46
  • 1
    \$\begingroup\$ You win. (15 chars) \$\endgroup\$ – FUZxxl Apr 19 '11 at 16:40
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – FUZxxl Apr 19 '11 at 16:44
  • 2
    \$\begingroup\$ Well, I'm glad we had this little talk. \$\endgroup\$ – Jesse Millikan Apr 19 '11 at 16:47
21
\$\begingroup\$

Haskell, 633 characters

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(i`min`m)..ceiling(j`max`n)],"</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
v=head.reads.tail
main=interact$s.map(w.break(=='(')).lines

Rather longish for code-golf, but produces a lovely SVG map: Mr Jones' Route

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


  • 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.
\$\endgroup\$
  • \$\begingroup\$ How about stripping the xmlns stuff? Some viewers don't need it. \$\endgroup\$ – FUZxxl Apr 3 '11 at 11:36
  • 1
    \$\begingroup\$ No browser I have will display the SVG w/o the xmlns declaration. \$\endgroup\$ – MtnViewMark Apr 3 '11 at 16:58
  • \$\begingroup\$ Hm... at least eyes of gnome will do. (Though it isn't a browser) \$\endgroup\$ – FUZxxl Apr 3 '11 at 17:36
12
\$\begingroup\$

Python, 516 476 bytes

#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
for L in sys.stdin.readlines():
 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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – FUZxxl Mar 31 '11 at 19:24
  • 1
    \$\begingroup\$ Sure, that would be fine. It's not a cash prize :) \$\endgroup\$ – Keith Randall Mar 31 '11 at 20:06
  • \$\begingroup\$ Thanl you very much. I am very sorry for making your entry wrong, you get a special price instead. \$\endgroup\$ – FUZxxl Mar 31 '11 at 20:09
6
\$\begingroup\$

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
for L in sys.stdin.readlines():
 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     └──────────────────────────┘
\$\endgroup\$
  • \$\begingroup\$ That one is nice, though it doesn't use the shortest connection possible`between two cities. \$\endgroup\$ – FUZxxl Apr 1 '11 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.