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
T which are combined to place the tiles with relative offsets of
aS + bT for all
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 code-golf, so the shortest program wins!