16

Inspiriert von Fibonacci-Domino-Kacheln geht es bei diesem Problem darum, ASCII-Kunst zu generieren, die eine andere berühmte kombinatorische Sequenz darstellt.

Ein n-stufiges Gebirgsdiagramm ist eine Zeichnung einer Bergkette, in der genau n '/' und n '\' Zeichen verwendet werden, sodass die Zeichen eine durchgehende Kurve zeichnen, die niemals unter ihre ursprüngliche "Höhe" abfällt. Beispielsweise,

   /\/\
/\/    \

und

   /\
/\/  \/\

sind beide 4-Stufen-Bergdiagramme, aber

/\  /\/\
  \/

ist nicht.

Eingang

Das Programm sollte eine Ganzzahl n von stdin oder als Parameter für eine Funktion akzeptieren .

Ausgabe

Drucken Sie alle n- stufigen Bergdiagramme nach Standard aus. Die Diagramme können in beliebiger Reihenfolge angezeigt werden, müssen jedoch durch Leerzeichen voneinander getrennt sein. Sie können entscheiden, ob verschiedene Diagramme horizontal, vertikal usw. ausgegeben werden sollen.

Wie beim Domino-Kachelproblem können Sie beliebige Leerzeichen verwenden. Dies schließt zusätzliche Zeilenumbrüche vor oder nach der Druckausgabe ein.

Beispiel

Einige Beispiele für gültige Ausgaben für n = 3:

Gültige Ausgabe A:

                                        /\
         /\             /\             /  \    /\/\
/\/\/\  /  \/\       /\/  \           /    \  /    \

Gültige Ausgabe B:

   /\
/\/  \

 /\/\
/    \

/\/\/\   

  /\
 /  \
/    \

 /\
/  \/\

Gültige Ausgabe C:

  /\
 /  \       /\
/    \   /\/  \
                  /\/\
 /\              /    \
/  \/\   /\/\/\

Das ist Code Golf; kürzestes Programm (in Bytes) gewinnt.

code-golf ascii-art combinatorics Matt Noonan
quelle

Wenn Sie "Sie können entscheiden, ob verschiedene Diagramme horizontal, vertikal usw. ausgegeben werden sollen", können sich die Gebirgszüge selbst seitwärts befinden?

18.

Die Bergketten selbst sollten nicht seitlich sein. Der leere Himmel zwischen den Gipfeln trägt meiner Meinung nach zur Herausforderung bei.

Matt Noonan

Können einige Bereiche mehrmals vorkommen?

stolzer Haskeller

@MattNoonan Sie haben Recht, das horizontale Drucken der Bergketten war definitiv schwierig.

Xnor

@stolz-haskeller Es sollte jeweils einmal sein.

Matt Noonan

10

Python 2: 151 Zeichen

N=2*input()
for i in range(2**N):
 L=[];c=1;exec"b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\/'[b];i=i/2*(c>0);"*N
 for x in(c==1)*zip(*L):print"".join(x)

#Output for n=3:




  /\  
 /  \ 
/    \




 /\/\ 
/    \




   /\ 
/\/  \




 /\   
/  \/\





/\/\/\

Wow, das ist ein Durcheinander.

Die erste Idee besteht darin, die Zahlen 0 to 2**N-1zu verwenden, um alle Sequenzen von NAufwärts- und Abwärtsbewegungen in ihren Bits zu codieren . Wir lesen diese Bits einzeln ab, indem wir sie wiederholt %2und /2in einer execSchleife durchlaufen.

Wir speichern das laufende Gebirge seitwärts in einer transponierten Liste von Zeichenketten L. Jedes Mal, wenn wir eine neue Zeile mit Leerzeichen erzeugen, wird ein Leerzeichen in der neuen Zeile durch ersetzt/ oder \abhängig davon ersetzt, ob eine Aufwärts- oder eine Abwärtsbewegung stattgefunden hat.

Der Index dieses Raums sind cLeerzeichen vom Ende, wobei cdie Laufhöhe ist. Wenn man es von vorne macht, werden die Berge auf den Kopf gestellt. Wir verschieben es weiter, indem wir bAufwärts- und Abwärtsbewegungen ausrichten und erhalten [b-c]. Wenn Sie cbei 1 anstatt bei 0 beginnen, wird ein Fehler behoben, der nur einmal auftritt.

