Code Golf: Sierpinski's Triangle

Question

The challenge

The shortest code, by character count to output an ASCII representation of Sierpinski's Triangle of N iterations made from the following ASCII triangle:

 /\
/__\

Input is a single positive number.

Test cases

Input:
    2
Output:
       /\
      /__\
     /\  /\
    /__\/__\

---

Input:
    3
Output:
           /\
          /__\
         /\  /\
        /__\/__\
       /\      /\
      /__\    /__\
     /\  /\  /\  /\
    /__\/__\/__\/__\

---

Input:
    5
Output:
                                   /\
                                  /__\
                                 /\  /\
                                /__\/__\
                               /\      /\
                              /__\    /__\
                             /\  /\  /\  /\
                            /__\/__\/__\/__\
                           /\              /\
                          /__\            /__\
                         /\  /\          /\  /\
                        /__\/__\        /__\/__\
                       /\      /\      /\      /\
                      /__\    /__\    /__\    /__\
                     /\  /\  /\  /\  /\  /\  /\  /\
                    /__\/__\/__\/__\/__\/__\/__\/__\
                   /\                              /\
                  /__\                            /__\
                 /\  /\                          /\  /\
                /__\/__\                        /__\/__\
               /\      /\                      /\      /\
              /__\    /__\                    /__\    /__\
             /\  /\  /\  /\                  /\  /\  /\  /\
            /__\/__\/__\/__\                /__\/__\/__\/__\
           /\              /\              /\              /\
          /__\            /__\            /__\            /__\
         /\  /\          /\  /\          /\  /\          /\  /\
        /__\/__\        /__\/__\        /__\/__\        /__\/__\
       /\      /\      /\      /\      /\      /\      /\      /\
      /__\    /__\    /__\    /__\    /__\    /__\    /__\    /__\
     /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\  /\
    /__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\/__\

Code count includes input/output (i.e full program).

Answer 1

F#, 225 chars

let rec p n=if n=1 then" "else p(n-1)+p(n-1)
and S n=if n=1 then[" /\\ ";"/__\\"]else let s=S(n-1)in List.append(List.map(fun s->p(n)+s+p(n))s)(List.map(fun x->x+x)s)
for s in S(int(System.Console.ReadLine()))do printfn"%s"s

Answer 2

Python, 135 chars

S=lambda n:[" /\\ ","/__\\"]if n==1 else[" "*(1<<n-1)+x+" "*(1<<n-1)for x in S(n-1)]+[x+x for x in S(n-1)]
for s in S(input()):print s

Answer 3

Python - 102

a=" /\ ","/__\\"
j=' '
for n in~-input()*j:j+=j;a=[j+x+j for x in a]+[x*2for x in a]
print"\n".join(a)

Python - 105

a=" /\ ","/__\\"
j=' '
for n in(input()-1)*j:j+=j;a=[j+x+j for x in a]+[x+x for x in a]
print"\n".join(a)

Python - 109

a=" /\ ","/__\\"
for n in range(1,input()):j=' '*2**n;a=[j+x+j for x in a]+[x+x for x in a]
print"\n".join(a)

Python2.6 - 120

N=1<<input()
a=1
while N:
 N-=2
 for s in" /\ ","/__\\":print' '*N+bin(a)[2:].replace('0',' '*4).replace('1',s)
 a=a^a*2

Answer 4

Haskell, 153 149 137 125 118 112 characters:

Using tail recursion:

(%)=zipWith(++)
p="  ":p
g t _ 1=t
g t s(n+1)=g(s%t%s++t%t)(s%s)n
main=interact$unlines.g[" /\\ ","/__\\"]p.read

earlier version, @118 characters:

(%)=zipWith(++)
f 1=[" /\\ ","/__\\"]
f(n+1)=s%t%s++t%t where t=f n;s=replicate(2^n)' ':s
main=interact$unlines.f.read

Using the (justly deprecated!) n+k pattern saved 4 characters.

I like how it comes out halfway readable even in compressed form.

edit:old main

main=do{n<-getLine;putStr$unlines$f$read n}

Answer 5

Python, 186 chars (UNIX line termination)

