Sierpinski triangle

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:

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

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> Gui version: <d>module sietrigui ; private import dfl.all;

float imin(int a, float b){ return a > b ? b : cast(float)a ; }

class DrawForm: Form {

 private int order = 4 ;
 private Pen pen ;
 private Graphics g ;
 private Size[] offsetL, offsetR ;
 const float sqrt5r1 = 0.447213595499958 ; // sqrt(1/5) ;
 this() {
   text = "Sierpinski Triangle";
   backColor = Color(0x0, 0x3f, 0x3f);
 }   
 final void seitri(int n, Point p) {   
   if(n <= order && n < offsetL.length - 1) {
     seitri(n+1, p) ;
     seitri(n+1, p + offsetL[n]) ;
     seitri(n+1, p + offsetR[n]) ; 
   } else if(n <= order && n < offsetL.length)
     g.drawPolygon(pen, [p, p + offsetL[n-1], p + offsetR[n-1]]) ;     
 } 
 void onResize(EventArgs ea) { invalidate() ; }
 void onPaint(PaintEventArgs ea) {
   super.onPaint(ea);
   pen = new Pen(Color(0xff, 0xff, 0x7f));
   g = ea.graphics  ;
   with(clientRectangle) {
     auto origin = Point(width/2 , 1) ;
     float h = imin(height-2, (width -2) / sqrt5r1 / 2 ) ;
     offsetL = offsetR = null ; 
     while (h >= 1.0 && offsetL.length <= order) {
       offsetL ~= Size( cast(int)( -h * sqrt5r1), cast(int)h ) ;
       offsetR ~= Size( cast(int)(  h * sqrt5r1), cast(int)h ) ;
       h = h / 2.0 ;
     }
     seitri(1, origin) ;
     g.drawText(std.format.format(" n=%s / res=", order, offsetL.length - 1 ), 
       font, Color(0xff,0xff,0xff), Rect(0, 0, 80, 20)) ; 
   }
   g  = null ;
   pen = null ;
 } 
 void neworder(int n) {
   if (n != order && n > 0) { order = n ; invalidate() ; }   
 }
 void onMouseWheel(MouseEventArgs mea) {     
   if(mea.delta > 0) neworder(order + 1) ;
   else if(mea.delta < 0) neworder(order - 1) ;
 }
 void onMouseDown(MouseEventArgs mea) {      
   if(mea.button & MouseButtons.LEFT) neworder(order + 1) ;
   else if(mea.button & MouseButtons.RIGHT) neworder(order - 1) ;
   else  if(mea.button & MouseButtons.MIDDLE) neworder(4) ;     
 }

}

void main(char[][] args) {

 try Application.run(new DrawForm);
 catch(Object o)
   msgBox(o.toString(), "Fatal Error", MsgBoxButtons.OK, MsgBoxIcon.ERROR);

}</d>

Works with: DFL

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