Um Fälle zu eliminieren, in denen cEinbrüche unter dem Startwert liegen 1, setzen wir in diesem Fall iauf 0, wodurch alle weiteren Bewegungen nach unten verlaufen und cnegativer werden. Dann, wenn wir prüfen, ob um cgeendet hat 1, prüfen wir auch, ob cjemals darunter gefallen ist. Wir haben nur printdie Bergkette wennc ist 1.

Drucken machen wir zip(*L) transponieren den Bereich von vertikal nach horizontal und drucken jede verbundene Zeichenfolge. Viele Probleme bei dieser Antwort sind darauf zurückzuführen, dass Python Zeichenfolgen als unveränderlich behandelt. Daher haben wir sie als Listen von Zeichen bearbeitet und sie nur zum Drucken zu Zeichenfolgen zusammengefügt.

Vielen Dank an @flornquake für Hilfe und Verbesserungen.

xnor
quelle

Sie müssen ' 'statt verwenden, " "wenn Sie eine Schleife verwenden möchten exec. :) Übrigens, du musst dem Backslash nicht entkommen.

Flornquake

@flornquake Ich habe vergessen zu schreiben. Ich habe ' 'versucht, die Zeichenfolge durch Anführungszeichen durch eine Variable zu ersetzen. Dies ergab immer noch einen Index außerhalb des for _ in[0]*N:exec("b=i%2;c+=2*b-1;L+=[[" "]*N];L[-1][b-c]='\\/'[b];i=i//2*(c>0);")

zulässigen

Ich meinte, Sie müssen schreiben exec("b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\\/'[b];i=i//2*(c>0);"), dh die inneren Anführungszeichen müssen sich von den äußeren unterscheiden.

Flornquake

@flornquake Wow, ich fühle mich albern, ich habe ein paar Anführungszeichen geändert, aber nicht das andere. Vielen Dank!

Xnor

7

APL (88)

{{⍉↑'\/'[1+⍵=1]/⍨¨¯1+2×K=⊂⌽⍳⌈/K←(⍵≠1)++\⍵}¨Z/⍨{(0=+/⍵)∧∧/0≤+\⍵}¨Z←↓⍉¯1+2×(N/2)⊤⍳2*N←2×⍵}

Ausgabe für n=3:

      {{⍉↑'\/'[1+⍵=1]/⍨¨¯1+2×K=⊂⌽⍳⌈/K←(⍵≠1)++\⍵}¨Z/⍨{(0=+/⍵)∧∧/0≤+\⍵}¨Z←↓⍉¯1+2×(N/2)⊤⍳2*N←2×⍵}3
 /\/\/\     /\    /\      /\/\     /\   
         /\/  \  /  \/\  /    \   /  \  
                                 /    \

Erläuterung:

(N/2)⊤⍳2*N←2×⍵: Erhalte ein Bitfeld für jede Zahl von 0bis 2^⍵.
Z←↓⍉¯1+2×: multiplizieren Sie mit 2 und subtrahieren Sie 1, wobei Sie 1für auf und -1ab geben. Speichern Sie einen Vektor von Vektoren, wobei jeder Vektor die Darstellung für eine Zahl enthält, in Z.
{... }¨Z: für jedes Element von Z:
- ∧/0≤+\⍵: Überprüfen Sie, ob die laufende Summe niemals unterschritten wird 0 (nicht unter den Boden geht),
- (0=+/⍵): und dass die Gesamtsumme ist 0(endet wieder auf Bodenniveau).
{... }¨Z/⍨: Wählen Sie die Elemente aus, Zfür die dies zutrifft. Für jeden von ihnen:
- K←(⍵≠1)++\⍵: Finde die Höhe für jedes Zeichen und speichere in K. Heben Sie jeweils \eine an, damit sie /richtig mit der s übereinstimmen. Das macht die Bodenhöhe 1.
- ¯1+2×K=⊂⌽⍳⌈/K: Erstellen Sie für jede Spalte eine Liste [1..max(K)]und markieren Sie die Position des Zeichens in dieser Spalte mit 1und den Rest mit -1. (Replizieren mit -1 füllt diese Position mit einem Leerzeichen.)
- '\/'[1+⍵=1]/⍨¨: Finden Sie das richtige Zeichen für jede Spalte und replizieren Sie es anhand der Liste für diese Spalte.
- ⍉↑: Verwandle das Ergebnis in eine Matrix und lege es mit der rechten Seite nach oben

