Sierpinski triangle: Difference between revisions
| Line 1,509: | Line 1,509: | ||
} |
} |
||
}</lang> |
}</lang> |
||
=={{header|Prolg}}== |
|||
Works with SWI-Prolog; |
|||
<lang Prolog>sierpinski_triangle(N) :- |
|||
Len is 2 ** (N+1) - 1, |
|||
length(L, Len), |
|||
numlist(1, Len, LN), |
|||
maplist(init(N), L, LN), |
|||
atomic_list_concat(L, Line), |
|||
writeln(Line), |
|||
NbTours is 2**N - 1, |
|||
loop(NbTours, LN, Len, L). |
|||
init(N, Cell, Num) :- |
|||
( Num is 2 ** N + 1 -> Cell = *; Cell = ' '). |
|||
loop(0, _, _, _) :- !. |
|||
loop(N, LN, Len, L) :- |
|||
maplist(compute_next_line(Len, L), LN, L1), |
|||
atomic_list_concat(L1, Line), |
|||
writeln(Line), |
|||
N1 is N - 1, |
|||
loop(N1, LN, Len, L1). |
|||
compute_next_line(Len, L, I, V) :- |
|||
I1 is I - 1, |
|||
I2 is I+1, |
|||
( I = 1 -> V0 = ' '; nth1(I1, L, V0)), |
|||
nth1(I, L, V1), |
|||
( I = Len -> V2 = ' '; nth1(I2, L, V2)), |
|||
rule_90(V0, V1, V2, V). |
|||
rule_90('*','*','*', ' '). |
|||
rule_90('*','*',' ', '*'). |
|||
rule_90('*',' ','*', ' '). |
|||
rule_90('*',' ',' ', '*'). |
|||
rule_90(' ','*','*', '*'). |
|||
rule_90(' ','*',' ', ' '). |
|||
rule_90(' ',' ','*', '*'). |
|||
rule_90(' ',' ',' ', ' '). |
|||
</lang> |
|||
Output : |
|||
<pre> ?- sierpinski_triangle(4). |
|||
* |
|||
* * |
|||
* * |
|||
* * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * |
|||
* * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * |
|||
* * * * * * * * |
|||
* * * * * * * * |
|||
* * * * * * * * * * * * * * * * |
|||
true </pre> |
|||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
| Line 1,528: | Line 1,591: | ||
Repeat |
Repeat |
||
Until WaitWindowEvent()=#PB_Event_CloseWindow |
Until WaitWindowEvent()=#PB_Event_CloseWindow |
||
End</lang> |
End</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Revision as of 18:15, 25 November 2011
You are encouraged to solve this task according to the task description, using any language you may know.
Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
See also Sierpinski carpet
Ada
This Ada example creates a string of the binary value for each line, converting the '0' values to spaces. <lang ada>with Ada.Text_Io; use Ada.Text_Io; with Ada.Strings.Fixed; with Interfaces; use Interfaces;
procedure Sieteri_Triangles is
subtype Practical_Order is Unsigned_32 range 0..4;
function Pow(X : Unsigned_32; N : Unsigned_32) return Unsigned_32 is
begin
if N = 0 then
return 1;
else
return X * Pow(X, N - 1);
end if;
end Pow;
procedure Print(Item : Unsigned_32) is
use Ada.Strings.Fixed;
package Ord_Io is new Ada.Text_Io.Modular_Io(Unsigned_32);
use Ord_Io;
Temp : String(1..36) := (others => ' ');
First : Positive;
Last : Positive;
begin
Put(To => Temp, Item => Item, Base => 2);
First := Index(Temp, "#") + 1;
Last := Index(Temp(First..Temp'Last), "#") - 1;
for I in reverse First..Last loop
if Temp(I) = '0' then
Put(' ');
else
Put(Temp(I));
end if;
end loop;
New_Line;
end Print;
procedure Sierpinski (N : Practical_Order) is
Size : Unsigned_32 := Pow(2, N);
V : Unsigned_32 := Pow(2, Size);
begin
for I in 0..Size - 1 loop
Print(V);
V := Shift_Left(V, 1) xor Shift_Right(V,1);
end loop;
end Sierpinski;
begin
for N in Practical_Order loop
Sierpinski(N);
end loop;
end Sieteri_Triangles;</lang>
alternative using modular arithmetic: <lang Ada>with Ada.Command_Line; with Ada.Text_IO;
procedure Main is
subtype Order is Natural range 1 .. 32; type Mod_Int is mod 2 ** Order'Last;
procedure Sierpinski (N : Order) is
begin
for Line in Mod_Int range 0 .. 2 ** N - 1 loop
for Col in Mod_Int range 0 .. 2 ** N - 1 loop
if (Line and Col) = 0 then
Ada.Text_IO.Put ('X');
else
Ada.Text_IO.Put (' ');
end if;
end loop;
Ada.Text_IO.New_Line;
end loop;
end Sierpinski;
N : Order := 4;
begin
if Ada.Command_Line.Argument_Count = 1 then
N := Order'Value (Ada.Command_Line.Argument (1));
end if;
Sierpinski (N);
end Main;</lang> output:
XXXXXXXXXXXXXXXX X X X X X X X X XX XX XX XX X X X X XXXX XXXX X X X X XX XX X X XXXXXXXX X X X X XX XX X X XXXX X X XX X
ALGOL 68
<lang algol68>PROC sierpinski = (INT n)[]STRING: (
FLEX[0]STRING d := "*";
FOR i TO n DO
[UPB d * 2]STRING next;
STRING sp := " " * (2 ** (i-1));
FOR x TO UPB d DO
STRING dx = d[x];
next[x] := sp+dx+sp;
next[UPB d+x] := dx+" "+dx
OD;
d := next
OD;
d
);
printf(($gl$,sierpinski(4)))</lang>
AutoHotkey
ahk discussion <lang autohotkey>Loop 6
MsgBox % Triangle(A_Index)
Triangle(n,x=0,y=1) { ; Triangle(n) -> string of dots and spaces of Sierpinski triangle
Static t, l ; put chars in a static string
If (x < 1) { ; when called with one parameter
l := 2*x := 1<<(n-1) ; - compute location, string size
VarSetCapacity(t,l*x,32) ; - allocate memory filled with spaces
Loop %x%
NumPut(13,t,A_Index*l-1,"char") ; - new lines in the end of rows
}
If (n = 1) ; at the bottom of recursion
Return t, NumPut(46,t,x-1+(y-1)*l,"char") ; - write "." (better at proportional fonts)
u := 1<<(n-2)
Triangle(n-1,x,y) ; draw smaller triangle here
Triangle(n-1,x-u,y+u) ; smaller triangle down-left
Triangle(n-1,x+u,y+u) ; smaller triangle down right
Return t
}</lang>
AWK
<lang AWK># WST.AWK - Waclaw Sierpinski's triangle contributed by Dan Nielsen
- syntax: GAWK -f WST.AWK [-v X=anychar] iterations
- example: GAWK -f WST.AWK -v X=* 2
BEGIN {
n = ARGV[1] + 0 # iterations
if (n !~ /^[0-9]+$/) { exit(1) }
if (n == 0) { width = 3 }
row = split("X,X X,X X,X X X X",A,",") # seed the array
for (i=1; i<=n; i++) { # build triangle
width = length(A[row])
for (j=1; j<=row; j++) {
str = A[j]
A[j+row] = sprintf("%-*s %-*s",width,str,width,str)
}
row *= 2
}
for (j=1; j<=row; j++) { # print triangle
if (X != "") { gsub(/X/,substr(X,1,1),A[j]) }
sub(/ +$/,"",A[j])
printf("%*s%s\n",width-j+1,"",A[j])
}
exit(0)
}</lang>
BASIC
<lang freebasic>SUB triangle (x AS Integer, y AS Integer, length AS Integer, n AS Integer)
IF n = 0 THEN
LOCATE y,x: PRINT "*";
ELSE
triangle (x, y+length, length/2, n-1)
triangle (x+length, y, length/2, n-1)
triangle (x+length*2, y+length, length/2, n-1) END IF
END SUB
CLS triangle 1,1,16,5</lang>
Note: The total height of the triangle is 2 * parameter length. It should be power of two so that the pattern matches evenly with the character cells. Value 16 will thus create pattern of 32 lines.
BBC BASIC
<lang bbcbasic> MODE 8
OFF
order% = 5
PROCsierpinski(0, 0, 2^(order%-1))
REPEAT UNTIL GET
END
DEF PROCsierpinski(x%, y%, l%)
IF l% = 0 THEN
PRINT TAB(x%,y%) "*";
ELSE
PROCsierpinski(x%, y%+l%, l% DIV 2)
PROCsierpinski(x%+l%, y%, l% DIV 2)
PROCsierpinski(x%+l%+l%, y%+l%, l% DIV 2)
ENDIF
ENDPROC</lang>
C
<lang C>#include <stdio.h>
- define SIZE (1 << 4)
int main() { int x, y, i; for (y = SIZE - 1; y >= 0; y--, putchar('\n')) { for (i = 0; i < y; i++) putchar(' '); for (x = 0; x + y < SIZE; x++) printf((x & y) ? " " : "* "); } return 0; }</lang>
Automaton
This solution uses a cellular automaton (rule 90) with a proper initial status. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <stdbool.h>
- include <string.h>
- ifndef _POSIX_C_SOURCE
char *strdup(const char *s) {
int l = strlen(s); char *r = malloc(l+1); memcpy(r, s, l+1); return r;
}
- endif
- define truth(X) ((X)=='*'?true:false)
void rule_90(char *evstr) {
int i; int l = strlen(evstr); bool s[3]; char *cp = strdup(evstr);
for(i=0;i < l; i++) {
s[1] = truth(cp[i]);
s[0] = (i-1) < 0 ? false : truth(cp[i-1]);
s[2] = (i+1) < l ? truth(cp[i+1]) : false;
if ( (s[0] && !s[2]) || (!s[0] && s[2]) ) {
evstr[i] = '*';
} else {
evstr[i] = ' ';
}
}
free(cp);
}</lang>
<lang c>void sierpinski_triangle(int n) {
int i; int l = 1<<(n+1); char *b = malloc(l+1);
memset(b, ' ', l); b[l] = 0; b[l>>1] = '*';
printf("%s\n", b);
for(i=0; i < l/2-1;i++) {
rule_90(b);
printf("%s\n", b);
}
free(b);
}</lang>
<lang c>int main() {
sierpinski_triangle(4); return EXIT_SUCCESS;
}</lang>
C++
A STL-centric recursive solution that uses the new lambda functions in C++11. <lang cpp>#include <iostream>
- include <string>
- include <list>
- include <algorithm>
- include <iterator>
using namespace std;
template<typename OutIt> void sierpinski(int n, OutIt result) {
if( n == 0 )
{
*result++ = "*";
}
else
{
list<string> prev;
sierpinski(n-1, back_inserter(prev));
string sp(1 << (n-1), ' ');
result = transform(prev.begin(), prev.end(),
result,
[sp](const string& x) { return sp + x + sp; });
transform(prev.begin(), prev.end(),
result,
[sp](const string& x) { return x + " " + x; });
}
}
int main() {
sierpinski(4, ostream_iterator<string>(cout, "\n")); return 0;
}</lang>
C#
<lang csharp>using System; using System.Collections;
namespace RosettaCode {
class SierpinskiTriangle {
int len;
BitArray b;
public SierpinskiTriangle(int n) {
if (n < 1) {
throw new ArgumentOutOfRangeException("Order must be greater than zero");
}
len = 1 << (n+1);
b = new BitArray(len+1, false);
b[len>>1] = true;
}
public void Display() {
for (int j = 0; j < len / 2; j++) {
for (int i = 0; i < b.Count; i++) {
Console.Write("{0}", b[i] ? "*" : " ");
}
Console.WriteLine();
NextGen();
}
}
private void NextGen() {
BitArray next = new BitArray(b.Count, false);
for (int i = 0; i < b.Count; i++) {
if (b[i]) {
next[i - 1] = next[i - 1] ^ true;
next[i + 1] = next[i + 1] ^ true;
}
}
b = next;
}
}
}</lang>
<lang csharp>namespace RosettaCode {
class Program {
static void Main(string[] args) {
SierpinskiTriangle t = new SierpinskiTriangle(4);
t.Display();
}
}
}</lang>
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
class Program {
public static List<String> Sierpinski(int n)
{
var lines = new List<string> { "*" };
string space = " ";
for (int i = 0; i < n; i++)
{
lines = lines.Select(x => space + x + space)
.Concat(lines.Select(x => x + " " + x)).ToList();
space += space;
}
return lines; }
static void Main(string[] args)
{
foreach (string s in Sierpinski(4))
Console.WriteLine(s);
}
}</lang>
Or, with fold / reduce (a.k.a. aggregate):
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
class Program {
static List<string> Sierpinski(int n)
{
return Enumerable.Range(0, n).Aggregate( new List<string>(){"*"}, (p, i) => { string SPACE = " ".PadRight((int)Math.Pow(2, i));
var temp = new List<string>(from x in p select SPACE + x + SPACE); temp.AddRange(from x in p select x + " " + x);
return temp; } );
}
static void Main ()
{
foreach(string s in Sierpinski(4)) { Console.WriteLine(s); }
}
}</lang>
Clojure
With a touch of Clojure's sequence handling. <lang clojure>(ns example
(:require [clojure.contrib.math :as math]))
- Length of integer in binary
- (copied from a private multimethod in clojure.contrib.math)
(defmulti #^{:private true} integer-length class)
(defmethod integer-length java.lang.Integer [n]
(count (Integer/toBinaryString n)))
(defmethod integer-length java.lang.Long [n]
(count (Long/toBinaryString n)))
(defmethod integer-length java.math.BigInteger [n]
(count (.toString n 2)))
(defn sierpinski-triangle [order]
(loop [size (math/expt 2 order)
v (math/expt 2 (- size 1))]
(when (pos? size)
(println
(apply str (map #(if (bit-test v %) "*" " ")
(range (integer-length v)))))
(recur
(dec size)
(bit-xor (bit-shift-left v 1) (bit-shift-right v 1))))))
(sierpinski-triangle 4)</lang>
Common Lisp
<lang lisp>(defun print-sierpinski (order)
(loop with size = (expt 2 order)
repeat size
for v = (expt 2 (1- size)) then (logxor (ash v -1) (ash v 1))
do (fresh-line)
(loop for i below (integer-length v)
do (princ (if (logbitp i v) "*" " ")))))</lang>
Printing each row could also be done by printing the integer in base 2 and replacing zeroes with spaces: (princ (substitute #\Space #\0 (format nil "~%~2,vR" (1- (* 2 size)) v)))
Replacing the iteration with for v = 1 then (logxor v (ash v 1)) produces a "right" triangle instead of an "equilateral" one.
Alternate approach:
<lang lisp>(defun sierpinski (n)
(if (= n 0) '("*")
(nconc (mapcar (lambda (e) (format nil "~A~A~0@*~A" (make-string (expt 2 (1- n)) :initial-element #\ ) e)) (sierpinski (1- n)))
(mapcar (lambda (e) (format nil "~A ~A" e e)) (sierpinski (1- n))))))
(mapc #'print (sierpinski 4))</lang>
D
<lang d>import std.stdio, std.algorithm, std.string, std.array;
void main() {
enum level = 4;
auto d = ["*"];
foreach (n; 0 .. level) {
auto sp = " ".repeat(2 ^^ n);
d = array(map!((a){ return sp ~ a ~ sp; })(d)) ~
array(map!q{a ~ " " ~ a}(d));
}
writeln(d.join("\n"));
}</lang> Output:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
At compile-time too (same output): <lang d>import std.string;
string sierpinski(int n) {
auto parts = ["*"];
auto space = " ";
foreach (i; 0 .. n) {
string[] parts2;
foreach (x; parts)
parts2 ~= space ~ x ~ space;
foreach (x; parts)
parts2 ~= x ~ " " ~ x;
parts = parts2;
space ~= space;
}
return parts.join("\n");
}
pragma(msg, sierpinski(4)); void main() {}</lang>
Delphi
<lang delphi>program SierpinskiTriangle;
{$APPTYPE CONSOLE}
procedure PrintSierpinski(order: Integer); var
x, y, size: Integer;
begin
size := (1 shl order) - 1;
for y := size downto 0 do
begin
Write(StringOfChar(' ', y));
for x := 0 to size - y do
begin
if (x and y) = 0 then
Write('* ')
else
Write(' ');
end;
Writeln;
end;
end;
begin
PrintSierpinski(4);
end.</lang>
DWScript
<lang delphi>procedure PrintSierpinski(order : Integer); var
x, y, size : Integer;
begin
size := (1 shl order)-1;
for y:=size downto 0 do begin
Print(StringOfChar(' ', y));
for x:=0 to size-y do begin
if (x and y)=0 then
Print('* ')
else Print(' ');
end;
PrintLn();
end;
end;
PrintSierpinski(4); </lang>
E
<lang e>def printSierpinski(order, out) {
def size := 2**order
for y in (0..!size).descending() {
out.print(" " * y)
for x in 0..!(size-y) {
out.print((x & y).isZero().pick("* ", " "))
}
out.println()
}
}</lang>
<lang e>? printSierpinski(4, stdout)</lang>
Non-ASCII version (quality of results will depend greatly on text renderer): <lang e>def printSierpinski(order, out) {
def size := 2**order
for y in (0..!size).descending() {
out.print(" " * y)
for x in 0..!(size-y) {
out.print((x & y).isZero().pick("◢◣", " "))
}
out.println()
}
}</lang>
Erlang
<lang erlang>-module(sierpinski). -export([triangle/1]).
triangle(N) ->
F = fun(X) -> io:format("~s~n",[X]) end,
lists:foreach(F, triangle(N, ["*"], " ")).
triangle(0, Down, _) -> Down; triangle(N, Down, Sp) ->
NewDown = [Sp++X++Sp || X<-Down]++[X++" "++X || X <- Down], triangle(N-1, NewDown, Sp++Sp).</lang>
Euphoria
<lang euphoria>procedure triangle(integer x, integer y, integer len, integer n)
if n = 0 then
position(y,x) puts(1,'*')
else
triangle (x, y+len, floor(len/2), n-1)
triangle (x+len, y, floor(len/2), n-1)
triangle (x+len*2, y+len, floor(len/2), n-1)
end if
end procedure
clear_screen() triangle(1,1,8,4)</lang>
F#
<lang fsharp>let sierpinski n =
let rec loop down space n =
if n = 0 then
down
else
loop (List.map (fun x -> space + x + space) down @
List.map (fun x -> x + " " + x) down)
(space + space)
(n - 1)
in loop ["*"] " " n
let () =
List.iter (fun (i:string) -> System.Console.WriteLine(i)) (sierpinski 4)</lang>
FALSE
<lang false>[[$][$1&["*"]?$~1&[" "]?2/]#%" "]s: { stars } [$@$@|@@&~&]x: { xor } [1\[$][1-\2*\]#%]e: { 2^n } [e;!1\[$][\$s;!$2*x;!\1-]#%%]t: 4t;!</lang>
Factor
<lang factor>USING: io kernel math sequences ; IN: sierpinski
- iterate-triangle ( triange spaces -- triangle' )
[ [ dup surround ] curry map ] [ drop [ dup " " glue ] map ] 2bi append ;
- (sierpinski) ( triangle spaces n -- triangle' )
dup 0 = [ 2drop "\n" join ] [
[
[ iterate-triangle ]
[ nip dup append ] 2bi
] dip 1 - (sierpinski)
] if ;
- sierpinski ( n -- )
[ { "*" } " " ] dip (sierpinski) print ;</lang>
Forth
<lang forth>: stars ( mask -- )
begin dup 1 and if [char] * else bl then emit 1 rshift dup while space repeat drop ;
- triangle ( order -- )
1 swap lshift ( 2^order ) 1 over 0 do cr over i - spaces dup stars dup 2* xor loop 2drop ;
5 triangle</lang>
Fortran
This method calculates a Pascal's triangle and replaces every odd number with a * and every even number with a space. The limitation of this approach is the size of the numbers in the Pascal's triangle. Tryng to print an order 8 Sierpinski's triangle will overflow a 32 bit integer and an order 16 will overflow a 64 bit integer. <lang fortran>program Sierpinski_triangle
implicit none call Triangle(4)
contains
subroutine Triangle(n)
implicit none
integer, parameter :: i64 = selected_int_kind(18)
integer, intent(in) :: n
integer :: i, k
integer(i64) :: c
do i = 0, n*4-1
c = 1
write(*, "(a)", advance="no") repeat(" ", 2 * (n*4 - 1 - i))
do k = 0, i
if(mod(c, 2) == 0) then
write(*, "(a)", advance="no") " "
else
write(*, "(a)", advance="no") " * "
end if
c = c * (i - k) / (k + 1)
end do
write(*,*)
end do
end subroutine Triangle end program Sierpinski_triangle</lang>
GAP
<lang gap># Using parity of binomial coefficients SierpinskiTriangle := function(n) local i, j, s, b; n := 2^n - 1; b := " "; while Size(b) < n do b := Concatenation(b, b); od; for i in [0 .. n] do s := ""; for j in [0 .. i] do if IsEvenInt(Binomial(i, j)) then Append(s, " "); else Append(s, "* "); fi; od; Print(b{[1 .. n - i]}, s, "\n"); od; end;
SierpinskiTriangle(4);
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
- * * * * * * * * * * * * * * * </lang>
Go
"Δ" (Greek capital letter delta) looks good for grain, as does Unicode triangle, "△". ASCII "." and "^" are pleasing. "/\\", "´`", and "◢◣"" make interesting wide triangles. <lang go>package main
import (
"fmt" "strings"
)
var order = 4 var grain = "*"
func main() {
t := []string{grain + strings.Repeat(" ", len([]int(grain)))}
for ; order > 0; order-- {
sp := strings.Repeat(" ", len([]int(t[0]))/2)
top := make([]string, len(t))
for i, s := range t {
top[i] = sp + s + sp
t[i] += s
}
t = append(top, t...)
}
for _, r := range t {
fmt.Println(r)
}
}</lang>
Groovy
Solution: <lang groovy>def stPoints; stPoints = { order, base=[0,0] ->
def right = [base[0], base[1]+2**order]
def up = [base[0]+2**(order-1), base[1]+2**(order-1)]
(order == 0) \
? [base]
: (stPoints(order-1, base) + stPoints(order-1, right) + stPoints(order-1, up))
}
def stGrid = { order ->
def h = 2**order
def w = 2**(order+1) - 1
def grid = (0..<h).collect { (0..<w).collect { ' ' } }
stPoints(order).each { grid[it[0]][it[1]] = (order%10).toString() }
grid
}</lang>
Test: <lang groovy>stGrid(0).reverse().each { println it.sum() } println() stGrid(1).reverse().each { println it.sum() } println() stGrid(2).reverse().each { println it.sum() } println() stGrid(3).reverse().each { println it.sum() } println() stGrid(4).reverse().each { println it.sum() } println() stGrid(5).reverse().each { println it.sum() } println() stGrid(6).reverse().each { println it.sum() }</lang>
Output:
0
1
1 1
2
2 2
2 2
2 2 2 2
3
3 3
3 3
3 3 3 3
3 3
3 3 3 3
3 3 3 3
3 3 3 3 3 3 3 3
4
4 4
4 4
4 4 4 4
4 4
4 4 4 4
4 4 4 4
4 4 4 4 4 4 4 4
4 4
4 4 4 4
4 4 4 4
4 4 4 4 4 4 4 4
4 4 4 4
4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4
4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4
5
5 5
5 5
5 5 5 5
5 5
5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5
5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5
5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
6
6 6
6 6
6 6 6 6
6 6
6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6
6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6
6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6
6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
Haskell
<lang haskell>sierpinski 0 = ["*"] sierpinski n = map ((space ++) . (++ space)) down ++
map (unwords . replicate 2) down
where down = sierpinski (n - 1)
space = replicate (2 ^ (n - 1)) ' '
main = mapM_ putStrLn $ sierpinski 4</lang> Output:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
HaXe
<lang HaXe>class Main { static function main() { triangle(3); }
static inline function println(str) { Lib.println(str); }
static inline var SPACE = ' '; static inline var STAR = '*';
static function triangle(o) { var n = 1 << o; var line = new Array<String>();
for (i in 0...(n*2)) line[i] = SPACE;
line[n] = '*';
for (i in 0...n) { println(line.join()); var u ='*'; var start = n - i; var end = n + i + 1; var t = SPACE; for (j in start...end) { t = (line[j-1] == line[j+1] ? SPACE : STAR); line[j-1] = u; u = t; }
line[n+i] = t; line[n+i+1] = STAR; } } }</lang>
IDL
The only 'special' thing here is that the math is done in a byte array, filled with the numbers 32 and 42 and then output through a "string(array)" which prints the ascii representation of each individual element in the array. <lang idl>pro sierp,n
s = (t = bytarr(3+2^(n+1))+32b)
t[2^n+1] = 42b
for lines = 1,2^n do begin
print,string( (s = t) )
for i=1,n_elements(t)-2 do if s[i-1] eq s[i+1] then t[i]=32b else t[i]=42b
end
end</lang>
Icon and Unicon
This is a text based adaption of a program from the IPL and Icon Graphics book. The triangle is presented with a twist. Based on an idea from "Chaos and Fractals" by Peitgen, Jurgens, and Saupe. <lang Icon># text based adaptaion of
procedure main(A)
width := 2 ^ ( 1 + (order := 0 < integer(\A[1]) | 4)) # order of arg[1] or 4
write("Triangle order= ",order)
every !(canvas := list(width)) := list(width," ") # prime the canvas
every y := 1 to width & x := 1 to width do # traverse it
if iand(x - 1, y - 1) = 0 then canvas[x,y] := "*" # fill
every x := 1 to width & y := 1 to width do
writes((y=1,"\n")|"",canvas[x,y]," ") # print
end</lang>
Adapted from graphics/sier1.icn
Sample output for order 3:
Triangle order = 2 * * * * * * * * * * * * * * * * * * * * * * * * * * *
J
There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity: <lang j> |. _31]\ ,(,.~ , ])^:4 ,: '* '</lang> Here's one that leverages the relationship between Sierpinski's and Pascal's triangles: <lang j> ' *' {~ '1' = (- |."_1 [: ": 2 | !/~) i._16</lang>
Java
<lang java>public static void triangle(int n){
n= 1 << n;
StringBuilder line= new StringBuilder(); //use a "mutable String"
char t= 0;
char u= 0; // avoid warnings
for(int i= 0;i <= 2 * n;++i)
line.append(" "); //start empty
line.setCharAt(n, '*'); //with the top point of the triangle
for(int i= 0;i < n;++i){
System.out.println(line);
u= '*';
for(int j= n - i;j < n + i + 1;++j){
t= (line.charAt(j - 1) == line.charAt(j + 1) ? ' ' : '*');
line.setCharAt(j - 1, u);
u= t;
}
line.setCharAt(n + i, t);
line.setCharAt(n + i + 1, '*');
}
}</lang>
<lang java>import java.util.*;
public class Sierpinski {
public static List<String> sierpinski(int n)
{
List<String> down = Arrays.asList("*");
String space = " ";
for (int i = 0; i < n; i++) {
List<String> newDown = new ArrayList<String>();
for (String x : down)
newDown.add(space + x + space);
for (String x : down)
newDown.add(x + " " + x);
down = newDown;
space += space;
}
return down;
}
public static void main(String[] args)
{
for (String x : sierpinski(4))
System.out.println(x);
}
}</lang>
JavaFX Script
<lang javafx>function sierpinski(n : Integer) {
var down = ["*"];
var space = " ";
for (i in [1..n]) {
down = [for (x in down) "{space}{x}{space}", for (x in down) "{x} {x}"];
space = "{space}{space}";
}
for (x in down) {
println("{x}")
}
}
sierpinski(4);</lang>
JavaScript
<lang javascript>function triangle(o) {
var n = 1<<o, line = new Array(2*n), i,j,t,u;
for (i=0; i<line.length; ++i) line[i] = ' ';
line[n] = '*';
for (i=0; i<n; ++i) {
document.write(line.join()+"\n");
u ='*';
for(j=n-i; j<n+i+1; ++j) {
t = (line[j-1] == line[j+1] ? ' ' : '*');
line[j-1] = u;
u = t;
}
line[n+i] = t;
line[n+i+1] = '*';
}
}
document.write("
\n");
triangle(6);
document.write("");</lang>
Liberty BASIC
<lang lb>nOrder=4 call triangle 1, 1, nOrder end
SUB triangle x, y, n
IF n = 0 THEN
LOCATE x,y: PRINT "*";
ELSE
n=n-1
length=2^n
call triangle x, y+length, n
call triangle x+length, y, n
call triangle x+length*2, y+length, n
END IF
END SUB</lang>
Logo
This will draw a graphical Sierpinski gasket using turtle graphics. <lang logo>to sierpinski :n :length
if :n = 0 [stop] repeat 3 [sierpinski :n-1 :length/2 fd :length rt 120]
end seth 30 sierpinski 5 200</lang>
Mathematica
Cellular automaton (rule 90) based solution: <lang mathematica>n=4;Grid[CellularAutomaton[90,{{1},0},2^n-1]/.{0->" ",1->"*"},ItemSize->All]</lang>
OCaml
<lang ocaml>let sierpinski n =
let rec loop down space n =
if n = 0 then
down
else
loop (List.map (fun x -> space ^ x ^ space) down @
List.map (fun x -> x ^ " " ^ x) down)
(space ^ space)
(n - 1)
in loop ["*"] " " n
let () =
List.iter print_endline (sierpinski 4)</lang>
Oz
<lang oz>declare
fun {NextTriangle Triangle}
Sp = {Spaces {Length Triangle}}
in
{Flatten
[{Map Triangle fun {$ X} Sp#X#Sp end}
{Map Triangle fun {$ X} X#" "#X end}
]}
end
fun {Spaces N} if N == 0 then nil else & |{Spaces N-1} end end
fun lazy {Iterate F X}
X|{Iterate F {F X}}
end
SierpinskiTriangles = {Iterate NextTriangle ["*"]}
in
{ForAll {Nth SierpinskiTriangles 5} System.showInfo}</lang>
Pascal
<lang pascal>program Sierpinski;
function ipow(b, n : Integer) : Integer; var
i : Integer;
begin
ipow := 1;
for i := 1 to n do
ipow := ipow * b
end;
function truth(a : Char) : Boolean; begin
if a = '*' then
truth := true
else
truth := false
end;</lang>
<lang pascal>function rule_90(ev : String) : String; var
l, i : Integer; cp : String; s : Array[0..1] of Boolean;
begin
l := length(ev);
cp := copy(ev, 1, l);
for i := 1 to l do begin
if (i-1) < 1 then
s[0] := false
else
s[0] := truth(ev[i-1]);
if (i+1) > l then
s[1] := false
else
s[1] := truth(ev[i+1]);
if ( (s[0] and not s[1]) or (s[1] and not s[0]) ) then
cp[i] := '*'
else
cp[i] := ' ';
end; rule_90 := cp
end;
procedure triangle(n : Integer); var
i, l : Integer; b : String;
begin
l := ipow(2, n+1);
b := ' ';
for i := 1 to l do
b := concat(b, ' ');
b[round(l/2)] := '*';
writeln(b);
for i := 1 to (round(l/2)-1) do begin
b := rule_90(b);
writeln(b)
end
end;</lang>
<lang pascal>begin
triangle(4)
end.</lang>
Perl
<lang perl>sub sierpinski {
my ($n) = @_;
my @down = '*';
my $space = ' ';
foreach (1..$n) {
@down = (map("$space$_$space", @down), map("$_ $_", @down));
$space = "$space$space";
}
return @down;
}
print "$_\n" foreach sierpinski 4;</lang>
Perl 6
<lang perl6>sub sierpinski ($n) {
my @down = '*';
my $space = ' ';
for ^$n {
@down = @down.map({"$space$_$space"}), @down.map({"$_ $_"});
$space ~= $space;
}
return @down;
}
.say for sierpinski 4;</lang>
PL/I
<lang PL/I>sierpinski: procedure options (main); /* 2010-03-30 */
declare t (79,79) char (1); declare (i, j, k) fixed binary; declare (y, xs, ys, xll, xrr, ixrr, limit) fixed binary;
t = ' ';
xs = 40; ys = 1;
/* Make initial triangle */
call make_triangle (xs, ys);
y = ys + 4;
xll = xs-4; xrr = xs+4;
do k = 1 to 3;
limit = 0;
do forever;
ixrr = xrr;
do i = xll to xll+limit by 8;
if t(y-1, i) = ' ' then
do;
call make_triangle (i, y);
if t(y+3,i-5) = '*' then
t(y+3,i-4), t(y+3,ixrr+4) = '*';
call make_triangle (ixrr, y);
end;
ixrr = ixrr - 8;
end;
xll = xll - 4; xrr = xrr + 4;
y = y + 4;
limit = limit + 8;
if xll+limit > xs-1 then leave;
end;
t(y-1,xs) = '*';
end;
/* Finished generation; now print the Sierpinski triangle. */ put edit (t) (skip, (hbound(t,2)) a);
make_triangle: procedure (x, y);
declare (x, y) fixed binary; declare i fixed binary;
do i = 0 to 3;
t(y+i, x-i), t(y+i, x+i) = '*';
end;
do i = x-2 to x+2; /* The base of the triangle. */
t(y+3, i) = '*';
end;
end make_triangle;
end sierpinski;</lang>
PicoLisp
<lang PicoLisp>(de sierpinski (N)
(let (D '("*") S " ")
(do N
(setq
D (conc
(mapcar '((X) (pack S X S)) D)
(mapcar '((X) (pack X " " X)) D) )
S (pack S S) ) )
D ) )
(mapc prinl (sierpinski 4))</lang>
PostScript
This draws the triangles in a string-rewrite fashion, where all edges form a single polyline. 9 page document showing progession. <lang postscript>%!PS-Adobe-3.0 %%BoundingBox 0 0 300 300
/F { 1 0 rlineto } def /+ { 120 rotate } def /- {-120 rotate } def /v {.5 .5 scale } def /^ { 2 2 scale } def /!0{ dup 1 sub dup -1 eq not } def
/X { !0 { v X + F - X - F + X ^ } { F } ifelse pop } def
0 1 8 { 300 300 scale 0 1 12 div moveto
X + F + F fill showpage } for
%%EOF</lang>
Pop11
Solution using line buffer in an integer array oline, 0 represents ' ' (space), 1 represents '*' (star). <lang pop11>define triangle(n);
lvars k = 2**n, j, l, oline, nline;
initv(2*k+3) -> oline;
initv(2*k+3) -> nline;
for l from 1 to 2*k+3 do 0 -> oline(l) ; endfor;
1 -> oline(k+2);
0 -> nline(1);
0 -> nline(2*k+3);
for j from 1 to k do
for l from 1 to 2*k+3 do
printf(if oline(l) = 0 then ' ' else '*' endif);
endfor;
printf('\n');
for l from 2 to 2*k+2 do
(oline(l-1) + oline(l+1)) rem 2 -> nline(l);
endfor;
(oline, nline) -> (nline, oline);
endfor;
enddefine;
triangle(4);</lang>
Alternative solution, keeping all triangle as list of strings <lang pop11>define triangle2(n);
lvars acc = ['*'], spaces = ' ', j;
for j from 1 to n do
maplist(acc, procedure(x); spaces >< x >< spaces ; endprocedure)
<> maplist(acc, procedure(x); x >< ' ' >< x ; endprocedure) -> acc;
spaces >< spaces -> spaces;
endfor;
applist(acc, procedure(x); printf(x, '%p\n'); endprocedure);
enddefine;
triangle2(4);</lang>
PowerShell
<lang powershell>function triangle($o) {
$n = [Math]::Pow(2, $o)
$line = ,' '*(2*$n+1)
$line[$n] = '█'
$OFS =
for ($i = 0; $i -lt $n; $i++) {
Write-Host $line
$u = '█'
for ($j = $n - $i; $j -lt $n + $i + 1; $j++) {
if ($line[$j-1] -eq $line[$j+1]) {
$t = ' '
} else {
$t = '█'
}
$line[$j-1] = $u
$u = $t
}
$line[$n+$i] = $t
$line[$n+$i+1] = '█'
}
}</lang>
Prolg
Works with SWI-Prolog; <lang Prolog>sierpinski_triangle(N) :- Len is 2 ** (N+1) - 1, length(L, Len), numlist(1, Len, LN), maplist(init(N), L, LN), atomic_list_concat(L, Line), writeln(Line), NbTours is 2**N - 1, loop(NbTours, LN, Len, L).
init(N, Cell, Num) :- ( Num is 2 ** N + 1 -> Cell = *; Cell = ' ').
loop(0, _, _, _) :- !.
loop(N, LN, Len, L) :- maplist(compute_next_line(Len, L), LN, L1), atomic_list_concat(L1, Line), writeln(Line), N1 is N - 1, loop(N1, LN, Len, L1).
compute_next_line(Len, L, I, V) :- I1 is I - 1, I2 is I+1, ( I = 1 -> V0 = ' '; nth1(I1, L, V0)), nth1(I, L, V1), ( I = Len -> V2 = ' '; nth1(I2, L, V2)), rule_90(V0, V1, V2, V).
rule_90('*','*','*', ' '). rule_90('*','*',' ', '*'). rule_90('*',' ','*', ' '). rule_90('*',' ',' ', '*'). rule_90(' ','*','*', '*'). rule_90(' ','*',' ', ' '). rule_90(' ',' ','*', '*'). rule_90(' ',' ',' ', ' '). </lang> Output :
?- sierpinski_triangle(4).
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
true
PureBasic
<lang PureBasic>Procedure Triangle (X,Y, Length, N)
If N = 0
DrawText( Y,X, "*",#Blue)
Else
Triangle (X+Length, Y, Length/2, N-1)
Triangle (X, Y+Length, Length/2, N-1)
Triangle (X+Length, Y+Length*2, Length/2, N-1)
EndIf
EndProcedure
OpenWindow(0, 100, 100,700,500 ,"Sierpinski triangle", #PB_Window_SystemMenu |1)
StartDrawing(WindowOutput(0))
DrawingMode(#PB_2DDrawing_Transparent ) Triangle(10,10,120,5) Repeat Until WaitWindowEvent()=#PB_Event_CloseWindow
End</lang>
Python
<lang python>def sierpinski(n):
d = ["*"]
for i in xrange(n):
sp = " " * (2 ** i)
d = [sp+x+sp for x in d] + [x+" "+x for x in d]
return d
print "\n".join(sierpinski(4))</lang>
Or, using fold / reduce
<lang python>import functools
def sierpinski(n):
def aggregate(TRIANGLE, I):
SPACE = " " * (2 ** I)
return [SPACE+X+SPACE for X in TRIANGLE] + [X+" "+X for X in TRIANGLE]
return functools.reduce(aggregate, range(n), ["*"])
print("\n".join(sierpinski(4)))</lang>
R
Based on C# but using some of R's functionality to abbreviate code where possible. <lang r>sierpinski.triangle = function(n) { len <- 2^(n+1) b <- c(rep(FALSE,len/2),TRUE,rep(FALSE,len/2)) for (i in 1:(len/2)) { cat(paste(ifelse(b,"*"," "),collapse=""),"\n") n <- rep(FALSE,len+1) n[which(b)-1]<-TRUE n[which(b)+1]<-xor(n[which(b)+1],TRUE) b <- n } } sierpinski.triangle(5)</lang>
Shortened to a function of one line. <lang r>sierpinski.triangle = function(n) { c(paste(ifelse(b<<- c(rep(FALSE,2^(n+1)/2),TRUE,rep(FALSE,2^(n+1)/2)),"*"," "),collapse=""),replicate(2^n-1,paste(ifelse(b<<-xor(c(FALSE,b[1:2^(n+1)]),c(b[2:(2^(n+1)+1)],FALSE)),"*"," "),collapse=""))) } cat(sierpinski.triangle(5),sep="\n")</lang>
REXX
<lang rexx>/*REXX program draws a Sierpinksi triangle of any order. */
parse arg n mk . /*get the order of the triangle. */ if n== | n==',' then n=4 /*if none specified, assume 4. */ if mk== then mk='*' /*use the default of an asterisk.*/ if length(mk)==2 then mk=x2c(mk) /*MK was specified in hexadecimal*/ if length(mk)==3 then mk=d2c(mk) /*MK was specified in decimal. */ numeric digits 2000 /*just in case they want a bigun.*/
do j=0 for n*4
!=1
_=left(,n*4-1-j)
do k=0 to j
if !//2==0 then _=_' '
else _=_ mk
!=!*(j-k)%(k+1)
end
say _
end</lang>
Output (using the default of order 4):
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
Output when using the input of:
8 1e
▲
▲ ▲
▲ ▲
▲ ▲ ▲ ▲
▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲
Output when using the input of:
32 db
█
█ █
█ █
█ █ █ █
█ █
█ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █
█ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █
█ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █
█ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █
█ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
█ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █
Output with an input of 64 was too large for this page. See Sierpinski triangle/REXX output 64
Ruby
From the command line: <lang ruby>ruby -le'16.times{|y|print" "*(15-y),(0..y).map{|x|~y&x>0?" ":" *"}}'</lang>
or,
<lang ruby>def sierpinski_triangle(n)
triangle = ["*"]
n.times do |i|
sp = " " * (2**i)
triangle = triangle.collect {|x| sp + x + sp} + \
triangle.collect {|x| x + " " + x}
end
triangle.join("\n")
end
puts sierpinski_triangle(4)</lang>
Using fold / reduce (aka. inject):
<lang ruby>def sierpinski_triangle(n)
(0..(n-1)).inject(["*"]) {|triangle, i|
space = " " * (2**i) triangle.map {|x| space + x + space} + triangle.map {|x| x + " " + x}
}
end
puts sierpinski_triangle(4)</lang>
Scala
The Ruby command-line version (on Windows): <lang scala>scala -e "for(y<-0 to 15){println(\" \"*(15-y)++(0 to y).map(x=>if((~y&x)>0)\" \"else\" *\")mkString)}"</lang>
The Forth version: <lang scala>def sierpinski(n: Int) {
def star(n: Long) = if ((n & 1L) == 1L) "*" else " "
def stars(n: Long): String = if (n == 0L) "" else star(n) + " " + stars(n >> 1)
def spaces(n: Int) = " " * n
((1 << n) - 1 to 0 by -1).foldLeft(1L) {
case (bitmap, remainingLines) =>
println(spaces(remainingLines) + stars(bitmap))
(bitmap << 1) ^ bitmap
}
}</lang>
The Haskell version: <lang scala>def printSierpinski(n: Int) {
def sierpinski(n: Int): List[String] = {
lazy val down = sierpinski(n - 1)
lazy val space = " " * (1 << (n - 1))
n match {
case 0 => List("*")
case _ => (down map (space + _ + space)) :::
(down map (List.fill(2)(_) mkString " "))
}
}
sierpinski(n) foreach println
}</lang>
Scheme
<lang scheme>(define (sierpinski n)
(for-each
(lambda (x) (display (list->string x)) (newline))
(let loop ((acc (list (list #\*))) (spaces (list #\ )) (n n))
(if (zero? n)
acc
(loop
(append
(map (lambda (x) (append spaces x spaces)) acc)
(map (lambda (x) (append x (list #\ ) x)) acc))
(append spaces spaces)
(- n 1))))))</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func array string: sierpinski (in integer: n) is func
result
var array string: parts is 1 times "*";
local
var integer: i is 0;
var string: space is " ";
var array string: parts2 is 0 times "";
var string: x is "";
begin
for i range 1 to n do
parts2 := 0 times "";
for x range parts do
parts2 &:= [] (space & x & space);
end for;
for x range parts do
parts2 &:= [] (x & " " & x);
end for;
parts := parts2;
space &:= space;
end for;
end func;
const proc: main is func
begin writeln(join(sierpinski(4), "\n")); end func;</lang>
Tcl
<lang tcl>package require Tcl 8.5
proc map {lambda list} {
foreach elem $list {
lappend result [apply $lambda $elem]
}
return $result
}
proc sierpinski_triangle n {
set down [list *]
set space " "
for {set i 1} {$i <= $n} {incr i} {
set down [concat \
[map [subst -nocommands {x {expr {"$space[set x]$space"}}}] $down] \
[map {x {expr {"$x $x"}}} $down] \
]
append space $space
}
return [join $down \n]
}
puts [sierpinski_triangle 4]</lang>
Ursala
the straightforward recursive solution <lang Ursala>#import nat
triangle = ~&a^?\<<&>>! ^|RNSiDlrTSPxSxNiCK9xSx4NiCSplrTSPT/~& predecessor</lang> the cheeky cellular automaton solution <lang Ursala>#import std
- import nat
rule = -$<0,&,0,0,&,0,0,0>@rSS zipp0*ziD iota8 evolve "n" = @iNC ~&x+ rep"n" ^C\~& @h rule*+ swin3+ :/0+ --<0> sierpinski = iota; --<&>@NS; iota; ^H/evolve@z @NS ^T/~& :/&</lang> an example of each (converting from booleans to characters) <lang Ursala>#show+
examples = mat0 ~&?(`*!,` !)*** <sierpinski3,triangle4></lang> output:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
* * * *
* * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
Vedit macro language
Iterative
The macro writes the fractal into an edit buffer where it can be viewed and saved to file if required. This allows creating images larger than screen, the size is only limited by free disk space. <lang vedit>#3 = 16 // size (height) of the triangle Buf_Switch(Buf_Free) // Open a new buffer for output Ins_Char(' ', COUNT, #3*2+2) // fill first line with spaces Ins_Newline Line(-1) Goto_Col(#3) Ins_Char('*', OVERWRITE) // the top of triangle for (#10=0; #10 < #3-1; #10++) {
BOL Reg_Copy(9,1) Reg_Ins(9) // duplicate the line
#20 = '*'
for (#11 = #3-#10; #11 < #3+#10+1; #11++) {
Goto_Col(#11-1)
if (Cur_Char==Cur_Char(2)) { #21=' ' } else { #21='*' } Ins_Char(#20, OVERWRITE) #20 = #21
}
Ins_Char(#21, OVERWRITE)
Ins_Char('*', OVERWRITE)
}</lang>
Recursive
Vedit macro language does not have recursive functions, so some pushing and popping is needed to implement recursion. <lang vedit>#1 = 1 // x
- 2 = 1 // y
- 3 = 16 // length (height of the triangle / 2)
- 4 = 5 // depth of recursion
Buf_Switch(Buf_Free) // Open a new buffer for output Ins_Newline(#3*2) // Create as many empty lines as needed Call("Triangle") // Draw the triangle BOF Return
- Triangle:
if (#4 == 0) {
Goto_Line(#2)
EOL Ins_Char(' ', COUNT, #1-Cur_Col+1) // add spaces if needed
Goto_Col(#1)
Ins_Char('*', OVERWRITE)
} else {
Num_Push(1,4)
#2 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
Num_Push(1,4)
#1 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
Num_Push(1,4)
#1 += 2*#3; #2 += #3; #3 /= 2; #4--; Call("Triangle")
Num_Pop(1,4)
} Return</lang>
- Programming Tasks
- Fractals
- Ada
- ALGOL 68
- AutoHotkey
- AWK
- BASIC
- BBC BASIC
- C
- C++
- C sharp
- Clojure
- Common Lisp
- D
- Delphi
- DWScript
- E
- Erlang
- Euphoria
- F Sharp
- FALSE
- Factor
- Forth
- Fortran
- GAP
- Go
- Groovy
- Haskell
- HaXe
- IDL
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaFX Script
- JavaScript
- Liberty BASIC
- Logo
- Mathematica
- OCaml
- Oz
- Pascal
- Perl
- Perl 6
- PL/I
- PicoLisp
- PostScript
- Pop11
- PowerShell
- Prolg
- PureBasic
- Python
- R
- REXX
- Ruby
- Scala
- Scheme
- Seed7
- Tcl
- Ursala
- Vedit macro language