# Draw A Sierpinski Triangle

The Sierpinsky Triangle is a fractal created by taking a triangle, decreasing the height and width by 1/2, creating 3 copies of the resulting triangle, and place them such each triangle touches the other two on a corner. This process is repeated over and over again with the resulting triangles to produce the Sierpinski triangle, as illustrated below.

Write a program to generate a Sierpinski triangle. You can use any method you want to generate the pattern, either by drawing the actual triangles, or by using a random algorithm to generate the picture. You can draw in pixels, ascii art, or whatever you want, so long as the output looks similar to the last picture shown above. Fewest characters wins.

• See also the old Stack Overflow version: stackoverflow.com/questions/1726698/… Commented Jun 9, 2012 at 3:12
• I got the idea for this after seeing the pascal's triangle question, and remembering the example program for this in my TI-86 manual. I decided to convert it to QBasic and then code golf it. Commented Jun 9, 2012 at 3:22
• There is no problem with running a challenge here that was already run on Stack Overflow, but many people will not want to present the same material again. So I link them for the edification of later visitors. Commented Jun 9, 2012 at 3:23
• To avoid duplication, perhaps you should change to rules to allow only graphical implementations. Commented Jun 9, 2012 at 3:45
• Lots of ideas from wolfram: wolframscience.com/nksonline/page-931 Commented Feb 6, 2014 at 6:06

## C, 106 chars

i,j;main(){for(;i<32;j>i/2?puts(""),j=!++i:0)
printf("%*s",j++?4:33-i+i%2*2,i/2&j^j?"":i%2?"/__\\":"/\\");}


(It still amuses me that puts("") is the shortest way to output a newline in C.)

Note that you can create larger (or smaller) gaskets by replacing the 32 in the for loop's test with a larger (smaller) power of two, as long as you also replace the 33 in the middle of the printf() with the power-of-two-plus-one.

• Suggest j>i/2&&puts("",j=!++i) instead of j>i/2?puts(""),j=!++i:0 Commented Mar 6, 2021 at 9:24

Postscript, 205 203

