Squaring the Square is a process of tiling a square using only other squares. If this tiling only uses squares of different sizes, then it is considered to be perfect. The smallest possible perfect squared square is a 112x112 square tiled using 21 different squares.

I have created the ascii art version of this square below:

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

Your submission should print out the above square. You may print a reflection and/or rotation of the above square if you wish. A trailing newline on the last line is allowed. This is a code-golf, so the smallest submission wins!

Nathan Merrill

Posted 2015-07-05T18:40:28.253

Reputation: 13 591

@Optimizer According to the question and Wikipedia, all the small squares have to be completely different sizes. – Level River St – 2015-07-05T20:43:58.973

Nathan, Is my submission in accordance with the rules? I used a uniform thickness for all lines. – DavidC – 2015-07-06T16:44:00.387

@DavidCarraher I have each side of the square outlined (so inner sides have multiple pound signs). Also, you need to use # instead of X – Nathan Merrill – 2015-07-06T18:05:26.713

1Nathan, In the plane, edges are not borders. They are one dimensional line segments. Where two tiles abut, we should see a single line, not two. Otherwise, we are conveying the idea that there is a gap between the tiles. – DavidC – 2015-07-07T07:12:38.617

@DavidCarraher while that is true, I think it makes more sense to represent it in ascii this way. – Nathan Merrill – 2015-07-07T12:57:36.043

Answers

CJam, 88 84 83 bytes

'p:Ci_C*a*"2#   *%!"{i_S*a*{3af.|W%z}4*1$0=C#C*f{\+}..e<{_C&{oNo}|}%}/

Test it here.

Explanation

Here is the basic idea: start with an "empty" 112x112 square. Now go through the squares in reading order (left to right, top to bottom). Add each square into the first available position. Afterwards, print all completed lines - this ensures that we only need to check the first (remaining) line to figure out where the next square goes.

The empty grid is initialised to ps, because I needed a character with character code larger than space and #, and because I could reuse its own character code 112 for the size of the initial grid. I made use of some of Dennis's ASCII art tricks here to fill the small squares into the grid.

'p:C        e# Store the character 'p' in C.
i           e# Convert to its character code 112.
_C*a*       e# Generate a 112x112 array of p's.
"2#   *%!"  e# The 21 characters in this string correspond to the side lengths of
            e# the squares in the solution in reading order.
{           e# For each character in that string...
  i         e#   Convert to its character code (the current square's side length N).
  _S*a*     e#   Generate an NxN array of spaces.
  {         e#   Run this block 4 times. Each iteration turns the leading column into #'s
            e#   and then rotates the square by 90 degrees.
    3af.|   e#     For the first character in each row, take the bitwise OR with 3. 
            e#     This turns spaces into #'s and leaves #'s unchanged.
    W%z     e#     Reverse and transpose, which rotates by 90 degrees.
  }4*
  1$0=      e#   Copy the remaining grid and fetch the top row.
  C#        e#   Find the index of the first 'p'.
  C*        e#   Get a string of that many p's.
  f{\+}     e#   Prepend this string to each row of the small square, which gives the
            e#   square the correct horizontal position.
  ..e<      e#   Take the pairwise minimum of the square and the remaining grid. The p's
            e#   prepended to the square will leave the grid unchanged, but the spaces
            e#   and #'s in the square will overwrite the p's in the grid.
  {         e#   Map this block onto each row of the grid.
    _C&     e#     Copy the row and check if any p's are left.
    {oNo}|  e#     If NOT, the row is complete and we print it together with a newline.
            e#     This also removes the row from the grid, such that the top row for
            e#     the next iteration will have space for the next square left.
  }%
}/

Martin Ender

Posted 2015-07-05T18:40:28.253

Reputation: 184 808

Mathematica 360 426

The code works by first drawing the perfect square of squares, rasterising and binarizing the image, and then converting 0 to "#" and 1 to " ".

The output is returned as ordinary ASCII characters in a table.

