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/… – dmckee Jun 9 '12 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. – Kibbee Jun 9 '12 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. – dmckee Jun 9 '12 at 3:23
• To avoid duplication, perhaps you should change to rules to allow only graphical implementations. – primo Jun 9 '12 at 3:45
• Lots of ideas from wolfram: wolframscience.com/nksonline/page-931 – luser droog Feb 6 '14 at 6:06

HTML + JavaScript, 150 characters (see notes for 126 characters)

Whitespace inserted for readability and not counted.

<title></title><canvas></canvas><script>
for(x=k=128;x--;)for(y=k;y--;)
x&y||document.body.firstChild.getContext("2d").fillRect(x-~y/2,k-y,1,1)
</script>


The core of it is applying the rule of coloring pixels for which x & y == 0 by the conditional x&y||, which produces a “Sierpinski right triangle”; and x-~y/2,k-y are a coordinate transformation to produce the approximately equilateral display.

A less correct (HTML-wise) version is 126 characters:

<canvas><script>
for(x=k=128;x--;)for(y=k;y--;)
x&y||document.body.firstChild.getContext("2d").fillRect(x-~y/2,k-y,1,1)
</script>


(The way in which this is less correct is that it omits the title element and the end tag of the canvas element, both of which are required for a correct document even though omitting them does not change the interpretation of the document.)

Three characters can be saved by eliminating k in favor of the constant 64, at the cost of a smaller result; I wouldn't count the 8 option as it has insufficient detail.

Note that a size of 256 or higher requires attributes on the <canvas> to increase the canvas size from the default.

• Nobody cares if your HTML validates at codegolf :-) Some improvements: <canvas id=c> and then c.getContext. Shorten loops: for(x=k=128;x--;)for(y=k;y--;) – copy Jun 9 '12 at 15:47
• ids being turned into global variables is a horrible misfeature which I refuse to acknowledge, and WebKit does not implement it in standards mode. Thank you for the loop trick. – Kevin Reid Jun 9 '12 at 16:53
• Minor improvement: x&y?0: can be replaced with x&y|| Otherwise nice solution. – primo Jun 10 '12 at 11:20
• Bravo, this is just wonderful. – boothby Jun 14 '12 at 7:17
• As this contains a script, I'd recommend titling it as HTML + Javascript. That'll make it clearer to someone skimming what sort of answer it is. – user62131 Nov 23 '16 at 21:31

