Zeichnen Sie einen Permutationspfad

20

Stellen Sie sich die folgenden Diagramme als Sätze vertikaler Kreuzungsrohre vor.

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

In dem äußersten linken Diagramm, das 1und 2nach unten rutscht ihre jeweiligen Schrägstriche, überquert an den X, und kommt an den gegenüberliegenden Seiten , von wo aus sie gestartet.

Es ist die gleiche Idee im mittleren Diagramm, aber das |bedeutet, dass sich die Pfade nicht kreuzen, sodass sich nichts ändert.

Das Diagramm ganz rechts zeigt eine komplexere Rohrführung, 1 2 3 4in die permeiert wird 3 1 4 2.

Tor

Ihr Ziel bei dieser Code-Golf-Herausforderung ist es, diese "Rohrleitungsdiagramme" bei einer Permutation wie z 3 1 4 2. Das kürzeste Programm in Bytes gewinnt.

Einzelheiten

  1. Die Eingabe erfolgt von stdin als Permutation der Zahlen von 1 bis n, die durch Leerzeichen getrennt sind, wobei n eine positive ganze Zahl ist. Sie können davon ausgehen, dass alle Eingaben korrekt sind.
  2. Die Ausgabe des Routing-Diagramms geht auf stdout.

    • Wenn Sie die Zahlen 1 bis n nacheinander oben im Diagramm ablegen, wird die Eingabepermutation unten ausgegeben. (Oben und unten sind immer Schrägstriche.)
    • Das Diagramm muss nicht optimal klein sein. Es können so viele Ebenen wie nötig sein, solange es korrekt ist.
    • Das Diagramm sollte nur die Zeichen \/ X|sowie die Zeilenumbrüche (keine Zahlen) enthalten.
    • |sollte immer an den äußersten Kreuzungen verwendet werden, da die Verwendung Xkeinen Sinn ergibt.
    • Ein paar führende oder nachfolgende Leerzeichen sind in Ordnung, solange das Diagramm korrekt ausgerichtet ist.

Beispiele

Eine Eingabe von 3 1 4 2könnte erzeugen (wie oben)

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

Eine Eingabe von 1könnte produzieren

 \
  |
 /
|
 \
  |
 /

Eine Eingabe von 3 2 1könnte produzieren

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

Eine Eingabe von 2 1 3 4 6 5könnte produzieren

\ / \ / \ /
 X   |   X
/ \ / \ / \
Calvins Hobbys
quelle
4
Gute Frage! Ich kann nicht glauben, dass Sie erst vor zwei Wochen beigetreten sind - Sie scheinen überall zu sein.
xnor
@xnor: D Vielen Dank. Aber ich habe wirklich zu viel Zeit hier verbracht ...
Calvins Hobbys
Kann man Xsich direkt mit einem verbinden, |wie es ein /tut? Zu einem anderen X?
Xnor
1
@xnor Nein , es sollte immer in der sein row of slashes, row of X's and |'s, row of slashes, row of X's and |'s, ... Format.
Calvins Hobbys
Kann ngrößer als 10 sein?
Urous

Antworten:

4

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]

Ich habe einen etwas anderen Ansatz gewählt: Ich finde die zum Sortieren der Eingabe erforderlichen Tauschvorgänge und invertiere sie dann vertikal, um die Tauschvorgänge zu erhalten, die zum Umwandeln der sortierten Liste in die Eingabe erforderlich sind. Als zusätzlichen Vorteil dieses Ansatzes kann eine beliebige Liste von Zahlen verwendet und der Permutationspfad angegeben werden, um die Art der Eingabe in die Eingabe umzuwandeln.

Beispiel:

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

Verbesserungen:

264 -> 261: Äußere Schleife von for nach while umgeschaltet.

261 -> 259: Wird f%2anstelle von verwendet (c^m), da in Python arithmetische Operatoren eine höhere Priorität haben als bitweise Operatoren.

259 -> 252: Innere Schleife von for nach while umgeschaltet. Kombiniert iund cvariabel.

252 -> 247: Der Build wurde geändert und dann in umgekehrter Reihenfolge erstellt.

247 -> 243: Neue Zeilen manuell hinzugefügt, anstatt Join zu verwenden.

243 -> 227: grcs Methode zur Erzeugung von Schrägstrichen (danke grc!) Übernommen und s hinzugefügt.

227 -> 224: Die Erzeugung von Schrägstrichen wurde in die vorinterne while-Schleife verschoben, %4um ein Zeichen zu entfernen und mit Extended Slicing zu speichern.

