Fill the rectangle

Question

Challenge

In this challenge, you have to fill an \$M\$ x \$N\$ rectangle grid with the most \$A\$ x \$B\$ rectangle pieces possible.

Requirements:

• The sizes of the \$M\$ x \$N\$ rectangle grid is always bigger than the sizes of the \$A\$ x \$B\$ rectangle pieces. In other words, \$min(M, N) ≥ max(A, B)\$
• You can freely rotate the \$A\$ x \$B\$ rectangle pieces.
• Those \$A\$ x \$B\$ rectangle pieces can touch each other on the edge, but it cannot overlap each other.
• Those \$A\$ x \$B\$ rectangle pieces, or part of it, cannot be outside of the \$M\$ x \$N\$ rectangle grid.
• You don't have to fill the whole \$M\$ x \$N\$ rectangle grid, because sometimes that is impossible.

Example

Given a \$5\$ x \$5\$ rectangle grid (or square) like below:

And you have to fill it with \$2\$ x \$2\$ rectangle (or square) pieces. The best you can do is \$4\$, like below:

Input/Output

Input can be taken in any resonable format, containing the size of the \$M\$ x \$N\$ rectangle grid and the \$A\$ x \$B\$ rectangle pieces.

Output can also be taken in any resonable format, containing the most number of pieces possible.

Example Input/Output:

Input         -> Output
[5, 5] [2, 2] -> 4
[5, 6] [2, 3] -> 5
[3, 5] [1, 2] -> 7
[4, 6] [1, 2] -> 12
[10, 10] [1, 4] -> 24

This is code-golf, so shortest answer (in bytes) wins!

Answer 1

JavaScript (Node.js), 175 bytes

Expects (m,n,[a,b]) with all values passed as BigInts.

(m,n,a,M,g=(p,y,i)=>q=i--&&p>>y*~m|g(p,~-y,i))=>(h=(k,N,x,y)=>{for(y=n;--y;)for(x=m;x--;)a.map((v,i)=>k&g(2n**v-1n<<x,y,a[i^1])?M>N?0:M=N:h(k|q,N+1))})(g(1n<<m,n,++n)|~-q,0)|M

Try it online!

How?

This is a (slow) brute-force search over a single BigInt bitmask representing the entire board with left and bottom borders.

For instance, a \$2\times3\$ board is initialized to \$2343\$, which is \$100100100111\$ in binary. Once re-arranged in 2D, this gives:

$$\begin{matrix}1&0&0\\1&0&0\\1&0&0\\1&1&1\end{matrix}$$

We use the helper function \$g\$ to create the bitmask \$q\$ of a rectangle:

g = (          // g is a recursive function taking:
  p,           //   p = row pattern
  y,           //   y = starting row
  i            //   i = remaining number of rows
) =>           //
q =            // save the final result in q
  i-- &&       // decrement i; stop if it was 0
  p            // insert the pattern
  >> y * ~m |  // shifted to the left by y * (m+1) positions
               // (we actually do a shift to the right by
               // y * (-m-1), which doesn't work as expected
               // with Numbers but works fine with BigInts)
  g(p, ~-y, i) // do a recursive call with y - 1

We use g(1n << m, n, ++n) | ~-q to initialize the board: the call to \$g\$ creates the left border and the bitwise OR with \$q-1\$ appends the bottom border.

We use \$g\$ again to create the smaller rectangles of size \$A\times B\$ and \$B\times A\$. We test collisions with bitwise ANDs and add them to the board with bitwise ORs.

Answer 2

Charcoal, 95 92 bytes

ＮθＮη≔Ｅ²Ｎζ⊞υ×⊖Ｘ²θ÷⊖Ｘ²×η⊕θ⊖Ｘ²⊕θＦ×η⊕θＦ×Ｘ²ιＥＸ²⟦ζ⮌ζ⟧×⊖⊟κ÷⊖Ｘ⊟κ⊕θ⊖Ｘ²⊕θＦυＦ⁼κ＆λκ⊞υ⁻λκＵＭυΣ⍘ι²Ｉ÷⁻⌈υ⌊υΠζ

