44
\$\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 --- ex-moderator kitten 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 --- ex-moderator kitten 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

39 Answers 39

1
2
2
\$\begingroup\$

Haskell, 166 154 bytes

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 154 bytes: Try it online! Nice explanation by the way! \$\endgroup\$ – Laikoni May 29 '18 at 7:28
  • \$\begingroup\$ @Laikoni Ooh, some very nice improvements in there! \$\endgroup\$ – Sacchan May 29 '18 at 11:54
2
\$\begingroup\$

05AB1E, 9 bytes

1=IGx^Db,

Try it online!

The number of rows is equal to the input.

Explanation:

1=IGx^Db,
1=         print "1" and push 1
  IG       for N in range(1, I): (where I is the input)
    x      push last element on stack multiplied by 2
     ^     pop last two elements, push their bitwise xor (output is in decimal)
      D    duplicate last element of stack
       b,  replace last element of stack with its binary representation, then print/pop

This takes advantage of the fact that a(n+1) = a(n) XOR 2*a(n), which I found on this relevant OEIS page

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 80 chars

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

Output:

ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ
Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ 
 ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ  ΔΔ 
 Δ   Δ   Δ   Δ   Δ   Δ   Δ   Δ  
  ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ    ΔΔΔΔ  
  Δ Δ     Δ Δ     Δ Δ     Δ Δ   
   ΔΔ      ΔΔ      ΔΔ      ΔΔ   
   Δ       Δ       Δ       Δ    
    ΔΔΔΔΔΔΔΔ        ΔΔΔΔΔΔΔΔ    
    Δ Δ Δ Δ         Δ Δ Δ Δ     
     ΔΔ  ΔΔ          ΔΔ  ΔΔ     
     Δ   Δ           Δ   Δ      
      ΔΔΔΔ            ΔΔΔΔ      
      Δ Δ             Δ Δ       
       ΔΔ              ΔΔ       
       Δ               Δ        
        ΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔΔ        
        Δ Δ Δ Δ Δ Δ Δ Δ         
         ΔΔ  ΔΔ  ΔΔ  ΔΔ         
         Δ   Δ   Δ   Δ          
          ΔΔΔΔ    ΔΔΔΔ          
          Δ Δ     Δ Δ           
           ΔΔ      ΔΔ           
           Δ       Δ            
            ΔΔΔΔΔΔΔΔ            
            Δ Δ Δ Δ             
             ΔΔ  ΔΔ             
             Δ   Δ              
              ΔΔΔΔ              
              Δ Δ               
               ΔΔ               
               Δ
| improve this answer | |
\$\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!

| improve this answer | |
\$\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\$

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!

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

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

the output

| improve this answer | |
\$\endgroup\$
1
2

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.