# Sierpinski Carpets

Who doesn't love a good fractal? The Sierpinski Carpet is a classic example of a fractal.

To complete this task, you will be required to generate a carpet of type and print the resulting image to the stdout (see example below for formatting) , representing the level carpet. Steps can be found on this Wikipedia article.

This value will be taken from stdin or equivalent.

For example, an input of 4 would produce a level 4 carpet:

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■
■   ■       ■   ■ ■   ■       ■   ■ ■   ■       ■   ■
■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■                   ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■                   ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■                   ■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■       ■ ■ ■                   ■ ■ ■       ■ ■ ■
■   ■       ■   ■                   ■   ■       ■   ■
■ ■ ■       ■ ■ ■                   ■ ■ ■       ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■                   ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■                   ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■                   ■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■
■   ■       ■   ■ ■   ■       ■   ■ ■   ■       ■   ■
■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■ ■ ■ ■       ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■


An input of 3 would produce a level 3 carpet:

■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■       ■ ■ ■
■   ■       ■   ■
■ ■ ■       ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■


An input of 2 would produce a level 2 carpet:

■ ■ ■
■   ■
■ ■ ■


And a input of 1 would produce a level 1 carpet (just a square):

■


Note the spaces between the columns.

The idea is to use the ■ character for blocks and space for gaps

The line starts with the ■ character.

As always, the smallest solution wins by character count (due to non-standard characters).

Alternatively, # can be used instead of the ■ character in languages that do not support Unicode.

• Isn't the first example a third level instead of second ? – Optimizer Oct 21 '14 at 17:26
• Nice question, but do they have to be those characters? those aren't ASCII, which rules out a lot of languages. Can they be just space and X or O? I actually think your image would look better with spaces instead of empty squares. – Level River St Oct 21 '14 at 17:32
• Changed sponge to carpets, thanks. – Paul Clavier Oct 21 '14 at 17:33
• What if your language does not support unicode output, is there also an ASCII alternative? – flawr Oct 21 '14 at 17:35
• Can the lines have trailing spaces? – Dennis Oct 21 '14 at 18:38

## CJam, 38373130 28 characters

Oh well, we're counting by characters, so let's do some Unicode unpacking:

"B胷맋풽巓뱖ᮨ㣙¬䙧੥墱륋청"2G#b129b:c~


Test it here. Just put the desired level into the input field.

### Explanation

After base conversion, this is

