Inspired by Fibonacci domino tiling, this problem is about generating ASCII art representing another famous combinatorial sequence.

A n-step mountain diagram is a drawing of a mountain range, using exactly n '/' and n '\' characters, such that characters sketch a continuous curve which never dips below its initial "altitude". For example,

   /\/\
/\/    \

and

   /\
/\/  \/\

are both 4-step mountain diagrams, but

/\  /\/\
  \/

is not.

Input

The program should accept an integer n from stdin or as the parameter to a function.

Output

Print all n-step mountain diagrams to stdout. The diagrams can be in any order, but should be separated by some sort of whitespace. You can decide if different diagrams will be output horizontally, vertically, etc.

As in the domino tiling problem, you can use whatever whitespace you want. This includes extra newlines before or after the printed output.

Example

Some sample valid outputs for n=3:

Valid output A:

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

Valid output B:

   /\
/\/  \

 /\/\
/    \

/\/\/\   

  /\
 /  \
/    \

 /\
/  \/\

Valid output C:

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

This is code golf; shortest program (in bytes) wins.

Matt Noonan

Posted 2014-09-18T00:57:57.537

Reputation: 1 014

When you say "You can decide if different diagrams will be output horizontally, vertically, etc.", can the mountain ranges themselves be sideways? – xnor – 2014-09-18T03:05:23.007

The mountain ranges themselves shouldn't be sideways. The empty skies between peaks add to the challenge, I think. – Matt Noonan – 2014-09-18T03:12:51.687

Can some ranges appear more than once? – proud haskeller – 2014-09-18T18:37:22.187

@MattNoonan You're right, printing the mountain ranges horizontally was definitely tricky. – xnor – 2014-09-18T19:48:18.137

@proud-haskeller It should be once each. – Matt Noonan – 2014-09-18T22:33:28.053

Answers

Python 2: 151 chars

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, this is a mess.

The first idea is to use the numbers 0 to 2**N-1 to encode all sequences of N up-moves and down-moves in their bits. We read off these bits one by one by repeated %2 and /2, iterated in an exec loop.

We store the running mountain range sideways in a transposed list of strings L. Each time, we generate a new a row of spaces are replace one space in the new row with / or \ depending on whether an up-move or down-move happened.

The index of that space is c spaces from the end, where c is the running height. Doing it from the front would make the mountains upside down. We further shift it by b to align upward and downward moves , getting [b-c]. Starting c at 1 rather than 0 fixes an off-by-one error.

To eliminate cases where c dips below the start value 1, when this happens, we set i to 0, which causes all further moves to be downward, making c become more negative. Then, when we check whether c ended at 1, we also check whether c ever fell below it. We only print the mountain range if c is 1.

To print, we do zip(*L) to transpose the range from vertical to horizontal, and print each joined string. A lot of trouble in this answer came from Python treats strings as immutable, so we worked with them as lists of characters and only joined them into strings for printing.

Thanks to @flornquake for help and improvements.

xnor

Posted 2014-09-18T00:57:57.537

Reputation: 115 687

You'll need to use ' ' instead of " " if you want to loop using exec. :) Btw, you don't need to escape the backslash. – flornquake – 2014-09-18T13:13:01.567

@flornquake I forgot to write, I did use ' ' and tried replacing the string with quotes with a variable for it. This still gave index out of range: 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 – 2014-09-18T19:00:45.237

I meant that you need to write exec("b=i%2;c+=2*b-1;L+=[[' ']*N];L[-1][b-c]='\\/'[b];i=i//2*(c>0);"), i.e. the inner quotes have to be different from the outer ones. – flornquake – 2014-09-18T20:55:18.170

@flornquake Wow do I feel silly, I changed one pair of quotes but not the other. Thanks! – xnor – 2014-09-18T21:40:48.693

APL (88)

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

Output for n=3:

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

Explanation:

