Narysuj pasmo górskie

16

Zainspirowany kafelkami Domino Fibonacciego , ten problem polega na generowaniu sztuki ASCII reprezentującej kolejną znaną sekwencję kombinatoryczną.

Góra schemat n kroków jest rysunkiem z gór, stosując dokładnie n „/” i n „\” znaków, tak że znaki szkic ciągłą krzywą, która nigdy nie wchodzi poniżej początkowej „wysokości”. Na przykład,

   /\/\
/\/    \

i

   /\
/\/  \/\

są to 4-stopniowe diagramy górskie, ale

/\  /\/\
  \/

nie jest.

Wejście

Program powinien zaakceptować liczbę całkowitą n ze standardowego wejścia lub jako parametr funkcji.

Wynik

Wydrukuj wszystkie n- stopniowe diagramy górskie na standardowe wyjście. Diagramy mogą być w dowolnej kolejności, ale powinny być oddzielone białą spacją. Możesz zdecydować, czy różne diagramy będą wyświetlane w poziomie, w pionie itp.

Podobnie jak w przypadku problemu z kafelkami domina, możesz użyć dowolnej białej spacji. Obejmuje to dodatkowe znaki nowego wiersza przed wydrukiem lub po nim.

Przykład

Niektóre przykładowe prawidłowe dane wyjściowe dla n = 3:

Prawidłowe wyjście A:

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

Prawidłowe wyjście B:

   /\
/\/  \

 /\/\
/    \

/\/\/\   

  /\
 /  \
/    \

 /\
/  \/\

Prawidłowe wyjście C:

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

To jest kod golfowy; najkrótszy program (w bajtach) wygrywa.

Matt Noonan
źródło
Kiedy powiesz „Możesz zdecydować, czy różne diagramy będą wyświetlane poziomo, pionowo itp.”, Czy same łańcuchy górskie mogą być na boki?
xnor
Same łańcuchy górskie nie powinny być z boku. Wydaje mi się, że puste niebo między szczytami stanowi wyzwanie.
Matt Noonan,
Czy niektóre zakresy mogą pojawić się więcej niż raz?
dumny haskeller
@MattNoonan Masz rację, drukowanie pasm górskich w poziomie było zdecydowanie trudne.
xnor
@ dumny-haskeller Powinno to być raz.
Matt Noonan,

Odpowiedzi:

10

Python 2: 151 znaków

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, to jest bałagan.

Pierwszym pomysłem jest użycie liczb 0 to 2**N-1do zakodowania wszystkich sekwencji Nruchów w górę i w dół w ich bitach. Odczytujemy te bity jeden po drugim, powtarzając %2i /2powtarzając w execpętli.

Przechowujemy pasmo górskie z boku w transponowanej liście ciągów L. Za każdym razem generujemy nowy rząd spacji zamieniamy jedno miejsce w nowym rzędzie na /lub w \zależności od tego, czy nastąpił ruch w górę, czy w dół.

Indeks tej przestrzeni to cspacje od końca, gdzie cjest wysokość robocza. Robienie tego z przodu sprawiłoby, że góry były do ​​góry nogami. bPrzesuwamy go dalej, aby wyrównać ruchy w górę i w dół [b-c]. Począwszy cod 1 zamiast 0 naprawia błąd off-by-one.

Aby wyeliminować przypadki, w których cspadki poniżej wartości początkowej 1, kiedy tak się dzieje, ustawiamy ina 0, co powoduje, że wszystkie dalsze ruchy są w dół, przez co cstają się bardziej negatywne. Następnie, gdy sprawdzamy, czy cskończył się w 1, sprawdzamy również, czy ckiedykolwiek spadł poniżej. My tylko printpasmo górskie, jeśli cjest 1.

Aby wydrukować, wykonujemy zip(*L)transpozycję zakresu z pionowego na poziomy i drukujemy każdy połączony ciąg. Wiele problemów w tej odpowiedzi wynikało z tego, że Python traktuje ciągi jako niezmienne, więc pracowaliśmy z nimi jako listami znaków i połączyliśmy je w ciągi do drukowania.

Dzięki @flornquake za pomoc i ulepszenia.