Marinus
quelle

Okay, eine horizontale!

Matt Noonan

2

Python, 261 241 236 Zeichen

import itertools as I
n=input()
S={}
for q in I.permutations((-1,1)*n):
 s=0;B=[[' ']*n*2 for _ in range(n+2)];o=0
 for i in q:
    B[n-s+(i==-1)][o]=' /\\'[i];s+=i;o+=1
    if s<0:break
 else:
    for l in (B,[])[q in S]:print''.join(l)
 S[q]=1

Es beginnt eine Weile zu dauern n=5und bis ...

$ echo 1 | py mountrange.py

/\



Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 2 | py mountrange.py


/\/\



 /\
/  \



Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 3 | py mountrange.py



/\/\/\




   /\
/\/  \




 /\
/  \/\




 /\/\
/    \



  /\
 /  \
/    \



Laxori@Laxori-PC /cygdrive/c/Programmin
$ echo 4 | py mountrange.py




/\/\/\/\





     /\
/\/\/  \





   /\
/\/  \/\





   /\/\
/\/    \




    /\
   /  \
/\/    \





 /\
/  \/\/\





 /\  /\
/  \/  \





 /\/\
/    \/\





 /\/\/\
/      \




    /\
 /\/  \
/      \




  /\
 /  \
/    \/\




  /\
 /  \/\
/      \




  /\/\
 /    \
/      \



   /\
  /  \
 /    \
/      \

Claudiu
quelle

2

JavaScript (ES6) 159 163

Genau wie meine Antwort für Fibonacci Domino Tiling untersuche ich alle Sequenzen von n + n Bits, wobei 1 ein '/' und 0 ein '\' markiert (nur für die Ausgabe wird später '2' hinzugefügt, um eine neue Zeile zu markieren). . Während ich das ASCII-Muster aufbaue, überprüfe ich den Kontostand - gleiche Zahlen von 0 und 1 und nie unter die Startgrundlinie - und gebe aus, was den Regeln entspricht.

Die Ausgabe erfolgt mit 'alert', was für JS-Codegolf Standard ist, aber ziemlich nervig und möglicherweise gegen die Regeln verstößt. Mit console.log wird die Zeichenanzahl auf 165 gesetzt.

F=n=>{
  for(i=0;++i<1<<n+n;l||alert((o+'').replace(/,\d?/g,r=>'\\/\n '[r[1]||3])))
    for(p=l=o=[],j=i;l+1&&p++-n-n;j/=2)
      b=j&1,
      l-=1-b-b,
      (o[k=b+n-l]=o[k]||[2])[p]=b;
}

Weniger golfen

F=n=>{
  m = n+n
  outer:
  for (i=1; i < 1<<m; i+=2)
  {
    o=[]
    l=0;
    p=1;
    for (j = 1; j <1<<m; j+=j,p++)
    {
      if (i&j)
      {
        q=o[n-l]||[]
        q[p]=1;
        o[n-l]=q
        ++l;
      }
      else
      {
        --l;
        if (l<0) continue outer;
        q=o[n-l]||[]
        q[p]=0;
        o[n-l]=q
      }
    }
    if (l==0) console.log(o.join('\n').replace(/,\d?/g,r=>'\\/'[r[1]]||' '));
  }
}

Test in der FireFox / FireBug-Konsole.

F(4)

Ausgabe

   /\
  /  \
 /    \
/      \ 

  /\/\
 /    \
/      \ 

    /\
 /\/  \
/      \ 

    /\
   /  \
/\/    \ 

  /\
 /  \/\
/      \ 

 /\/\/\
/      \ 

   /\/\
/\/    \ 

 /\  /\
/  \/  \ 

     /\
/\/\/  \ 

  /\
 /  \
/    \/\ 

 /\/\
/    \/\ 

   /\
/\/  \/\ 

 /\
