Представьте себе следующие диаграммы как наборы вертикальных пересекающихся трубок.

1 2    1 2    1 2 3 4
\ /    \ /    \ / \ /
 X      |      |   |
/ \    / \    / \ / \
2 1    1 2   |   X   |
              \ / \ /
               X   X
              / \ / \
              3 1 4 2

На самой левой диаграмме 1и 2скользят вниз по соответствующим слешам, пересекаются Xи выходят с противоположных сторон от того места, где они начинались.

Это та же идея на средней диаграмме, но это |означает, что пути не пересекаются, поэтому ничего не меняется.

Крайняя правая диаграмма показывает более сложную маршрутизацию труб, которая 1 2 3 4переходит в 3 1 4 2.

Цель

Ваша цель в этой задаче для игры в гольф кода состоит в том, чтобы нарисовать эти «диаграммы маршрутизации труб» с учетом такой перестановки, как 3 1 4 2. Самая короткая программа в байтах победит.

Детали

1. Входные данные поступают из stdin как любая перестановка чисел от 1 до n, разделенных пробелами, где n - положительное целое число. Вы можете предположить, что все входные данные правильно сформированы.

2. Вывод диаграммы маршрутизации идет в стандартный вывод.

   • «Сброс» чисел от 1 до n по порядку в верхнюю часть диаграммы должен привести к тому, что входная перестановка выходит внизу. (Верх и низ всегда являются слоями слеша.)
   • Диаграмма не должна быть оптимально маленькой. Это может быть столько уровней, сколько необходимо, если это правильно.
   • Диаграмма должна содержать только символы \/ X|и символы новой строки (без цифр).
   • |всегда следует использовать на самых внешних пересечениях, так как использование Xне имеет смысла.
   • Несколько начальных или конечных пробелов в порядке, если диаграмма правильно выстроена.

Примеры

Ввод 3 1 4 2может производить (так же, как выше)

 \ / \ /
  |   | 
 / \ / \
|   X   |
 \ / \ /
  X   X 
 / \ / \

Вклад 1может производить

 \
  |
 /
|
 \
  |
 /

Вклад 3 2 1может производить

 \ / \
  X   |
 / \ /
|   X
 \ / \
  X   |
 / \ /

Вклад 2 1 3 4 6 5может производить

\ / \ / \ /
 X   |   X
/ \ / \ / \

Python 2, 218 219 220 222 224 227 243 247 252 259 261 264

l=map(int,raw_input().split())
f=n=len(l)
o=s=n*' \ /'
while f+n%2:
 f-=1;i=f+n&1;a=s[2*i:][:2*n]+'\n|   '[::2-i]
 while~i>-n:a+='|X'[l[i+1]<l[i]]+'   ';l[i:i+2]=sorted(l[i:i+2]);i+=2
 o=a+f%2*'|'+'\n'+o
print o[:-2*n]

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

Пример:

$ python sort_path.py <<< '3 1 4 5 9 2 6 8 7'
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   |   |   |   |   
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   |   |   |   |   
 \ / \ / \ / \ / \
  |   |   |   |   |
 / \ / \ / \ / \ /
|   X   |   |   X   
 \ / \ / \ / \ / \
  |   X   |   X   |
 / \ / \ / \ / \ /
|   |   X   X   |   
 \ / \ / \ / \ / \
  X   |   X   |   |
 / \ / \ / \ / \ /
|   |   |   |   X   
 \ / \ / \ / \ / \

Улучшения:

264 -> 261: переключил внешний цикл с на на время.

261 -> 259: используется f%2вместо (c^m), потому что в python арифметические операторы имеют более высокий приоритет, чем побитовые операторы.

259 -> 252: переключил внутренний цикл с на на время. Совмещенные iи cпеременные.

252 -> 247: Изменили сборку, затем перевернули, чтобы построить только в обратном порядке.

247 -> 243: добавлены новые строки вручную, вместо использования объединения.

243 -> 227: Принят метод генерации линии слеша от grc (спасибо grc!) И добавил s.

227 -> 224: перемещена генерация линии слеша до внутреннего цикла while для удаления %4и сохранения символа с использованием расширенного среза.

224 -> 222: Удалено m.

222 -> 220: f%2+n%2->f+n&1

220 -> 219: | 1<n-1|-> |~i>-n|(удалено начальное пространство)

219 -> 218: Комбинированные инициализации oи sи переместить срез до конца.

Python, 290

def g(o,u=1):
 s=['|']*o
 for i in range(o,n-1,2):v=r[i+1]in a[:a.index(r[i])]*u;s+=['|X'[v]];r[i:i+2]=r[i:i+2][::1-2*v]
 print'  '*(1-o)+'   '.join(s+['|']*(o^n%2))*u+'\n'*u+(' / \\'*n)[2*o:][:n*2]