xnor
źródło
Musisz użyć ' 'zamiast, " "jeśli chcesz używać pętli exec. :) Przy okazji, nie musisz uciekać przed odwrotnym ukośnikiem.
trzęsienie ziemi
@flornquake Zapomniałem napisać, użyłem ' 'i próbowałem zastąpić ciąg cudzysłowami zmienną. To wciąż dawało indeks poza zakresem:for _ in[0]*N:exec("b=i%2;c+=2*b-1;L+=[[" "]*N];L[-1][b-c]='\\/'[b];i=i//2*(c>0);")
xnor
Miałem na myśli, że musisz pisać exec("b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\\/'[b];i=i//2*(c>0);"), tzn. Wewnętrzne cytaty muszą różnić się od zewnętrznych.
trzęsienie ziemi
@flornquake Wow, czuję się głupio, zmieniłem jedną parę cytatów, ale nie drugą. Dzięki!
xnor
7

APL (88)

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

Dane wyjściowe dla n=3:

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

Wyjaśnienie:

  • (N/2)⊤⍳2*N←2×⍵: uzyskaj pole bitowe dla każdej liczby od 0do 2^⍵.
  • Z←↓⍉¯1+2×: pomnóż przez 2 i odejmij 1, dając 1w górę i -1w dół. Przechowuj wektor wektorów, każdy wektor zawierający reprezentację dla jednej liczby, w Z.
  • {... }¨Z: dla każdego elementu Z:
    • ∧/0≤+\⍵: sprawdź, czy suma bieżąca nigdy nie spada poniżej 0(nie schodzi poniżej poziomu gruntu),
    • (0=+/⍵): i że całkowita suma wynosi 0(kończy się na poziomie gruntu).
  • {... }¨Z/⍨: wybierz te elementy, Zdla których to prawda. Dla każdego z nich:
    • K←(⍵≠1)++\⍵: znajdź wysokość każdej postaci i zapisz K. Podnieś każdy \z nich, tak aby odpowiednio dopasował się do /s. To sprawia, że ​​wysokość gruntu 1.
    • ¯1+2×K=⊂⌽⍳⌈/K: dla każdej kolumny utwórz listę [1..max(K)]i zaznacz pozycję znaku w tej kolumnie za pomocą, 1a resztę jako -1. (Replikacja przez -1 wypełnia tę pozycję spacją.)
    • '\/'[1+⍵=1]/⍨¨: znajdź poprawny znak dla każdej kolumny i powtórz go według listy dla tej kolumny.
    • ⍉↑: zamień wynik w matrycę i umieść go po prawej stronie
marinus
źródło
W porządku, pozioma!
Matt Noonan,
2

Python, 261 241 236 znaków

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

Zaczyna się to długo n=5i dłużej ...

$ 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
źródło
2

JavaScript (ES6) 159 163

Podobnie jak moja odpowiedź na płytki Fibonacciego Domino, badam wszystkie sekwencje n + n bitów, z 1 oznaczeniem „/” i 0 oznaczeniem „\” (tylko dla wyjścia, „2” jest później dodawany, aby zaznaczyć nowy wiersz) . Budując wzór ascii sprawdzam równowagę - te same liczby 0 i 1 i nigdy nie schodząc poniżej linii bazowej - i wypisuję to, co jest zgodne z regułami.

Wyjście wykonane z „alert”, co jest standardem dla kodegolfa JS, ale dość denerwujące i być może niezgodne z regułami. Przy użyciu console.log liczba znaków wynosi 165.

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

Mniej golfa

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]]||' '));
  }
}

Przetestuj w konsoli FireFox / FireBug.

F(4)

Wynik

   /\
  /  \
 /    \
/      \ 

  /\/\
 /    \
/      \ 

    /\
 /\/  \
/      \ 

    /\
   /  \
/\/    \ 

  /\
 /  \/\
/      \ 

 /\/\/\
/      \ 

   /\/\
/\/    \ 

 /\  /\
/  \/  \ 

     /\
/\/\/  \ 

  /\
 /  \
/    \/\ 

 /\/\
/    \/\ 

   /\
/\/  \/\ 

 /\
