# Draw a Permutation Path

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

• Great question! I can't believe it's only been two weeks that you joined -- you seem to be everywhere.
– xnor
Jul 21, 2014 at 23:58
• @xnor :D Thanks a bunch. But really I've been spending too much time here... Jul 22, 2014 at 0:00
• Can an X connect directly to a | the way a / does? To another X?
– xnor
Jul 22, 2014 at 0:17
• @xnor No. It should always be in the row of slashes, row of X's and |'s, row of slashes, row of X's and |'s, ... format. Jul 22, 2014 at 0:20
• Can n be larger than 10? Jul 23, 2014 at 7:32

## 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 | \ / \ / \ / \ / \  # Python 2, 218 219220222224227243247252259261264 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.

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.

## 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

• You made one little mistake: the first line should be the sorted numbers and the last line should be your input like in the examples above. Jul 23, 2014 at 5:24
• You are right. Thanks. I looked at @grc's output and thought the numbers were the starting position. Oops. Jul 23, 2014 at 7:55
• I might be looking at this wrong, but in both picture you posted, isn't the last row redundant as nothing changes?
– TMH
Jul 23, 2014 at 11:27
• Yes you are right. I knew this was a consensus of how I did it. But it probably doesn't have to be. I'll think about this. Thanks for the comment. Jul 23, 2014 at 18:44
• @izlin - Thanks for noticing this. I fixed this error. Jul 23, 2014 at 22:29

## 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


• (1) I see that you use the BR tag in a three places, and so you could save a little by putting this in a variable. Also you could probably use \n since your outputting to a PRE. Jul 23, 2014 at 22:11
• (2) I've been trying different ways to deal with golfing JavaScript and also having convenient input and output. I think I like my latest method inspired by your prompt and alert... I use prompt and alert in the code so it can be pasted into a console and it works for anyone. But I also made a webpage with a TEXTAREA and PRE to show it working. The webpage overrides prompt and alert to use the TEXTAREA and PRE - so it's the same code and there is less confusion - maybe? Jul 23, 2014 at 22:18
• @JeffSB I used the <br> tag and textarea only on jsfiddle, because it looks much better. The alert has no monospaced font so the output looks bad. In my golfed Version I use alert and \n. Is your webpage public? Jul 24, 2014 at 5:16

# Cobra - 334 344356360

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