Draw a range of mountain ranges

Question

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.

When you say "You can decide if different diagrams will be output horizontally, vertically, etc.", can the mountain ranges themselves be sideways? — xnor, Commented Sep 18, 2014 at 3:05
The mountain ranges themselves shouldn't be sideways. The empty skies between peaks add to the challenge, I think. — Matt Noonan, Commented Sep 18, 2014 at 3:12
@MattNoonan You're right, printing the mountain ranges horizontally was definitely tricky. — xnor, Commented Sep 18, 2014 at 19:48

xnor · Accepted Answer · 2014-09-18 22:58:24Z

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.

You'll need to use ' ' instead of " " if you want to loop using exec. :) Btw, you don't need to escape the backslash. — flornquake, Commented Sep 18, 2014 at 13:13
@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, Commented Sep 18, 2014 at 19:00
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, Commented Sep 18, 2014 at 20:55
@flornquake Wow do I feel silly, I changed one pair of quotes but not the other. Thanks! — xnor, Commented Sep 18, 2014 at 21:40

marinus · Accepted Answer · 2014-09-18 22:08:51Z

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

\$\begingroup\$ Alright, a horizontal one! \$\endgroup\$
– Matt Noonan
Commented Sep 18, 2014 at 22:32 — Matt Noonan, Commented Sep 18, 2014 at 22:32

Claudiu · Accepted Answer · 2014-09-18 02:36:17Z

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




/\/\/\/\





     /\
/\/\/  \





   /\
/\/  \/\





   /\/\
/\/    \




    /\
   /  \
/\/    \





 /\
/  \/\/\





 /\  /\
/  \/  \





 /\/\
/    \/\





 /\/\/\
/      \




    /\
 /\/  \
/      \




  /\
 /  \
/    \/\




  /\
 /  \/\
/      \




  /\/\
 /    \
/      \



   /\
  /  \
 /    \
/      \

Downgoat · Accepted Answer · 2016-01-09 17:28:57Z

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

   /\
  /  \
 /    \
/      \ 

  /\/\
 /    \
/      \ 

    /\
 /\/  \
/      \ 

    /\
   /  \
/\/    \ 

  /\
 /  \/\
/      \ 

 /\/\/\
/      \ 

   /\/\
/\/    \ 

 /\  /\
/  \/  \ 

     /\
/\/\/  \ 

  /\
 /  \
/    \/\ 

 /\/\
/    \/\ 

   /\
/\/  \/\ 

 /\
/  \/\/\ 

/\/\/\/\

Curious if there's any particular reason you write -b-b and -n-n instead of -2*b? — Steve Bennett, Commented Jun 6, 2017 at 0:46
@SteveBennett no reason. Sometimes this pattern is shorter, but not this time (for instance: 2*b+1 -> b-~b) — edc65, Commented Jun 6, 2017 at 8:04

Downgoat · Accepted Answer · 2016-01-09 17:16:42Z

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

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, Commented Sep 19, 2014 at 0:33

Community · Accepted Answer · 2020-06-17 09:04:33Z

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)

Community · Accepted Answer · 2020-06-17 09:04:33Z

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
  /\  
 /  \ 
/    \
      
 /\/\ 
/    \
      
 /\   
/  \/\
      
   /\ 
/\/  \
      
      
/\/\/\
λ>

Cristian Lupascu · Accepted Answer · 2014-09-20 09:23:56Z

0

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

answered Sep 20, 2014 at 9:23

Cristian Lupascu

8,6792 gold badges25 silver badges52 bronze badges

Add a comment |

Razetime · Accepted Answer · 2020-11-07 11:11:44Z

Husk, 54 bytes

mȯ¶↔T' §zoFz:,mömR' ∫Ẋo±+:_1†o!"/¦">0uf(Λ≥0∫)†?I←IPṘḋ2

Try it online!

Does surprisingly well in this challenge.

Explanation

ḋ2 array [0,1]

Ṙ repeat each \$n\$ times : 3 → [1,1,1,0,0,0]

†?I←I decrement the zeroes

f(Λ≥0∫) filter out the non-ranges using cumulative sum

u uniquify

§zoFz:, apply the following two functions a & b to the above result and zip them together

mömR' ∫Ẋo±+:_1 Function a: convert unequal pairs to 0's and create the required amount of spaces

†o!"/¦">0 Function b: convert 1 to / and -1 to \

These are now joined to create the mountains.

↔T' Transpose each mountain, filling with spaces then reverse

mȯ¶ join with newlines

Each mountain is then auto-displayed with newlines.

Stack Exchange Network

Draw a range of mountain ranges

9 Answers 9

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)

Husk, 54 bytes

Explanation

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
ascii-art
combinatorics
or ask your own question.

Linked

Hot Network Questions

Draw a range of mountain ranges

9 Answers 9

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)

Husk, 54 bytes

Explanation

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
ascii-art
combinatorics
or ask your own question.