Draw a Permutation Path

Question

Imagine the following diagrams as sets of vertical criss-crossing tubes.

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

In the leftmost diagram, the 1 and 2 slide down their respective slashes, cross at the X, and come out at opposite sides from where they started.

It's the same idea in the middle diagram, but the | signifies that the paths do not cross, so nothing changes.

The rightmost diagram shows a more complex tube routing that permutes 1 2 3 4 into 3 1 4 2.

Goal

Your goal in this code golf challenge is to draw these "tube routing diagrams" given a permutation such as 3 1 4 2. The shortest program in bytes will win.

Details

1. Input comes from stdin as any permutation of the numbers from 1 to n separated by spaces, where n is a positive integer. You may assume all input is well formed.

2. The routing diagram output goes to stdout.

   • "Dropping" the numbers 1 through n in order into the top of the diagram should result in the input permutation coming out at the bottom. (Top and bottom are always layers of slashes.)
   • The diagram does not need to be optimally small. It may be as many levels as necessary as long as it is correct.
   • The diagram should only contain the characters \/ X| as well as newlines (no numbers).
   • | should always be used on the outermost intersections since using X wouldn't make sense.
   • A few leading or trailing spaces is fine as long as the diagram is all lined up correctly.

Examples

An input of 3 1 4 2 might produce (same as above)

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

An input of 1 might produce

 \
  |
 /
|
 \
  |
 /

An input of 3 2 1 might produce

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

An input of 2 1 3 4 6 5 might produce

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

Answer 1

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]

I took a slightly different approach: I find the swaps necessary to sort the input, then vertically invert that to get the swaps necessary to turn the sorted list into the input. As an added bonus of this approach, it can take an arbitrary list of numbers and give the permutation path to turn the sort of the input into the input.

Example:

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

Improvements:

264 -> 261: Switched outer loop from for to while.

261 -> 259: Used f%2 instead of (c^m), because in python arithmetic operators have higher priority than bitwise operators.

259 -> 252: Switched inner loop from for to while. Combined i and c variables.

252 -> 247: Changed build then reverse to just build in reverse order.

247 -> 243: Added newlines manually, instead of using join.

243 -> 227: Adopted grc's method of slash line generation (thanks grc!) and added s.

227 -> 224: Moved slash line generation to before inner while loop to remove a %4 and save a character by using extended slicing.

224 -> 222: Removed m.

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

220 -> 219: | 1<n-1| -> |~i>-n| (removed leading space)

219 -> 218: Combined initializations of o and s and moved the slice to the end.

Answer 2

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

I went for a fairly basic approach, but it turned out a bit longer than I was hoping. It considers the list in pairs and decides whether or not to swap each pair. This is repeated for every intersecting row until the list matches the input.

Example:

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

Answer 3

HTML JavaScript, 553 419

Thank you to @izlin and @TomHart for pointing out my errors.

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

Test here: http://goo.gl/NRsXEj

Answer 4

Javascript - 395

378 if i don't print the numbers on my output, but it looks much better and improves the readability.
Test it here. (with ungolfed version)

golfed Version:

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)

Explanation

First I substitude the input, with the index number and change the first line with the results. For example

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

With this substitution i can use a bubble-sort algorithm to sort 2,4,1,3 to 1,2,3,4 and the graph will be the shortest possible one we're searching for.
If you have any ideas how i can make the code smaller just comment :)

Example

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

Answer 5

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

It works by moving each element into place starting from the left. Due to this, it will often output a ridiculously large (although still correct) path-map.

Examples:

3 1 4 2

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