Sierpinski triangle

Produce an ASCII representation of a Sierpinski triangle of order N. For example, the Sierpinski triangle of order 4 should look like this:


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

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

: .line ( n -- )
  begin
    dup 1 and if [char] * else bl then emit
    1 rshift  dup 0=
  until drop ;

: triangle ( order -- )
  1 swap lshift   ( 2^order )
  1 over lshift
  swap 0 do
    dup cr .line
    dup 2/ swap 2* xor
  loop drop ;

4 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

Scheme

As the Haskell.

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