for j in range(1,n):
 for s in p:
  print s
 x=2**j;y=2*x;p.extend(['']*x)
 for i in range(y-1,-1,-1):
  if i<x:
   s=' '*x;p[i]=s+p[i]+s
  else:
   q=p[i-x];p[i]=q+q

Answer 6

Perl

94 characters when newlines are removed.

$c=2**<>;$\=$/;for$a(0..--$c){print$"x($c-$a&~1),
map$_*2&~$a?$"x4:$a&1?'/__\\':' /\ ',0..$a/2}

Answer 7

Lua, 139 characters

t={" /\\ ","/__\\"}for i=2,(...)do for j=1,#t do
t[#t+1]=t[j]:rep(2)k=(" "):rep(#t[j]/2)t[j]=k..t[j]..k end end
print(table.concat(t,"\n"))

Answer 8

Golfscript - 46

' /\ /__\ '4/{).+: ;.{ \ ++}%\{.+}%+~ ]}@~(*n*

Golfscript - 47

' /\ /__\ '4/): ;{  +: ;.{ \ ++}%\{.+}%+}@~(*n*

Golfscript - 48

' ': '/\ /__\\'+4/{2 *: ;.{ \ ++}%\{.+}%+}@~(*n*

Golfscript - 51

~' ': '/\ /__\\'+4/\(,{;2 *: ;.{ \ ++}%\{.+}%+}%;n*

Same algorithm as my shorter python ( and ruby ) answer

Golfscript - 78

2\~(?,{-1*}$1: ;{"  ":$*. 2base.{[$$+' /\ ']=}%n+@@{[$$+"/__\\"]=}%n .2*^: ;}%

Same algorithm as my longer python solution

This one has significant newlines

2\~(?,{-1*}$1: ;{"  ":
*. 2base.{[
2*' /\ ']=}%n+@@{[
2*"/__\\"]=}%n .2*^: ;}%

Answer 9

Go, 273 characters

package main
import(f"fmt";"os";s"strconv";)func main(){var
t=[2]string{" /\\ ","/__\\"};
n,_:=s.Atoi(os.Args[1]);a:=1;N:=a<<uint(n);for
N>0{N-=2;for
k:=0;k<2;k++{for
j:=0;j<N;j++{f.Print(" ")}b:=a;for
b>0{o:=t[k];if
b&1==0{o="    "}f.Print(o);b>>=1}f.Print("\n")}a^=a*2}}

Whitespace is all significant.

Unminized with gofmt sierpinski-3.go | perl -p -e's/\t/ /g':

package main

import (
    "fmt";
    "os";
    "strconv";
)

func main() {
    var t = [2]string{" /\\ ", "/__\\"};
    n, _ := strconv.Atoi(os.Args[1]);
    a := 1;
    N := a << uint(n);
    for N > 0 {
        N -= 2;
        for k := 0; k < 2; k++ {
            for j := 0; j < N; j++ {
                fmt.Print(" ")
            }
            b := a;
            for b > 0 {
                o := t[k];
                if b&1 == 0 {
                    o = "    "
                }
                fmt.Print(o);
                b >>= 1;
            }
            fmt.Print("\n");
        }
        a ^= a * 2;
    }
}

I got a good hint for Go golf here.

Answer 10

Perl, 82 strokes

This version no longer prints a trailing newline. Only the first newline is necessary:

$_=' /\ 
/__\\';
for$x(2..<>){
my$y;
$".=$";
s#.+#$y.=$/.$&x2,$".$&.$"#ge;
$_.=$y
}
print

If command-line switches are allowed, then by traditional Perl golf scoring, this is 77+3 strokes (the first newline is literal):

#!perl -p
$\=' /\ 
/__\\';
$y="",
$".=$",
$\=~s#.+#$y.=$/.$&x2,$".$&.$"#ge,
$\.=$y
for 2..$_

Please feel free to edit my answer if you find an improvement.

Answer 11

C

Same algorithm as the Perl answer, but weighing in heavier, at 131 necessary characters.

a,b;main(c,v)char**v;{c=1<<atoi(v[1]);for(a=0;a<c;a++,puts(""))
for(b=c;b--;write(1,b&~a?"    ":a&1?"/__\\":" /\\ ",4-2*(b>a)))--b;}

I thought write(1,…) was UNIX API, but this seems to compile and run fine on Windows too.

If you replace char by int, it saves one character and still works, but it's of questionable legality.

Answer 12

Clojure: 174 characters

Algorithm stolen from others above.

(doseq[q((fn f[n](if(= n 1)[" /\\ ""/__\\"](let[z(f(dec n))](concat(map #(let[y(repeat(Math/pow 2(dec n))\ )](apply str(concat y % y)))z)(map str z z)))))(read))](println q))

38 of those characters are parentheses. : (

(doseq [q ((fn f [n]
           (if (= n 1)
             [" /\\ " "/__\\"]
             (let [z (f (dec n))]
               (concat
                (map #(let [y (repeat (Math/pow 2 (dec n))\ )]
                        (apply str (concat y % y))) z)
                (map str z z))))) (read))] 
  (println q))

Answer 13

Ruby - 85 Characters

a=' /\ ','/__\\'
j=' '
2.upto(gets.to_i){j+=j;a=a.map{|x|j+x+j}+a.map{|x|x+x}}
puts a

Answer 14

Python, 120 characters (recursive solution)

S=lambda n:n<2and[" /\ ","/__\\"]or[" "*n+x+" "*n for x in S(n/2)]+[x+x for x in S(n/2)]
print"\n".join(S(1<<input()-1))

I started putting on the green where @fserb left off...

Answer 15

MATLAB - 64 characters (script version)

This assumes that you have the variable N already defined in your workspace:

A=[' /\ ';'/__\'];for i=1:N-1,B=32*ones(2^i);A=[B A B;A A];end;A

---

MATLAB - 78 characters (m-file function version)

Pass N as an argument to the function s:

function A=s(N),A=[' /\ ';'/__\'];for i=1:N-1,B=32*ones(2^i);A=[B A B;A A];end

Answer 16

Sorry I'm late. This is based on A. Rex's Perl solution:

                           &I                               
                          ;for                              
                         $x  (2                             
                        ..<>){$E                            
                       .=      $E                           
                      ;my$    y;3*                          
                     33  +3  **  3;                         
                    s".+"$y.=$n.$&x2                        
                   ,$              E.                       
                  $&.$            E"ge                      
                 ;;  $_          .=  $y                     
                }print;;        sub I{($                    
               E,      $n      ,$      F,                   
              $B,$    U)=(    $",$    /,qw                  
             (/   \   _  ))  ;$  _=  $E  .$                 
            F.$B.$E.$n.$F.$U.$U.$B};33333333

Answer 17

Nroff, 542

$ nroff -rn=5 file.n

.pl 1
.nf
.de b
. nr i 0
. while d\\$1\\ni \{\
.   \\$3 \\$1\\ni \\$2\\ni
.   nr i +1
. \}
..
.de push
. nr i 0
. while d\\$2\\ni \{\
.   nr i +1
. \}
. nr j 0
. while d\\$1\\nj \{\
.   ds \\$2\\ni \&\\*[\\$1\\nj]
.   nr i +1
.   nr j +1
. \}
..
.ds l0 \& /\[rs] \&
.ds l1 "/__\[rs]
.ds s \&\ 
.de o
. ds \\$2 \&\\*s\\*[\\$1]\\*s
..
.de p
. ds \\$2 \&\\*[\\$1]\\*[\\$1]
..
.de assign
. ds \\$2 \&\\*[\\$1]
..
.nr a 2
.while \na<=\nn \{\
. ds s \&\*s\*s
. b l m o
. b l n p
. b m l assign
. push n l
. nr a +1
.\}
.de t
\\*[\\$1]
..
.b l zz t

Answer 18

Logo (not exactly following the requirements): 47 characters

to F:n if:n[repeat 3[F(:n-1)fd 2^:n rt 120]]end

I tested this only with http://www.calormen.com/Logo/ so I don't know if it's portable. It doesn't follow the requirements, but surely logo must be the appropriate language here? :) I love that at the time of writing logo is one character short of equalling golfscript and J.