Sierpinski Carpets

23

2

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 n and print the resulting image to the stdout (see example below for formatting) n, 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.

Paul Clavier

Posted 2014-10-21T17:19:36.507

Reputation: 335

1Isn't the first example a third level instead of second ? – Optimizer – 2014-10-21T17:26:58.083

6Nice 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 – 2014-10-21T17:32:22.793

Changed sponge to carpets, thanks. – Paul Clavier – 2014-10-21T17:33:54.900

What if your language does not support unicode output, is there also an ASCII alternative? – flawr – 2014-10-21T17:35:39.550

@steveverrill Good idea, I'll specify # and spaces as an alternative. – Paul Clavier – 2014-10-21T17:36:14.123

Okay, I've specified a ASCII alternative as #, and replaced the white square with a space. – Paul Clavier – 2014-10-21T17:39:56.503

@steveverrill Good catch, added level 3. – Paul Clavier – 2014-10-21T17:45:53.990

1Can the lines have trailing spaces? – Dennis – 2014-10-21T18:38:58.257

Answers

15

CJam, 38 37 31 30 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
                                        as an additional parameter.";
                   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.

Martin Ender

Posted 2014-10-21T17:19:36.507

Reputation: 184 808

2#0<'■S -> #~S'■ saves 1 character. – Optimizer – 2014-10-21T19:46:26.143

You can replace [1_]a#~ with 3Yba&. – Dennis – 2014-10-21T22:49:01.030

@Dennis neat. thank you! – Martin Ender – 2014-10-21T22:50:01.887

@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 – 2014-10-21T22:58:25.480

Man, also post more insights on the base conversions and tricks to it :) – Optimizer – 2014-10-21T23:15:49.353

Should save two chars: 3li(#,{3b1f&4b}%_f{f{&S9632c?S}N} – Dennis – 2014-10-22T04:30:06.687

@Dennis Thanks! The f{f{...}} is a really nice idea. :) – Martin Ender – 2014-10-22T10:25:59.577

Doesn't the Unicode trick use more characters in this case? – Ypnypn – 2014-10-23T21:42:01.723

1@Ypnypn Nope. It looks longer but that's because the Unicode characters aren't monospaces. The unpacked code has 30 characters. – Martin Ender – 2014-10-23T21:43:39.027

7

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

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

flawr

Posted 2014-10-21T17:19:36.507

Reputation: 40 560

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 – 2014-10-21T18:32:18.787

Instead of d=zeros(size([c,c])) you should use d=[c c]*0. – feersum – 2014-10-21T19:48:15.523

nice, a suggestion: the variable d can be avoided by abusing kron once more: disp(char(kron(c,[1,0])*3+32));, – RTL – 2014-10-23T10:28:54.150

6

Haskell, 114 108

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

proud haskeller

Posted 2014-10-21T17:19:36.507

Reputation: 5 866

5

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.

nutki

Posted 2014-10-21T17:19:36.507

Reputation: 3 634

5

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)

Wrzlprmft

Posted 2014-10-21T17:19:36.507

Reputation: 2 772

4

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.

Readable Code

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);
    }
}

Compass

Posted 2014-10-21T17:19:36.507

Reputation: 393

I know it's been almost three years, but you can still golf quite a bit: class T{public static void main(String[]a){for(int m=(int)Math.pow(3,new Long(a[0])-1),n=-1,j,x,y;++n<m;p("\n"))for(j=0;j<m;){String s="#";for(x=n,y=j++;x>0|y>0;x/=3,y/=3)s=x%3==1&y%3==1?" ":s;p(s);}}static<T>void p(T s){System.out.print(s);}} (243 bytes) Less int by combining them; less brackets by putting everything inside the loops; and static void p(String s){System.out.print(""+s);} to static<T>void p(T s){System.out.print(s);}; changing && and || to & and |; etc. – Kevin Cruijssen – 2017-09-26T12:20:47.127

Or even shorter by not having a separated print method and no for-loop brackets at all anymore: class T{public static void main(String[]a){String r,s;for(int m=(int)Math.pow(3,new Long(a[0])-1),n=-1,j,x,y;++n<m;System.out.println(r))for(r="",j=0;j<m;r+=s)for(s="#",x=n,y=j++;x>0|y>0;x/=3,y/=3)s=x%3==1&y%3==1?" ":s;}} (221 bytes)

– Kevin Cruijssen – 2017-09-26T13:20:03.757

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 – 2014-10-21T20:15:28.023

@StretchManiac thanks for the tips. I'll implement them in a bit. – Compass – 2014-10-21T20:17:17.940

3Why 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 – 2014-10-21T20:48:00.750

1Change 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 – 2014-10-21T21:05:44.617

You can save seven characters by changing Integer.valueOf to new Byte – Ypnypn – 2014-10-23T21:44:17.807

4

Racket 230 229 225 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)) " ")))))

Matthew Butterick

Posted 2014-10-21T17:19:36.507

Reputation: 401

4

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");
}

nutki

Posted 2014-10-21T17:19:36.507

Reputation: 3 634

