# 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/… 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. 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. Jun 9, 2012 at 3:23
• To avoid duplication, perhaps you should change to rules to allow only graphical implementations. Jun 9, 2012 at 3:45
• Lots of ideas from wolfram: wolframscience.com/nksonline/page-931 Feb 6, 2014 at 6:06

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. 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 Jan 21, 2014 at 3:05

# 6502 ASM, 134 bytes

start:
lda #$e1 sta$0
lda #$01 sta$1
ldy #$20 w_e: ldx #$00
eor ($0, x) sta ($0),y
inc $0 bne w_e inc$1
ldx $1 cpx #$06
bne w_e
rts


Pretty simple. Displays the triangles. Note that the top and left sides of the image are invisible due to the white background of PPCG. (-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++];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++]


First, we generate three versions of p: 1:p which is p with a 1 prepended, p itself and tail p++ 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! May 29, 2018 at 7:28
• @Laikoni Ooh, some very nice improvements in there! May 29, 2018 at 11:54

## 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,c,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 Mar 28, 2018 at 9:18
• @ASCII-only Good idea! 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


## The output ## 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


# 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