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

Wiencke

I am sorry this is a 'generic' golf, I'm starting to run out of ideas... – Wiencke

I started implementing this last night in javascript using the canvas tag, so I will assume that won't work here. – Hinda

I can draw this to the screen in about 2 lines in C++ :p That XOR operator is freaking crazy. – Lanciform

"I'm starting to run out of ideas..." You've been mining the "console output figures" vein pretty hard. Maybe it's time to give that a break. One of the things that made Lasers different was that the input was non-trivial. Or even take a break on the whole thing, but I've gotten used to Thursday tee time. I dink around with most of your problems even if I don't submit many solutions. – Cheery

LiraNuna, you've done an awesome job. There is a reason that your challenges get by far the most votes. If you never posted another you would still be a Stack Overflow legend. Thanks for all the fun! – Camargo

I'm just curious... can someone please do one up in Mindfuck? – Whom

@Whom - It's brain (traditionally lowercase), not Mind, and the word from @Atwood is that it's "The Language that Shall Not Be Named". See meta.stackoverflow.com/questions/19478/the-many-memes-of-meta/… – Lesser

@dmckee: Then I'll try to think more of the way of Lasers. Though designing Lasers was tough. I have a few ideas but they are not polished. I can always start "Reverse" series! (reverse beehive!) – Wiencke

I really don't like these text formatting golfs. I end up doing half of them anyways, though, since coming up with good mathematical/computational puzzle golfs is even harder. – Alathia

ephemient: "text formatting" ? What about cubes or hourglass style? those created ASCII from variables in input. Were those bad? I personally loved cubes and beehive - They were simple enough for newbies to create long answers and participate, but had the potential to be short with proper code. – Wiencke

@LiraLuna: Those were interesting, and I feel sad that I was too late to make any good contributions to them. And despite my "dislike" I answered anyways (probably because it only took minutes to write the J solution, as opposed to the hours it usually takes). – Alathia

FYI: I started some meta discussion about these code-golf questions @ meta.stackexchange.com/questions/29687/… – Immoderacy

@LiraNuna: If you've seen mine, they don't get voted up as much but i think that vein of questions has plenty of unasked ones waiting or your touch! Or maybe those will be my trademark... :) – Entero

So, we have a tie - J vs. Golfscript. Which one should be picked? Golfscript was the first to reach 46 char count, should it be the 'winner'? I always select the 'winner' on Monday. – Wiencke

Answer 1

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*^: ;}%

Luisaluise

Thanks for your hard work, you've pushed me to strip my solution as much as I can -- and I still can't beat yours :) – Alathia

This one was selected since it was the first to reach the 46 character mark. – Wiencke

Answer 2

J

46 characters, reading from stdin.