[48(0-1+0+1-0)49(11)43(+)45(-)/s{dup
0 eq{exch{[48{1 0 rlineto}49 1 index
43{240 rotate}45{120 rotate}>>exch
exch 1 sub s}forall}ifelse 1 add}>>begin
9 9 moveto(0-1-1)9 s fill


Rewrite using strings and recursion ends up at exactly the same count. But the depth-limitations of the macro-approach are overcome.

Edit: fill is shorter than stroke.

Indented and commented.

%!
[   % begin dictionary
48(0-1+0+1-0) % 0
49(11)        % 1
43(+)         % +
45(-)         % -
/s{ % string recursion-level
dup 0 eq{ % level=0
exch{  % iterate through string
[
48{1 0 rlineto} % 0
49 1 index      % 1
43{240 rotate}  % +
45{120 rotate}  % -
>>exch get exec % interpret turtle command
}forall
}{ % level>0
exch{  % iterate through string
1 sub s    % recurse with level-1
}forall
}ifelse
}
>>begin
9 9 moveto(0-1-1)9 s fill % execute and fill


Adding 0 setlinewidth gives a better impression of how deep this one goes.

• This one's my favorite. Commented Jan 17, 2014 at 14:10
• There's a way to make it shorter with this external lib that I wrote after the fact and cannot use. :P Commented Jan 21, 2014 at 3:05

(-12 bytes thanks to Laikoni, (zip and list comprehension instead of zipWith and lambda, better way of generating the first line))

i#n|let k!p=p:(k+1)![m*l*r+(m*(l*r-l-r)+1)*0^mod k(2^(n-i))|(l,m,r)<-zip3(1:p)p$tail p++[1]];x=1<$[2..2^n]=mapM(putStrLn.map("M "!!))$take(2^n)$1!(x++0:x)


Try it online!

Explanation:

The function i#n draws an ASCII-Triangle of height 2^n after i steps of iteration.

The encoding used internally encodes empty positions as 1 and full positions as 0. Therefore, the first line of the triangle is encoded as [1,1,1..0..1,1,1] with 2^n-1 ones on both sides of the zero. To build this list, we start with the list x=1<$[2..2^n], i.e. the list [2..2^n] with everything mapped to 1. Then, we build the complete list as x++0:x The operator k!p (detailed explanation below), given a line index k and a corresponding p generates an infinite list of lines that follow p. We invoke it with 1 and the starting line described above to get the entire triangle, and then only take the first 2^n lines. Then, we simply print each line, replacing 1 with space and 0 with M (by accessing the list "M " at location 0 or 1). Operator k!p is defined as follows: k!p=p:(k+1)![m*l*r+(m*(l*r-l-r)+1)*0^mod k(2^(n-i))|(l,m,r)<-zip3(1:p)p$tail p++[1]]


First, we generate three versions of p: 1:p which is p with a 1 prepended, p itself and tail p++[1] which is everything but the first element of p, with a 1 appended. We then zip these three lists, giving us effectively all elements of p with their left and right neighbors, as (l,m,r). We use a list comprehension to then calculate the corresponding value in the new line:

m*l*r+(m*(l*r-l-r)+1)*0^mod k(2^(n-i))


To understand this expression, we need to realise there are two basic cases to consider: Either we simply expand the previous line, or we are at a point where an empty spot in the triangle begins. In the first case, we have a filled spot if any of the spots in the neighborhood is filled. This can be calculated as m*l*r; if any of these three is zero, then the new value is zero. The other case is a bit trickier. Here, we basically need edge detection. The following table gives the eight possible neighborhoods with the resulting value in the new line:

000 001 010 011 100 101 110 111
1   1   1   0   1   1   0   1


A straightforward formula to yield this table would be 1-m*r*(1-l)-m*l*(1-r) which simplifies to m*(2*l*r-l-r)+1. Now we need to choose between these two cases, which is where we use the line number k. If mod k (2^(n-i)) == 0, we have to use the second case, otherwise, we use the first case. The term 0^(mod k(2^n-i)) therefore is 0 if we have to use the first case and 1 if we have to use the second case. As a result, we can use

m*l*r+(m*(l*r-l-r)+1)*0^mod k(2^(n-i))


in total - if we use the first case, we simply get m*l*r, while in the second case, an additional term is added, giving the grand total of m*(2*l*r-l-r)+1.

• 154 bytes: Try it online! Nice explanation by the way! Commented May 29, 2018 at 7:28
• @Laikoni Ooh, some very nice improvements in there! Commented May 29, 2018 at 11:54

# Binary Lambda Calculus (BLC): 51 bits (6.375 bytes)

000100011010000100000101010110110000010110110011010


Equivalent to the term \(\(0 0) \(\\(0 1 \\0 1 1) (0 0))).

Since BLC has no graphical output, this solution assumes a screen as defined in this blog post.

The term has no normal form and generates an infinitely detailed Sierpinski triangle. Rendered using lambda-screen which stops after a finite amount of reductions:

## Python (215 209)

Uses the Chaos Theory method of generating Sierpinski's Triangle.

import random as r,pygame as p
d=p.display
x=99;X=49;y=x,x
s=d.set_mode(y)
c=[X,X]
P=(X,0),(0,x),y
while 1:
a=r.choice(P)
for i in 0,1:c[i]=(c[i]+a[i])/2
p.draw.rect(s,[x]*3,p.Rect(c[0],c[1],2,2))
d.flip()


# Common Lisp, 80 chars

(#1=dotimes(i 32)(#1#(j 32)(princ(if(logtest(- j(ash i -1))i)' 'Δ)))(terpri))


Output:

ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ
ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ
Δ   Δ   Δ   Δ   Δ   Δ   Δ   Δ
ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ
Δ Δ     Δ Δ     Δ Δ     Δ Δ
ΔΔ      ΔΔ      ΔΔ      ΔΔ
Δ       Δ       Δ       Δ
ΔΔΔΔΔΔΔΔ        ΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ         Δ Δ Δ Δ
ΔΔ  ΔΔ          ΔΔ  ΔΔ
Δ   Δ           Δ   Δ
ΔΔΔΔ            ΔΔΔΔ
Δ Δ             Δ Δ
ΔΔ              ΔΔ
Δ               Δ
ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ Δ Δ Δ Δ
ΔΔ  ΔΔ  ΔΔ  ΔΔ
Δ   Δ   Δ   Δ
ΔΔΔΔ    ΔΔΔΔ
Δ Δ     Δ Δ
ΔΔ      ΔΔ
Δ       Δ
ΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ
ΔΔ  ΔΔ
Δ   Δ
ΔΔΔΔ
Δ Δ
ΔΔ
Δ


# JavaFx, 400 bytes

import javafx.scene.*;import javafx.scene.canvas.*;public class S extends javafx.application.Application{public void start(javafx.stage.Stage s){Canvas v=new Canvas(640,640);int[]xs={320,0,640},ys={0,640,640};for(int i=0,x=0,y=0,n=0;i<999999;i++){n=new java.util.Random().nextInt(3);v.getGraphicsContext2D().fillRect(x+=(xs[n]-x)/2,y+=(ys[n]-y)/2,1,1);}s.setScene(new Scene(new Group(v)));s.show();}}


Operates via the move-halfway-to-a-random-vertex method. 999,999 iterations, 640x640 canvas. I could have golfed a few more bytes by reducing the size or the number of iterations, but when you're at 400 bytes what's the point? No one wants to look at postage stamp-sized output.

Ungolfed, mostly:

import javafx.scene.*;
import javafx.scene.canvas.*;

public class S extends javafx.application.Application {
public void start(javafx.stage.Stage s) {
Canvas v = new Canvas(640, 640);
int[] xs = {320,0,640}, ys = {0,640,640};
for (int i=0, x=0, y=0, n=0; i < 999999; i++) {
n = new java.util.Random().nextInt(3);
v.getGraphicsContext2D().fillRect(
x += (xs[n]-x)/2, y += (ys[n]-y)/2, 1, 1);
}
s.setScene(new Scene(new Group(v)));
s.show();
}
}


JavaFx has a very annoying way of putting every class you might want to use in separate javafx.application, javafx.stage, javafx.scene, javafx.canvas packages. Grr!

• Can't you use 1e6 for number of iterations Commented Mar 28, 2018 at 9:18
• @ASCII-only Good idea! Commented Mar 29, 2018 at 0:02

# Pyt, 19 bytes

02⁵ř↔Á⁻Đ0⇹Řć2%ǰƥłŕ


# Result:

1
11
101
1111
10001
110011
1010101
11111111
100000001
1100000011
10100000101
111100001111
1000100010001
11001100110011
101010101010101
1111111111111111
10000000000000001
110000000000000011
1010000000000000101
11110000000000001111
100010000000000010001
1100110000000000110011
10101010000000001010101
111111110000000011111111
1000000010000000100000001
11000000110000001100000011
101000001010000010100000101
1111000011110000111100001111
10001000100010001000100010001
110011001100110011001100110011
1010101010101010101010101010101
11111111111111111111111111111111


# Explanation:

0                        Push 0
2⁵                      Push 32
ř↔                    Pop 32, and push [32,31,30,29,...,3,2,1]
Á                   Push contents of array onto stack
ł       While the top of the stack is not zero, loop:
⁻                 Decrement the number at the top of the stack
Đ0⇹Řć2%ǰƥ        Calculate the kth row of Pascal's Triangle mod 2 and print
ŕ      Remove the 0


Try it online!

# asm2bf, 219 bytes

## Code

@a
clrr2
@b
pshr1
movr4,r2
@c
movr5,r1
modr5,2
movr6,r4
modr6,2
mulr5,r6
cger5,1
cmor5,1
cjn%d
asrr1
asrr4
jnzr1,%c
jnzr4,%c
clrr3
@d
cger3,1
movr3,42
cmor3,32
outr3
popr1
incr2
cger2,64
cjz%b
out10
incr1
cger1,64
cjz%a


## JavaScript (70 chars):

for(y=32;y--;){for(s="",x=32;x--;)s+=(x-y/2)&y?" ":"o";console.log(s)}


Using HTML guy's method. This feels like cheating, though. He gets the thread.

               oo
oo
o oo
oooo
o   oo
oo  oo
o o o oo
oooooooo
o       oo
oo      oo
o o     o oo
oooo    oooo
o   o   o   oo
oo  oo  oo  oo
o o o o o o o oo
oooooooooooooooo
o               oo
oo              oo
o o             o oo
oooo            oooo
o   o           o   oo
oo  oo          oo  oo
o o o o         o o o oo
oooooooo        oooooooo
o       o       o       oo
oo      oo      oo      oo
o o     o o     o o     o oo
oooo    oooo    oooo    oooo
o   o   o   o   o   o   o   oo
oo  oo  oo  oo  oo  oo  oo  oo
o o o o o o o o o o o o o o o oo
oooooooooooooooooooooooooooooooo


=y$171--=x$172--!t$x-yœy]3#" "?393~!x+[2>""!+[  output: 0 00 0 0 0000 0 0 00 00 0 0 0 0 00000000 0 0 00 00 0 0 0 0 0000 0000 0 0 0 0 00 00 00 00 0 0 0 0 0 0 0 0 0000000000000000  # Applesoft BASIC, 246 bytes 1 HGR:HCOLOR=3:HOME:DIM x(3),y(3):x(0)=0:y(0)=160:x(1)=90:y(1)=0:x(2)=180:y(2)=160:FOR i=0 to 2:HPLOT x(i),y(i):NEXT i 2 x=int(RND(1)*180):y=int(RND(1)*150):HPLOT x,y:FOR i=1 to 2000:v=int(rnd(1)*3):x=(x+x(v))/2:y=(y+y(v))/2:HPLOT x,y:NEXT:GOTO 2  Not the most efficient, nor does it draw a perfect Sierpinski, but it's fun. May stick pixels in random places or miss a few points depending on your system's pRNG quality. Ungolfed: 100 HGR : HCOLOR=3 : HOME 110 REM set up three points to form a triangle 120 DIM x(3), y(3) 130 x(0) = 0 : y(0) = 160 140 x(1) = 90 : y(1) = 0 150 x(2) = 180 : y(2) = 160 160 REM plot the vertices of the triangle 170 FOR i= 0 to 2 180 HPLOT x(i), y(i) 190 NEXT i 200 REM pick a random starting point 210 x = int(RND(1)*180) : y = int(RND(1)*150) 220 hplot x,y 230 FOR i = 1 to 2000 240 REM randomly pick one of the triangle vertices 250 v = int(rnd(1)*3) 260 REM move the point half way to the triangle vertex 270 x = (x + x(v)) / 2 : y = (y + y(v)) / 2 280 HPLOT x,y 290 NEXT  # Bash (94 chars) Copyed from the html guy of this thread for((y=64;y--;));do s="";for((x=64;x--;));do(((x-y/2)&y))&&s+=" "||s+="Δ";done;echo "$s";done


# Uiua, 13 bytes

⍥⬚0(⊂≡⊂..)9¤1


Try it!

Here's the output, you can get more iterations by changing the 9 to a higher number.

Explanation:

Starting with [1], 9 times do: duplicate horizontally, and prepend to current result, all with a fill-value of 0.

Intermediate values (using o instead of 1 and _ instead of 0):

o

oo
o_

oooo
o_o_
oo__
o___

oooooooo
o_o_o_o_
oo__oo__
o___o___
oooo____
o_o_____
oo______
o_______

[etc]
`