224 -> 222: m entfernt.

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

220 -> 219: | 1<n-1|-> |~i>-n|(Leerzeichen entfernt)

219 -> 218: Kombinierte Initialisierungen von ound sund verschob das Slice an das Ende.

isaacg
quelle
9

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

Ich habe mich für einen ziemlich einfachen Ansatz entschieden, aber es hat sich als etwas länger herausgestellt, als ich gehofft hatte. Es betrachtet die Liste paarweise und entscheidet, ob jedes Paar getauscht wird oder nicht. Dies wird für jede sich überschneidende Zeile wiederholt, bis die Liste mit der Eingabe übereinstimmt.

Beispiel:

$ 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   |
 \ / \ / \ / \ / \
grc
quelle
2

HTML JavaScript, 553 419

Vielen Dank an @izlin und @TomHart für den Hinweis auf meine Fehler.

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

Testen Sie hier: http://goo.gl/NRsXEj
Bildbeschreibung hier eingeben Bildbeschreibung hier eingeben

JeffSB
quelle
Sie haben einen kleinen Fehler gemacht: Die erste Zeile sollte die sortierten Zahlen sein und die letzte Zeile sollte Ihre Eingabe sein, wie in den obigen Beispielen.
Izlin
Du hast recht. Vielen Dank. Ich habe mir die Ausgabe von @ grc angesehen und dachte, die Zahlen wären die Ausgangsposition. Hoppla.
JeffSB
Vielleicht sehe ich das falsch, aber in beiden Bildern, die Sie gepostet haben, ist die letzte Zeile nicht überflüssig, da sich nichts ändert?
TMH
Ja, du hast recht. Ich wusste, dass dies ein Konsens darüber war, wie ich es tat. Muss aber wohl nicht sein. Ich werde darüber nachdenken. Danke für den Kommentar.
JeffSB
@izlin - Danke, dass du das bemerkt hast. Ich habe diesen Fehler behoben.
JeffSB
1

Javascript - 395

378 wenn ich die zahlen nicht auf meine ausgabe drucke, aber es sieht viel besser aus und verbessert die lesbarkeit.
Teste es hier . (mit 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)

Erläuterung

Zuerst setze ich die Eingabe auf die Indexnummer und ändere die erste Zeile mit den Ergebnissen. Beispielsweise

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

Mit dieser Ersetzung kann ich einen Blasensortierungsalgorithmus verwenden, um 2,4,1,3 bis 1,2,3,4 zu sortieren, und der Graph wird der kürzestmögliche sein, den wir suchen.
Wenn Sie irgendwelche Ideen haben, wie ich den Code verkleinern kann, kommentieren Sie einfach :)

Beispiel

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

Izlin
quelle
(1) Ich sehe, dass Sie das BR-Tag an drei Stellen verwenden und so ein wenig sparen können, indem Sie dies in eine Variable einfügen. Sie könnten wahrscheinlich auch \ n verwenden, seit Sie auf einem PRE ausgegeben haben.
JeffSB
(2) Ich habe verschiedene Möglichkeiten ausprobiert, um mit Golf-JavaScript umzugehen, und habe auch praktische Ein- und Ausgaben. Ich glaube, ich mag meine neueste Methode, die von Ihrer Aufforderung und Warnung inspiriert ist. Ich verwende Aufforderung und Warnung im Code, damit sie in eine Konsole eingefügt werden kann und für jeden funktioniert. Ich habe aber auch eine Webseite mit TEXTAREA und PRE erstellt, um zu zeigen, dass es funktioniert. Die Webseite überschreibt Eingabeaufforderung und Warnung, um TEXTAREA und PRE zu verwenden - also ist es der gleiche Code und es gibt weniger Verwirrung - vielleicht?
JeffSB
@JeffSB Ich habe das <br>Tag und den Textbereich nur auf jsfiddle verwendet, weil es viel besser aussieht. Die Warnung hat keine monospaced Schriftart, also sieht die Ausgabe schlecht aus. In meiner Golfversion verwende ich alert und \ n. Ist Ihre Webseite öffentlich?
Izlin
1

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]

Dabei wird jedes Element von links nach rechts verschoben. Aus diesem Grund wird es oft eine lächerlich große (wenn auch immer noch korrekte) Pfadkarte ausgeben.

Beispiele:

3 1 4 2

\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
 X   X  
/ \ / \ 
|  X  |
\ / \ / 
Οurous
quelle