/  \/\/\ 

/\/\/\/\

edc65
quelle

Neugierig, ob es einen bestimmten Grund gibt, den Sie schreiben -b-bund -n-nstattdessen -2*b?

Steve Bennett

@SteveBennett kein Grund. Manchmal ist dieses Muster kürzer, aber diesmal nicht (zum Beispiel:2*b+1 -> b-~b)

edc65

1

CJam, 84 Bytes

q~:Q{Q[XW]*mr1\{\_@+}%_{*}*{(\{_Q\-)S*@2$m0<" /""\\"?+QS*+Q)<\}%);z{N\++}*o}{;}?1}g

Beachten Sie, dass dieses Programm die Berge in einer Endlosschleife ausgibt, sodass der Online-Interpreter Ihnen nicht weiterhilft. Rufen Sie in der Befehlszeile mit

java -jar cjam-0.6.2.jar mountain.cjam <<< 5

oder um es online zu versuchen

q~:Q{Q[XW]*mr1\{\_@+}%_{*}*{(\{_Q\-)S*@2$m0<" /""\\"?+QS*+Q)<\}%);z{N\++}*o}{;}?}fZ

und drücke einfach ein paar Mal hintereinander auf die Schaltfläche "Ausführen" und stelle dir vor, die Ausgabe sei verkettet.

Die Grundidee ist, dass wir wissen, dass ein Gebirgszug der Größe Q Q von jedem Aufwärts- und Abwärtsübergang hat.

 Q[XW]*mr                                   #shuffled list of Q 1s and -1s
1        {\_@+}%                            #height map after each transition
                _{*}*                       #if it passes through 0 it's invalid

Wenn es gültig ist, drucken wir es, wenn nicht, entfernen wir es aus dem Stapel, damit es nicht überläuft.

Die Druckroutine erstellt im Grunde genommen jede Spalte als Q-Höhen-Leerzeichen, dann das Symbol, dann genügend Leerzeichen, um Q + 1 Gesamtzeichen zu erreichen, und dann transponieren und drucken wir die Zeilen mit Zeilenumbrüchen dazwischen.

z{N\++}*o                                   #transpose, insert newlines, print

Paradigmensort
quelle

Während ich daran arbeitete, wurde die Frage geklärt, dass die Berge jeweils einmal gedruckt werden müssen. Das erfordert einige Überlegungen und wahrscheinlich mehr Charaktere: /

paradigmsort

0

C 179

ohne unnötige Leerzeichen.

Eine ähnliche Strategie wie bei edc65. Ich durchlaufe alle n*2-Bit-Binärwerte unter Berücksichtigung von /= 1 und \= 0.

Ich formatiere eine einzelne Zeichenfolge, die nZeilenumbrüche für alle n*3Zeichen enthält. Wie geschrieben, enthält die Zeichenfolge 1000 Zeichen, daher wird normalerweise viel Leerzeichen nach dem Berg gedruckt. (Dies kann durch Hinzufügen s[n*n*3]=0vor dem behoben werden puts.) Auf jeden Fall ermöglicht dies mir, den gesamten Berg mit einem einzigen auszugebenputs nachdem überprüft habe, ob er den Regeln entspricht.

Ich werde versuchen, es in eine Funktion umzuwandeln und forspäter auf eine einzelne Schleife zu reduzieren .

i,n,x,y,q,r;
main(){
  scanf("%d",&n);
  for(i=1<<n*2;i--;){                              //run though all n*2-digit binary numbers
    char s[]={[0 ...999]=32};                      //fill an array with spaces. This syntax is allowed by GCC
    y=n;                                           //start y one square below the grid (note: r is initialised to 0 by default.)
    for(x=n*2;x--;)                                //for each digit of i
      q=i>>x&1,
      y+=q+r-1,                                    //move up if the current and last digit are 0, down if they are 1, and stay on the same line if they are different.
      y<n?s[y*n*3]=10,s[y*n*3+x+1]=92-45*q:(x=0),  //if y is within the grid, put a newline (ASCII 10)at the beginning of the row and write \ or / (ASCII 92 or 47) to the correct square. Otherwise abort the x loop.
      r=q;                                         //store the current bit of i to r as it will be needed on the next iteration 
    n-1-y||puts(s);                                //if y is on the bottom row of the grid, output the mountain 
  }
}