a=map(int,raw_input().split())
n=len(a)
r=range(1,n+1)
o=1
g(1,0)
g(0)
while r!=a:g(o);o^=1

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

Пример:

$ python path.py
5 3 8 1 4 9 2 7 6
 \ / \ / \ / \ / \
  |   |   |   X   |
 / \ / \ / \ / \ /
|   X   X   X   X
 \ / \ / \ / \ / \
  X   X   X   X   |
 / \ / \ / \ / \ /
|   X   X   |   X
 \ / \ / \ / \ / \
  X   X   X   |   |
 / \ / \ / \ / \ /
|   |   |   X   |
 \ / \ / \ / \ / \

HTML JavaScript, 553 419

Спасибо @izlin и @TomHart за указание на мои ошибки.

p=prompt();b=p.split(" "),l=b.length,d=l%2,o="",s=["","","\\/"],n="\n",a=[];for(i=0;i<l;i++){a[b[i]-1]=i+1;s[1]+=" "+s[2][i%2];s[0]+=" "+s[2][(i+1)%2];o+=" "+(i+1)}s[1]+=n,s[0]+=n;o+=n+s[1];f=1,g=2;do{var c="";for(var i=(f=f?0:1);i<l-1;i+=2)if(a[i]>a[i+1]){c+="  x ";g=2;t=a[i];a[i]=a[i+1];a[i+1]=t;}else c+="  | ";if(g==2){o+=(d?(f?"| "+c:c+"  |"):(f?"| "+c+"  |":c))+n;o+=(s[f]);}}while(--g);o+=" "+p;alert(o);

Проверьте здесь: http://goo.gl/NRsXEj

Javascript - 395

378, если я не печатаю числа на моем выходе, но это выглядит намного лучше и улучшает удобочитаемость.
Проверьте это здесь . (с негольфированной версией) версия для

гольфа:

a=prompt(),n=a.split(" "),l=n.length,k=[],s="",i=1;for(j=0;j<l;j++){k[n[j]-1]=j+1;s+=" "+(j+1)}s+="\n";while(i++){for(j=0;j<l;j++)s+=i%2?j%2?" \\":" /":j%2?" /":" \\";for(z=0,y=0;z<l-1;z++)if(k[z]>k[z+1])y=1;if(y==0&&i!=2)break;s+="\n";for(m=i%2;m<l;m+=2){s+=i%2&&m==1?"|":"";if(k[m]>k[m+1]){[k[m],k[m+1]]=[k[m+1],k[m]];s+=i%2?"   X":"  X "}else{s+=i%2?"   |":"  | "}}s+="\n"}s+="\n "+a;alert(s)

объяснение

Сначала я подставляю ввод с порядковым номером и изменяю первую строку с результатами. Например

3 1 4 2
v v v v substitude with
1 2 3 4

so the first line will become:
1 2 3 4
v v v v
2 4 1 3

sorting 1,2,3,4 to 3,1,4,2 is equivalent to 2,4,1,3 to 1,2,3,4

С помощью этой замены я могу использовать алгоритм сортировки пузырьков, чтобы отсортировать от 2,4,1,3 до 1,2,3,4, и график будет кратчайшим, который мы ищем.
Если у вас есть идеи, как сделать код меньше, просто прокомментируйте :)

пример

input: 3 4 2 1 7 5 6
output:
 1 2 3 4 5 6 7
 \ / \ / \ / \
  X   |   |   | 
 / \ / \ / \ /
|   X   |   X
 \ / \ / \ / \
  X   X   X   | 
 / \ / \ / \ /
|   X   |   |
 \ / \ / \ / \
 3 4 2 1 7 5 6

Кобра - 334 344 356 360

class P
    def main
        a,o,n=CobraCore.commandLineArgs[1:],['/','\\'],0
        c,l=a.count,a.sorted
        while (n+=1)%2or l<>a
            p,d='',(~n%4+4)//3
            for i in n%2*(c+1-c%2),p,o=p+o[1]+' ',[o.pop]+o
            for i in 1+d:c-n%2*c:2
                z=if(l[:i]<>a[:i],1,0)
                l.swap(i-z,i)
                p+=' ['|X'[z]]  '
            print[['','| '][d]+[p,p+'|'][d^c%2],p][n%2][:c*2]

Он работает, перемещая каждый элемент на место, начиная слева. Из-за этого он часто будет выводить смехотворно большую (хотя все еще правильную) карту путей.

Примеры:

3 1 4 2

\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ /