14
\$\begingroup\$

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:

enter image description here

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

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!

\$\endgroup\$
3
  • \$\begingroup\$ It says they can't overlap each other, but can they touch? \$\endgroup\$
    – Steffan
    Jun 4 at 0:36
  • \$\begingroup\$ @Steffan Yes they can. \$\endgroup\$
    – badatgolf
    Jun 4 at 0:36
  • \$\begingroup\$ Not related \$\endgroup\$
    – Arnauld
    Jun 5 at 14:58

4 Answers 4

4
\$\begingroup\$

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.

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

Charcoal, 95 92 bytes

NθNη≔E²Nζ⊞υ×⊖X²θ÷⊖X²×η⊕θ⊖X²⊕θF×η⊕θF×X²ιEX²⟦ζ⮌ζ⟧×⊖⊟κ÷⊖X⊟κ⊕θ⊖X²⊕θFυF⁼κ&λκ⊞υ⁻λκUMυΣ⍘ι²I÷⁻⌈υ⌊υΠζ

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

NθNη

Input the dimensions of the grid to be filled.

≔E²Nζ

Input the dimensions of the rectangle.

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

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

F×η⊕θ

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

F×X²ιEX²⟦ζ⮌ζ⟧×⊖⊟κ÷⊖X⊟κ⊕θ⊖X²⊕θ

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

Fυ

Loop over the grid layouts found so far.

F⁼κ&λκ

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

⊞υ⁻λκ

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

UMυΣ⍘ι²

Calculate the number of squares left on each grid.

I÷⁻⌈υ⌊υΠζ

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

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

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
\$\endgroup\$
3
\$\begingroup\$

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!

\$\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.