Ausgabe (beachte die enorme Menge an Leerzeichen rechts)

Level River St
quelle

0

Haskell, 140 Bytes

Nachdem einige Versuche nicht sehr erfolgreich waren, kam ich zu dieser Haskell-Implementierung. Ich bin froh, nur einen Faktor 2 von der APL-Lösung entfernt zu sein!

Golf Lösung:

e=' ':e
m=[[]]:[[('/':e):map(' ':)x++('\\':e):y|k<-[0..n],x<-m!!(n-k),y<-m!!k]|n<-[0..]]
f n=putStr$unlines[map(!!(n-k))a|a<-m!!n,k<-[1..n]]

Ungolfed und kommentiert:

Das Programm erstellt die Menge der n- stufigen Bergdiagramme rekursiv. Jedes Diagramm wird durch eine Liste unendlich langer Zeichenfolgen dargestellt, die die seitwärts gezogenen Berge gefolgt von Räumen bis ins Unendliche darstellen. Dies stellt sicher, dass alle Diagramme dieselbe Höhe haben, was die Rekursion erleichtert. Der Bergdrucker akzeptiert einen Parameter, der die Höhe auf einen endlichen Wert begrenzt.

import Data.List (transpose)

-- Elementary picture slices, extending to infinity.
empty = ' ' : empty
up    = '/' : empty
down  = '\\': empty

-- A function which draws a mountain picture to stdout, clipping
-- its height to n.
printMtn n = putStr . unlines . reverse . take n . transpose 

{-- Combine mountain pictures x and y by

              x
 x # y  ==   / \y

--}
x # y = up : raised x ++ down : y
    where raised = map (' ':)

-- Given two sets X,Y of mountain pictures, compute the set X <> Y of all
-- combined pictures x#y for x in X, y in Y.
xs <> ys = [ x # y | x <- xs, y <- ys ]

-- Compute the (++,<>)-convolution of a list with itself, e.g.:
--   autoConvolve [x0,x1,x2] == (x2 <> x0) ++ (x1 <> x1) ++ (x0 <> x2)
autoConvolve xs = concat $ zipWith (<>) (reverse xs) xs

{--
    mtns is a list whose nth entry is the list of all n-step mountain diagrams.
    It is defined recursively by:
        --  The only 0-step mountain diagram is empty.
        --  Each (n+1)-step diagram can be uniquely drawn as x#y for
            some k-step diagram x and (n-k)-step diagram y.
--}
mtns = [[]] : [autoConvolve (prefix n) | n <- [1..]]
    where prefix n = take n mtns

-- The driver function: apply the height n mountain printer to each
-- n-step mountain diagram.  Whitespace is guaranteed by the order
-- in which the diagrams appear.
test n = mapM_ (printMtn n) $ mtns!!n

Beispielnutzung:

$ ghci mtn3.hs
GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
[1 of 1] Compiling Main             ( mtn3.hs, interpreted )
Ok, modules loaded: Main.
λ> f 3
  /\  
 /  \ 
/    \

 /\/\ 
/    \

 /\   
/  \/\

   /\ 
/\/  \


/\/\/\
λ>

Matt Noonan
quelle

0

GolfScript 103 ( Demo )

2*:§2\?,{2base.,§\-[0]*\+:a 1\{.2*@(.@+@@+}%:l$)\;),-1%{a,,{.l=2$=\a=1$+*' \\/'= }%\;n+}%\1=*l$(\;0>*}/

Das Programm verwendet einen Integer-Parameter, um alle binären Darstellungen der Zahlen von 0 bis 2 ^ (n-1) als Berge darzustellen. Es werden keine ungültigen Kombinationen ausgegeben (z. B. diejenigen, die unter Stufe 0 liegen).

Cristian Lupascu
quelle

Zeichne eine Reihe von Gebirgszügen

Antworten:

Python 2: 151 Zeichen

APL (88)

Python, 261 241 236 Zeichen

JavaScript (ES6) 159 163

CJam, 84 Bytes

C 179

Haskell, 140 Bytes

GolfScript 103 ( Demo )