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
Translated from Lisp examples. <d>module sierpinski ; import std.stdio ;
long ipow(int x, int n) { return n > 0 ? x*ipow(x, n-1) : 1 ; }
void sietri(uint n) {
if(n > 5) return writefln("integer bit size limited : n should not be larger than 5") ;
long size = ipow(2,n) ;
long v = ipow(2, size) ;
for(int i = 0 ; i < size ; i++) {
for(int j = 0; j <v.sizeof*8 ; j++ )
writef(ipow(2,j) & v ? "*" : " ") ;
writefln() ;
v = (v << 1) ^ (v >> 1) ;
}
}
void main() {
for(int n = 0; n < 5 ; n++) sietri(n) ;
}</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
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>
Based on Haskell: <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>
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>