f@{n_,x_,y_}:=Rectangle[{x,y},{x+n,y+n}];t=Transpose;
Flatten[i=Rasterize[Graphics[{EdgeForm[{(*Thickness[.015],*)Black}],White,
f/@ Partition[{33,0,0,29,0,33,50,0,62,37,33,0,25,29,37,42,70,0,18,70,42,24,88,42,9,54,53,7,63,53,15,50,62,17,65,60,
11,82,66,19,93,66,35,50,77,27,85,85},3]
},ImageSize->70
],RasterSize->70]//Binarize//ImageData,1]/.{0:> "#",1:> " "};
GraphicsGrid@t@Most@Most@Rest@t[Most@Most[Rest[ArrayReshape[%,Dimensions[i]]]]]

I prefer this rendering, obtained by deleting Thickness[.015]

DavidC

Posted 2015-07-05T18:40:28.253

Reputation: 24 524

The line thickness does not vary, the 50x50 square is 48 space characters across and 48 space characters down, with a border of #'s. It butts up against other squares at the right and bottom, which are drawn in a similar way. Where two squares which have # all round the outside meet, you therefore get a double # for inside lines, And the squares are indeed square, they have the same number of characters vertically and horizontally, The problem is the font. This answer does not comply with the spec, If it got accepted, the question would get closevoted for a non-objective win. – Level River St – 2015-07-06T17:21:12.310

The lines are conceived as one-dimensional, not two-dimensional. They are not to be interpreted as borders having thickness. After all, we are partitioning a square region into square subregions. The borders should not take up any area. – DavidC – 2015-07-06T20:51:31.307

That's kinda the point. The lines go between the squares, and OP chose to represent the squares with internal borders. It might've been clearer if he'd chosen to use a different symbol for each square (and possibly also filled them.) In any case, as you can see from recent flag questions, usual understanding (and whole point of the komolgorov complexity tag) is to faithfully reproduce the Ascii art representation supplied by the OP, not make your own interpretation. While interesting, this isn't a valid answer. Many squares still have different numbers of characters in their height & width. – Level River St – 2015-07-07T11:59:14.237

Reminds me of Von Karman Streets – Beta Decay – 2015-08-03T17:25:22.940

Ruby, 180 bytes

Golfed version based on the ungolfed version below. We take advantage of the fact that there are typically 2 or 3 squares with the same y coordinate for the top left corner.

The first magic string contains ASCII codes for the square sidelength+70 and y increment +40. When encountering a square sidelength (Ascii code >67) we assume the next square is at the same y coordinate, and the x coordinate can be obtained by incrementing the current x coordinate by sidelength+2. When encountering a y increment (Ascii code<67) we increment the y coordinate accordingly and reset the x coordinate to the figure encoded in the second magic string.

a=Array.new(112){?#*112}
x=y=1
j=9
'vg_CLW0SUO3J\,a]M*KV/T3n-Hi,e'.each_byte{|i|i>67?(s=i-70;(y..y+s-1).map{|i|a[i][x,s]=" "*s};x+=s+2):(x=')Fo_h){[~'[j-=1].ord-40;y+=i-40)}
puts a

Original version

This (completely ungolfed) solution contains 315 bytes, excluding unnecessary blank lines and indents. It simply creates an array of 112 strings of 112 #'s then replaces the insides of the squares with spaces.

$a=Array.new(112){"#"*112}
def f(x,y,s)
  (y..y+s-1).map{|i|$a[i][x,s]=" "*s}
end

f(1,1,48)
f(51,1,33)
f(86,1,25)

f(86,28,6)
f(94,28,17)

f(51,36,13)
f(66,36,15)
f(83,36,9)

f(83,47,4)
f(89,47,22)

f(1,51,27)
f(30,51,23)
f(55,51,7)

f(64,53,5)
f(71,53,16)

f(55,60,14)

f(71,71,40)

f(30,76,2)
f(34,76,35)

f(1,80,31)

puts $a

Level River St

Posted 2015-07-05T18:40:28.253

Reputation: 22 049

R, 293 291 287 282 bytes

a=array('#',112:113)
a[,113]='
'
for(g in list(c(0,0,49,34,26),c(27,85,7,18),c(35,50,14,16,10),c(46,82,5,23),c(50,0,28,24,8,1),c(52,63,6,17),c(59,54,15),c(70,70,41),c(75,29,3,36),c(79,0,32))){y=g[1];x=g[2]
for(b in g[0:1-2]){a[(y+2):(y+b),(x+2):(x+b)]=' '
x=x+b+1}}
cat(t(a),sep='')

After I did this, I realized I had done almost the identical process as @steveverrill. An array of '#' and blank the square interiors. Can probably squeeze some more out of this. The carriage return for the 3rd line is significant. Thanks to AlexA for a few.

MickyT

Posted 2015-07-05T18:40:28.253

Reputation: 11 735

You only reference s once, so couldn't you do for(g in list(...)) rather than specifying s separately beforehand? I think that would save you 2-3 bytes. – Alex A. – 2015-07-06T03:14:50.070

@AlexA. Thanks, an obvious one that I totally missed – MickyT – 2015-07-06T19:03:38.790

C, 198 bytes

char*i="bSK8C?A;6HMI927B@Z4UQ",o[112][113],x,y,p,q,n;main(){for(;y<112;puts(o[y]),y++)for(x=-1;++x<112;)if(!o[y][x]){n=*i++-48;for(p=-1;++p<n;)for(q=-1;++q<n;)o[q+y][p+x]=p&&n-1-p&&q&&n-1-q?32:35;}}

(Ungolfed)

char *i="bSK8C?A;6HMI927B@Z4UQ", o[112][113], x, y, p, q, n;
main() {
  for ( ; y<112; puts(o[y]),y++) {
    for (x=-1; ++x<112; ) {
      if (!o[y][x]) {
        n = *i++ - 48;
        for (p=-1; ++p<n; ) {
          for(q=-1; ++q<n; ) {
            o[q+y][p+x] = (p && n-1-p && q && n-1-q) ? ' ' : '#';
          }
        }
      }
    }
  }
}

All this does is scan through an array of 112×112 bytes (initialized to zero). Whenever it encounters a zero byte, it fetches a value from array i and adds a box of the corresponding size. The extra byte in each row acts as a string terminator so we can use puts() to output entire lines instead of using putchar() to output characters individually.

This can probably be golfed a little more, but I don't think it stands much chance of beating steveverrill's answer.

(ideone link)

r3mainer

Posted 2015-07-05T18:40:28.253

Reputation: 19 135

+1 This is an excellent concept, far better than mine, in a less golfy language. I believe it might be able to beat my answer. Note you need to print a #when !(p%(n-1)&&q%(n-1))I would also look into reducing the number of for loops from four to two , using x=i%113 and y=i/113 etc. – Level River St – 2015-07-10T01:30:59.300

MS-DOS Binary, 137

The following code will run in MS-DOS if you write it into a file called square.com, no further compilation required (but since it's given in hex, you need to "unhex" it first):

fcba8f01b82370e83000bd1400bb4d018b1743438a27b02043e81e004d75
f1b97000ba8f3289d7b00daab00aaab82409aa83ea70cd214975ecc331c9
88e189ce89d788e1f3aa83c2704e75f4c3201d30e223218527190524063d
1f11521d0d811c0f321f09921c04b8141670101b4d12176619076f1905a6
141066120e4602288d100221022300021f

The output will be unrecognisable in most terminals, but you can redirect it to a file (square.com > output.txt) and look at it in an text editor. If you want something more readable, the following code will produce a working square.com if fed into debug.exe (debug.exe < square.asm):

a
cld
mov dx,18f
mov ax,7023
call 13a
mov bp,14
mov bx,14d
mov dx,[bx]
inc bx
inc bx
mov ah,[bx]
mov al,20
inc bx
call 13a
dec bp
jnz 110
mov cx,70
mov dx,328f
mov di,dx
mov al,d
stosb
mov al,a
stosb
mov ax,924
stosb
sub dx,70
int 21
dec cx
jnz 125
ret
xor cx,cx
mov cl,ah
mov si,cx
mov di,dx
mov cl,ah
rep stosb
add dx,70
dec si
jnz 140
ret
db 20,1d,30,e2,23,21
db 85,27,19,05,24,6
db 3d,1f,11,52,1d,d
db 81,1c,f,32,1f,9
db 92,1c,4,b8,14,16
db 70,10,1b,4d,12,17
db 66,19,7,6f,19,5
db a6,14,10,66,12,e
db 46,02,28,8d,10,2
db 21,02,23,00,02,1f

n square.com
rcx
89
w
q

user2845840

Posted 2015-07-05T18:40:28.253

Reputation: 391

Matlab/Octave, 258

As always, Matrices. I hardcoded the row and the column indices of each square ans well as the size. I can use these to fill up a big 'blank' square of #s.

r=[2,2,2,29,29,37,37,37,48,48,52,52,52,54,54,61,72,77,77,81];
c=[2,52,87,87,95,52,67,84,84,90,2,31,56,65,72,56,72,31,35,2];
s=[47,32,24,5,16,12,14,8,3,21,26,22,6,4,15,13,39,1,34,30];
z=ones(112)*35;
for i=1:20;
    z(r(i)+(0:s(i)),c(i)+(0:s(i)))=32;
end;disp([z,''])

flawr

Posted 2015-07-05T18:40:28.253

Reputation: 40 560

Bash, 252

Every codegolfer should be able to beat a general purpose compression algorithm:

base64 -d<<<H4sIADyFv1UCA+3ZOw6EMAwFwH5PgeT735EOUSyfQAgOmVeCxUgusAkRbfOLqTARd0qAQCAQCAQCgcAvg80375dW/T+lQGAbsCCdgvsdXl0AAoHjgM8e7mUA92bKG+DtpAevDPflRsko7BXcKAQCD9+X3wOPCoFA4ABgnZ/OmcHTS+bw4PXzkV7Ak93KDdboVm6wxrOAQCAQCAQCgUAgENj++7BuZsq8xQ1vMQAA|gunzip

Thanks to Toby Speight for the hint to use shorter input (silly me used gzip instead of gzip -9 for compression) and a here-string.

user2845840

Posted 2015-07-05T18:40:28.253

Reputation: 391

2 shorter with here-string: base64 -d<<<H4sIAP9YuVUAA+3XQQrDIBAF0H1PUfD+d+yq0FA7GirGie/vdEZfkCy0lLl5lOfJlPaKoAUIBAKBQCAQCLwzOP3mfdFVv9IKBM4BTyQpGA0PE0AgcB8wzC3A6vS7egH4d5YH64WPtVGh/zvygj8agcCvQuufzA+2GoFA4AZgd9KCwS7Hzu3B7qQFO09rbXDEaa0NjtgLCAQCgUAgEAgEAoHz34dj8wLKvMUNbzEAAA==|gunzip – Toby Speight – 2015-08-03T15:04:51.930

And a shorter input gets us down to 251: base64 -d<<<H4sIADyFv1UCA+3ZOw6EMAwFwH5PgeT735EOUSyfQAgOmVeCxUgusAkRbfOLqTARd0qAQCAQCAQCgcAvg80375dW/T+lQGAbsCCdgvsdXl0AAoHjgM8e7mUA92bKG+DtpAevDPflRsko7BXcKAQCD9+X3wOPCoFA4ABgnZ/OmcHTS+bw4PXzkV7Ak93KDdboVm6wxrOAQCAQCAQCgUAgENj++7BuZsq8xQ1vMQAA|gunzip – Toby Speight – 2015-08-03T15:16:02.503

Are you sure that works? I only get gunzip: command not found. I can get it working using a subshell: (base64 -d|gunzip)<<<..., but that still uses 258 bytes. – user2845840 – 2015-08-03T16:12:12.060

Strange, @user284584 - something odd with your path? I tested what I wrote (in an interactive shell, if that makes a difference) – Toby Speight – 2015-08-03T16:59:22.657

oh god ... try copying your comment and pasting it back into the shell. Stackexchange "helpfully" inserted 6 invisible characters, 3 each of u+200c & u+200b. After removing them, it works. – user2845840 – 2015-08-03T18:11:28.713

Good catch! linebreaks :-( – Toby Speight – 2015-08-04T07:31:37.640

Print out the Smallest Perfect Squared Square

Answers

CJam, 88 84 83 bytes

Explanation

Mathematica 360 426

Ruby, 180 bytes

R, 293 291 287 282 bytes

C, 198 bytes

(Ungolfed)

MS-DOS Binary, 137

Matlab/Octave, 258

Bash, 252