' /\ /__\ '4/){.+\.{[2$.]*}%\{.+}%+\}3*;n*  Output:  /\ /__\ /\ /\ /__\/__\ /\ /\ /__\ /__\ /\ /\ /\ /\ /__\/__\/__\/__\ /\ /\ /__\ /__\ /\ /\ /\ /\ /__\/__\ /__\/__\ /\ /\ /\ /\ /__\ /__\ /__\ /__\ /\ /\ /\ /\ /\ /\ /\ /\ /__\/__\/__\/__\/__\/__\/__\/__\  Change the "3" to a larger number for a larger triangle. Python (234) Maximal golfing, tiny image: #!/usr/bin/env python3 from cairo import* s=SVGSurface('_',97,84) g=Context(s) g.scale(97,84) def f(w,x,y): v=w/2 if w>.1:f(v,x,y);f(v,x+w/4,y-v);f(v,x+v,y) else:g.move_to(x,y);g.line_to(x+v,y-w);g.line_to(x+w,y);g.fill() f(1,0,1) s.write_to_png('s.png')  Requires python3-cairo. To get a nice large image I needed 239 characters. • import cairo as c whould save you a few characters – quasimodo Jun 17 '12 at 13:33 • this answer needs more upvotes – ixtmixilix Jan 1 '13 at 23:47 Mathematica - 32 characters Nest[Subsuperscript[#,#,#]&,0,5]  Mathematica - 37 characters Grid@CellularAutomaton[90,{{1},0},31]  This will produce a 2D table of 0 and 1, where 1s are drawing Sierpinski Triangle. • At the cost of 5 additional characters, your second solution will display better with ArrayPlot@CellularAutomaton[90, {{1}, 0}, 31] or MatrixPlot@CellularAutomaton[90, {{1}, 0}, 31]. – DavidC Jan 2 '13 at 18:25 • ...or with ReliefPlot@... – DavidC Jan 2 '13 at 18:29 • I get this. How did you get the output without all the brackets? – Mr.Wizard Mar 27 '13 at 5:52 • @Mr.Wizard hmm... where in the world brackets are from? It even works here: mathics.net Try and let me know. – Vitaliy Kaurov Mar 27 '13 at 6:23 • @Vitaliy Kaurov The primary (32 character) solution is astonishing. Can you do the "fractal tree" challenge (elsewhere on PCG) using the same technique? – Michael Stern Jan 21 '14 at 16:57 Python, 101 86 Uses the rule 90 automaton. x=' '*31 x+='.'+x exec"print x;x=''.join(' .'[x[i-1]!=x[i-62]]for i in range(63));"*32  This is longer, but prettier. x=' '*31 x+=u'Δ'+x exec u"print x;x=''.join(u' Δ'[x[i-1]!=x[i-62]]for i in range(63));"*32  Edit: playing with strings directly, got rid of obnoxiously long slicing, made output prettier. Output:  Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ  • That looks really cool :D – beary605 Jun 11 '12 at 5:14 • Using that U+0394 capital Delta is a really nice touch. – David Conrad May 26 '17 at 19:08 J ,/.(,~,.~)^:6,'o'  Not ideal, since the triangle is lopsided and followed by a lot of whitespace - but interesting nonetheless I thought. Output: o oo o o oooo o o oo oo o o o o oooooooo o o oo oo o o o o oooo oooo o o o o oo oo oo oo o o o o o o o o oooooooooooooooo o o oo oo o o o o oooo oooo o o o o oo oo oo oo o o o o o o o o oooooooo oooooooo o o o o oo oo oo oo o o o o o o o o oooo oooo oooo oooo o o o o o o o o oo oo oo oo oo oo oo oo o o o o o o o o o o o o o o o o oooooooooooooooooooooooooooooooo o o oo oo o o o o oooo oooo o o o o oo oo oo oo o o o o o o o o oooooooo oooooooo o o o o oo oo oo oo o o o o o o o o oooo oooo oooo oooo o o o o o o o o oo oo oo oo oo oo oo oo o o o o o o o o o o o o o o o o oooooooooooooooo oooooooooooooooo o o o o oo oo oo oo o o o o o o o o oooo oooo oooo oooo o o o o o o o o oo oo oo oo oo oo oo oo o o o o o o o o o o o o o o o o oooooooo oooooooo oooooooo oooooooo o o o o o o o o oo oo oo oo oo oo oo oo o o o o o o o o o o o o o o o o oooo oooo oooo oooo oooo oooo oooo oooo o o o o o o o o o o o o o o o o oo oo oo oo oo oo oo oo oo oo oo oo oo oo oo oo o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o o oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo  A quick explanation: The verb (,~,.~) is what's doing the work here. It's a hook which first stitches ,. the argument to itself (o -> oo) and then appends the original argument to the output: oo  becomes oo o  This verb is repeated 6 times ^:6 with the output of each iteration becoming the input of the next iteration. So oo o  becomes oooo o o oo o  which in turn becomes oooooooo o o o o oo oo o o oooo o o oo o  etc. I've then used the oblique adverb on append ,/. to read the rows diagonally to straighten(ish) the triangle. I didn't need to do this, as randomra points out. I could have just reversed |. the lot to get the same result. Even better, I could have just used (,,.~)^:6,'o' to save the reverse step completely. Ah well, you live and learn. :-) • Could you briefly explain how it works? I'm not familiar with J – aditsu Feb 27 '13 at 10:18 • |.(,~,.~)^:6,'o' is shorter and without extra spaces. And (,~,.~)^:6,1 also gives decent input in just 12 characters! – randomra Feb 27 '13 at 10:19 • @aditsu I've added an explanation. – Gareth Feb 27 '13 at 12:20 • So if I get it, that operator concatenates two 2d arrays? – MaiaVictor Mar 23 '13 at 10:56 APL (51)  A←67⍴0⋄A[34]←1⋄' ○'[1+32 67⍴{~⊃⍵:⍵,∇(1⌽⍵)≠¯1⌽⍵⋄⍬}A]  Explanation: • A←67⍴0: A is a vector of 67 zeroes • A[34]←1: the 34th element is 1 • {...}A: starting with A, do: • ~⊃⍵:: if the first element of the current row is zero • ⍵,∇: add the current row to the answer, and recurse with: • (1⌽⍵)≠¯1⌽⍵: the vector where each element is the XOR of its neighbours in the previous generation • ⋄⍬: otherwise, we're done • 32 67⍴: format this in a 67x32 matrix • 1+: add one to select the right value from the character array • ' ○'[...]: output either a space (not part of the triangle) or a circle (when it is part of the triangle) Output:  ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○  • Yikes. I expected this to be 4 characters, using binomials mod 2... (ok... maybe a little longer than that) – boothby Jun 9 '12 at 17:47 Haskell (291) I'm not very good at golfing haskell codes. solve n = tri (putStrLn "") [2^n] n tri m xs 1 = do putStrLn (l1 1 xs "/\\" 0) putStrLn (l1 1 xs "/__\\" 1) m tri m xs n=tri m' xs (n-1) where m'=tri m (concat[[x-o,x+o]|x<-xs]) (n-1) o=2^(n-1) l1 o [] s t="" l1 o (x:xs) s t=replicate (x-o-t) ' '++s++l1 (x+2+t) xs s t  Output of solve 4 is:  /\ /__\ /\ /\ /__\/__\ /\ /\ /__\ /__\ /\ /\ /\ /\ /__\/__\/__\/__\ /\ /\ /__\ /__\ /\ /\ /\ /\ /__\/__\ /__\/__\ /\ /\ /\ /\ /__\ /__\ /__\ /__\ /\ /\ /\ /\ /\ /\ /\ /\ /__\/__\/__\/__\/__\/__\/__\/__\  QBasic 151 Characters As an example, here is how it can be done in QBasic. SCREEN 9 H=.5 P=300 FOR I=1 TO 9^6 N=RND IF N > 2/3 THEN X=H+X*H:Y=Y*H ELSEIF N > 1/3 THEN X=H^2+X*H:Y=H+Y*H ELSE X=X*H:Y=Y*H END IF PSET(P-X*P,P-Y*P) NEXT  • Could you describe the measure under which this program is 129 characters? I get 151 if I strip out all the probably-unnecessary whitespace. (I'm not familiar with QBasic.) – Kevin Reid Jun 9 '12 at 12:44 • I stripped out all the whitespace for my count. I guess I could count only non-essential whitespace. I'm not sure what the "official" rule is for code golf. – Kibbee Jun 10 '12 at 0:41 • You should count the actual number of characters, including whitespace, in a program which runs and produces the correct output. Naturally you'll want to have no unnecessary whitespace. – Kevin Reid Jun 10 '12 at 0:43 • Corrected my character count. – Kibbee Jun 12 '12 at 12:18 Python (42) I originally wanted to post a few suggestions on boothbys solution (who actually uses rule 18 :), but i didn't have enough reputation to comment, so i made it into another answer. Since he changed his approach, i added some explanation. My suggestions would have been: 1. use '%d'*64%tuple(x) instead of ''.join(map(str,x) 2. shift in zeros instead of wraping the list around which would have led to the following code (93 characters): x=[0]*63 x[31]=1 exec"print'%d'*63%tuple(x);x=[a^b for a,b in zip(x[1:]+[0],[0]+x[:-1])];"*32  But i optimzed further, first by using a longint instead of an integer array and just printing the binary representation (75 characters): x=2**31 exec"print'%d'*63%tuple(1&x>>i for i in range(63));x=x<<1^x>>1;"*32  And finally by printing the octal representation, which is already supported by printf interpolation (42 characters): x=8**31 exec"print'%063o'%x;x=x*8^x/8;"*32  All of them will print: 000000000000000000000000000000010000000000000000000000000000000 000000000000000000000000000000101000000000000000000000000000000 000000000000000000000000000001000100000000000000000000000000000 000000000000000000000000000010101010000000000000000000000000000 000000000000000000000000000100000001000000000000000000000000000 000000000000000000000000001010000010100000000000000000000000000 000000000000000000000000010001000100010000000000000000000000000 000000000000000000000000101010101010101000000000000000000000000 000000000000000000000001000000000000000100000000000000000000000 000000000000000000000010100000000000001010000000000000000000000 000000000000000000000100010000000000010001000000000000000000000 000000000000000000001010101000000000101010100000000000000000000 000000000000000000010000000100000001000000010000000000000000000 000000000000000000101000001010000010100000101000000000000000000 000000000000000001000100010001000100010001000100000000000000000 000000000000000010101010101010101010101010101010000000000000000 000000000000000100000000000000000000000000000001000000000000000 000000000000001010000000000000000000000000000010100000000000000 000000000000010001000000000000000000000000000100010000000000000 000000000000101010100000000000000000000000001010101000000000000 000000000001000000010000000000000000000000010000000100000000000 000000000010100000101000000000000000000000101000001010000000000 000000000100010001000100000000000000000001000100010001000000000 000000001010101010101010000000000000000010101010101010100000000 000000010000000000000001000000000000000100000000000000010000000 000000101000000000000010100000000000001010000000000000101000000 000001000100000000000100010000000000010001000000000001000100000 000010101010000000001010101000000000101010100000000010101010000 000100000001000000010000000100000001000000010000000100000001000 001010000010100000101000001010000010100000101000001010000010100 010001000100010001000100010001000100010001000100010001000100010 101010101010101010101010101010101010101010101010101010101010101  Of course there is also a graphical solution (131 characters): from PIL.Image import* from struct import* a='' x=2**31 exec"a+=pack('>Q',x);x=x*2^x/2;"*32 fromstring('1',(64,32),a).save('s.png')  :D • 36: x=8**31;exec"print'%o'%x;x^=x/8;"*32 – aditsu Feb 27 '13 at 11:08 8086 Machine code - 30 bytes. NOTE: This is not my code and should not be accepted as an answer. I found this while working on a different CG problem to emulate an 8086 CPU. The included text file credits David Stafford, but that's the best I could come up with. I'm posting this because it's clever, short, and I thought you'd want to see it. It makes use of overlapping opcodes to pack more instructions in a smaller space. Amazingly clever. Here is the machine code: B0 13 CD 10 B3 03 BE A0 A0 8E DE B9 8B 0C 32 28 88 AC C2 FE 4E 75 F5 CD 16 87 C3 CD 10 C3  A straight-up decode looks like this: 0100: B0 13 mov AL, 13h 0102: CD 10 int 10h 0104: B3 03 mov BL, 3h 0106: BE A0 A0 mov SI, A0A0h 0109: 8E DE mov DS, SI 010B: B9 8B 0C mov CX, C8Bh 010E: 32 28 xor CH, [BX+SI] 0110: 88 AC C2 FE mov [SI+FEC2h], CH 0114: 4E dec SI 0115: 75 F5 jne/jnz -11  When run, when the jump at 0x0115 happens, notice it jumps back to 0x010C, right into the middle of a previous instruction: 0100: B0 13 mov AL, 13h 0102: CD 10 int 10h 0104: B3 03 mov BL, 3h 0106: BE A0 A0 mov SI, A0A0h 0109: 8E DE mov DS, SI 010B: B9 8B 0C mov CX, C8Bh 010E: 32 28 xor CH, [BX+SI] 0110: 88 AC C2 FE mov [SI+FEC2h], CH 0114: 4E dec SI 0115: 75 F5 jne/jnz -11 010C: 8B 0C mov CX, [SI] 010E: 32 28 xor CH, [BX+SI] 0110: 88 AC C2 FE mov [SI+FEC2h], CH 0114: 4E dec SI 0115: 75 F5 jne/jnz -11 010C: 8B 0C mov CX, [SI]  Brilliant! Hope you guys don't mind me sharing this. I know it's not an answer per se, but it's of interest to the challenge. Here it is in action: C 127119116108 65 This one uses the trick of the HTML answer of ^ i & j getting it to print pretty output would take 1 more char (you can get really ugly output by sacrificing the a^). a=32,j;main(i){for(;++i<a;)putchar(a^i&j);++j<a&&main(puts(""));}  To make it pretty turn (32^i&j) to (32|!(i&j)) and turn it from ++i<a to ++i<=a. However wasting chars on looks seems ungolfish to me. Ugly output:  ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! "" "" "" "" "" "" "" "" "# !"# !"# !"# !"# !"# !"# !"#     !$%$% ! !$%$% ! !$%$% ! !$%$% ""$$&& ""$$&& ""$$&& ""$$&& "#$%&' !"#$%&' !"#$%&' !"#$%&' (((((((( (((((((( ! ! !()()()() ! ! ! !()()()() "" ""((**((** "" ""((**((** "# !"#()*+()*+ !"# !"#()*+()*+ ((((,,,, ((((,,,, !$%$%()(),-,- ! !$%$%()(),-,- ""$$&&((**,,.. ""$$&&((**,,.. "#$%&'()*+,-./ !"#$%&'()*+,-./ 0000000000000000 ! ! ! ! ! ! !0101010101010101 "" "" "" ""0022002200220022 "# !"# !"# !"#0123012301230123  0000444400004444 !$%$% ! !$%$%0101454501014545 ""$$&& ""$$&&0022446600224466 "#$%&' !"#$%&'0123456701234567 ((((((((0000000088888888 ! ! !()()()()0101010189898989 "" ""((**((**0022002288::88:: "# !"#()*+()*+0123012389:;89:; ((((,,,,000044448888<<<< !$%$%()(),-,-010145458989<=<= ""$$&&((**,,..0022446688::<<>> "#$%&'()*+,-./0123456789:;<=>?


