# Sierpinski Layers

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


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.

• Can you please make it "fewest bytes" to avoid code compression shenanigans?
– xnor
Oct 4, 2014 at 5:31
• @xnor Changed . Oct 4, 2014 at 6:05
• I was literally about to post this. Meanie. :/ Oct 4, 2014 at 8:34
– Joe
Oct 4, 2014 at 23:13

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

# 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 :=  "; \{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'                             ";
}                  "                                                                ";


# 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 > /\
• b*(N-1)+m+n could be b*~-N+m+n Oct 4, 2014 at 16:02
• @FryAmTheEggman: Awesome! Now I got you, JavaScript! ;) Oct 4, 2014 at 16:16

# 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

# Pyth, 45 bytes

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


$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 + " ") " /" # " /" # ))))  # 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. # 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  • 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 Oct 4, 2014 at 17:05 • @Flonk unlines is in the prelude. Oct 4, 2014 at 17:07 • Oops, maybe I should have looked that up before commenting. My bad! Oct 4, 2014 at 17:08 # 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  /\ /\/\ /\ /\ /\/\/\/\ /\ /\ /\/\ /\/\ /\ /\ /\ /\ /\/\/\/\/\/\/\/\ /\ /\ /\/\ /\/\ /\ /\ /\ /\ /\/\/\/\ /\/\/\/\ /\ /\ /\ /\ /\/\ /\/\ /\/\ /\/\ /\ /\ /\ /\ /\ /\ /\ /\  # 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  ## 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  # Mathematica, 86 bytes Column[Row/@Mod[Table[Binomial[n,k],{n,0,#-1},{k,0,n}],2]/.{1->"/\\",0->" "},Center]&  ## 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):

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

# Python 2, 97 bytes

i=input()
x=1
while i:i-=1;print " "*i+bin(x)[2:].replace("0","  ").replace("1", "/\\");x^=2*x

• Welcome to Programming Puzzles & Code Golf! Nice answer :D
– cat
Mar 30, 2016 at 13:27