6
\$\begingroup\$

A while ago, I posted a challenge asking to determine whether or not it's possible to arrange arbitrary rectangles to fill a rectangular space, here. That got answers, so clearly it was too easy. (Just kidding, it was fairly challenging, congrats to the answerers :D)

Challenge

Given a bunch of arbitrary shapes (consisting of 1x1 square tiles) (up to 100 with a combined area of at most 1000), can you arrange them to fill a rectangular space, without rotations or reflections?

A shape is valid as input if it has at least 1 tile and all tiles are connected to each other by edges. For example:

Valid:

XXX
X X
XXX

Invalid:

XXX
X
 XX

The shapes will be represented in input by using a non-whitespace character X, spaces, and newlines. Individual shapes will be separated by two newlines (i.e. split on \n\n). You can choose to use LF, CR, or CRLF as a newline. Alternatively, you can choose to use LF or CR as a single newline and CRLF as a double-newline for separating shapes. Please specify in your answer what you choose.

For example, this would be the input format for a 2x2 square and a 3x3 "donut":

XX
XX

XXX
X X
XXX
(Optional trailing newline or double-newline)

The output should be either any truthy value or a consistent falsy value (but not an error). For example, you may output the valid arrangement if one exists or false, but you cannot error if there is no valid arrangement, neither can you output different values for having no valid arrangement.

Test Cases

Test Case 1

XXXX
X  X
XX X

X
X

X

TRUE

Valid Arrangement:

XXXX
XYYX
XXYX

Test Case 2

XXXX
XX

X

FALSE

Test Case 3

XXXXXX
X X  X
X XXX

XX

X
X

X

TRUE

Valid Arrangement:

XXXXXX
XYXZZX
XYXXXA

Test Case 4

XX
X

 X
XX

XXX

X
X
X

TRUE

Valid Arrangement:

XXYZ
XYYZ
AAAZ

Notes

  • Each shape must be used exactly once in the arrangement
  • Shapes may not be rotated or reflected
  • The input can contain multiple identical shapes; in this case, each of those still needs to be used exactly once; that is, if two 5x3 rectangles are given in the input, two 5x3 rectangles must appear in the arrangement
\$\endgroup\$
  • 2
    \$\begingroup\$ Can the shapes be rotated or reflected? \$\endgroup\$ – xnor Jun 11 '17 at 22:01
  • \$\begingroup\$ @xnor For the purposes of this challenge, I will say no. Thanks for noticing that; I always forget to include that. And also thanks for the tag edits :) \$\endgroup\$ – HyperNeutrino Jun 11 '17 at 23:21
  • \$\begingroup\$ I take it each shape must be used exactly once in the tiling? Can the input have multiple identical shapes? \$\endgroup\$ – xnor Jun 12 '17 at 0:32
  • \$\begingroup\$ @xnor Sorry for the missed points; yes, each shape may only be used once (hence arrangements over tilings). And yes the input can have multiple identical shapes. \$\endgroup\$ – HyperNeutrino Jun 12 '17 at 0:54
1
\$\begingroup\$

Python 2, 434 bytes

lambda s:F([[' ']*sum(map(lambda s:len(s[0]),s)) for _ in' '*sum(map(len,s))],s)
L=len
R=range
def F(a,s):
 if not s:return len(set(tuple(l)for l in a if'X'in l))==len(set(tuple(l)for l in zip(*a)if'X'in l))==1
 c=s[0];h,w=L(c),L(c[0])
 for i in R(L(a)-h):
	for j in R(L(a[0])-w):
	 T=1;A=[l[:]for l in a]
	 for y in R(h):
		for x in R(w):
		 C=c[y][x]
		 if C>' ':T&=A[y+i][x+j]<'!';A[y+i][x+j]=C
	 r=T and F(A,s[1:])
	 if r:return r

Try it online!

Takes input as a list of lists.

Returns True or None

Assumes that each line in a shape is padded to the length of that shape.

(based on my answer to Do the figures fit?)

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