I actually kind of like how it looks. But if you insist on it being pretty you can dock four chars. Pretty Output:

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! ! ! ! ! ! ! ! ! ! ! ! ! ! ! !
!!  !!  !!  !!  !!  !!  !!  !
!   !   !   !   !   !   !   !
!!    !!!!    !!!!    !!!!    !
!     ! !     ! !     ! !     !
!!      !!      !!      !
!       !       !       !
!!!!!!        !!!!!!!!        !
! ! !         ! ! ! !         !
!!          !!  !!          !
!           !   !           !
!!            !!!!            !
!             ! !             !
!!              !
!               !
!!!!!!!!!!!!!!                !
! ! ! ! ! ! !                 !
!!  !!  !!                  !
!   !   !                   !
!!    !!!!                    !
!     ! !                     !
!!                      !
!                       !
!!!!!!                        !
! ! !                         !
!!                          !
!                           !
!!                            !
!                             !
!
!


Leaving up the older 108 char, cellular automata version.

j,d[99][99];main(i){d[0][31]=3;for(;i<64;)d[j+1][i]=putchar(32|d[j][i+2]^d[j][i++]);++j<32&&main(puts(""));}


So I don't think I'm going to get it much shorter than this so I'll explain the code. I'll leave this explanation up, as some of the tricks could be useful.

j,d[99][99]; // these init as 0
main(i){ //starts at 1 (argc)
d[0][48]=3; //seed the automata (3 gives us # instead of !)
for(;i<98;) // print a row
d[j+1][i]=putchar(32|d[j][i+2]]^d[j][i++]);
//relies on undefined behavoir. Works on ubuntu with gcc ix864
//does the automata rule. 32 + (bitwise or can serve as + if you know
//that (a|b)==(a^b)), putchar returns the char it prints
++j<32&&main(puts(""));
// repeat 32 times
// puts("") prints a newline and returns 1, which is nice
}


Some output

                             # #
#   #
# # # #
#       #
# #     # #
#   #   #   #
# # # # # # # #
#               #
# #             # #
#   #           #   #
# # # #         # # # #
#       #       #       #
# #     # #     # #     # #
#   #   #   #   #   #   #   #
# # # # # # # # # # # # # # # #
#                               #
# #                             # #
#   #                           #   #
# # # #                         # # # #
#       #                       #       #
# #     # #                     # #     # #
#   #   #   #                   #   #   #   #
# # # # # # # #                 # # # # # # # #
#               #               #               #
# #             # #             # #             # #
#   #           #   #           #   #           #   #
# # # #         # # # #         # # # #         # # # #
#       #       #       #       #       #       #       #
# #     # #     # #     # #     # #     # #     # #     # #
#   #   #   #   #   #   #   #   #   #   #   #   #   #   #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

• This does not appear to be a Sierpinski triangle; it splits into three sub-triangles (proceeding downward) rather than two, and it can be seen that this produces no large central empty triangle. – Kevin Reid Jun 9 '12 at 13:10
• That's because I used the wrong rule :O. Fixed, and shaved a couple of chars. – walpen Jun 9 '12 at 13:59

80x86 Code / MsDos - 10 Bytes

As a sizecoder specialized for very tiny intros on MsDos i managed to come up with a program that occupies only 10 bytes.

in hex:

04 13 CD 10 20 E9 B4 0C E2 F6


in asm:

X: add al,0x13
int 0x10
and cl,ch
mov ah,0x0C
loop X


The first version i coded was "Colpinski" which is 16 bytes in size, and even interactive in a way that you can change the color with the keyboard and the mouse. Together with "Frag" - another sizecoder - we brought that one down to 13 bytes, allowing for a 10 byte program which just contains the core routine.

It gets a bit more interesting when things are animated, so i'll mention another version, Zoompinski 64 - trying to mimic the exact behavior of "Zoompinski C64" in 512 bytes - also for MsDos, 64 bytes in size as the name suggests.

It's possible to optimize this further downto 31 Bytes, while losing elegance, colors and symmetry (source and executable available behind the link above)

• You should post a hex dump of your code, so we can see the actual bytes. – mbomb007 Oct 6 '16 at 19:44

