20
\$\begingroup\$

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
/ \ / \ / \
\$\endgroup\$
  • 4
    \$\begingroup\$ Great question! I can't believe it's only been two weeks that you joined -- you seem to be everywhere. \$\endgroup\$ – xnor Jul 21 '14 at 23:58
  • \$\begingroup\$ @xnor :D Thanks a bunch. But really I've been spending too much time here... \$\endgroup\$ – Calvin's Hobbies Jul 22 '14 at 0:00
  • \$\begingroup\$ Can an X connect directly to a | the way a / does? To another X? \$\endgroup\$ – xnor Jul 22 '14 at 0:17
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Calvin's Hobbies Jul 22 '14 at 0:20
  • \$\begingroup\$ Can n be larger than 10? \$\endgroup\$ – Οurous Jul 23 '14 at 7:32
4
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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   |
 \ / \ / \ / \ / \
\$\endgroup\$
2
\$\begingroup\$

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
enter image description here enter image description here

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – izlin Jul 23 '14 at 5:24
  • \$\begingroup\$ You are right. Thanks. I looked at @grc's output and thought the numbers were the starting position. Oops. \$\endgroup\$ – JeffSB Jul 23 '14 at 7:55
  • \$\begingroup\$ I might be looking at this wrong, but in both picture you posted, isn't the last row redundant as nothing changes? \$\endgroup\$ – TMH Jul 23 '14 at 11:27
  • \$\begingroup\$ 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. \$\endgroup\$ – JeffSB Jul 23 '14 at 18:44
  • \$\begingroup\$ @izlin - Thanks for noticing this. I fixed this error. \$\endgroup\$ – JeffSB Jul 23 '14 at 22:29
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ (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. \$\endgroup\$ – JeffSB Jul 23 '14 at 22:11
  • \$\begingroup\$ (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? \$\endgroup\$ – JeffSB Jul 23 '14 at 22:18
  • \$\begingroup\$ @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? \$\endgroup\$ – izlin Jul 24 '14 at 5:16
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.