19
\$\begingroup\$

Starting with /\ you can create a Sierpinski triangle like pattern by adding a line beneath such that...

  1. Any loose branch / or \ splits again into two branches: /\.
  2. Any collision of branches \/ dies with nothing (but spaces) under it.

Repeating these rules yields

     /\
    /\/\
   /\  /\
  /\/\/\/\
 /\      /\
/\/\    /\/\
etc...

(Inspiration by ViHart)

Write a program or function that takes in a positive integer N and prints the first N lines of this pattern to stdout, with no more leading or trailing spaces than necessary.

For example, if the input is 1 the output must be

/\

If the input is 2 the output must be

 /\
/\/\

If the input is 8 the output must be

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

And so on.

The code with the fewest bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you please make it "fewest bytes" to avoid code compression shenanigans? \$\endgroup\$ – xnor Oct 4 '14 at 5:31
  • \$\begingroup\$ @xnor Changed . \$\endgroup\$ – Calvin's Hobbies Oct 4 '14 at 6:05
  • \$\begingroup\$ I was literally about to post this. Meanie. :/ \$\endgroup\$ – Kaz Wolfe Oct 4 '14 at 8:34
  • \$\begingroup\$ Where's the APL answer? \$\endgroup\$ – Joe Oct 4 '14 at 23:13

13 Answers 13

9
\$\begingroup\$

GolfScript (42 bytes)

~,-1%1\{' '*\.2base{'  /\\'2/=}%n@.2*^}/;;

Online demo

This exploits a well-known relationship between Pascal's triangle and the Sierpinski triangle.

\$\endgroup\$
6
\$\begingroup\$

CJam, 48 46 bytes