PostScript, 120 chars

-7 -4 moveto
14 0 rlineto
7{true upath dup
2{120 rotate uappend}repeat[2 0 0 2 7 4]concat}repeat
matrix setmatrix
stroke


Ghostscript output:

This is drawing the figure by recursively tripling what's already drawn.

First step is drawing a line. The line is saved as a userpath, then the userpath is added two more times after rotating 120 degrees each time. [2 0 0 2 7 4]concat moves the "rotation point" to the center of the next big white "center triangle" that is to be enclosed by replications of the triangle we already have. Here, we're back to step 1 (creating a upath that's tripled by rotation).

The number of iterations is controlled by the first number in line 3.

• +1 Very nice. I had no idea upath could be used like that. – luser droog Jul 20 '12 at 6:28
• Hey, you've got the rep to add that image now! – luser droog Jan 1 '13 at 7:01
• @luserdroog: That's right (even partly thanks to you)! – Thomas W. Jan 1 '13 at 15:21

J (9 characters)

Easily the ugliest, you really need to squint to see the output ;)

2|!/~i.32


produces the output

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1


of course you can display it graphically:

load 'viewmat'
viewmat 2|!/~i.32


• how the... what? – acolyte Apr 3 '13 at 17:16
• The code exploits the property of Pascal's triangle that if you colour all the odd (even) numbers black (white), you end up with the Sierpinski triangle. (see this image). i.32 generates the list 0 1 2 ... 31. Then !/~ computes the binomial coefficients of each element in the list against itself, i.e. produces a 32 x 32 matrix which has Pascal's triangle embedded in it. Then 2| is simply each element in this matrix mod 2, producing Sierpinski's triangle. – Mark Allen Apr 7 '13 at 17:55

APL, 37 32 (28 23)

Upright triangle (37 32-char)

({((-1⌷⍴⍵)⌽⍵,∊⍵)⍪⍵,⍵}⍣⎕)1 2⍴'/\'


Explanation

• 1 2⍴'/\': Create a 1×2 character matrix /\
• {((-1⌷⍴⍵)⌽⍵,∊⍵)⍪⍵,⍵}: A function that pad the right argument on both sides with blanks to create a matrix double as wide, then laminates the right argument itself doubled onto the bottom.
E.g. /\ would become
 /\
/\/\
• ⍣⎕: Recur the function (user input) times.

Example output

               /\
/\/\
/\  /\
/\/\/\/\
/\      /\
/\/\    /\/\
/\  /\  /\  /\
/\/\/\/\/\/\/\/\
/\              /\
/\/\            /\/\
/\  /\          /\  /\
/\/\/\/\        /\/\/\/\
/\      /\      /\      /\
/\/\    /\/\    /\/\    /\/\
/\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\


Skewed Triangle (28 23-char)

({(⍵,∊⍵)⍪⍵,⍵}⍣⎕)1 1⍴'○'


Explaination

• 1 1⍴'○': Create a 1×1 character matrix ○
• {(⍵,∊⍵)⍪⍵,⍵}: A function that pad the right argument on the right with blanks to create a matrix double as wide, then laminates the right argument itself doubled onto the bottom.
E.g. ○ would become
○
○○
• ⍣⎕: Recur the function (user input) times.

Example output

○
○○
○ ○
○○○○
○   ○
○○  ○○
○ ○ ○ ○
○○○○○○○○
○       ○
○○      ○○
○ ○     ○ ○
○○○○    ○○○○
○   ○   ○   ○
○○  ○○  ○○  ○○
○ ○ ○ ○ ○ ○ ○ ○
○○○○○○○○○○○○○○○○


Python (75)

I'm two years late to the party, but I'm surprised that nobody has taken this approach yet

from pylab import*
x=[[1,1],[1,0]]
for i in'123':x=kron(x,x)
imsave('a',x)


Uses the Kronecker product to replace a matrix by multiple copies of itself.

