Sierpinski carpet
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 carpet of order N. For example, the Sierpinski carpet of order 3 should look like this:
########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ########################### ######### ######### # ## ## # # ## ## # ######### ######### ### ### ### ### # # # # # # # # ### ### ### ### ######### ######### # ## ## # # ## ## # ######### ######### ########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ###########################
The use of # characters is not rigidly required. The important requirement is the placement of whitespace and non-whitespace characters.
See also Sierpinski triangle
Ada
<lang ada>with Ada.Text_Io; use Ada.Text_Io;
procedure Sierpinski_Carpet is
subtype Index_Type is Integer range 1..81;
type Pattern_Array is array(Index_Type range <>, Index_Type range <>) of Boolean;
Pattern : Pattern_Array(1..81,1..81) := (Others =>(others => true));
procedure Clear_Center(P : in out Pattern_Array; X1 : Index_Type; X2 : Index_Type;
Y1 : Index_Type; Y2 : Index_Type) is
Xfirst : Index_Type;
Xlast : Index_Type;
Yfirst : Index_Type;
Ylast : Index_Type;
Diff : Integer;
begin
Xfirst :=(X2 - X1 + 1) / 3 + X1;
Diff := Xfirst - X1;
Xlast := Xfirst + Diff;
Yfirst := (Y2 - Y1) / 3 + Y1;
YLast := YFirst + Diff;
for I in XFirst..XLast loop
for J in YFirst..YLast loop
P(I, J) := False;
end loop;
end loop;
end Clear_Center;
procedure Print(P : Pattern_Array) is
begin
for I in P'range(1) loop
for J in P'range(2) loop
if P(I,J) then
Put('*');
else
Put(' ');
end if;
end loop;
New_Line;
end loop;
end Print;
procedure Divide_Square(P : in out Pattern_Array; Order : Positive) is
Factor : Natural := 0;
X1, X2 : Index_Type;
Y1, Y2 : Index_Type;
Division : Index_Type;
Num_Sections : Index_Type;
begin
while Factor < Order loop
Num_Sections := 3**Factor;
Factor := Factor + 1;
X1 := P'First;
Division := P'Last / Num_Sections;
X2 := Division;
Y1 := X1;
Y2 := X2;
loop
loop
Clear_Center(P, X1, X2, Y1, Y2);
exit when X2 = P'Last;
X1 := X2;
X2 := X2 + Division;
end loop;
exit when Y2 = P'Last;
Y1 := Y2;
Y2 := Y2 + Division;
X1 := P'First;
X2 := Division;
end loop;
end loop;
end Divide_Square;
begin
Divide_Square(Pattern, 3); Print(Pattern);
end Sierpinski_Carpet;</lang>
ALGOL 68
<lang algol68>PROC in carpet = (INT in x, in y)BOOL: (
INT x := in x, y := in y;
BOOL out;
DO
IF x = 0 OR y = 0 THEN
out := TRUE; GO TO stop iteration
ELIF x MOD 3 = 1 AND y MOD 3 = 1 THEN
out := FALSE; GO TO stop iteration
FI;
x %:= 3;
y %:= 3
OD;
stop iteration: out
);
PROC carpet = (INT n)VOID:
FOR i TO 3 ** n DO
FOR j TO 3 ** n DO
IF in carpet(i-1, j-1) THEN
print("* ")
ELSE
print(" ")
FI
OD;
print(new line)
OD;
carpet(3)</lang>
AutoHotkey
ahk discussion <lang autohotkey>Loop 4
MsgBox % Carpet(A_Index)
Carpet(n) {
Loop % 3**n {
x := A_Index-1
Loop % 3**n
t .= Dot(x,A_Index-1)
t .= "`n"
}
Return t
}
Dot(x,y) {
While x>0 && y>0
If (mod(x,3)=1 && mod(y,3)=1)
Return " "
Else x //= 3, y //= 3
Return "."
}</lang>
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
typedef struct sCarpet {
int dim; // dimension char *data; // character data char **rows; // pointers to data rows
} *Carpet;
/* Clones a tile into larger carpet, or blank if center */ void TileCarpet( Carpet d, int r, int c, Carpet tile ) {
int y0 = tile->dim*r; int x0 = tile->dim*c; int k,m;
if ((r==1) && (c==1)) {
for(k=0; k < tile->dim; k++) {
for (m=0; m < tile->dim; m++) {
d->rows[y0+k][x0+m] = ' ';
}
}
}
else {
for(k=0; k < tile->dim; k++) {
for (m=0; m < tile->dim; m++) {
d->rows[y0+k][x0+m] = tile->rows[k][m];
}
}
}
}
/* define a 1x1 starting carpet */ static char s1[]= "#"; static char *r1[] = {s1}; static struct sCarpet single = { 1, s1, r1};
Carpet Sierpinski( int n ) {
Carpet carpet; Carpet subCarpet; int row,col, rb; int spc_rqrd;
subCarpet = (n > 1) ? Sierpinski(n-1) : &single;
carpet = malloc(sizeof(struct sCarpet));
carpet->dim = 3*subCarpet->dim;
spc_rqrd = (2*subCarpet->dim) * (carpet->dim);
carpet->data = malloc(spc_rqrd*sizeof(char));
carpet->rows = malloc( carpet->dim*sizeof(char *));
for (row=0; row<subCarpet->dim; row++) {
carpet->rows[row] = carpet->data + row*carpet->dim;
rb = row+subCarpet->dim;
carpet->rows[rb] = carpet->data + rb*carpet->dim;
rb = row+2*subCarpet->dim;
carpet->rows[rb] = carpet->data + row*carpet->dim;
}
for (col=0; col < 3; col++) {
/* 2 rows of tiles to copy - third group points to same data a first */
for (row=0; row < 2; row++)
TileCarpet( carpet, row, col, subCarpet );
}
if (subCarpet != &single ) {
free(subCarpet->rows);
free(subCarpet->data);
free(subCarpet);
}
return carpet;
}
void CarpetPrint( FILE *fout, Carpet carp) {
char obuf[730];
int row;
for (row=0; row < carp->dim; row++) {
strncpy(obuf, carp->rows[row], carp->dim);
fprintf(fout, "%s\n", obuf);
}
fprintf(fout,"\n");
}
int main(int argc, char *argv[]) { // FILE *f = fopen("sierp.txt","w");
CarpetPrint(stdout, Sierpinski(3));
// fclose(f);
return 0;
} </lang>
C#
<lang csharp>using System; using System.Collections.Generic; using System.Linq;
class Program {
static List<string> NextCarpet(List<string> carpet)
{
return carpet.Select(x => x + x + x)
.Concat(carpet.Select(x => x + x.Replace('#', ' ') + x))
.Concat(carpet.Select(x => x + x + x)).ToList();
}
static List<string> SierpinskiCarpet(int n)
{
return Enumerable.Range(1, n).Aggregate(new List<string> { "#" }, (carpet, _) => NextCarpet(carpet));
}
static void Main(string[] args)
{
foreach (string s in SierpinskiCarpet(3))
Console.WriteLine(s);
}
}</lang>
Clojure
<lang clojure>(ns example
(:require [clojure.contrib.math :as math]))
(defn in-carpet? [x y]
(loop [x x, y y]
(cond
(or (zero? x) (zero? y)) true
(and (= 1 (mod x 3)) (= 1 (mod y 3))) false
:else (recur (quot x 3) (quot y 3)))))
(defn carpet [n]
(apply str
(interpose
\newline (for [x (range (math/expt 3 n))] (apply str (for [y (range (math/expt 3 n))] (if (in-carpet? x y) "*" " ")))))))
(println (carpet 3))</lang>
Common Lisp
This solution works by printing a square of # except where both of the coordinates of a cell contain a 1 in the same digit position in base 3. For example, the central empty square has a 1 in the highest base-3 digit of all its cells, and the smallest empty squares have 1s in the lowest base-3 digit.
<lang lisp>(defun print-carpet (order)
(let ((size (expt 3 order)))
(flet ((trinary (x) (format nil "~3,vR" order x))
(ones (a b) (and (eql a #\1) (eql b #\1))))
(loop for i below size do
(fresh-line)
(loop for j below size do
(princ (if (some #'ones (trinary i) (trinary j))
" "
"#")))))))</lang>
D
<lang d>module siecarpet ; import std.stdio ; import std.string ;
string fenceH(int n) {
if(n == 0) return "-" ;
string inner = repeat("-",fenceH(n-1).length) ;
return "+" ~ inner ~ "+" ~ inner ~ "+" ~ inner ~ "+" ;
} string scarpet(int n) {
if(n < 0) return join(scarpet(-n, true ), "\n") ; return join(scarpet( n, false), "\n") ;
} string[] scarpet(int n, bool fenced) {
if(n == 0 )
return ["#"] ;
string[] inner = scarpet(n-1, fenced) ;
string vFence = fenced ? "|" : "" ;
string hFence = fenceH(n) ;
string[] result ;
void combine(bool center) {
foreach(l ; inner) {
string middle = center ? repeat(" ", l.length) : l ;
string newline = vFence ~ l ~ vFence ~ middle ~ vFence ~ l ~ vFence ;
result ~= newline ;
}
}
for(int i = -1 ; i <= 1 ; i++) {
if (fenced) result ~= hFence ;
combine(i == 0) ;
}
if (fenced) result ~= hFence ;
return result ;
}
void main(string[] args) {
for(int i = -2; i <= 2;i++) writefln(scarpet(i)) ;
}</lang> Iterative approach: <lang d>module siecarpet2 ; import std.stdio ; import std.string ; import std.conv ;
int ipow(int x, int n) { return n <= 0 ? 1 : x * ipow(x, n-1) ; }
string ItoA(ulong num, int radix = 10) {
string result = null ;
while (num > 0) {
int temp = num / radix ;
result = cast(char)('0' + num - temp*radix)~ result ;
num = temp ;
}
return result == null ? "0" : result ;
}
struct S {
int lvl = 3 ;
int pat = 0020 ;
static S opCall(int l, int p) {
S s ;
s.lvl = l >= 0 ? l : 3 ;
s.pat = p ^ 0777;
return s ;
}
int bitp(int i, int j) {
return 1 & (pat >> (3*i + j)) ;
}
char cbit(int n) {
if(lvl == 0) return '#' ;
string pstr1 = (repeat("0", lvl*2) ~ ItoA(n, 3)) [$-lvl*2..$] ;
string pstr2 = pstr1[lvl..$] ;
pstr1.length = lvl ;
int acc = 1 ;
foreach(i,c; pstr1)
if ((acc &= bitp(toInt([c]), toInt(pstr2[i..i+1]))) == 0)
break ;
return acc ? '#' : ' ' ;
}
string toString() {
string str ;
int m = ipow(3,lvl) ;
for(int i = 0 ; i < m ; i++) {
for(int j = 0 ; j < m ; j++)
str ~= cbit(i*m + j ) ;
str ~= '\n' ;
}
return str ;
}
}
void main(string[] args) {
int arg2int(int index, int def) {
int res = def ;
if(index < args.length)
try res = toInt(args[index]) ;
catch(Object o) res = def ;
return res ;
}
int lvl = arg2int(1, 3) ; int pat = arg2int(2, 0) + arg2int(3, 2)*8 + arg2int(4, 0)*64 ; // base 8 pattern S s = S(lvl, pat) ; writefln(s) ;
}</lang>
E
<lang e>def inCarpet(var x, var y) {
while (x > 0 && y > 0) {
if (x %% 3 <=> 1 && y %% 3 <=> 1) {
return false
}
x //= 3
y //= 3
}
return true
}
def carpet(order) {
for y in 0..!(3**order) {
for x in 0..!(3**order) {
print(inCarpet(x, y).pick("#", " "))
}
println()
}
}</lang>
Fan
<lang Fan>**
- Generates a square Sierpinski gasket
class SierpinskiCarpet {
public static Bool inCarpet(Int x, Int y){
while(x!=0 && y!=0){
if (x % 3 == 1 && y % 3 == 1)
return false;
x /= 3;
y /= 3;
}
return true;
}
static Int pow(Int n, Int exp)
{
rslt := 1
exp.times { rslt *= n }
return rslt
}
public static Void carpet(Int n){
for(i := 0; i < pow(3, n); i++){
buf := StrBuf()
for(j := 0; j < pow(3, n); j++){
if( inCarpet(i, j))
buf.add("*");
else
buf.add(" ");
}
echo(buf);
}
}
Void main()
{
carpet(4)
}
}</lang>
Forth
<lang forth>\ Generates a square Sierpinski gasket
- 1? over 3 mod 1 = ; ( n1 n2 -- n1 n2 f)
- 3/ 3 / swap ; ( n1 n2 -- n2/3 n1)
\ is this cell in the carpet?
- incarpet ( n1 n2 -- f)
begin over over or while 1? 1? and if 2drop false exit then 3/ 3/ repeat 2drop true \ return true if in the carpet
\ draw a carpet of n size
- carpet ( n --)
1 swap 0 ?do 3 * loop dup \ calculate power of 3 0 ?do dup 0 ?do i j incarpet if [char] # else bl then emit loop cr loop drop \ evaluate every cell in the carpet
cr 4 carpet</lang>
Fortran
<lang fortran>program Sierpinski_carpet
implicit none call carpet(4)
contains
function In_carpet(a, b)
logical :: in_carpet integer, intent(in) :: a, b integer :: x, y
x = a ; y = b
do
if(x == 0 .or. y == 0) then
In_carpet = .true.
return
else if(mod(x, 3) == 1 .and. mod(y, 3) == 1) then
In_carpet = .false.
return
end if
x = x / 3
y = y / 3
end do
end function
subroutine Carpet(n)
integer, intent(in) :: n
integer :: i, j
do i = 0, 3**n - 1
do j = 0, 3**n - 1
if(In_carpet(i, j)) then
write(*, "(a)", advance="no") "#"
else
write(*, "(a)", advance="no") " "
end if
end do
write(*,*)
end do
end subroutine Carpet end program Sierpinski_carpet</lang>
Groovy
Solution, uses list-indexing of base 3 string representation: <lang groovy>def base3 = { BigInteger i -> i.toString(3) }
def sierpinskiCarpet = { int order ->
StringBuffer sb = new StringBuffer() def positions = 0..<(3**order) def digits = 0..<([order,1].max())
positions.each { i ->
String i3 = base3(i).padLeft(order, '0')
positions.each { j ->
String j3 = base3(j).padLeft(order, '0')
sb << (digits.any{ i3[it] == '1' && j3[it] == '1' } ? ' ' : order.toString().padRight(2) )
}
sb << '\n'
}
sb.toString()
}</lang>
Test Program: <lang groovy>(0..4).each { println sierpinskiCarpet(it) }</lang>
Output:
0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
Haskell
<lang haskell>inCarpet :: Int -> Int -> Bool inCarpet 0 _ = True inCarpet _ 0 = True inCarpet x y = not ((xr == 1) && (yr == 1)) && inCarpet xq yq
where ((xq, xr), (yq, yr)) = (x `divMod` 3, y `divMod` 3)
carpet :: Int -> [String] carpet n = map
(zipWith
(\x y -> if inCarpet x y then '#' else ' ')
[0..3^n-1]
. repeat)
[0..3^n-1]
printCarpet :: Int -> IO () printCarpet = mapM_ putStrLn . carpet</lang>
<lang haskell>nextCarpet :: [String] -> [String] nextCarpet carpet = border ++ map f carpet ++ border
where border = map (concat . replicate 3) carpet
f x = x ++ map (const ' ') x ++ x
sierpinskiCarpets :: String sierpinskiCarpets = iterate nextCarpet ["#"]
main :: IO () main = mapM_ putStrLn $ sierpinskiCarpets !! 3</lang>
J
Like the sierpinski triangle, the carpet is easy to produce in J. One way: <lang j>N=:3 (a:(<1;1)}3 3$<)^:N' '</lang>
or another: <lang j>((#:7 5 7){_2{.<)^:N' '</lang>
That said, using spaces and '#' characters takes a bit more work. One approach would be: <lang j>' #'{~(#:7 5 7) ,/@(1 3 ,/"2@|: */)^:N ,.1</lang>
Java
<lang java>public static boolean inCarpet(long x, long y){
while(x!=0 && y!=0){
if (x % 3 == 1 && y % 3 == 1)
return false;
x /= 3;
y /= 3;
}
return true;
}
public static void carpet(int n){
for(long i = 0;i < Math.pow(3, n);i++){
for(long j = 0 ;j < Math.pow(3, n);j++){
if( inCarpet(i, j))
System.out.print("*");
else
System.out.print(" ");
}
System.out.println();
}
}</lang>
JavaScript
This version also produces a "graphic" via HTML and CSS <lang html4strict><!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <meta http-equiv="Content-Type" content="text/html;charset=utf-8"> <title>Sierpinski Carpet</title> <script type='text/javascript'> var
black_char = "#",
white_char = " ",
SierpinskiCarpet = function(size) {
var i;
this.carpet = [black_char];
for (i = 1; i <= size; i++)
this.carpet = [].concat(this.carpet.map(this.sier_top),this.carpet.map(this.sier_middle),this.carpet.map(this.sier_top));
};
SierpinskiCarpet.prototype.sier_top = function(x) {
var str = new String(x); return new String(str + str + str);
};
SierpinskiCarpet.prototype.sier_middle = function (x) {
var str = new String(x), spacer = str.replace(new RegExp(black_char, 'g'), white_char); return new String(str + spacer + str);
};
SierpinskiCarpet.prototype.to_string = function() {
return this.carpet.join("\n");
};
SierpinskiCarpet.prototype.to_html = function(target) {
var
table = document.createElement('table'),
i, row, j, cell;
for (i = 0; i < this.carpet.length; i++)
{
row = document.createElement('tr');
for (j = 0; j < this.carpet[i].length; j++)
{
cell = document.createElement('td');
cell.setAttribute('class', this.carpet[i][j] === black_char ? 'black' : 'white');
cell.appendChild(document.createTextNode('\u00a0'));
row.appendChild(cell);
}
table.appendChild(row);
}
target.appendChild(table);
}; </script> <style type='text/css'> table{border-collapse:collapse} td{width:1em} .black{background-color:#000} .white{background-color:#FFF} </style> </head> <body>
<script type='text/javascript'> var
sc = new SierpinskiCarpet(3);
document.getElementById('to_string').appendChild(document.createTextNode(sc.to_string()));
sc.to_html(document.getElementById('to_html'));
</script> </body> </html></lang>
Output:
Mathematica
Replace a empty spot with a 3x3 empty matrix, and replace a full spot with an empty spot surrounded by 8 full spots: <lang Mathematica>full={{1,1,1},{1,0,1},{1,1,1}} empty={{0,0,0},{0,0,0},{0,0,0}} n=3; Grid[Nest[ArrayFlatten[#/.{0->empty,1->full}]&,Template:1,n]//.{0->" ",1->"#"}]</lang>
OCaml
<lang ocaml>let rec in_carpet x y =
if x = 0 || y = 0 then true else if x mod 3 = 1 && y mod 3 = 1 then false else in_carpet (x / 3) (y / 3)
(* I define my own operator for integer exponentiation *) let rec (^:) a b =
if b = 0 then 1 else if b mod 2 = 0 then let x = a ^: (b / 2) in x * x else a * (a ^: (b - 1))
let carpet n =
for i = 0 to (3 ^: n) - 1 do
for j = 0 to (3 ^: n) - 1 do
print_char (if in_carpet i j then '*' else ' ')
done;
print_newline ()
done</lang>
<lang ocaml>let nextCarpet carpet =
List.map (fun x -> x ^ x ^ x) carpet @ List.map (fun x -> x ^ String.make (String.length x) ' ' ^ x) carpet @ List.map (fun x -> x ^ x ^ x) carpet
let rec sierpinskiCarpet n =
let rec aux n carpet =
if n = 0 then carpet
else aux (n-1) (nextCarpet carpet)
in
aux n ["#"]
let () =
List.iter print_endline (sierpinskiCarpet 3)</lang>
Oz
<lang oz>declare
%% A carpet is a list of lines.
fun {NextCarpet Carpet}
{Flatten
[{Map Carpet XXX}
{Map Carpet X_X}
{Map Carpet XXX}
]}
end
fun {XXX X} X#X#X end
fun {X_X X} X#{Spaces {VirtualString.length X}}#X 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
SierpinskiCarpets = {Iterate NextCarpet ["#"]}
in
%% print all lines of the Sierpinski carpet of order 3
{ForAll {Nth SierpinskiCarpets 4} System.showInfo}</lang>
Perl 6
<lang perl6>sub carpet {
(['#'], -> @c {
[ @c.map({$_ x 3}),
@c.map({ $_ ~ $_.trans('#'=>' ') ~ $_}),
@c.map({$_ x 3}) ]
} ... *).map: { .join("\n") };
}
say carpet[3];</lang>
PicoLisp
<lang PicoLisp>(de carpet (N)
(let Carpet '("#")
(do N
(setq Carpet
(conc
(mapcar '((S) (pack S S S)) Carpet)
(mapcar
'((S) (pack S (replace (chop S) "#" " ") S))
Carpet )
(mapcar '((S) (pack S S S)) Carpet) ) ) ) ) )
(mapc prinl (carpet 3))</lang>
PowerShell
<lang powershell>function inCarpet($x, $y) {
while ($x -ne 0 -and $y -ne 0) {
if ($x % 3 -eq 1 -and $y % 3 -eq 1) {
return " "
}
$x = [Math]::Truncate($x / 3)
$y = [Math]::Truncate($y / 3)
}
return "█"
}
function carpet($n) {
for ($y = 0; $y -lt [Math]::Pow(3, $n); $y++) {
for ($x = 0; $x -lt [Math]::Pow(3, $n); $x++) {
Write-Host -NoNewline (inCarpet $x $y)
}
Write-Host
}
}</lang>
PureBasic
<lang PureBasic>Procedure in_carpet(x,y)
While x>0 And y>0
If x%3=1 And y%3=1
ProcedureReturn #False
EndIf
y/3: x/3
Wend
ProcedureReturn #True
EndProcedure
Procedure carpet(n)
Define i, j, l=Pow(3,n)-1
For i=0 To l
For j=0 To l
If in_carpet(i,j)
Print("#")
Else
Print(" ")
EndIf
Next
PrintN("")
Next
EndProcedure</lang>
Python
This inserts a space after every character; but this makes the spacing look better anyway.
<lang python>def in_carpet(x, y):
while True:
if x == 0 or y == 0:
return True
elif x % 3 == 1 and y % 3 == 1:
return False
x /= 3
y /= 3
def carpet(n):
for i in xrange(3 ** n):
for j in xrange(3 ** n):
if in_carpet(i, j):
print '*',
else:
print ' ',
print</lang>
This version is elegant:
<lang python>def sierpinski_carpet(n):
carpet = ["#"]
for i in xrange(n):
carpet = [x + x + x for x in carpet] + \
[x + x.replace("#"," ") + x for x in carpet] + \
[x + x + x for x in carpet]
return "\n".join(carpet)
print sierpinski_carpet(3)</lang>
REXX
<lang rexx> /*REXX program draws a Sierpinksi carpet of any order. */
parse arg n mk . /*get the order of the carpet. */ if n== | n==',' then n=3 /*if none specified, assume 3. */ 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 100 /*just in case they want a bigun.*/
do j=0 for 3**n; _=
do k=0 for 3**n; jj=j; kk=k; ?=1
do while jj\==0 & kk\==0
if jj//3==1 & kk//3==1 then do; ?=0; leave; end
jj=jj%3; kk=kk%3
end
if ? then _=_||mk
else _=_' '
end /*k*/
say _
end /*j*/
</lang> Output when using the default:
*************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** *************************** * ** ** ** ** ** ** ** ** * *************************** ********* ********* * ** ** * * ** ** * ********* ********* *** *** *** *** * * * * * * * * *** *** *** *** ********* ********* * ** ** * * ** ** * ********* ********* *************************** * ** ** ** ** ** ** ** ** * *************************** *** ****** ****** *** * * * ** * * ** * * * *** ****** ****** *** *************************** * ** ** ** ** ** ** ** ** * ***************************
Output when using the input of:
1 db
███ █ █ ███
Output when using the input of:
2 db
█████████ █ ██ ██ █ █████████ ███ ███ █ █ █ █ ███ ███ █████████ █ ██ ██ █ █████████
Output when using the input of:
3 db
███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ███ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ █████████ █████████ █ ██ ██ █ █ ██ ██ █ █████████ █████████ ███ ███ ███ ███ █ █ █ █ █ █ █ █ ███ ███ ███ ███ █████████ █████████ █ ██ ██ █ █ ██ ██ █ █████████ █████████ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ███ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████
Output when using the input of:
4 db
█████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ █████████ ██████████████████ ██████████████████ █████████ █ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ █ █████████ ██████████████████ ██████████████████ █████████ ███ ███ ███ ██████ ███ ███ ██████ ███ ███ ███ █ █ █ █ █ █ █ ██ █ █ █ █ █ █ ██ █ █ █ █ █ █ █ ███ ███ ███ ██████ ███ ███ ██████ ███ ███ ███ █████████ ██████████████████ ██████████████████ █████████ █ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ █ █████████ ██████████████████ ██████████████████ █████████ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ ███████████████████████████ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███████████████████████████ ███ ██████ ██████ ███ ███ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ █ █ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ███ ███ ██████ ██████ ███ ███████████████████████████ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███████████████████████████ █████████ █████████ █████████ █████████ █ ██ ██ █ █ ██ ██ █ █ ██ ██ █ █ ██ ██ █ █████████ █████████ █████████ █████████ ███ ███ ███ ███ ███ ███ ███ ███ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ █ ███ ███ ███ ███ ███ ███ ███ ███ █████████ █████████ █████████ █████████ █ ██ ██ █ █ ██ ██ █ █ ██ ██ █ █ ██ ██ █ █████████ █████████ █████████ █████████ ███████████████████████████ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███████████████████████████ ███ ██████ ██████ ███ ███ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ █ █ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ███ ███ ██████ ██████ ███ ███████████████████████████ ███████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ ██ ██ ██ █ ███████████████████████████ ███████████████████████████ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ █████████ ██████████████████ ██████████████████ █████████ █ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ █ █████████ ██████████████████ ██████████████████ █████████ ███ ███ ███ ██████ ███ ███ ██████ ███ ███ ███ █ █ █ █ █ █ █ ██ █ █ █ █ █ █ ██ █ █ █ █ █ █ █ ███ ███ ███ ██████ ███ ███ ██████ ███ ███ ███ █████████ ██████████████████ ██████████████████ █████████ █ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ ██ ██ ██ █ █ ██ ██ █ █████████ ██████████████████ ██████████████████ █████████ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ ██ █ █ █ ███ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ██████ ███ █████████████████████████████████████████████████████████████████████████████████ █ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ ██ █ █████████████████████████████████████████████████████████████████████████████████
Ruby
<lang ruby>def sierpinski_carpet(n)
carpet = ["#"]
n.times do
carpet = carpet.collect {|x| x + x + x} + \
carpet.collect {|x| x + x.tr("#"," ") + x} + \
carpet.collect {|x| x + x + x}
end
carpet.join("\n")
end
puts sierpinski_carpet(3)</lang>
Scala
<lang scala>def nextCarpet(carpet: List[String]): List[String] = (
carpet.map(x => x + x + x) :::
carpet.map(x => x + x.replace('#', ' ') + x) :::
carpet.map(x => x + x + x))
def sierpinskiCarpets(n: Int) = (Iterator.iterate(List("#"))(nextCarpet) drop n next) foreach println</lang>
Scheme
<lang scheme>(define (carpet n)
(define (in-carpet? x y)
(cond ((or (zero? x) (zero? y))
#t)
((and (= 1 (remainder x 3)) (= 1 (remainder y 3)))
#f)
(else
(in-carpet? (quotient x 3) (quotient y 3)))))
(do ((i 0 (+ i 1))) ((not (< i (expt 3 n))))
(do ((j 0 (+ j 1))) ((not (< j (expt 3 n))))
(display (if (in-carpet? i j)
#\*
#\space)))
(newline)))</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func boolean: inCarpet (in var integer: x, in var integer: y) is func
result
var boolean: result is TRUE;
begin
while result and x <> 0 and y <> 0 do
if x rem 3 = 1 and y rem 3 = 1 then
result := FALSE;
else
x := x div 3;
y := y div 3;
end if;
end while;
end func;
const proc: carpet (in integer: n) is func
local
var integer: i is 0;
var integer: j is 0;
begin
for i range 0 to pred(3 ** n) do
for j range 0 to pred(3 ** n) do
if inCarpet(i, j) then
write("#");
else
write(" ");
end if;
end for;
writeln;
end for;
end func;
const proc: main is func
begin carpet(3); 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_carpet n {
set carpet [list "#"]
for {set i 1} {$i <= $n} {incr i} {
set carpet [concat \
[map {x {subst {$x$x$x}}} $carpet] \
[map {x {subst {$x[string map {"#" " "} $x]$x}}} $carpet] \
[map {x {subst {$x$x$x}}} $carpet] \
]
}
return [join $carpet \n]
}
puts [sierpinski_carpet 3]</lang>
Ursala
The carpet function works for any natural number n and is tested on 0,1,2, and 3. The carpet is stored as a list of lists of booleans but converted to characters for display. <lang Ursala>#import std
- import nat
carpet = ~&a^?\<<&>>! (-*<7,5,7>; *=DS ~&K7+ ~&B**DS*=rlDS)^|R/~& predecessor
- show+
test = mat0 ~&?(`#!,` !)*** carpet* <0,1,2,3></lang> output:
# ### # # ### ######### # ## ## # ######### ### ### # # # # ### ### ######### # ## ## # ######### ########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ########################### ######### ######### # ## ## # # ## ## # ######### ######### ### ### ### ### # # # # # # # # ### ### ### ### ######### ######### # ## ## # # ## ## # ######### ######### ########################### # ## ## ## ## ## ## ## ## # ########################### ### ###### ###### ### # # # ## # # ## # # # ### ###### ###### ### ########################### # ## ## ## ## ## ## ## ## # ###########################