Sierpinski triangle
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. <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;</ada>
Common 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) "*" " ")))))
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.
D
Adapted from Java version (this version is slower than the Python one). <d>import std.stdio, std.string;
string[] sierpinski(int n) {
string[] parts = ["*"];
string space = " ";
for (int i; i < n; i++) {
string[] parts2;
foreach (x; parts)
parts2 ~= space ~ x ~ space;
foreach (x; parts)
parts2 ~= x ~ " " ~ x;
parts = parts2;
space ~= space;
}
return parts;
}
void main() {
writefln(sierpinski(4).join("\n"));
}</d>
That sierpinski() function can run at compile time too, so with a compile-time join it can compute the whole result at compile-time:
<d>import std.stdio;
string[] sierpinski(int n) {
string[] parts = ["*"];
string space = " ";
for (int i; i < n; i++) {
string[] parts2;
foreach (x; parts)
parts2 ~= space ~ x ~ space;
foreach (x; parts)
parts2 ~= x ~ " " ~ x;
parts = parts2;
space ~= space;
}
return parts;
}
string joinCT(string[] parts, char sep) {
string result;
if (parts.length) {
foreach (part; parts[0 .. $-1]) {
result ~= part;
result ~= sep;
}
result ~= parts[$-1];
}
return result;
}
auto result = sierpinski(4).joinCT('\n');
void main() {
writefln(result);
}</d>
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
Haskell
sierpinski 0 = ["*"]
sierpinski (n+1) = map ((space ++) . (++ space)) down
++ map (unwords . replicate 2) down
where down = sierpinski n
space = replicate (2^n) ' '
printSierpinski = mapM_ putStrLn . sierpinski
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.
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
J
There are any number of succinct ways to produce this in J. Here's one that exploits self-similarity:
|._31]\,(,.~,])^:4,:'* '
Here's one that leverages the relationship between Sierpinski's and Pascal's triangles:
' *'{~'1'=(-|."_1[:":2|!/~)i.-16
Java
<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, '*'); } }</java>
<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);
}
} </java>
JavaScript
<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("");
</javascript>
OCaml
<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)
</ocaml>
Perl
<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; </perl>
Python
<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)) </python>
Scheme
As the Haskell. <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))))))
</scheme>