li(_S*"/\\":T+\{_N@S+TW%/S2**" /"/"\ "f/:+T*}*

Simple recursive approach based on observations 1 and 2 in the question.

Try it online.

How it works

li(         " L := int(input()) - 1            ";
_S*         " A := L * ' '                     ";
"/\\":T+    " A += (T := '/\')                 ";
\{          " do L times:                      ";
  _N        "   push A, '\n'                   ";
  @S+       "   A += ' '                       ";
  TW%/      "   B := A.split(reverse(T))       ";
  S2**      "   A := '  '.join(B)              ";
  " /"/     "   B := A.split(' /')             ";
  "\ "f/    "   C := { X.split('\ ') : X ∊ B } ";
  :+T*      "   A := T.join(sum(C, []))        ";
}*          "                                  ";

CJam, 51 bytes

li__2mL,1a\{2_@##)1$f*+}/<f{2b_"  /\\"2/f=@@,-S*\N}

I like this approach better, but it can't compete with the recursive one. Even after eliminating 2mL (which results in at least O(2n) execution time), I'm still at 48 bytes...

This approach encodes /\'s as 1's and double spaces between them as 0's. Considering the resulting arrays binary numbers, we see that the configuration of the nth row corresponds to the nth integer larger than 1 that can be expressed as a product of different Fermat numbers (integers of the form 22k+1).

How it works

li__2mL,1a         " push L := int(input()), L, R := range(log(L)/log(2)), A := [1] ";
\{2_@##)1$f*+}/    " for I in R: A += { a × 2**(2**I) : a ∊ A }                     ";
<                  " A := A[:L]                                                     ";
f{                 " for I in R: push L, I                                          ";
  2b_"  /\\"2/     "   push (B := base(I, 2)), B, S := [ '  ' '/\' ]                ";
  f=               "   for J in I: J := S[J]                                        ";
  @@,-S*\N         "   push (L - len(B)) * ' ', J, '\n'                             ";
}                  "                                                                ";
\$\endgroup\$
5
\$\begingroup\$

Python 2 - 140 139 127 122 121 118 116

N=input()
b,V,m,n=' V/\\'
s=b*~-N+m+n
R=str.replace
while N:print s;N-=1;s=R(R(R(R(s+b,b+m,V),n+b,V),n+m,b+b),V,m+n)

Based on temporary string replacements (https://stackoverflow.com/a/8687380/3419103):

  1. / > V
  2. \ > V
  3. \/ > __ (2 spaces)
  4. V > /\
\$\endgroup\$
  • \$\begingroup\$ b*(N-1)+m+n could be b*~-N+m+n \$\endgroup\$ – FryAmTheEggman Oct 4 '14 at 16:02
  • \$\begingroup\$ @FryAmTheEggman: Awesome! Now I got you, JavaScript! ;) \$\endgroup\$ – Falko Oct 4 '14 at 16:16
4
\$\begingroup\$

Javascript - 117 bytes

Minified:

T=n=>{S=' '.repeat(n-1);a='/\\';for(t=s=S+a+S;--n;t+='\n'+s)s=s.replace(/\\\//g,'  ').replace(/ \/|\\ /g,a);return t}

Expanded:

T = n => {
    S = ' '.repeat( n-1 );
    a = '/\\';
    for( t = s = S + a + S; --n; t += '\n' + s )
        s = s.replace( /\\\//g, '  ' ).replace( / \/|\\ /g, a );

    return t;
}

Sample Output (for n = 20):

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

Now if only the repeat and replace function names weren't so long. :P

\$\endgroup\$
3
\$\begingroup\$

Pyth, 45 bytes

K"/\\"Jt+*QdKVQpbJ=JjKsmcd"\ "cj*2dc+Jd_K" /"

Example run

$ pyth -c 'K"/\\"Jt+*QdKVQpbJ=JjKsmcd"\ "cj*2dc+Jd_K" /"' <<< 16
               /\
              /\/\
             /\  /\
            /\/\/\/\
           /\      /\
          /\/\    /\/\
         /\  /\  /\  /\
        /\/\/\/\/\/\/\/\
       /\              /\
      /\/\            /\/\
     /\  /\          /\  /\
    /\/\/\/\        /\/\/\/\
   /\      /\      /\      /\
  /\/\    /\/\    /\/\    /\/\
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

How it works

                            # Q = eval(input())
K"/\\"                      # K = "/\\"
      Jt+*QdK               # J = (Q * " " + K)[1:]
             VQ             # for N in range(Q):
               pbJ          #     print(J, end="\n")
                            #
=JjK                        #     J = K.join(
    sm                      #         sum(list(map(lambda d:
      cd"\ "                #             d.split("\ "),
            c               #                                                .split(    )
             j*2d           #              " ".join(                        )
                 c   _K     #                                .split(K[::-1])
                  +Jd       #                       (J + " ")
                       " /" #                                                       " /"
                            #     ))))
\$\endgroup\$
3
\$\begingroup\$

Ruby, 90

f=->n{a=["/\\".center(2*n)]
2.upto(n){a<<a[-1].gsub("\\/","  ").gsub(/ \/|\\ /,"/\\")}
puts a}

Explanation

  • Input is taken as an argument to a lambda. It is expected to be an Integer.
  • Use String#center to create a String "/\" with n - 2 spaces on each side and put it into an Array (a).
  • Add to a the last element of a with every occurrence of "\/" replaced with " " and every occurrence of " /" or " \" replaced with "/\".
  • Use puts to print each element in a on its own line.
\$\endgroup\$
3
\$\begingroup\$

Haskell, 128 112

g n=unlines$take n$i t([1..n]>>" ")%(i(\l->l++l%i(t.t)(t l>>"  ")%l)["/\\"]!!n)
t=tail
(%)=zipWith(++)
i=iterate
\$\endgroup\$
  • \$\begingroup\$ If I count the characters I get 128 - also you forgot to import Data.List (since you used unlines), which brings it up to 145 \$\endgroup\$ – Flonk Oct 4 '14 at 17:05
  • \$\begingroup\$ @Flonk unlines is in the prelude. \$\endgroup\$ – proud haskeller Oct 4 '14 at 17:07
  • \$\begingroup\$ Oops, maybe I should have looked that up before commenting. My bad! \$\endgroup\$ – Flonk Oct 4 '14 at 17:08
2
\$\begingroup\$

JavaScript (E6) 107 106

Edit: fixed byte count, made recursive.

Not much different from the other JS answer ... at least this one 'prints' the pattern as requested. The core is replacing ' /' '\ ' with '/\' and all the rest with ' ' on each new line.

F=(n,o=t='/\\',b=' ')=>
  n--&&
    console.log(b.repeat(n)+o)|
    F(n,(b+o+b).replace(/../g,s=>s==b+b|s=='\\/'?b+b:t))

Test In FireFox/FireBug console

F(15)

Output

                  /\
                 /\/\
                /\  /\
               /\/\/\/\
              /\      /\
             /\/\    /\/\
            /\  /\  /\  /\
           /\/\/\/\/\/\/\/\
          /\              /\
         /\/\            /\/\
        /\  /\          /\  /\
       /\/\/\/\        /\/\/\/\
      /\      /\      /\      /\
     /\/\    /\/\    /\/\    /\/\
    /\  /\  /\  /\  /\  /\  /\  /\
\$\endgroup\$
2
\$\begingroup\$

Perl 5 - 56 bytes

\0's can be replaced by actual null byte characters

#!/usr/bin/perl -l
$p="/\\";$_=$"x~$_.$p,y/\0/ /,print,$p^="\0\0$p"for-<>..-1

It is using the fact that if you ignore leading spaces and represent '/\' as 1 and ' ' as 0 the pattern in a given row f(n) = f(n-1) ^ (f(n-1) << 1). However the calculations in the code above are executed on strings that are close to the expected output (no leading spaces, other spaces replaced by null bytes) thanks to perl's bitwise string manipulation.

$p="/\\";          # initialize
  $_=$"x~$_.$p,    # loop start, add spaces
  y/\0/ /,         # replace nulls with spaces
  print,           # output
  $p^="\0\0$p"     # calculate next string
for-<>..-1         # loop from -n to -1
\$\endgroup\$
1
\$\begingroup\$

Python 2, 84 bytes

n=i=input()
while i:print' '*i+''.join("/ \ "[j&i+1>0::2]for j in range(n-i+1));i-=1
\$\endgroup\$
0
\$\begingroup\$

Javascript with lambdas, 141 128

141

f=n=>{for(a="25",q=0;++q<n;a=a[r='replace'](/^|$/mg,1)[r](/(.*)$/,"$1\n$1")[r](/..(?=.*$)/g,x=>x%3?11:25));return a[r](/./g,x=>"  /  \\"[x])}

128

f=n=>(t=a=>--n?t(a[r='replace'](/^|$/mg,1)[r](/(.*)$/,"$1\n$1")[r](/..(?=.*$)/g,x=>x%3?11:25)):a)("25")[r](/./g,x=>"  /  \\"[x])

Can be tested at Firefox (n=16):

               /\               
              /\/\              
             /\  /\             
            /\/\/\/\            
           /\      /\           
          /\/\    /\/\          
         /\  /\  /\  /\         
        /\/\/\/\/\/\/\/\        
       /\              /\       
      /\/\            /\/\      
     /\  /\          /\  /\     
    /\/\/\/\        /\/\/\/\    
   /\      /\      /\      /\   
  /\/\    /\/\    /\/\    /\/\  
 /\  /\  /\  /\  /\  /\  /\  /\ 
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\$\endgroup\$
0
\$\begingroup\$

Python 2, 97 bytes

i=input()
x=1
while i:i-=1;print " "*i+bin(x)[2:].replace("0","  ").replace("1", "/\\");x^=2*x
\$\endgroup\$
  • \$\begingroup\$ Welcome to Programming Puzzles & Code Golf! Nice answer :D \$\endgroup\$ – cat Mar 30 '16 at 13:27
0
\$\begingroup\$

Mathematica, 86 bytes

Column[Row/@Mod[Table[Binomial[n,k],{n,0,#-1},{k,0,n}],2]/.{1->"/\\",0->"  "},Center]&
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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