11
\$\begingroup\$

Background

I have a bunch of square-shaped boxes of equal size, and since I'm a neat person, I want to arrange them all into a square formation. However, their number is not necessarily a perfect square, so I may have to approximate the square shape. I want you to find me the most aesthetically pleasing arrangement -- programmatically, of course.

Input

Your input is a single positive integer k, representing the number of boxes.

Output

Your program shall choose two positive integers m, n such that m*(n-1) < k ≤ m*n holds. They represent the width and height of the large square-like shape we are arranging. Since we are looking for aestethically pleasing shapes, the quantity (m - n)2 + (m*n - k)2 shall be minimal, so that the shape is close to a square, and its area is close to k. If there are still several candidates for the pair (m, n), choose the one where the width m is maximal.

Now, your actual output shall not be the numbers m and n. Instead, you shall print the arrangement of boxes, using the character # to represent a box. More specifically, you shall print n-1 rows, each of which consists of m characters #, and then one row of k - m*(n-1) characters #. Note that the output contains exactly k characters #.

Rules and Scoring

There shall not be any leading or trailing whitespace in the output, except that the last row may be padded with trailing spaces to be of length m, if desired. There may be one trailing newline, but no preceding newlines. You may use any printable ASCII character in place of #, if desired.

You may write a full program, or return a string from a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

Here are the correct outputs for a few input values.

1
#
2
##
3
##
#
4
##
##
8
###
###
##
13
#####
#####
###
17
######
######
#####
18
#####
#####
#####
###
20
#####
#####
#####
#####
21
######
######
######
###
22
######
######
######
####
23
#####
#####
#####
#####
###
\$\endgroup\$
6
\$\begingroup\$

Pyth, 28 bytes

jbc*\#Qho.a,,N*NJ_/_QN,JQ_SQ

Try it online.

The crux is that I sort potential m on the following property:

(m - ceil(k/m))^2 + (m*ceil(k/m) - k)^2

Note the total absence of n. The total shape is defined merely by m. Then I transform the above property once more, and my final sorting weight is defined as the Euclidean distance between the following two points:

(m, m*ceil(k/m)) and (ceil(k/m), k)

This changes the weight values, but not their ordering.

\$\endgroup\$
3
\$\begingroup\$

Python 3, 202 bytes

I know that its longer than the CJam or Pyth solutions, but nevertheless, here is a way of solving this problem in Python:

k=int(input())
r,d,s=range(k+1),{},'#'*k
for n in r:
 for m in r:
  if m*n>=k:
   d[m,n]=(m-n)**2+(m*n-k)**2
x,y=max(i for i in d.keys()if d[i]==min(d.values()))
[print(s[i*x:(i*x+x])for i in range(y+1)]

The basic principle is that we know m and n are both less than k. Also, m*n >= k . That means that we can simply find the minimum of the expression given in the challenge for all m,n < k, excluding values whose product is greater than k.

\$\endgroup\$
  • \$\begingroup\$ I actually count 231 bytes in your source, not 234. But regardless, you can reduce it by decreasing your indent size from four spaces to one space. It'll work the same. \$\endgroup\$ – Alex A. Aug 25 '15 at 4:59
  • \$\begingroup\$ This is a handy tool for getting your byte count. By the way, nice submission and welcome to the site! \$\endgroup\$ – Alex A. Aug 25 '15 at 5:12
  • \$\begingroup\$ : missing at line 5. Comma is what defines a tuple, brackets () can be removed at line 6. Spaces between ) and (if or for) too. max can get generator as parameter, thus brackets [] are redundant. You iterate over d keys, so you can safely use d[i]. \$\endgroup\$ – Trang Oul Aug 25 '15 at 11:06
  • \$\begingroup\$ You can save two bytes changing (i+1)*x to -~i*x or i*x+x. \$\endgroup\$ – Kade Aug 25 '15 at 13:23
  • \$\begingroup\$ You have an extra, invalid paren at (i*x+x... \$\endgroup\$ – FlipTack Dec 21 '16 at 19:35
2
\$\begingroup\$

CJam (44 42 bytes)

qi_,{)_2$d\/m]_2$-_*@@*2$-_*+~}$W=)'#@*/N*

Online demo

I was rather expecting there to be a simpler solution involving square roots, but it's not at all that simple. E.g. for input 31 the row width is two greater than the ceiling of the square root; for 273 (square root just over 16.5) the best approximate square is a perfect 21x13 rectangle.

\$\endgroup\$
1
\$\begingroup\$

CJam, 42 bytes

li:K_,f-{:XdK\/m]:YX-_*XY*K-_*+}$0='#K*/N*

Try it online

Explanation:

li    Get and interpret input.
:K    Store in variable K for later use.
_     Copy.
,     Build sequence [0 .. K-1].
f-    Subtract from K, to get sequence [K .. 1]. Larger values have to come
      first so that they are ahead in ties when we sort later.
{     Begin block for calculation of target function for sort.
  :X    Store width in variable X.
  d     Convert to double.
  K\/   Calculate K/X.
  m]    Ceiling.
  :Y    Store height in variable Y.
  X-    Calculate Y-X.
  _*    Square it.
  XY*   Calculate X*Y...
  K-    ... and X*Y-K
  _*    Square it.
  +     Add the two squares.
}$    Sort by target function value.
0=    Get first element, this is the best width.
'#K*  Build string of K '# characters.
/     Split using width.
N*    Join with newlines.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.