# Fill the rectangle

## 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 , so shortest answer (in bytes) wins!

• It says they can't overlap each other, but can they touch? Jun 4, 2022 at 0:36
• @Steffan Yes they can. Jun 4, 2022 at 0:36
• Not related Jun 5, 2022 at 14:58

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

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

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


Ｆ×η⊕θ


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.

# 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!

# 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: