Sierpinski Layers

Question

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

Any loose branch / or \ splits again into two branches: /\.
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.

Can you please make it "fewest bytes" to avoid code compression shenanigans? — xnor, Oct 4, 2014 at 5:31

Peter Taylor · Accepted Answer · 2014-10-06 13:31:59Z

9

GolfScript (42 bytes)

~,-1%1\{' '*\.2base{'  /\\'2/=}%[email protected]*^}/;;

Online demo

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

answered Oct 6, 2014 at 13:31

Peter Taylor

43.1k4 gold badges70 silver badges168 bronze badges

Add a comment |

Dennis · Accepted Answer · 2014-10-05 04:19:50Z

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(2ⁿ) 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 2^{2^k}+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'                             ";
}                  "                                                                ";

Community · Accepted Answer · 2017-05-23 12:41:24Z

5

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

/ > V
\ > V
\/ > __ (2 spaces)
V > /\

edited May 23, 2017 at 12:41

CommunityBot

1

answered Oct 4, 2014 at 6:31

Falko

5,6072 gold badges20 silver badges31 bronze badges

\$\begingroup\$ b*(N-1)+m+n could be b*~-N+m+n \$\endgroup\$
– FryAmTheEggman
Oct 4, 2014 at 16:02
\$\begingroup\$ @FryAmTheEggman: Awesome! Now I got you, JavaScript! ;) \$\endgroup\$
– Falko
Oct 4, 2014 at 16:16

Add a comment |

COTO · Accepted Answer · 2014-10-04 06:10:12Z

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

Dennis · Accepted Answer · 2014-10-04 16:42:04Z

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 + " ")
                       " /" #                                                       " /"
                            #     ))))

britishtea · Accepted Answer · 2014-10-05 01:49:13Z

3

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.

edited Oct 5, 2014 at 1:49

answered Oct 4, 2014 at 14:16

britishtea

1,1896 silver badges14 bronze badges

Add a comment |

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

3

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Oct 4, 2014 at 8:44

proud haskeller

6,1711 gold badge23 silver badges37 bronze badges

\$\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, 2014 at 17:05
\$\begingroup\$ @Flonk unlines is in the prelude. \$\endgroup\$
– proud haskeller
Oct 4, 2014 at 17:07
\$\begingroup\$ Oops, maybe I should have looked that up before commenting. My bad! \$\endgroup\$
– Flonk
Oct 4, 2014 at 17:08

Add a comment |

edc65 · Accepted Answer · 2014-10-22 06:57:58Z

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

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

nutki · Accepted Answer · 2014-10-22 15:56:03Z

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

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

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Mar 30, 2016 at 2:43

xnor

145k26 gold badges277 silver badges642 bronze badges

Add a comment |

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

1

Mathematica, 86 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 1, 2017 at 0:11

ZaMoC

24.9k2 gold badges30 silver badges81 bronze badges

Add a comment |

Qwertiy · Accepted Answer · 2014-10-22 22:06:16Z

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

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

pbochniak · Accepted Answer · 2016-03-30 11:34:46Z

0

Python 2, 97 bytes

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

answered Mar 30, 2016 at 11:34

pbochniak

573 bronze badges

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

Add a comment |

Stack Exchange Network

Sierpinski Layers

13 Answers 13

GolfScript (42 bytes)

CJam, 48 46 bytes

How it works

CJam, 51 bytes

How it works

Python 2 - 140 139 127 122 121 118 116

Javascript - 117 bytes

Pyth, 45 bytes

Example run

How it works

Ruby, 90

Explanation

Haskell, 128 112

JavaScript (E6) 107 106

Perl 5 - 56 bytes

Python 2, 84 bytes

Mathematica, 86 bytes

Javascript with lambdas, 141 128

Python 2, 97 bytes

Your Answer

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

Linked

Hot Network Questions

Sierpinski Layers

13 Answers 13

GolfScript (42 bytes)

CJam, 48 46 bytes

How it works

CJam, 51 bytes

How it works

Python 2 - 140 139 127 122 121 118 116

Javascript - 117 bytes

Pyth, 45 bytes

Example run

How it works

Ruby, 90

Explanation

Haskell, 128 112

JavaScript (E6) 107 106

Perl 5 - 56 bytes

Python 2, 84 bytes

Mathematica, 86 bytes

Javascript with lambdas, 141 128

Python 2, 97 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

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