text:
Approximated (unsorted) square from a set of values
So a colleaque came with this problem lately and I want to challange you to solve the problem in the code-golf style, shortest solution in any language wins.
The Problem:
Given is a random set of values, where the values themselfs are
not the concern, but the amount (which is random as well)of values.
To keep the posts readable, let's limit the amount of values to 200, but the program must be able to handly any amount of values, which the language supports.
Input:
No Input needet, due the programm should set an random amount of values (limited to 200).
Output:
Can be text or graphic(px)
I recommend to use single digits as values if you use text based output, to keep the output clear.
Example:
{1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7}   -- Amount : 16

Now you should sort these values in a approcimated square matrix like:
1 2 3 4
5 6 7 8
9 1 2 3
4 5 6 7
(4 x 4)

Pretty simple so far, if not boring.
But now the challange:
The number of fields in the matrix must be equivalent to the amount of values given.
No empty fields or ignored values are allowed.
As an example, with 12 values, an square matrix is not possible, so you have to find the next aproximitation to it, which is 3x4 or 4x3 but NOT 4x4.
For any prime, the matrix would be 1 x prime
Examples:
For 12 Values:
1 2 3 4
5 6 7 8
9 1 2 3
X X X X   <- NOT ALLOWED, it makes the matrix square, but inserts non existing values.

or
1 2 3
4 5 6
7 8 9
1 2 3

For 35 Values:
1 2 3 4 5 6 7
8 9 1 2 3 4 5
6 7 8 9 1 2 3
4 5 6 7 8 9 1
2 3 4 5 6 7 8

You should give more details about the values. Are they continues ? How is {1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7} sorted ? How does the input look like ? What are the ways of input.

As I already wrote, the're not sorted and the values themself are not the concern. You could use strings as well, if you want to.

Can you improve your examples by properly stating what is input and what is output ?

Is the question "Find the factor of a natural number which is closest to its square root?" or is there more to it than that? It's tagged [tag:sorting] but the title implies that there's no need to sort. I am confused.

Basicly no, but I don't think we always have to do brain-breaking gigaquests.

@Sempie Not sure what you mean by "no input needed". Do you just mean the input should be hardcoded into the program?

What do you need input for? Both, amount of values and values should be random.

What is the point of the values if they aren't used? X's would serve just as well.

@Sempie Ah I see. I somehow read "random" as "arbitrary".

Uhm yeah indeed. This quest is a job my colleage had to solve, where the values had been a concern. You're right, here they're not.

Side-Question: I noticed that an algorithm to solve this problem will find primes. Is there actual a better way to find primes?

If the program defines the list itself, it could simply print an arbitrary valid result without bothering about the input. I could always argue, the output corresponds to the random (non existing) input, the program thought of.

Well if you want this challenge to survive it would be best to rephrase is without the values. They distract from the main goal which as PeterTaylor said is simply to "Find the factor of a natural number which is closest to its square root?" That only needs a few sentences, and may have been done before.

And there are many better ways of generating primes than looping over all the numbers below the square root.

Mathematica, 91 bytes
n=RandomInteger@199+1
TableForm@Partition[Range@9~RandomChoice~n,Divisors@n~Nearest~Sqrt@n]

I hope I got this right:

Generate a random length between 1 and 200 (inclusive).
Generate a list of that length with numbers from 1 to 9 (inclusive).
Find one of the two divisors closest to the square root, with Divisors@n~Nearest~Sqrt@n.
Break the list into rows of that length.
Display the grid with TableForm.

Example run:

Javasript, 156 or 119 152 or 115
Output numbers 1 to 9: 152
for(q=~~Math.sqrt(n=new Date%200);~~(w=n/q)!=w;--q);i=q=0;alert("".replace.call(Array(n+1),/./g,function(){return(++q>9?q=1:q)+(++i==w?i=0||"\n":" ")}))