(N/2)⊤⍳2*N←2×⍵: get a bitfield for each number from 0 to 2^⍵.
Z←↓⍉¯1+2×: multiply by 2 and subtract 1, giving 1 for up and -1 for down. Store a vector of vectors, each vector containing the representation for one number, in Z.
{...}¨Z: for each element of Z:
- ∧/0≤+\⍵: check that the running sum never falls below 0 (doesn't go below ground level),
- (0=+/⍵): and that the total sum is 0 (ends up back at ground level).
{...}¨Z/⍨: select those elements from Z for which that is true. For each of them:
- K←(⍵≠1)++\⍵: find the height for each character, and store in K. Raise each \ up one, so that they line up with the /s properly. This makes the ground height 1.
- ¯1+2×K=⊂⌽⍳⌈/K: for each column, make a list [1..max(K)], and mark the position of the character in that column with 1 and the rest as -1. (Replicating by -1 fills that position with a space.)
- '\/'[1+⍵=1]/⍨¨: find the correct character for each column, and replicate it by the list for that column.
- ⍉↑: turn the result into a matrix and put it right-side-up

marinus

Posted 2014-09-18T00:57:57.537

Reputation: 30 224

Alright, a horizontal one! – Matt Noonan – 2014-09-18T22:32:22.090

Python, 261 241 236 characters

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

It starts taking a while for n=5 and up...

$ 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

Posted 2014-09-18T00:57:57.537

Reputation: 3 870

JavaScript (ES6) 159 163

Just like my answer for Fibonacci Domino Tiling, I examine all the sequences of n+n bits, with 1 marking a '/' and 0 marking a '\' (just for output, '2' is later added to mark a newline). While building tha ascii pattern I check the balance - same numbers of 0 and 1, and never going below the starting base line - and output what obey the rules.

Output done with 'alert', that is standard for JS codegolf but quite annoying, and maybe against the rules. Using console.log the character count goes to 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;
}

Less golfed

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 FireFox/FireBug console.

F(4)

Output

   /\
  /  \
 /    \
/      \ 

  /\/\
 /    \
/      \ 

    /\
 /\/  \
/      \ 

    /\
   /  \
/\/    \ 

  /\
 /  \/\
/      \ 

 /\/\/\
/      \ 

   /\/\
/\/    \ 

 /\  /\
/  \/  \ 

     /\
/\/\/  \ 

  /\
 /  \
/    \/\ 

 /\/\
/    \/\ 

   /\
/\/  \/\ 

 /\
/  \/\/\ 

/\/\/\/\

edc65

Posted 2014-09-18T00:57:57.537

Reputation: 31 086

Curious if there's any particular reason you write -b-b and -n-n instead of -2*b? – Steve Bennett – 2017-06-06T00:46:27.847

@SteveBennett no reason. Sometimes this pattern is shorter, but not this time (for instance: 2*b+1 -> b-~b) – edc65 – 2017-06-06T08:04:05.337

CJam, 84 bytes

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

Note that this program prints the mountains in an infinite loop so the online interpreter will not help you; invoke at the command line using

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

or to try online use

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

and just hit the run button a bunch of times in succession and imagine the output is concatenated.

The basic idea is that we know a mountain range of size Q has Q of each upward and downward transitions.

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

Then if it's valid we print it, if not we pop it from the stack so it doesn't overflow.

The print routing basically builds each column as Q - height spaces, then the symbol, then enough more spaces to hit Q+1 total characters, and then we transpose and print the lines with newlines between them.

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

paradigmsort

Posted 2014-09-18T00:57:57.537

Reputation: 71

While I was working on this the question got clarified to require that the mountains be printed once each. That will require some rethinking and probably more characters :/ – paradigmsort – 2014-09-19T00:33:44.903

C,179

excluding unnecessary whitespace.

A similar strategy to edc65. I run through all the n*2-bit binary values, considering /=1 and \=0.

I format a single string containing n linebreaks every n*3 characters. As written the string contains 1000 characters, so there is usually a lot of whitespace printed after the mountain. (This can be fixed by adding s[n*n*3]=0 before the puts.) Anyway, this enables me to output the whole mountain with a single puts after checking that it complies with the rules.

I will try converting it to a function and reducing to a single for loop later.

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

Output (note the massive amount of whitespace to the right)

Level River St

Posted 2014-09-18T00:57:57.537

Reputation: 22 049

Haskell, 140 bytes

After several attempts failed to be very golfable, I ended up with this Haskell implementation. I'm happy just to be within a factor of 2 of the APL solution!

Golfed solution:

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 and commented:

The program builds the set of n-step mountain diagrams recursively. Each diagram is represented by a list of infinitely-long strings, representing the mountain drawn sideways followed by spaces extending to infinity. This ensures that all diagrams have the same height, which makes the recursion easier. The mountain printer accepts a parameter which clips the height to a finite value.

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

Sample usage:

$ 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

Posted 2014-09-18T00:57:57.537

Reputation: 1 014

GolfScript 103 (demo)

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

The program takes an integer parameter tries to render as mountains all binary representations of the numbers from 0 to 2^(n-1). It does not render invalid combinations (ex: the ones that go below level 0).

Cristian Lupascu

Posted 2014-09-18T00:57:57.537

Reputation: 8 369

Draw a range of mountain ranges

Answers

Python 2: 151 chars

APL (88)

Python, 261 241 236 characters

JavaScript (ES6) 159 163

CJam, 84 bytes

C,179

Haskell, 140 bytes

GolfScript 103 (demo)