3li(#,{3b1f&2b}%_f{f{&S9632c?S}N}


which is the same as the following, just with the Unicode character written as 9632c:

3li(#,{3b1f&2b}%_f{f{&S'■?S}N}


This code is based on the following observation: if we look at the coordinates (x,y) of each cell, then we get an empty cell, whenever both x and y have a 1 at the same position in their base-3 representation. If you think about it, the small-scale repeating pattern is the significant base-3 digit, then the next more significant digit governs the next larger-scale repetition and so on.

3                                      "Push a 3 on the stack.";
li(                                   "Read input, convert to integer, decrement.";
#                                  "Raise to that power. This yields the dimensions.";
,                                 "Turn into a range array.";
{       }%                       "Map the block onto the array.";
3b                              "Convert to base 3.";
1f&                           "Bit-wise AND each digit with 1.";
2b                         "Convert to base 2.";
_                      "Duplicate this list.";
f{          }         "Map this block onto one list, with the second list
f{      }           "Map this block onto the second list, with the first
list's current element as an additional parameter.";
"I.e. this iterates over all coordinate pairs.";
&                 "Bitwise AND to check that the base-3 representations
had a 1 in the same position.";
S'■?             "Select the right character.";
S            "Push a space.";
N          "Push a newline";


The contents of the resulting array are printed automatically.

Thanks to Dennis for shaving off three bytes.

• #0<'■S -> #~S'■ saves 1 character. – Optimizer Oct 21 '14 at 19:46
• You can replace [1_]a#~ with 3Yba&. – Dennis Oct 21 '14 at 22:49
• @Dennis neat. thank you! – Martin Ender Oct 21 '14 at 22:50
• @Dennis I keep forgetting that & produces a truthy/falsy value (or even that it exists). Might be worth a post in the CJam tips for the canonical way to test whether an array contains some element. – Martin Ender Oct 21 '14 at 22:58
• @Ypnypn Nope. It looks longer but that's because the Unicode characters aren't monospaces. The unpacked code has 30 characters. – Martin Ender Oct 23 '14 at 21:43

# Matlab (113)(110)(99)(85)

You can try it here (You'll have to replace input('') with your desired input.)

Now 99 thanks to feersum! And now down to 85 thanks to RTL!

Golfed:

a=ones(3);a(5)=0;c=1;for i=2:input('');c=kron(c,a);end;disp(char(kron(c,[1,0])*3+32))


Ungolfed:

a=ones(3);a(5)=0;c=1;  %creating the template / anchor
for i=2:input('');
c=kron(c,a);       %recursive iterations
end;
disp(char(kron(c,[1,0])*3+32))


d=[c,c]*0;  %this is all just for adding the additional spaces
d(:,1:2:end)=c;
disp(char(d*3+32));    %converting to spaces (32) and # (35)


Explanation:

I am abusing the kronecker product for this task. (It is a special product defined for two each arbitrary sized matrices. Example:

A = [1,2] is a 3x2 matrix, B is a nxm matrix.
[3,4]
[5,6]


Then

kron(A,B) = [1*B , 2*B] is a 2n x 2m matrix.
[3*B , 4*B]
[5*B , 6*B]


So heres an example for n=5 (In the old counting method it's 4);

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
# # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # #
#   #       #   #                   #   #       #   # #   #       #   #                   #   #       #   # #   #       #   #                   #   #       #   #
# # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #                                                       #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # #                                                       # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   #                                                       #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # #                                                       # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #                                                       #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #                   # # # # # # # # #                                                       # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   #                                                       #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # #                                                       # # # # # # # # #                   # # # # # # # # #
# # #       # # #                   # # #       # # #                                                       # # #       # # #                   # # #       # # #
#   #       #   #                   #   #       #   #                                                       #   #       #   #                   #   #       #   #
# # #       # # #                   # # #       # # #                                                       # # #       # # #                   # # #       # # #
# # # # # # # # #                   # # # # # # # # #                                                       # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   #                                                       #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # #                                                       # # # # # # # # #                   # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #                                                       #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # #                                                       # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   #                                                       #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # #                                                       # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   #                                                       #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # #                                                       # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
# # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # #
#   #       #   #                   #   #       #   # #   #       #   #                   #   #       #   # #   #       #   #                   #   #       #   #
# # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # # # # #       # # #                   # # #       # # #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
#   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   # #   # #   # #   #                   #   # #   # #   #
# # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # # # # # # # # # # #                   # # # # # # # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
#   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   # #   #       #   #
# # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # # # # #       # # #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
#   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   # #   #
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #

• Thanks, I didn't notice that the requirements changed. I also updated the code (I just had to change the starting value of the for loop.) – flawr Oct 21 '14 at 18:32
• Instead of d=zeros(size([c,c])) you should use d=[c c]*0. – feersum Oct 21 '14 at 19:48
• nice, a suggestion: the variable d can be avoided by abusing kron once more: disp(char(kron(c,[1,0])*3+32));, – RTL Oct 23 '14 at 10:28

s 1=["# "]
s n=k j++k(map(>>" ")j)++k j where j=s$n-1;k i=j%i%j (%)=zipWith(++) main=interact$unlines.s.read


# Perl 5: 68 characters

n on stdin.

#!/usr/bin/perl -l
//,print map/2/?"  ":"■ ",map$_+$',@,for@,=grep!/[24-9]/,0..3x<>/10


A decimal coded ternary representation of the list of coordinates is first generated in @, (name chosen so there is no need for space between @, and for) using digits 0, 1, and 3. Now adding x and y coordinates in the decimal domain will have a 2 in the result if and only if there were two ones at matching positions. // is used to propagate the default variable $_ from the outer loop (for) to the postmatch variable $' when it is shadowed by the default map variable in the inner loop.

# Python – 100

r=range(3**~-input())
for i in r:print" ".join("# "[any(i/3**k%3==j/3**k%3==1for k in r)]for j in r)


# Java, 330 283 Characters

class T{public static void main(String[]a){int n=Integer.valueOf(a[0]);int m=(int)Math.pow(3,n-1);for(n=0;n<m;n++){for(int j=0;j<m;){String s="#";int x=n;int y=j++;while(x>0||y>0){if(x%3==1&&y%3==1){s=" ";}x/=3;y/=3;}p(s);}p("\n");}}static void p(String s){System.out.print(""+s);}}


Param is the size you want. Unless there's an optimization for the algorithm, I tried squishing everything down.

Thanks to @StretchManiac removing the i method and cleaning up the declarations squished a fair bit down.

class T {
public static void main(String[] a) {
int n = Integer.valueOf(a[0]);
int m = (int) Math.pow(3, n - 1);
for (n = 0; n < m; n++) {
for (int j = 0; j < m;) {
String s = "#";
int x = n;
int y = j++;
while (x > 0 || y > 0) {
if (x % 3 == 1 && y % 3 == 1) {
s = " ";
}
x /= 3;
y /= 3;
}
p(s);
}
p("\n");
}
}

static void p(String s) {
System.out.print("" + s);
}
}

• You can get rid of "public" before class, as main arg you can do String[]a, and if you are only using i once, then you would be better off getting rid of the method. – Stretch Maniac Oct 21 '14 at 20:15
• @StretchManiac thanks for the tips. I'll implement them in a bit. – Compass Oct 21 '14 at 20:17
• Why on earth do you do ""+s in your p method? That's three extra characters for absolutely no purpose. Even if the type of s were anything besides String, it would still be completely unnecessary. – David Conrad Oct 21 '14 at 20:48
• Change it to static void p(int s){System.out.print((char)s);} and in main make it int s=35;, s=32;, and p(10); (instead of p("\n");) and save a few more characters. – David Conrad Oct 21 '14 at 21:05
• You can save seven characters by changing Integer.valueOf to new Byte – Ypnypn Oct 23 '14 at 21:44

# Racket 230229225 220

Not Racket's finest hour for golfing.

Golfed:

(define(s n)(letrec([t(λ(x y)(if(or(= x 0)(= y 0))"■"(if(=(modulo x 3)(modulo y 3)1)" "(t(floor(/ x 3))(floor(/ y 3))))))][i(expt 3(- n 1))])(for-each displayln(for/list([r i])(string-join(for/list([c i])(t r c))" ")))))


Ungolfed:

(define (s n)
(letrec ([t (λ (x y)
(if (or (= x 0) (= y 0))
"■"
(if (= (modulo x 3) (modulo y 3) 1)
" "
(t (floor (/ x 3)) (floor (/ y 3))))))]
[i (expt 3 (- n 1))])
(for-each displayln
(for/list ([r i])
(string-join
(for/list ([c i])
(t r c)) " ")))))


# C: 123 118 111 104 characters

Based on a similar idea as my perl solution. After adding some spaces:

m=0x55555555;
x;
main(n){
scanf("%d",&n);
n=1<<2*--n;
for(x=n*n;x--;)
printf(x&x/2&m?"":"%c%c",x&x/n&m?32:35,x&n-1?32:10);
}


Uses ternary system coding each digit with 2 bits. Illegal values (having two ones in odd-even position) are filtered with x & (x>>1) & 0b01010101. Both coordinates are stored in one value, so checking the pixel color is down to x & (x >> 2 * n) & 0b01010101. n is stored as a power of 2 for convenience.

## Edit

Replaced define with a simple constant m.

## Edit 2

0x5555555 mask can be represented with (1LL<<32)/3, but we only need n of those bits so n/3 is sufficient.

x;
main(n){
scanf("%d",&n);
n=1<<2*--n;
for(x=n*n;x--;)
printf(x&x/2&n*n/3?"":"%c%c",x&x/n&n/3?32:35,x&n-1?32:10);
}


## Edit 3

Minor tweaks. One 2 char gain relying on scanf being executed before the loading value of n for the execution of --n. The eol can only follow #, duh.

x;
main(n){
n=scanf("%d",&n)<<2*--n;
for(x=n*n;x--;)
x&x/2&n*n/3||printf(x&x/n&n/3?"  ":x&n-1?"# ":"#\n");
}


# HTML/JavaScript, 205 Chars

## Obfuscatweet, 205 Chars

document.write(unescape(escape('🁳𨱲𪑰𭀾𬰽𙰦𫡢𬱰𞰧𞱮🐴𞱭👍𨑴𪀮𬁯𭰨𜰬𫠭𜐩𞱦𫱲𚁩🐰𞱩🁭𞱩𚰫𛁤𚀧🁢𬠾𙰩𚑻𩡯𬠨𪠽𜀻𪠼𫐻𚑩𩠨𨰨𪐬𪠫𚰩𚑤𚀧𘰧𚐻𩑬𬱥𘁤𚁳𚑽𩡵𫡣𭁩𫱮𘁣𚁸𛁹𚑻𭱨𪑬𩐨𮁼𯁹𚑻𪑦𚁸𙐳🐽𜐦𙡹𙐳🐽𜐩𬡥𭁵𬡮𘀰𞱸👦𚁸𚐻𮐽𩠨𮐩𯑲𩑴𭑲𫠠𜑽𩡵𫡣𭁩𫱮𘁦𚁡𚑻𬡥𭁵𬡮𘁍𨑴𪀮𩡬𫱯𬠨𨐯𜰩𯑦𭑮𨱴𪑯𫠠𩀨𨐩𮱤𫱣𭑭𩑮𭀮𭱲𪑴𩐨𬰫𨐩𯐼𛱳𨱲𪑰𭀾🁳𭁹𫁥🠪𮱦𫱮𭀭𩡡𫑩𫁹𞠢𠱯𭑲𪑥𬠢').replace(/uD./g,'')))


## HTML/JS, 298 Chars

Due to how HTML plays with whitespace, a few characters had to be dedicated to the nbsp char. In addition, the default font of most browsers is not Courier, so I had to set it to that, too. About 20 characters worth of styling. If this requires a direct input method, I can add it, but changing the input currently is setting n to a different value.

Demo

<script>s='&nbsp;';n=4;m=Math.pow(3,n-1);for(i=0;i<m;i++,d('<br>')){for(j=0;j<m;)if(c(i,j++))d('#');else d(s)}function c(x,y){while(x||y){if(x%3==1&&y%3==1)return 0;x=f(x);y=f(y)}return 1}function f(a){return Math.floor(a/3)}function d(a){document.write(s+a)}</script><style>*{font-family:"Courier"


<script>
s='&nbsp;';
n=4;
m=Math.pow(3,n-1);
for(i=0;i<m;i++,d('<br>')){
for(j=0;j<m;)
if(c(i,j++))
d('#');
else d(s)
}
function c(x,y){
while(x||y){
if(x%3==1&&y%3==1)
return 0;
x=f(x);
y=f(y)
}
return 1
}
function f(a){
return Math.floor(a/3)
}
function d(a){
document.write(s+a)
}
</script>
<style>
*{font-family:"Courier"


# CJam, 383532 31 characters

"■ ""՛ୗ䁎뽔휼ꆩ闳⾿➺⥧槲㩡郊"6e4b128b:c~


Try it online.

$cjam <(echo '"■ ""՛ୗ䁎뽔휼ꆩ闳⾿➺⥧槲㩡郊"6e4b128b:c~') <<< 3; echo ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■  ### How it works "՛ୗ䁎뽔휼ꆩ闳⾿➺⥧槲㩡郊"6e4b128b:c~  converts the Unicode string from base 60,000 (6e4b) to base 128 (128b), casts to Character (:c) and evaluates the resulting string (~). As a result, the following code gets executed: "■ " " C := '■ ' "; li( " J := int(input()) - 1 "; { }* " for I in range(J): "; z]A* " T := [zip(C)] * 10 "; ):, " U := pop(T) "; Sf* " V := [ ' ' * len(u) : u ∊ U ] "; 4\t " U[4] := V "; 3/{:+z~}% " C := { c : c ∊ zip(concat(u)), u ∊ U.split(3) } "; zN* " print '\n'.join(zip(C)) ";  # Python 3 – 116 113 characters EDIT: Well, used the trick I don't like too much myself and compressed the code by 3 bytes. Dunno if that's the best possible way, but I'll go with it. exec(bytes('ⱴ㵬❛離₠崧氬浡摢⁡㩺癥污稨✫⁫潦⁲⁫湩琠❝਩潦⁲⁩湩爠湡敧椨瑮椨灮瑵⤨⴩⤱爺瀬氽✨㍛✪Ⱙ⡬嬢⭫‧✠⠪⨳椪⬩⤢琻爽瀫爫昊牯椠椠⁮㩴牰湩⡴⥩','utf-16')[2:].decode('utf-8'))  It may contain some unprintable characters, so here's a printable version of the string. 'ⱴ㵬❛離₠崧氬浡摢\u2061㩺癥污稨✫\u206b潦\u2072\u206b湩琠❝\u0a29潦\u2072\u2069湩爠湡敧椨瑮椨灮瑵⤨\u2d29⤱爺瀬氽✨㍛✪Ⱙ⡬嬢\u2b6b‧✠⠪⨳椪⬩⤢琻爽瀫爫昊牯椠椠\u206e㩴牰湩⡴⥩'  Not too great, but at least beats some languages. What it expands to: t=['■ '] for i in range(int(input())-1):r,p=[k*3for k in t],[k+' '*(3**i)+k for k in t];t=r+p+r for i in t:print(i)  Somewhat ungolfed in case someone can't see how it works: t=['■ '] # iteration 1 for i in range(int(input()) - 1): # do n-1 more iterations r = [k * 3 for k in t] # first & last rows are the last carpet x3 p = [k + ' ' * (3 ** i) + k for k in t] # middle row: last carpet, space, last carpet t = r + p + r # and put them to the new carpet for i in t: # print final iteration print(i)  • Wow python, that's impressive – Paul Clavier Oct 22 '14 at 11:13 # Mathematica, 71 bytes Grid@Nest[ArrayFlatten@ArrayPad[{{0}},1,{{#}}]&,1,#]/.{0->"",1->"■"}&  input 3 output • I followed you like a total creeper. +1 ;). – Magic Octopus Urn Jun 13 '17 at 22:17 • Do you think you can shorten this with SubstitutionSystem ? – Vitaliy Kaurov Sep 26 '17 at 16:57 ## CJam, 76 characters 3ri(#:M_*,{_M/:I\M%:J;;{I3%1=J3%1=&0X?:X;I3/:I0>J3/:J0>|}gX'■S?1:X;}%M/Sf*N*  This is a direct translation of the formula given here Try it here # Bash+coreutils, 105 unicode characters Since we're counting characters and not bytes: eval iconv -tunicode<<<潦⡲眨㌽⨪␨ⴱ⤱琬〽琻眼眪琻⬫⤩笻戠ꂖ昻牯⠨㵸╴ⱷ㵹⽴㭷㹸簰祼〾砻㴯ⰳ⽹㌽⤩笻⠠砨㌥ㄭ籼╹ⴳ⤱簩扼尽簠硼〽紻瀻楲瑮⁦␢⁢㬢⠨╴⵷⭷⤱簩敼档㭯੽|cut -b3-  In its decoded form: # Pure Bash, 143 bytes for((w=3**($1-1),t=0;t<w*w;t++));{
b=■
for((x=t%w,y=t/w;x>0||y>0;x/=3,y/=3));{
((x%3-1||y%3-1))||b=\ ||x=0
}
printf "$b " ((t%w-w+1))||echo }  Input is taken from command-line args: ### Output: $ ./sierpinskicarpet.sh 3
■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■
■ ■ ■       ■ ■ ■
■   ■       ■   ■
■ ■ ■       ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ■ ■
■   ■ ■   ■ ■   ■
■ ■ ■ ■ ■ ■ ■ ■ ■
$ ## C# Full program - 237: using System;class P{static void Main(string[] a){int b=(int)Math.Pow(3,int.Parse(a[0])-1),c,d,e,f;for(c=0;c<b;c++){var g="";for(d=0;d<b;){var h="■";e=c;f=d++;while(e>0|f>0){h=e%3==1&f%3==1?" ":h;e/=3;f/=3;}g+=h;}Console.WriteLine(g);}}}  LINQPad - 166 + Math.Ceiling(Math.Log(a + 1) / Math.Log(10)) int a=3;int b=(int)Math.Pow(3,a-1),c,d,e,f;for(c=0;c<b;c++){var g="";for(d=0;d<b;){var h="■";e=c;f=d++;while(e>0|f>0){h=e%3==1&f%3==1?" ":h;e/=3;f/=3;}g+=h;}g.Dump();}  # C - 154 Input from stdin. I tried to find a good way to avoid an extra function, but couldn't come up with any. The character count includes only necessary spaces. p(l,x,y){ return l?x/l&y/l&1||p(l/3,x%l,y%l):0; } x,y; main(v){ scanf("%d",&v); v=pow(3,--v); for(;y<v;y++,puts("")) for(x=0;x<v;) printf("%c ",p(v,x++,y)?32:35); }  # PHP, 194 characters The n received as first argument in command line. <?php function d(&$a,$n,$e,$x,$y){if(--$n)for(;$i<9;)$p=pow(3,$n)|d($a,$n,$e|$i==4,$x+$p*$j,$y+$p*($i-$j)/3)|$j=++$i%3;else$a[$x][$y]=$e?" ":■;}@d($a,$argv[1]);foreach($a as$s)echo join($s),"
";


<?php

function draw(&$array,$n, $empty,$x, $y) {$n--;
if ($n != 0) { for ($i = 0; $i < 9;$i++) {
$j =$i % 3;
$p = pow(3,$n);
draw($array,$n, $empty ||$i == 4, $x +$p * $j,$y + $p * ($i - $j) / 3); } } else {$array[$x][$y] = $empty ? " " : "#"; } }$array = array();
draw($array,$argv[1], false, 0, 0);
foreach ($array as$line) {
echo join(\$line), "\n";
}

• If you use the char ■ instead of #, you can save 2 chars by removing the quotes. – Ismael Miguel Oct 22 '14 at 8:48

Scala 230 characters

Golfed code:

object T extends App {def m=math.pow(3,args(0).toInt-1).toInt-1;def p=print _;val x=0 to m;x.map{n=>x.map{j=>if(q(n,j)==1)p(" #");else p("  ")};p("\n");};def q(n:Int,j:Int):Int={if(n>0|j>0)if((n%3&j%3)==1)0 else q(n/3,j/3)else 1}}


Ungolfed code:

object T extends App {
def m = math.pow(3, args(0).toInt - 1).toInt - 1;

def p = print _;
val x = 0 to m;
x.map { n => x.map { j => if (q(n, j) == 1) p(" #"); else p("  ")}; p("\n");};

def q(n: Int, j: Int): Int = {
if (n > 0 | j > 0) if ((n % 3 & j % 3) == 1) 0 else q(n / 3, j / 3) else 1
}
}


Only necessary spaces are included.

# V, 21 bytes (non-competing)

é*Àñ}yPgvr PGï3pyGHP


Try it online!

Hexdump:

00000000: e92a c0f1 167d 7950 6776 7220 5047 ef33  .*...}yPgvr PG.3
00000010: 7079 4748 50                             pyGHP


V is newer than the challenge, so it must be marked as non-competing. But still, it's nice to see this answer being waaaaay shorter than all the other ones, even when counting in bytes rather than characters.

• Just a reminder; it's no longer non-competing – RedClover Mar 10 '18 at 18:47

# oK, 40 bytes

0:" #"{(x-1)(,'//3 3#111101111b*9#,)/1}


Try it online.

It starts with 1, and then draws it in a grid (1 1 1;1 0 1;1 1 1), which it then draws in a grid the same way, etc. repeated the necessary number of times.

# SOGL V0.12, 27 bytes

 ■¹.H{³³┼┼≥: ■@ŗ;┼┼⁴++}{@∑P


Try it Here!

# Python 2, 91 bytes

r=input()-1
for i in range(3**r):x,s='# ','  ';exec"x+=[x,s][i%3%2]+x;s*=3;i/=3;"*r;print x


Try it online!

# C# (.NET Core), 162 bytes

n=>{var f="";int s=(int)Math.Pow(3,n),z=0;while(z<s*s){int x=z%s,y=z/s,h=1;for(;x>0|y>0;y/=3,x/=3)if(y%3==1&x%3==1)h=0;f+=" #"[h]+(z++%s<s-1?" ":"\n");}return f;}


Try it online!

### Degolfed

n=>{
var f="";
int s=(int)Math.Pow(3,n),z=0;

while(z<s*s)
{
int x=z%s, y=z/s, h=1;
for(; x>0 | y>0; y/=3, x/=3)
if(y%3==1 & x%3==1)
h=0;

f += " #"[h] + (z++%s<s-1? " " : "\n");
}

return f;
}


# K (ngn/k), 50 49 bytes

thanks @DLosc for reminding me I should output spaces between the columns

thanks @coltim for -1 byte

1@"\n"/("# "1_,/1,'+/')'a*/:\:a:+2!!1_(. 0:"")#3;


Try it online!

• @DLosc thanks, fixed other strange requirements too: stdin/stdout instead of arg/result; off-by-one "level" – ngn May 17 '18 at 21:50
• I think you can drop a byte by using ("# "1_,/1,'+/')' instead of "# "1_',/'1,''+/'' – coltim Dec 17 '20 at 15:17
• @coltim thank you! – ngn Dec 17 '20 at 20:10

# R, 92 characters

94 bytes with the special character.

write(c(" ","■")[1+Reduce("%x%",rep(list(matrix(c(1,1,1,1,0,1),3,3)),n<-scan()-1),1)],1,3^n)


Try it online!

• I'm just amazed people are still doing this 4 years later – Paul Clavier Mar 12 '18 at 20:10
• @PaulClavier it's a great challenge; you should be proud :) – Giuseppe Mar 12 '18 at 20:10

## Canvas, 1716 17 characters

■；╷［⌐ ＋２×；┌∔∔；３＊＋


Try it here!

-1: Used ［ instead of ｛ to delete the first ； inside the loop.
+1: Fixed errenous behavior: ■ now corresponds to level 1, as specified in the original post.

• It is competing, per a newer consensus. – Erik the Outgolfer Mar 10 '18 at 13:58
• @EriktheOutgolfer oh, thanks for letting me know! – hakr14 Mar 10 '18 at 18:39
• And yes, in this case the score is 17, but we count solutions in bytes, not characters (Canvas has a code page). – Erik the Outgolfer Mar 10 '18 at 18:40
• @EriktheOutgolfer normally yes, but this challenge uses characters, due to ■ being multibyte. Says so toward the bottom in the original post. – hakr14 Mar 10 '18 at 18:45
• You need to add one to all your inputs. 1 should return a square (i.e. what 0 returns here) – Paul Clavier Mar 12 '18 at 20:14

# Pip-S, 30 characters

"■■ "@MX{{aTB3R2i}MSg}MC3**a/3


Try it online!

The basic idea: consider a coordinate grid in base 3. The holes in the carpet occur where 1) a trit in the x-coordinate is 1, and 2) the trit in the same position in the y-coordinate is also 1.

"■■ "@MX{{aTB3R2i}MSg}MC3**a/3
i is 0; a is 1st cmdline arg (implicit)
3**a/3  Width/height of the carpet
MC        Make a coordinate grid that size and map this function
to the coordinate pairs:
g            Take each [x y] pair
MS             Map this function to each coord and add the results:
{aTB3   }                Convert to base 3
R2i                 Replace 2's with 0's
E.g. 15 -> 120 -> 100 and 16 -> 121 -> 101
When we add the results, we get [15 16] -> 201
MX{            }           Take the max of that list (0, 1, or 2)
"■■ "@                           Use that to index into this string (resulting in a space
iff two 1's coincided to make a 2, or ■ otherwise)
Print the resulting nested list with each sublist on its
own line and space-delimited (implicit, -S flag)


Similar solution, same number of characters but -2 bytes: {2N({aTB3R2i}MSg)?s'■}MC3**a/3

# J, 35 bytes

' #'{~]9&([:,/_3,./\0"+4}(#,:)),:@1


Try it online!

# Jelly, 17 bytes

’3*Ḷb3ḂḄ&þ¬ị⁾# G


Try it online!

### How?

’3*Ḷb3ḂḄ&þ¬ị⁾# G - Link: integer, n
’                 - decrement -> n-1
3*               - three raised to (that)
Ḷ              - lowered range -> [0,1,...,3^(n-1)-1]
b3            - convert to base three (vectorises)
Ḃ           - least significant bit (vectorises) -> i.e. make 2 trits become 0s
Ḅ          - convert from base two (vectorises)
- use that as both arguments of:
þ        -   outer product with:
&         -     bitwise AND
¬      - logical NOT (vectorises)
ị     - index into:
⁾#   -   list of characters ['#', ' ']
G - format as a grid


# Husk, 23 bytes

´Ṫȯ!"□ "¬nmḋ†%2mB3ŀ^3←
`

Try it online!

Translation of Jonathan Allan's program.

uses the '□' character.