4
\$\begingroup\$

Challenge

Given a rectangular area arrange a group of rectangles such that they cover the rectangular area entirely.

Input

  • An integer denoting the height.

  • An integer denoting the width.

  • The dimensions of the rectangles consisting of the following form: axb,cxd,... where a,b,c, and d are integers - any reasonable format is acceptable.

Output

An exact cover of the rectangular area.

Rectangles used to cover the area are represented in the following way:

2x3

00
00
00

or

000
000

1x3

0
0
0

or

000

Each rectangle is represented using a character 0-9 where 0 is used for the first rectangle inputted 1 for the second and so on. The max number of rectangles given in input is therefore 10.

Test Cases

Input 1

5
7
4x2,3x2,3x2,5x2,5x1

Output 1

0000111
0000111
2233333
2233333
2244444

Input 2

4
4
3x2,2x1,2x2,2x2

Output 2

0001
0001
2233
2233

Input 3

2
10
4x2,3x2,3x2

Output 3

0000111222
0000111222

Clarifications

  • The dimensions of the rectangles used to cover the region are interchangeable e.g. for axb a could be the height or width same goes for b.
  • If there are multiple solutions any of them is acceptable (just display 1).
  • Assume all inputs are valid.
  • You can have a full program or a function (inputs may be treated broadly as 3 separate arguments).
  • Output to stdout (or something similar).
  • This is so shortest answer in bytes wins.
\$\endgroup\$
  • \$\begingroup\$ How do you handle cases with no solution/invalid input? \$\endgroup\$ – Julian Lachniet May 20 '17 at 23:46
  • \$\begingroup\$ @JulianLachniet all inputs are assumed to be valid. I'll add this to post. \$\endgroup\$ – Bobas_Pett May 20 '17 at 23:48
  • \$\begingroup\$ @JonathanAllan edited in "Clarifications" not sure if that's sufficient, if not I can try again. \$\endgroup\$ – Bobas_Pett May 21 '17 at 0:27
  • \$\begingroup\$ @JonathanAllan I could paste in an edit if you have one. Sorry for the annoyance. \$\endgroup\$ – Bobas_Pett May 21 '17 at 0:44
  • 1
    \$\begingroup\$ @JonathanAllan yeah that's great. Thanks \$\endgroup\$ – Bobas_Pett May 21 '17 at 0:50
1
\$\begingroup\$

Python 3, 262 bytes

from numpy import*
def g(h,w,t,m,i):
 if[]==t:print(m);return
 u,v=t[0]
 for _ in'12':
  for r,c in argwhere(m<0):
   if(m[r:r+u,c:c+v]<0).all()and u+r<=h and v+c<=w:e=copy(m);e[r:r+u,c:c+v]=i;g(h,w,t[1:],e,i+1)
  u,v=v,u
f=lambda h,w,t:g(h,w,t,zeros((h,w))-1,0)

Called like: f(4,4,[(3,2),(2,1),(2,2),(2,2)]). It uses a brute force, recursive function that prints all solutions (uses fewer bytes).

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