Помогите мистеру Джонсу насладиться велосипедным путешествием

18

Мистер Джонс хочет совершить поездку в оба конца на своем велосипеде. Он хочет посетить несколько городов в произвольном порядке, но его маршрут не должен пересекать его сам, так как он ненавидит быть в одном и том же месте дважды в отпуске. Поскольку он действительно любит кататься на велосипеде, длина его маршрута совершенно не имеет значения, но он не любит ездить по ландшафту без цели. Маршрут, который ему нравится, идет по городу по прямой линии в другой, без объездов.

Поскольку мистер Джонс - увлеченный игрок в код, он хочет, чтобы вы нашли программу, которая планирует для него поездку туда и обратно, учитывая множество городов. Вход имеет форму A (B|C). Aэто название города Bи Cего координаты. Вы можете предположить, что координаты положительные и меньше 1000. Наборы данных для городов разделены линией. Вот пример того, как может выглядеть пример ввода:

SomeTown (1 | 10)
ACity (3 | 4)
Везде (7 | 7)
Дом (5 | 1)

Мистер Джонс не педантичен, он просто хочет иметь полезную программу. Таким образом, вы можете сами решить, как будет выглядеть результат, если он соответствует следующим критериям:

  • Результатом является карта городов с маршрутом, проведенным между ними. Если что-то правильно, маршрут не должен перекрывать себя и должен заканчиваться там, где он начался
  • Координаты такие же, как в обычном программировании: (1 | 1) находится в северо-западном углу. Добавьте вид линейки к границе карты, чтобы облегчить ее чтение
  • Названия городов должны быть записаны на карте, но не стесняйтесь использовать сокращения, которые объясняются где-то еще на карте
  • Карта может быть как ASCII-art, так и изображением
  • Держите вывод читабельным

Вывод может выглядеть так:

  1234567
 1 D  
 2 * * 
 3 * * 
 4 Б *
 5 * *
 6 * *
 7 * С
 8 * ** 
 9 * *   
10A **

A: SomeTown
B: ACity
C: везде
D: Домой

Программа с наименьшим количеством символов выигрывает. Я не считаю параметры компилятору / интерпретатору, если они необходимы для компиляции, но, пожалуйста, не злоупотребляйте этим правилом. Обычный код правила гольфа применяются.

Вот еще один тестовый пример. Ваш вывод не должен совпадать с моим, и вы не должны выбирать тот же путь, что и я. Вывод отрисовывается вручную и показывает возможный вывод. Входные данные:

дом (5 | 7)
супермаркет (13 | 12)
парк (15 | 5)
Новая площадь (9 | 16)
дом друга (20 | 11)
старый замок (14 | 21)
берег реки (1 | 20)
пляж (10 | 1)
кинотеатр (21 | 18)
лес (23 | 7)
маленький остров (21 | 1)
музей код-гольфа (6 | 25)
аэропорт (18 | 25)
чайный магазин (24 | 14)
ресторан (24 | 22)
великий мост (3 | 12)
SO здание (25 | 9)

И это пример вывода:

           1111111111222222
  1234567890123456789012345
 1 Н * * К    
 2 * * * *   
 3 * * * *   
 4 * * ** *   
 5 * С *   
 6 * *   
 7 AJ  
 8 * *  
 9 * Q
10 * *
11 * *** E *
12 ПБ *** * * 
13 * * * * 
14 * * * N 
15 * * * * 
16 * Д * * 
17 * * * * 
18 * * I * 
19 * * * * 
20G * * * 
21 * F * *
22 * ** * O 
23 * ** * **  
24 * ** * *    
25 л ** м **

Дом
B: супермаркет
C: парк
D: новая площадь
E: дом друга
F: старый замок
G: берег реки
H: пляж
Я: кино
J: лес
К: маленький остров
L: музей код-гольфа
М: аэропорт
N: чайный магазин
O: ресторан
П: великий мост
Q: ТАК здание

Я не носитель английского языка. Не стесняйтесь исправлять мой язык и грамматику, если это необходимо.

code-golf ascii-art graph-theory graphical-output FUZxxl
источник

Ответы:

9

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

Это просто быстрое сжатие оригинала (см. Ниже). Много игры в гольф, вероятно, все еще возможно, чтобы устранить множество бесполезных манипуляций ранга и бокса.

Единственное предостережение: линейка - это просто последняя цифра в отличие от примера вывода.

Изменить: Исправление ошибки - Города имели неправильные метки (и не были в альфа-порядке на карте).

Редактировать 2: Убраны всевозможные скачки и дурачество для экономии 69 персонажей.

Вывод (дословно, из тестового скрипта):

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

Не раскрученный оригинал:

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)
Джесси Милликен
источник
Вы знаете, в вопросе говорится, что выходные данные в основном произвольной формы, поэтому вам не нужно соблюдать определенный порядок меток.
FUZxxl
@FUZxxl: Это не порядок, это то, что города были помечены неправильно (неправильные позиции)
Джесси Милликен
1
Ты победил. (15 символов)
FUZxxl
2
Комментарий должен содержать не менее 15 символов. Так как я хотел сказать вам, что вы выиграли мое задание, и простое сообщение «Вы выиграли.» Короче 15, мне пришлось добавить этот текст.
FUZxxl
2
Что ж, я рад, что мы немного поговорили.
Джесси Милликен
21

Хаскелл, 633 персонажа

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

Довольно длинноват для код-гольфа, но создает прекрасную карту SVG: Путь мистера Джонса

Или, если ваш браузер не может обработать SVG, PNG этого изображения: Путь мистера Джонса

  • Редактировать: (648 -> 633) линейное координатное рисование и, возможно, рисовать больше, чем нужно, позволяя им обрезаться с помощью viewBox; также несколько уловок гольфа здесь и там.
MtnViewMark
источник
Как насчет удаления материала xmlns? Некоторым зрителям это не нужно.
FUZxxl
1
Ни один мой браузер не будет отображать SVG без декларации xmlns.
MtnViewMark
Хм ... хотя бы глаза гнома подойдут. (Хотя это не браузер)
FUZxxl
12

Python, 516 476 байт

#!/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])

(Примечание: я не включил первые две строки в число байтов, я считаю их «параметрами интерпретатора». Но я взял плату за длину программы utf-8 в байтах.)

На вашем втором примере я произвожу:

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└──────────────────────────────┘

Уу, символы Юникода!

Кит Рэндалл
источник
Ооо ... это не то, как я хотел бы мою поездку на велосипеде. Первоначально я планировал разрешить кратчайший маршрут только между двумя городами, но я забыл об этом ограничении. Если вы согласны, я бы хотел переписать вопрос, чтобы разрешались только прямые маршруты между двумя городами.
FUZxxl
1
Конечно, это было бы хорошо. Это не денежный приз :)
Кит Рэндалл
Спасибо вам большое. Мне очень жаль, что вы ошиблись при вводе, вместо этого вы получаете специальную цену.
FUZxxl
6

Python, 1074 байта

Хорошо, потрачено слишком много байтов (и времени), чтобы найти разумные пути для работы.

#!/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])

Делает хорошие пути, хотя:

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


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

и

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     └──────────────────────────┘
Кит Рэндалл
источник
Это хорошо, хотя он не использует кратчайшее соединение между двумя городами.
FUZxxl