Output zeroes: 115
for(q=~~Math.sqrt(n=new Date%200);~~(w=n/q)!=w;--q);alert(Array(q+1).join("".replace.call(Array(w+1),/./g,0)+"\n"))

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
JavaScript: Tricks to shorten onkeydown, setInterval etc
Are there any tricks to shorten defined function names like setInterval, onkeydown, onkeyup, createLinearGradient or even return?
When using it more than once it's nice to put it as a string into a variable and reuse it afterwards but most functions I only need once.
I know that ES6 has arrowed functions - maybe there is an apporach?

FYI: return is not a function.

I'm aware of that - I acutally meant "long" strings in general :)

There is a rather clever trick for shortening method names for a particular object that I first learned about during the first JS1k competition.  See Martijn Haverbeke's page about it, under "Mechanized Abbreviation".
The idea is that you iterate over the keys of the object and apply a hash function h(k) to each of the keys in order to compute an alias for the key.  With some trickery you can make sure to only apply the aliasing to keys referring to function values (i.e. only if typeof o[k] == 'function'), but of course this costs some extra characters.  If only one of the keys being aliased hash to the same value, then you can use the abbreviated name unambiguously.  If there are collisions you have to fall back to the full name (since the order of iteration is undefined).
When using this trick, remember that it's a trade-off between length of hash function (expression) and number of collisions.  Of course, this approach is only helpful when you use a lot of long-name methods on one particular object (e.g. canvas code).  For a paricular snippet that you want to golf, it could be useful to find the number of occurrences of each identifier and put together something like this page, to simplify the search for a good hash function.
This trick could be used with global functions since the global object is this at the global scope (or even shorter, windows = window.top = top in a web environment).  Also, another thing to keep in mind with frequent use of methods on one object is the with statement.

There are a lot of different cases here. I'll try to address as many as I can think of, but others might spot a few additional ones.
For starts, return is not a function. It's a keyword. So you're out of luck there. (Unless you can write your function in a single statement, in which case ES6 arrow functions make the return implicit, like f=s=>s.length instead of f=s=>{return s.length;}.)
For static-like functions such as setInterval or Math.sin you can just give them a new name:
t=setInterval
s=Math.sin

If you want to call a function on an object repeatedly, you'll have to work a bit harder though. For instance if you want to use s.charCodeAt multiple times on a string s, then you cannot do:
c=s.charCodeAt
c(1)
c(2)
...

Because if invoked like this, c will not know it's this-context. The simplest option here is to store c as a property of s:
s.c=s.charCodeAt
s.c(1)
s.c(2)

If you're using this very often though, you don't want to write the s. every time. To get rid of that, you'll need to write your own function. Using ES6 notation:
c=i=>s.charCodeAt(i)
c(1)
c(2)

Note however that this requires that you always want to call it on the same s. However, if you want to use a shortened member function on several objects, you can make those parameters:
c=(o,i)=>o.charCodeAt(i)
c(s,1)
c(t,2)
...

Then there's also the option to modify the prototype to patch the function into every instance of a class, but I'd have to look up the details.

Alternatively, you could cache the property name: s[c='charCodeAt'](1) s[c](2)

c="".charCodeAt.call ... OK, it's not very short, but at least I tried.

Note: comma operator can be used to squash some things into a single statement.

ES6 can be the answer regarding function definition, with arrow functions, array comprehension and closure expressions
ECMAScript 5:
function z(a) {
  statement; statement; ...
  return value;
}

ECMAScript 6
z=a=> {
   statement; statement; ...
   return value;
}

// or

z=a=> expression

Example Factorial
function f(n) { for(r=1;n;n--;) r*=n; return r } // Iterative

function f(n) { return n>1 ? n*f(n-1) : 1 } // recursive

f=n=> n>1 ? n*f(n-1):1// ES6 recursive

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Catch some drug dealers
(spoilers on decade-old TV show below)
In the HBO show "The Wire", the dealers use a system of encoding phone numbers where they "jump the 5" on the number pad.
+-----------+
| 1 | 2 | 3 |
+-----------+
| 4 | 5 | 6 |
+-----------+
| 7 | 8 | 9 |
+-----------+
| # | 0 | * |
+-----------+