Try it online! Link is to verbose version of code. Explanation: Brute-force breadth-first search, so very slow.

ＮθＮη

Input the dimensions of the grid to be filled.

≔Ｅ²Ｎζ

Input the dimensions of the rectangle.

⊞υ×⊖Ｘ²θ÷⊖Ｘ²×η⊕θ⊖Ｘ²⊕θ

Start a breadth-first search with a bitmask representing an empty grid.

Ｆ×η⊕θ

Loop over all the possible top left corners of the rectangle, and some impossible ones too.

Ｆ×Ｘ²ιＥＸ²⟦ζ⮌ζ⟧×⊖⊟κ÷⊖Ｘ⊟κ⊕θ⊖Ｘ²⊕θ

Calculate and loop over the bitmasks for both orientations of the rectangle at this position.

Ｆυ

Loop over the grid layouts found so far.

Ｆ⁼κ＆λκ

If the rectangle can be placed at this position...

⊞υ⁻λκ

... then add a new layout with the updated grid.

ＵＭυΣ⍘ι²

Calculate the number of squares left on each grid.

Ｉ÷⁻⌈υ⌊υΠζ

Divide the difference between the maximum (i.e. the original area of the grid) and minimum by the area of the rectangle.

Answer 3

Python3, 460 bytes:

R=range
S=lambda x,y:[(X,Y)for X in R(x)for Y in R(y)]
def L(m,X,Y,w,h):
 m=eval(str(m))
 for x,y in S(X,Y):
  if 0==m[y][x]and Y-y>=h and X-x>=w:
   for j,k in S(h,w):
    if m[y+j][x+k]:return
    m[y+j][x+k]=1
   return m
def f(a,b):
 m=[[0 for _ in R(a[0])]for _ in R(a[1])]
 q,s,l=[(m,0)],[],[]
 while q:
  m,c=q.pop(0);l+=[c]
  if(t:=L(m,*a,*b))and t not in s:q+=[(t,c+1)];s+=[t]
  if(t:=L(m,*a,*b[::-1]))and t not in s:q+=[(t,c+1)];s+=[t]
 return max(l)

Try it online!

Answer 4

Jelly, 22 bytes

Rṡ"p/⁺€ɗⱮṚƬ}ẎŒPẎQƑ$ƇṪL

A dyadic Link that accepts the large rectangle dimensions, [M, N], on the left and the small rectangle dimensions, [A, B], on the right and yields the maximal count.

Try it online! Too slow to complete on TIO for any other test case.

How?

Dumb brute-force...
Creates all possible sub-rectangles where each one is a list of the cell coordinates it covers in the \$M\$ by \$N\$ rectangle. Then filters the collection of every possible set of distinct sub-rectangles keeping only those with no overlap (repeated coordinate) and outputs the length of (one of) the longest one(s).

Rṡ"p/⁺€ɗⱮṚƬ}ẎŒPẎQƑ$ƇṪL - Link: [M, N]; [A, B]
R                      - range -> [[1..M], [1..N]]
           }           - use right argument, [A, B], with:
          Ƭ            -   collect up until no change applying:
         Ṛ             -     reverse
                           -> [[A, B], [B, A]] ...or [[A, B]] if A==B 
        Ɱ              - map - i.e. for [i,j] in those apply:
       ɗ               -   last three links as a dyad - f([[1..M], [1..N]], [i,j]):
  "                    -     zip with - i.e. [f(l=[1..M], r=i), f(l=[1..N], r=j)]:
 ṡ                     -       all sublists of l of length r
    /                  -     reduce by:
   p                   -       Cartesian product
      €                -     for each:
     ⁺                 -       repeat (reduce by Cartesian product)
            Ẏ          - tighten -> all possible A by B or B by A sub-rectangles
                                    as 1-indexed coordinates
             ŒP        - powerset (Note: elements cardinality is non-decreasing)
                   Ƈ   - filter keep those for which:
                  $    -   last two links as a monad:
               Ẏ       -     tighten
                 Ƒ     -     is invariant under?:
                Q      -       deduplicate (i.e. we keep those with no overlap)
                    Ṫ  - tail (the/one way to maximise small rectangles)
                     L - length