43
\$\begingroup\$

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.

enter image description here

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ See also the old Stack Overflow version: stackoverflow.com/questions/1726698/… \$\endgroup\$ – dmckee Jun 9 '12 at 3:12
  • 3
    \$\begingroup\$ 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. \$\endgroup\$ – Kibbee Jun 9 '12 at 3:22
  • \$\begingroup\$ 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. \$\endgroup\$ – dmckee Jun 9 '12 at 3:23
  • \$\begingroup\$ To avoid duplication, perhaps you should change to rules to allow only graphical implementations. \$\endgroup\$ – primo Jun 9 '12 at 3:45
  • \$\begingroup\$ Lots of ideas from wolfram: wolframscience.com/nksonline/page-931 \$\endgroup\$ – luser droog Feb 6 '14 at 6:06

37 Answers 37

1
\$\begingroup\$

Common Lisp, 80 chars

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

Output:

ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ 
 ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ 
 Δ   Δ   Δ   Δ   Δ   Δ   Δ   Δ  
  ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ  
  Δ Δ     Δ Δ     Δ Δ     Δ Δ   
   ΔΔ      ΔΔ      ΔΔ      ΔΔ   
   Δ       Δ       Δ       Δ    
    ΔΔΔΔΔΔΔΔ        ΔΔΔΔΔΔΔΔ    
    Δ Δ Δ Δ         Δ Δ Δ Δ     
     ΔΔ  ΔΔ          ΔΔ  ΔΔ     
     Δ   Δ           Δ   Δ      
      ΔΔΔΔ            ΔΔΔΔ      
      Δ Δ             Δ Δ       
       ΔΔ              ΔΔ       
       Δ               Δ        
        ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ        
        Δ Δ Δ Δ Δ Δ Δ Δ         
         ΔΔ  ΔΔ  ΔΔ  ΔΔ         
         Δ   Δ   Δ   Δ          
          ΔΔΔΔ    ΔΔΔΔ          
          Δ Δ     Δ Δ           
           ΔΔ      ΔΔ           
           Δ       Δ            
            ΔΔΔΔΔΔΔΔ            
            Δ Δ Δ Δ             
             ΔΔ  ΔΔ             
             Δ   Δ              
              ΔΔΔΔ              
              Δ Δ               
               ΔΔ               
               Δ
\$\endgroup\$
1
\$\begingroup\$

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.

800x800 Sierpinski triangle generated with JavaFx

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!

\$\endgroup\$
  • \$\begingroup\$ Can't you use 1e6 for number of iterations \$\endgroup\$ – ASCII-only Mar 28 '18 at 9:18
  • \$\begingroup\$ @ASCII-only Good idea! \$\endgroup\$ – David Conrad Mar 29 '18 at 0:02
1
\$\begingroup\$

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.

sierpinski

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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()
\$\endgroup\$
0
\$\begingroup\$

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 
\$\endgroup\$
0
\$\begingroup\$

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.

output

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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