I could save two chars by using x=kron(x,x);x=kron(x,x) in line three to get a 16x16 pixel image with three visible levels or add another char to the iterator and end up with a 2^16 x 2^16 = 4.3 Gigapixel image and 15 triangle levels.

Logo, 75 characters

59 characters for just the first function, the second one calls the first with the size and the depth/number of iterations. So you could just call the first function from the interpreter with the command: e 99 5, or whatever size you want to output

to e :s :l
if :l>0[repeat 3[e :s/2 :l-1 fd :s rt 120]]
end
to f
e 99 5
end

• +1 I've read about Logo. What interpreter are you using? ... Logo might be a natural fit for my l-system challenge. – luser droog Feb 28 '13 at 2:50
• If you just remove the to f and end around e 99 5, you have a complete runnable program in fewer characters. Also, in UCBLogo (though not other versions) you can lose the colons on the variables to save more chars. – Mark Reed Jan 21 '14 at 3:38

matlab 56

v=[1;-1;j];plot(filter(1,[1,-.5],v(randi(3,1,1e4))),'.')


J (18 characters)

' *'{~(,,.~)^:9 ,1


Result

*
**
* *
****
*   *
**  **
* * * *
********
*       *
**      **
* *     * *
****    ****
*   *   *   *
**  **  **  **
* * * * * * * *
****************
*               *
**              **
* *             * *
****            ****
*   *           *   *
**  **          **  **
* * * *         * * * *
********        ********
*       *       *       *
**      **      **      **
* *     * *     * *     * *
****    ****    ****    ****
*   *   *   *   *   *   *   *
**  **  **  **  **  **  **  **
* * * * * * * * * * * * * * * *
********************************


Python (90 chars)

from turtle import*
def l():left(60)
def r():right(60)
def f():forward(1)
def L(n):
if n:n-=1;R(n);l();L(n);l();R(n)
else:f()
def R(n):
if n:n-=1;L(n);r();R(n);r();L(n)
else:f()
l();L(8)


Try it online

Draw fractal line filling Sierpinsky Triangle

• Before running, I recommend inserting ht();speed(0);up();goto(20-window_width()/2, 20-window_height()/2);down() after the import. This will run it much faster and ensure that the output fits on the canvas. – mbomb007 Oct 6 '16 at 19:42

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. – cjfaure Jan 17 '14 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 – luser droog Jan 21 '14 at 3:05

Mathematica 67

ListPlot@NestList[(#+RandomChoice@{{0,0},{2,0},{1,2}})/2&,{0,0},8!]


Mathematica 92

Graphics@Polygon@Nest[Join@@(Mean/@#&/@#~Tuples~2~Partition~3&/@#)&,{{{0,0},{2,0},{1,1}}},3]


(-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! – Laikoni May 29 '18 at 7:28
• @Laikoni Ooh, some very nice improvements in there! – Sacchan May 29 '18 at 11:54

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.

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 – ASCII-only Mar 28 '18 at 9:18
• @ASCII-only Good idea! – David Conrad Mar 29 '18 at 0:02

APL (Dyalog Classic), 12 bytes

×.≥∘⍉⍨↑,⍳⎕⍴2


Try it online!

Asymptote, 152 bytes

I'll add this, mostly since I've seen more or less no answers in asymptote on this site. A few wasted bytes for nice formatting and generality, but I can live with that. Changing A,B and C will change where the corners of the containing triangle are, but probably not in the way you think. Increase the number in the inequality to increase the depth.

pair A=(0,0),B=(1,0),C=(.5,1);void f(pair p,int d){if(++d<7){p*=2;f(p+A*2,d);f(p+B*2,d);f(p+C*2,d);}else{fill(shift(p/2)*(A--B--C--cycle));}}f((0,0),0);


pair A=(0,0), B=(1,0), C=(.5,1);

void f(pair p, int d) {
if (++d<7) {
p *= 2;
f(p+A*2,d);
f(p+B*2,d);
f(p+C*2,d);
} else {
fill(shift(p/2)*(A--B--C--cycle));
}
}

f((0,0),0);


So asymptote is a neat vector graphics language with somewhat C-like syntax. Quite useful for somewhat technical diagrams. Output is of course in a vector format by default (eps, pdf, svg) but can be converted into basically everything imagemagick supports. Output:

Mathematica, 29 bytes

Image@Array[BitAnd,{2,2}^9,0]


The Sierpinski tetrahedron can be drawn in a similar way:

Image3D[1-Array[BitXor,{2,2,2}^7,0]]