3

Mathematica, 71 bytes

Grid@Nest[ArrayFlatten@ArrayPad[{{0}},1,{{#}}]&,1,#]/.{0->"",1->"■"}&

input

3

output

enter image description here

J42161217

Posted 2014-10-21T17:19:36.507

Reputation: 15 931

I followed you like a total creeper. +1 ;). – Magic Octopus Urn – 2017-06-13T22:17:03.960

Do you think you can shorten this with SubstitutionSystem ?

– Vitaliy Kaurov – 2017-09-26T16:57:30.507

3

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"

Readable HTML/JS

<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"

Compass

Posted 2014-10-21T17:19:36.507

Reputation: 393

3

CJam, 38 35 32 31 characters

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

Try it online.

Example run

$ 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))                              ";

Dennis

Posted 2014-10-21T17:19:36.507

Reputation: 196 637

3

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)

PurkkaKoodari

Posted 2014-10-21T17:19:36.507

Reputation: 16 699

Wow python, that's impressive – Paul Clavier – 2014-10-22T11:13:12.417

2

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

Optimizer

Posted 2014-10-21T17:19:36.507

Reputation: 25 836

2

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);
}

Allbeert

Posted 2014-10-21T17:19:36.507

Reputation: 489

2

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
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■   ■ ■   ■ ■   ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■ ■ ■       ■ ■ ■ 
■   ■       ■   ■ 
■ ■ ■       ■ ■ ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■   ■ ■   ■ ■   ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
$

Digital Trauma

Posted 2014-10-21T17:19:36.507

Reputation: 64 644

2

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

William Barbosa

Posted 2014-10-21T17:19:36.507

Reputation: 3 269

I know it's been almost three years, but you can golf a few things like this: using System;class P{static void Main(string[]a){string g,h;for(int b=(int)Math.Pow(3,int.Parse(a[0])-1),c=-1,d,e,f;++c<b;Console.WriteLine(g))for(g="",d=0;d<b;g+=h)for(h="■",e=c,f=d++;e>0|f>0;e/=3,f/=3)h=e%3==1&f%3==1?" ":h;}} (229 bytes / 227 characters) (■ = 3 bytes, so you could replace it with # to save 2 bytes as well). I mainly placed everything inside the for-loops so there is no need for brackets anymore.

– Kevin Cruijssen – 2017-09-26T13:23:58.730

1

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.

James

Posted 2014-10-21T17:19:36.507

Reputation: 54 537

Just a reminder; it's no longer non-competing – RedClover – 2018-03-10T18:47:54.127

1

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.

zgrep

Posted 2014-10-21T17:19:36.507

Reputation: 1 291

1

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!

xnor

Posted 2014-10-21T17:19:36.507

Reputation: 115 687

1

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;
}

Ayb4btu

Posted 2014-10-21T17:19:36.507

Reputation: 541

1

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),"
";

Readable

<?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";
}

Gedrox

Posted 2014-10-21T17:19:36.507

Reputation: 111

1If you use the char ■ instead of #, you can save 2 chars by removing the quotes. – Ismael Miguel – 2014-10-22T08:48:07.167

1

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.

Mathill

Posted 2014-10-21T17:19:36.507

Reputation: 11

0

SOGL V0.12, 27 bytes

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

Try it Here!

dzaima

Posted 2014-10-21T17:19:36.507

Reputation: 19 048

0

Canvas, 17 16 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.

hakr14

Posted 2014-10-21T17:19:36.507

Reputation: 1 295

It is competing, per a newer consensus. – Erik the Outgolfer – 2018-03-10T13:58:46.877

@EriktheOutgolfer oh, thanks for letting me know! – hakr14 – 2018-03-10T18:39:45.367

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 – 2018-03-10T18:40:23.037

@EriktheOutgolfer normally yes, but this challenge uses characters, due to ■ being multibyte. Says so toward the bottom in the original post. – hakr14 – 2018-03-10T18:45:30.087

You need to add one to all your inputs. 1 should return a square (i.e. what 0 returns here) – Paul Clavier – 2018-03-12T20:14:16.010

@PaulClavier ah, ok, it's been fixed. – hakr14 – 2018-03-13T21:53:27.593

0

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!

Giuseppe

Posted 2014-10-21T17:19:36.507

Reputation: 21 077

I'm just amazed people are still doing this 4 years later – Paul Clavier – 2018-03-12T20:10:09.983

1@PaulClavier it's a great challenge; you should be proud :) – Giuseppe – 2018-03-12T20:10:43.700

0

K (ngn/k), 50 bytes

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

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

Try it online!

ngn

Posted 2014-10-21T17:19:36.507

Reputation: 11 449

@DLosc thanks, fixed other strange requirements too: stdin/stdout instead of arg/result; off-by-one "level" – ngn – 2018-05-17T21:50:55.563

0

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

DLosc

Posted 2014-10-21T17:19:36.507

Reputation: 21 213

Asked: 2014-10-21T17:19:36.507

Viewed: 4 026 times

Active: 2018-05-17T21:48:51.150