(,.~,~[,.~' '$~#,#)^:(<:".1!:1]3)' /\',:'/__\'

---

\n always delimits sentences, which made it impossible to fit inside S₃ (only 54 characters to play with). S₄ is a bit big at 162, so I padded it to fit. Serendipitously, /\ is a legal adverb. ☺

               /\
              i=:3
             /\  /\
            %r=:1!:1
           /\      /\
          t=:]    [r+i
         /\  /\  /\  /\
        b=:' /\',:'/__\'
       /\              /\
      i=:1            -".t
     /\  /\          /\  /\
    h=:(' '$        ~#,#),.]
   /\      /\      /\      /\
  s=:(    h^:1    ,d=:    ,.~)
 /\  /\  /\  /\  /\  /\  /\  /\
(,,&(10{a.)"1[s^:(-i)b)(1!:2)(4)

Alathia

It's 60 characters. Challenge asks for a full program. – Wiencke

Aww, there's are two sleepy smilies there (~,~) and a smiling one! (=]). This is so cute! – Wiencke

I actually see another one :( – Entero

I already gave you +1 on Friday :p, but the triangle is fantastic – Spooner

Answer 3

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                

Morven

I was going to do this for golfscript but I didn't have enough characters – Spooner

Answer 4

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.

Bethel

I'm guessing that "Go" isn't short for "Golfing Language" – Morven

@mobrule: I only started learning Go yesterday. I'm sure that more experienced Go programmers could do better. Unfortunately there are not many experienced Go programmers since the language was only announced two days ago. See stackoverflow.com/questions/1712172 – Missing

@LiraNuna: probably just my one-day-old Go is ugly. b&1==0 is true if b contains an even number. It pulls the bottom bit out of b and tests whether it is zero or not. This is straight from Gnibbler's algorithm. – Missing

The := makes me feel like I'm back in my high school Turbo Pascal class. – Radiogram

I don't know Turbo Pascal, but in Go x:=1 is short for var x int = 1 and y:="moo" is short for var y string = "moo". It pulls the type off the variable. – Missing

It's not fair to call a language ugly based on a code golf example. Beautiful code is almost against the code golf requirements. – Insurrection

In the unminimized version, all semicolons should be removed. – Slambang

Answer 5

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

Luisaluise

This same challenge was posted on AnarchyGolf. Here was my solution: golf.shinh.org/reveal.rb?Sierpinski+Fractal/MarkByers/… – Osmic

Answer 6

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.

Suzansuzann

If you're going to make extensive use of switches, you traditionally write it as a shell invocation: perl -pae'code here' (counting all the characters of the shell invocation and the shell quotes as part of the answer, which would also disallow you from using single quotes in your answer). But that might actually get longer. – Lesser

@Chris Lutz: Traditional Perl golf scoring is the length of your code plus how many characters you have to add over the usual perl. So in my case, I think it's 77 strokes plus 4 for the extra ` -pa`. – Suzansuzann

@ephemient: I wasn't counting the newlines you just deleted anyway; they were there only for readability reasons (if you can say "readability" in this context). After I'm sure you're done editing, I'll change the answer to make that clear. Thanks for the help, though. – Suzansuzann

@A. Rex - I've always counted the invocation. (And #!perl isn't a valid shebang line on my system.) – Lesser

@Chris Lutz: That's fine. I put the solutions in this order because I presume the first is the minimal one accepted by this particular golfing community. The Perl golf community would accept the second. It's worth noting that Perl golf has a long and storied tradition and I believe is the source of the word "golf". – Suzansuzann

Re #!perl: I include that because it's the shortest string so that Perl itself will interpret the switches. If I can push them to the command-line, great! If not, I can count those as raw characters. I think the second solution should be 87 characters now, which of course is longer than the first. It is possible in theory, however, to have it be less -- see my improvements on @mobrule's solution for the "Musical Notes" competition: https://mcmap.net/q/226262/-code-golf-musical-notes/… – Suzansuzann

Here's a 104-stroke solution that might inspire someone: $_='/'.$"x(1+1<<<>)."/ \n";$\=$_.$\while s'.__.' /\ 'g||s#/.+?\S.#$"."/__\\"x($&=~y///c/4).$"#ge;print"" -- yes, it prints the empty string at the end =) – Suzansuzann

This is a neat solution. Sure GolfScript and J are shorter, but... surprise, this is readable. – Tepid

@dlamblin, I'm sure the golfscript and J would be readable for you if you had spent as much time learning them as you have perl. I have only been using golfscript a short time. Everything you need to learn is on one webpage golfscript.com/golfscript/builtin.html – Spooner

And (almost) everything you need to know in J is linked from one webpage jsoftware.com/help/dictionary/vocabul.htm – Alathia

Answer 7

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}

Kemme

something i just found in the prelude that might help main=readLn>>=putStr.unlines.f – Bantling

zipWith! i knew there was a better way to do that – Bantling

Answer 8

Ruby — 85

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

---

101 chars — /\-modified solution from Rosetta Code

(a=2**gets.to_i).times{|y|puts" "*(a-y-1)+(0..y).map{|x|~y&x>0?'  ':y%2>0?x%2>0?'_\\':'/_':'/\\'}*''}

Luisaluise

Answer 9

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}

Alathia

You can save 5 characters by reading from stdin with <> if you want. If you don't, pop still saves characters. Either way, you can use the ridiculous construct $c=2**~-<>; or $c=2**~-pop; to save on parentheses around the /2. – Suzansuzann

Answer 10

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.

Ibby

Answer 11

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

Radiogram

Answer 12

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.

Alathia

write() is a Unix API, and part of POSIX, but Windows provides a lot of POSIX functions. They're all "deprecated" so to be "correct" on Windows you should use _write() but a) this is code golf, and b) the idea that POSIX is deprecated makes me giggle. – Lesser

Answer 13

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

Toilette

This can be shortened slightly by changing int(raw_input()) to input() – Coat

Answer 14

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

Camargo

Answer 15

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

Fishy

Answer 16

GolfScript (45 44 chars)

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

Similar to gnibbler's solution. My initial attempt was already quite similar, and then I looked at his and borrowed some ideas.

Centenarian

Answer 17

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

Adeno

Answer 18

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

Fernandes

Answer 19

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

Merta

There must be a way to shorten this awful System.Console.ReadLine... what a waste of bytes ;) – Robertson

Answer 20

Prolog, 811 Chars

:- module(sierpinsky, [draw/1]).

% draw(+Level)
draw(N) :- K is 2^(N+1)-1,
  for(Line, 0, K),
  draw2(N, Line, true, nl),
  fail.
draw(_).

% draw2(+Level, +Line, +Before, +After)
draw2(0, 0, Before, After) :- !,
  Before, write(' /\\ '), After.
draw2(0, 1, Before, After) :- !,
  Before, write('/__\\'), After.
draw2(N, Line, Before, After) :- N>0, K is 2^N, Line < K, !, M is N-1,
  draw2(M, Line, (Before, tab(K)), (tab(K), After)).
draw2(N, Line, Before, After) :- N>0, K is 2^N, Line >= K, !, M is N-1,
  Line2 is Line - K,
  draw2(M, Line2, Before, draw2(M, Line2, true, After)).

% for(+Variable, +Integer, +Integer)
for(V, N, M) :- N =< M, V = N.
for(V, N, M) :- N < M, K is N+1, for(V, K, M).

% tab(+Integer)
tab(N) :- for(_, 1, N), write(' '), fail.
tab(_).

Spleenful

Answer 21

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

Lesley