8
\$\begingroup\$

Write a program or function that takes as input three positive integers x, y, and a and returns or outputs the maximum number of whole a✕1 rectangles that can be packed (axis-aligned) into an x✕y rectangle. Although the result will always be an integer, the program need not give the result using an integer type; in particular, floating-point outputs are acceptable. Use of standard loopholes is forbidden. Answers are scored in bytes including the cost of non-standard compiler flags or other marks.

Sample inputs and outputs:

 x,  y,  a -> result
--------------------
 1,  1,  3 ->      0
 2,  2,  3 ->      0
 1,  6,  4 ->      1
 6,  1,  4 ->      1
 1,  6,  3 ->      2
 6,  1,  3 ->      2
 2,  5,  3 ->      2
 5,  2,  3 ->      2
 3,  3,  3 ->      3
 3,  4,  3 ->      4
 4,  3,  3 ->      4
 4,  4,  3 ->      5
 6,  6,  4 ->      8
 5,  7,  4 ->      8
 7,  5,  4 ->      8
 6,  7,  4 ->     10
 7,  6,  4 ->     10
 5,  8,  3 ->     13
 8,  5,  3 ->     13
12, 12,  8 ->     16
12, 13,  8 ->     18
13, 12,  8 ->     18
 8,  8,  3 ->     21
12, 12,  5 ->     28
13, 13,  5 ->     33

In response to a question in the comments, note that some optimal packings may not be obvious at first glance. For instance, the case x=8, y=8, and a=3 has solutions that look like this:

||||||||
||||||||
||||||||
---||---
---||---
|| ||---
||------
||------

(8 + 2 + 2 = 12 vertical placements and 2 + 3 + 4 = 9 horizontal placements gives 12 + 9 = 21 placements in total.)

\$\endgroup\$
8
  • \$\begingroup\$ So many links to meta... o.O \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 1:27
  • 1
    \$\begingroup\$ I feel like I've seen this question beforw. Lemme search. \$\endgroup\$
    – xnor
    Aug 18, 2016 at 1:39
  • 1
    \$\begingroup\$ Nice first question (even if confirmed to be duplicate)! \$\endgroup\$
    – Leaky Nun
    Aug 18, 2016 at 1:41
  • 1
    \$\begingroup\$ Not finding a dupe. I seem to remember something with fitting 1x4's, so having variable sizes would make this different. \$\endgroup\$
    – xnor
    Aug 18, 2016 at 2:13
  • 2
    \$\begingroup\$ Must the rectangles be placed axis-aligned? \$\endgroup\$
    – xnor
    Aug 18, 2016 at 2:37

1 Answer 1

8
\$\begingroup\$

Python 2, 53 bytes

lambda p,q,n:p/n*q+q/n*(p%n)-min(0,n-p%n-q%n)*(p>n<q)

Adapts the formula given in this paper, which is:

def f(p,q,n):a=p%n;b=q%n;return(p*q-[a*b,(n-a)*(n-b)][a+b>=n and p>=n and q>=n])/n
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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