/  \/\/\ 

/\/\/\/\ 
edc65
źródło
Ciekawy czy jest jakiś szczególny powód piszesz -b-bi -n-nzamiast -2*b?
Steve Bennett,
@ SteveBennett bez powodu. Czasami ten wzór jest krótszy, ale nie tym razem (na przykład: 2*b+1-> b-~b)
edc65
1

CJam, 84 bajty

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

Zauważ, że ten program drukuje góry w nieskończonej pętli, więc tłumacz online ci nie pomoże; wywołaj w wierszu poleceń, używając

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

lub spróbuj użyć online

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

i po prostu kilka razy z rzędu nacisnąłem przycisk Uruchom i wyobraźcie sobie, że wynik jest połączony.

Podstawową ideą jest to, że wiemy, że pasmo górskie o wielkości Q ma Q każdego przejścia w górę i w dół.

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

Następnie, jeśli jest poprawny, drukujemy go, a jeśli nie, usuwamy go ze stosu, aby się nie przepełnił.

Trasa drukowania w zasadzie buduje każdą kolumnę jako odstępy Q - wysokość, następnie symbol, a następnie wystarczająco dużo spacji, aby trafić Q + 1 znaków ogółem, a następnie transponujemy i drukujemy linie z nowymi liniami między nimi.

z{N\++}*o                                   #transpose, insert newlines, print
paradigmsort
źródło
Podczas gdy nad tym pracowałem, pytanie zostało wyjaśnione, aby wymagać wydrukowania gór raz. Będzie to wymagało ponownego przemyślenia i prawdopodobnie większej liczby znaków: /
paradigmsort
0

C 179

wykluczając niepotrzebne białe znaki.

Podobna strategia do edc65. Przeglądam wszystkie n*2-bitowe wartości binarne, biorąc pod uwagę /= 1 i \= 0.

nFormatuję pojedynczy ciąg zawierający podziały wierszy dla każdego n*3znaku. Jak napisano, ciąg zawiera 1000 znaków, więc po górze zwykle drukowanych jest wiele białych znaków. (Można to naprawić, dodając s[n*n*3]=0przed puts.) W każdym razie pozwala mi to wyprowadzić całą górę za jednym razem putspo sprawdzeniu, czy jest zgodna z regułami.

Spróbuję później przekonwertować go na funkcję i zredukować do pojedynczej forpętli.

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

Wyjście (zwróć uwagę na dużą ilość białych znaków po prawej stronie)

$ ./a
4

 /\
/  \/\/\                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

   /\
/\/  \/\                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

 /\/\
/    \/\                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

  /\
 /  \
/    \/\                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

     /\
/\/\/  \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

 /\  /\
/  \/  \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

   /\/\
/\/    \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

 /\/\/\
/      \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

  /\
 /  \/\
/      \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

    /\
   /  \
/\/    \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

    /\
 /\/  \
/      \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

  /\/\
 /    \
/      \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        

   /\
  /  \
 /    \
/      \                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
Level River St
źródło
0

Haskell, 140 bajtów

Po kilku próbach niemożności gry w golfa skończyłem z tą implementacją Haskell. Cieszę się, że jestem w odległości 2-krotności rozwiązania APL!

Rozwiązanie w golfa:

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

Nie golfił i skomentował:

Program rekurencyjnie tworzy zestaw n- krokowych diagramów górskich. Każdy diagram jest reprezentowany przez listę nieskończenie długich łańcuchów, reprezentujących górę narysowaną bokiem, a następnie spacje rozciągające się do nieskończoności. Zapewnia to, że wszystkie diagramy mają tę samą wysokość, co ułatwia rekurencję. Drukarka górska akceptuje parametr, który przycina wysokość do skończonej wartości.

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

Przykładowe użycie:

$ 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
źródło
0

GolfScript 103 ( wersja demo )

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

Program przyjmuje parametr liczby całkowitej, który próbuje renderować jako góry wszystkie binarne reprezentacje liczb od 0 do 2 ^ (n-1). Nie wyświetla niepoprawnych kombinacji (np. Tych, które schodzą poniżej poziomu 0).

Cristian Lupascu
źródło