Wyobraź sobie następujące diagramy jako zestawy pionowych rur krzyżujących się.

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

Na schemacie najbardziej po lewej stronie 1i 2przesuwają się po swoich odpowiednich ukośnikach, krzyżują się Xi wychodzą po przeciwnych stronach od miejsca, w którym zaczęli.

To ten sam pomysł na środkowym schemacie, ale |oznacza, że ​​ścieżki się nie krzyżują, więc nic się nie zmienia.

Skrajnej prawej przedstawia schemat bardziej złożona rurka trasowania permutacji 1 2 3 4się 3 1 4 2.

Cel

Twoim celem w tym golfowym wyzwaniu golfowym jest narysowanie tych „schematów trasowania rur” z uwzględnieniem permutacji takiej jak 3 1 4 2. Zwycięży najkrótszy program w bajtach.

Detale

1. Dane wejściowe pochodzą ze stdin jako dowolnej permutacji liczb od 1 do n oddzielonych spacjami, gdzie n jest dodatnią liczbą całkowitą. Możesz założyć, że wszystkie dane wejściowe są dobrze sformułowane.

2. Wyjście ze schematu routingu przechodzi na standardowe wyjście.

   • „Upuszczenie” liczb od 1 do n w kolejności na górze schematu powinno spowodować, że permutacja wejściowa wyjdzie na dole. (Góra i dół to zawsze warstwy ukośników).
   • Schemat nie musi być optymalnie mały. Może to być tyle poziomów, ile to konieczne, o ile jest poprawne.
   • Schemat powinien zawierać tylko znaki \/ X|oraz znaki nowej linii (bez cyfr).
   • |należy zawsze używać na najbardziej oddalonych skrzyżowaniach, ponieważ używanie Xnie ma sensu.
   • Kilka początkowych lub końcowych spacji jest w porządku, pod warunkiem, że schemat jest poprawnie ułożony.

Przykłady

Dane wejściowe 3 1 4 2mogą produkować (tak samo jak powyżej)

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

Dane wejściowe 1mogą produkować

 \
  |
 /
|
 \
  |
 /

Dane wejściowe 3 2 1mogą produkować

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

Dane wejściowe 2 1 3 4 6 5mogą produkować

\ / \ / \ /
 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]

Przyjąłem nieco inne podejście: znajduję wymiany potrzebne do sortowania danych wejściowych, a następnie odwracam je pionowo, aby uzyskać wymiany potrzebne do przekształcenia posortowanej listy w dane wejściowe. Jako dodatkowy bonus tego podejścia, może on przyjąć dowolną listę liczb i podać ścieżkę permutacji, aby zmienić rodzaj danych wejściowych na dane wejściowe.

Przykład:

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

Ulepszenia:

264 -> 261: Przełączana zewnętrzna pętla od do do chwili.

261 -> 259: Używany f%2zamiast (c^m), ponieważ w pythonie operatory arytmetyczne mają wyższy priorytet niż operatory bitowe.

259 -> 252: Przełączana pętla wewnętrzna od do chwili. Połączone ii czmienne.

252 -> 247: Zmieniono kompilację, a następnie odwrócono, aby po prostu budować w odwrotnej kolejności.

247 -> 243: ręcznie dodawano nowe linie zamiast łączenia.

243 -> 227: Przyjęto metodę generowania linii cięcia przez grc (dzięki grc!) I dodano s.

227 -> 224: Przeniesiono generowanie linii ukośnika na wewnętrzną pętlę while, aby usunąć a %4i uratować postać za pomocą rozszerzonego krojenia.

224 -> 222: Usunięto m.

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

220 -> 219: | 1<n-1|-> |~i>-n|(usunięto wiodące miejsce)

219 -> 218: Połączone inicjalizacje o oi si przeniesiony segment do końca.

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

Postawiłem na dość podstawowe podejście, ale okazało się, że było trochę dłużej, niż się spodziewałem. Rozpatruje listę parami i decyduje, czy zamienić każdą parę. Jest to powtarzane dla każdego przecinającego się wiersza, dopóki lista nie pasuje do danych wejściowych.

Przykład:

$ 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

Dziękuję @izlin i @TomHart za wskazanie moich błędów.

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);

Przetestuj tutaj: http://goo.gl/NRsXEj

JavaScript - 395

378 jeśli nie wydrukuję liczb na wydruku, ale wygląda to znacznie lepiej i poprawia czytelność.
Sprawdź to tutaj . (z wersją bez

golfa ) wersja golfowa :

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)

Wyjaśnienie

Najpierw zastępuję dane wejściowe numerem indeksu i zmieniam pierwszy wiersz z wynikami. Na przykład

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

Z tym podstawieniem mogę użyć algorytmu sortowania bąbelkowego, aby posortować 2,4,1,3 do 1,2,3,4, a wykres będzie najkrótszym możliwym, którego szukamy.
Jeśli masz jakieś pomysły, jak mogę zmniejszyć kod, po prostu skomentuj :)

Przykład

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

Kobra - 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]

Działa poprzez przesunięcie każdego elementu na miejsce, zaczynając od lewej. Z tego powodu często generuje absurdalnie dużą (choć nadal poprawną) mapę ścieżki.

Przykłady:

3 1 4 2

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