A "1" becomes a "9", "4" becomes "6", etc ... and "5" and "0" swap places.  So, the input number 2983794-07 becomes 8127316-53.  # and * are undefined.  Input in the show was numeric with a dash, your code does not need to preserve the dash but it does need to accept it.  No real restrictions on how user interaction is handled, can be a function or console application as needed.
Scoring criteria:
This is a code golf, fewest characters wins.  There is a 100 character penalty for solving it with a number/character swap or array lookup (I'm trying to broadly paint a brush stroke to avoid "9876043215"[i]-style lookups).  10 character bonus for not stripping dashes.

Isn't every solution going to use number/character swap with or without a detour?

Maybe I should make it a pop-con question instead, to get creative answers out of it?

Isn't this just ten minus each digit? (Beside 5/0)

@insta Taking a simple task and saying "solve this creatively", generally makes for a very bad popularity contest.

Rats, well it seemed like it would have been a good challenge on the drive in :(

"There is a 100 character penalty for solving it with a number/character swap or array lookup." This is a vague and unenforceable rule. If your challenge has a boring optimal solution, you should rethink the challenge rather than try to ban that solution.

@MartinBüttner taking a simple task and linking it to not only drug dealers, but the illustrious "Wire" and you're generally bound to have a few happy people. Omar's coming

MATLAB, 25 bytes
Function accepting a string.
- is converted to =... so the dash is not just preserved, there is twice as much of it?
@(n)106-n-5*(n==48|n==53)

LOL twice as much :D

I think you need to add a few bytes. You need to convert the answer from int to char. I think the easiest way is: f=@(n)['' 106-n-5*(n==48|n==53)]. (Fewer bytes than char(...).)

@RobertP. True, it will display numbers if you simply evaluate f on the command line, but it will work fine if used where a string is expected, e.g. fprintf('%s\n', f('3259232352'))

tr, 107 (17 + 100 - 10)
tr 0-9 5987604321

Perl port: y/0-9/5987604321/ and -p flag. Run with: perl -pe'y/0-9/5987604321/' <(echo 2983794-07) Score is 17 + 1 + 100 - 10 = 108.

GolfScript 9 (= 19 - 10)
{16|106\-.5%3=5*-}%

or
{16|~107+.5%3=5*-}%

Online demo
Explanation
As observed by a few people, this calls for subtraction of the digit from 10 in most cases. Since the digits in ASCII start at 48, that means subtracting the ASCII code from 48*2+10 = 106. That leaves three special cases:

0 and 5: these map to 10 and 5 respectively, and need to map to 5 and 0. Solution: .5%3=5*- subtracts 5 if the result is equal to 3 modulo 5.
-: this is the fun one. ASCII code 45, so equivalent to digit -3. After the reflection it's equivalent to digit 13, so I need to subtract 16. But I can equivalently do that by adding 16 before the reflection, and since 45 is the only relevant ASCII code not to have the bit corresponding to 16 set, I can accomplish that with a simple bitwise OR: 16|.

JavaScript, ES6, 27 bytes (37 - 10)
f=_=>_.replace(/\d/g,y=>y%5?10-y:5-y)

Try it in latest Firefox like
f("2983794-07")

Perl port: Run s/\d/$&%5?10-$&:5-$&/ge with p flag like this: perl -pe's/\d/$&%5?10-$&:5-$&/ge' <(echo "2983794-07") which would be 23 + 1 - 10 = 14 bytes.

CJam, 13 (23 - 10) bytes
'-_l\/{{si_5%A5?\-}%}%*

Try it online here

C (63 - 10 = 53)
main(_){while(_=getchar())putchar(_>47?(_-=48)%5?58-_:53-_:_);}


text:
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 \$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.

Isn't the first example a third level instead of second ?

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.

Changed sponge to carpets, thanks.

What if your language does not support unicode output, is there also an ASCII alternative?

@steveverrill Good idea, I'll specify # and spaces as an alternative.

Okay, I've specified a ASCII alternative as #, and replaced the white square with a space.

@steveverrill Good catch, added level 3.

Can the lines have trailing spaces?

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.

#0<'■S -> #~S'■ saves 1 character.

You can replace [1_]a#~ with 3Yba&.

@Dennis neat. thank you!

@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.

Man, also post more insights on the base conversions and tricks to it :)

Should save two chars: 3li(#,{3b1f&4b}%_f{f{&S9632c?S}N}

@Dennis Thanks! The f{f{...}} is a really nice idea. :)

Doesn't the Unicode trick use more characters in this case?

@Ypnypn Nope. It looks longer but that's because the Unicode characters aren't monospaces. The unpacked code has 30 characters.

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

Instead of d=zeros(size([c,c])) you should use d=[c c]*0.

nice, a suggestion: the variable d can be avoided by abusing kron once more: disp(char(kron(c,[1,0])*3+32));,

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

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)

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

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

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

