# How should I tile my kitchen?

I recently ordered some new and colorful tiles to replace my boring old white tiling for my kitchen. However, when the tiles arrived, they were all in a weird shape! Therefore, I need a program to figure out how to arrange the tiles so that I need to use as few of my old boring white tiling as possible.

Even though the tiles are weird, I'm not a fan of abstract design stuff, so the tiling should be regular. To be precise, it should be a lattice: there should no rotation or reflection of the tiles, and there should be two translations S and T which are combined to place the tiles with relative offsets of aS + bT for all a and b. Of course, the tiles shouldn't overlap when placed in this lattice arrangement.

I'll give you the tile in string format, and I need you to output the tiling. You may need to cut some of the tiles where they extend beyond the edges of my kitchen. For example:

abc        abcdefabcdef
def   ->  cdefabcdefab
efabcdefabcd


can be broken down as

+-----+   +-+-----+   +-+
|a b c|d e f|a b c|d e f|
+-+   +-+---+-+   +-+---+
c|d e f|a b c|d e f|a b
+-+---+-+   +-+---+-+
e f|a b c|d e f|a b c|d
----+-+   +-----+-+   +-


where the translations are (+6, 0) and (+4, +1). All but three of the tiles have been cut in this example.

You will be given a string to tile either via function parameter or STDIN. Spaces in the tile are considered "empty" and can be filled with other tiles.

My kitchen is 30x30 squares big, so all you need to do is make the number of empty squares is as small as possible in that area. You only need to print out 1 valid 30x30 square, which means that there may not be any lattice arrangement which has a 30x30 square with fewer empty squares.

Examples (I'm not going to give the full 30x30 square for brevity):

Input:
ab
a
Output:
abaaba
baabaa
aabaab

Input:
xxx
x x y
xxx

Output:
xxxxxxxxxxx
xyxxyxxyxxy
xxxxxxxxxxx
xxxxxxxxxxx
xyxxyxxyxxy
xxxxxxxxxxx

Input:
012
3 4
56
Output:
0123 456
23 45601
4560123
5601234

Input:
rrr
R r
Output:
rrrR r
R rrrr
rrrR r

Input:
defg
c
ab
Output:
cabdefg cab
defg cabdef
g cabdefg c
abdefg cabd
efg cabdefg
cabdefg ca
bdefg cabde
fg cabdefg


Your program should run in a reasonable amount of time, and this is , so the shortest program wins!

• I'm not sure I understand the question. Are we supposed to find a lattice arrangement of the tiles which avoids overlap and contains a 30x30 area with minimum uncovered space, and then output that 30x30 area? – Peter Taylor Dec 1 '15 at 20:38
• Yes. How can I make it clearer in my post? – Nathan Merrill Dec 1 '15 at 20:44
• I'll make an edit, and if you don't like it you can roll it back. – Peter Taylor Dec 1 '15 at 21:04
• Why wouldn't the single offset (3,0) be valid in your first example? That also results in a proper lattice. – Jitse Sep 18 '19 at 7:53
• (3,0) is perfectly acceptable response. It's not as obvious what is happening unless there's also a vertical offset, which is why I did use a vertical offset :) – Nathan Merrill Sep 18 '19 at 12:50