input

3

output

I followed you like a total creeper. +1 ;).

Do you think you can shorten this with SubstitutionSystem ?

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

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

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

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

143 bytes

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

oK, 40 45 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.

Ah, sorry about that! It should meet the spec now (at the cost of 5 more bytes).

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!

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

Haskell, 77 characters
f n|a<-mapM(:[0,1])[2..n]=[do x<-a;"■ "!!(0^product(zipWith(+)x y)):" "|y<-a]

Try it online!

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

If you use the char ■ instead of #, you can save 2 chars by removing the quotes.

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.

SOGL V0.12, 27 bytes
 ■¹.H{³³┼┼≥: ■@ŗ;┼┼⁴++}{@∑P

Try it Here!

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

156 bytes

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.

It is competing, per a newer consensus.

@EriktheOutgolfer oh, thanks for letting me know!

And yes, in this case the score is 17, but we count solutions in bytes, not characters (Canvas has a code page).

@EriktheOutgolfer normally yes, but this challenge uses characters, due to ■ being multibyte. Says so toward the bottom in the original post.

You need to add one to all your inputs. 1 should return a square (i.e. what 0 returns here)

@PaulClavier ah, ok, it's been fixed.

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"

I think you can drop a byte by using ("# "1_,/1,'+/')' instead of "# "1_',/'1,''+/''

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

Vyxal, 19 bytes
‛ #3?‹eʁ3τ∷vB:v⋏†İ⁋

Try it Online!
How?
‛ #3?‹eʁ3τ∷vB:v⋏†İ⁋
    ?‹              # Push input - 1
   3  e             # Push 3 to the power of it
       ʁ            # Get range [0, that)
        3τ          # Convert each to base 3 (ternary)
          ∷         # Modulo each by two to convert twos to zeros
           vB       # Convert each from binary to integers
             :v⋏    # Outer product bitwise AND with itself
                †   # Logical NOT for each
‛ #              İ  # Index each into " #"
                  ⁋ # Join each by spaces, and then join on newlines

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

@PaulClavier it's a great challenge; you should be proud :)

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

Try it online!
+15 thanks to DLosc for pointing out there had to be spaces between columns.
This was a quick fix to satisfy the spec and could likely be re-golfed further.
J, original answer, cleaner, 35 bytes
' #'{~]9&([:,/_3,./\0"+4}(#,:)),:@1

Try it online!

Husk, 27 bytes
mJ' ´Ṫȯ!"□ "¬nmḋ†%2mB3ŀ`^3←

Try it online!
Translation of Jonathan Allan's program.
uses the '□' character.

05AB1E, 21 bytes
„# 3I<mÝ¨3δвÉJCDδ&Āè»

Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well!
Try it online or verify all test cases.
Explanation:
    I<                # Push the input-1
   3  m               # Take 3 to the power this input-1
       Ý              # Pop and push a list in the range [0,3**(input-1)]
        ¨             # Remove the last item to lower the range to: [0,3**(input-1))
          δ           # Map over each integer:
         3 в          #  Convert it to a base-3 list
            É         # Check for each trigit if it's odd, converting the 2s to 0s
             J        # Join the inner bit-lists together to strings
              C       # Convert each from a binary-string to an integer
               D      # Using a copy of itself,
                δ     # apply double-vectorized over this list of integer:
                 &    #  Bitwise-AND the integers together
                  Ā   # Check for each integer whether it's NOT 0 (0 if 0; 1 otherwise)
„#                 è  # 0-based index it into the string "# "
                    » # Join each inner list by spaces, and then each string by newlines
                      # (after which the result is output implicitly)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Print Hamlet's monologue using as few characters as possible
The task here is to print the text below, using as few characters as possible in your code. You can't use any external resource. (file, stdin, network)
To be, or not to be: that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,
Or to take arms against a sea of troubles,
And by opposing end them? To die: to sleep;
No more; and by a sleep to say we end
The heart-ache and the thousand natural shocks
That flesh is heir to, 'tis a consummation
Devoutly to be wish'd. To die, to sleep;
To sleep: perchance to dream: ay, there's the rub;
For in that sleep of death what dreams may come
When we have shuffled off this mortal coil,
Must give us pause: there's the respect
That makes calamity of so long life;
For who would bear the whips and scorns of time,
The oppressor's wrong, the proud man's contumely,
The pangs of dispriz'd love, the law's delay,
The insolence of office and the spurns
That patient merit of the unworthy takes,
When he himself might his quietus make
With a bare bodkin? Who would these fardels bear,
To grunt and sweat under a weary life,
But that the dread of something after death,
The undiscover'd country from whose bourn
No traveller returns, puzzles the will
And makes us rather bear those ills we have
Than fly to others that we know not of?
Thus conscience does make cowards of us all;
And thus the native hue of resolution
Is sicklied o'er with the pale cast of thought,
And enterprises of great pith and moment
With this regard their currents turn away,
And lose the name of action.--Soft you now!
The fair Ophelia! Nymph, in thy orisons
Be all my sins remember'd.

Don't you mean monologue?

@feersum Don't you mean soliloquy? :P

@Geobits Touché.

I'd just like to give a reason for my downvote: I don't like generic kolmogorov complexity challenges unless there is some internal structure to cleverly utilize, and I really dislike character counting golfs.

Welcome to Programming Puzzles and Code Golf. We've had similar challenges before, unfortunately this one doesn't add anything different. Stick around, answer a few questions to find out what we're about, and feel free to post your next question at our sandbox for feedback: http://meta.codegolf.stackexchange.com/q/2140/15599

My downvote is because you count in characters, not bytes.

@steveverrill I search before I asked this, but as I didn't I haven't found anything. The question that this is a duplicate of has a title that doesn't even hint that it might be related to my question, possibly that's why I didn't find it. Still, thanks!

@JanDvorak Tell that to the guys at Ericsson, this in one of their programming competitions: http://www.ericssonbajnoksag.hu/regebbi_feladatok

CJam, 713 683 characters
We're counting by characters so here's the usual Unicode encoding approach. I'm sure this can be beaten, but at least it's less than half as many characters as the output.
"=迗拢쌜僨糌ࢬꭖ杋鏊ꦓ廃啒⼬ᏸꛒ멉尬䳉藋底淡蟖ꣃ⪖恉囻ꮠⶠ榯൨鞺㹑悩眷ဋ㟯ㅕ葡Ż㼡惽Т託⹡嫰뵴䕞凿绸䷛䴽繋㐚挻ᙶ᪻뼶䌼냞ോ貿ꐯ欲鄁卒梷몧臡ꙉꐰ臸惽ệ昣䙍樬ᓜ녖谴鈦⃇炣膊Ე戭⟣䌮ꆰ躍➥կ语鄂셸ⷽⁿ덝곋䚴䚗Ḹ硅㺁餌쀎柁ᛔ礳괰蚴變㿢䅋砤鈴綸䨜᾽㓔䘅䊶䭚⦑럜䧑䔠⳾뇾䴓ꣽ鎋੩呝䓔ᇽἰ䗚笨簛䀣䲮攌꘦↢ኲㄉ⥈䎺韧᭩滥叒㰥ꬔ懭彼垥丼됑艨ᒝ荶뵴枀膛㛏닱関㵃踫⹦瀗媂㴫꺼柝➍ꜙ纫弡ꔕ㦂蹘ꬃ粅ᛧ熄寝㎍衰飔㩏鈅廀裝굗猪맊␰例㘇ꓶ᫋⟗㟔獇⍨ꉔ뵯瓗ℎ岻摔撎偱紁꽓澤䔷刪㒰墄㰑쀨ꦞ沣뤣葇欕鎨빵ဟ赊剡篠壃ఌ忎꺉鴩绘腀뉂每倢觌びው錵ꏅ儅몧瑳갎媢㗿陣欿᫉ꋿ週䰧鉝깊屌軌먝궔꘹ҙ伔肢⨘緍㰑㐩삭善เⴹ뫑勂㣗曝㛊瘐蠚椂ỿꖴ⎫ᶬ鐸它蒗ؑ謅໐뮦ꩇℇ虇ヽ襟餰塹媬蕥偃⒭躧ꩆ꣢麡翲ⷜ緤飆㛉鴳㾂偾ᖈ欍㩻䦛ꄆꏝ꣭䠦᭳㭱囃㣝䥀鿆䴹෽蝩荲輳蓆娠啃帶ᮾᨍ쀶ѱⴣ㻝順᫰掽紈걉壬虾撆Ⅴ軚䀥ᚑF㠡㞮ᨣ溹뷝欬듺㡧玌딿섄ଷ럫㏵椉䴚ጪ⾗瞾䕼效㠐翢Տ须䈲蘸อ괟㿬む攩糼烏뼊ⷫ庁诔뀗瀦䴇鳨匿ò韑祋夯稚骪愫蕁렒蒔룳πབྷℇଉ簿ّ뺦謃刨㫳ᔥ槦ᑃ璽皩宩傜䷗᥁ꊙ庉놨ꠑᯋ撿ᰃ⧹ⷅ瓴눥᮶â䏶뒾ञ代뫵ਫ㙺Ἑధॆ偟끎녘ৈ黗돃Ὄ檮㢈괿哟繹ꈥ垌喞ᘜ齈㒹뭹ᴴ轳浬曥瑾級꫼ᡊᴮ留㝸螱Ḵ嗳汏ᔔ藁嫜≵୛掣Ẁ恪⍩슅手彶䤇萴櫹ວჲ⽢а琨늪ㇲᭈ쇰ӳ㧠㥡놀Ꙭ碐ゼ⎴릊⍢蠐贈㧑请骰곮쀕렳ಊ祟㽖葬汓䢢兘뢺韴泧馆净벏ᵢ䕋僛♃⩖䎹ᑟ㓆虑鈃ڳ눼絇移ꝴ匯䇸㓀♔⳶㓧෴較õ乛ᔫ欚嗶᥄ꈢャ✉Ꝼ拂橳˯㶲ʤ댯ᡃ볿籚䊋釗␶傍궔樥泤趡鮚㺅卫㲴汒穿ⵑ衙ꞅ修쉚皨ƽ┐꣚漛༻ꔤ꾰䖓澐꣗輘醵醸乯ᦳ䕴䛯词麈鏡棧ᚒ᳜朝ꙧꬫ諒㜑瑕⨱㴥뎋面ᬀ滯憮௦庰民눿隆磁꼓詮䡎䵩费㤋腔杦薎㱿ᇆ韗騏⧢盚븎"5e4b128b:c

For some reason I end up with a leading a after decoding, which I need to remove first.