How should I tile my kitchen?

Question

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 code-golf, so the shortest program wins!

Answer 1

APL (Dyalog Unicode), 193 bytes

{G←{⍵⊃⍨⊃⍋(+/' '=,)¨⍵}
G{s←,30-⍳,⍨61
G,⊢∘⊂⌺30 30⊢((≢a)/⍪' '~⍨,x)@(B∘.+a)⊢''⍴⍨(⍴b)+⊃⌈/a←(⊢-⌊/)(⊃+/)¨s×⊂⍵}¨o/⍨(⍱/X∊⍨+/,-/)¨o←,∘.,⍨⊂¨∪{⍵/⍨0<2⊥¨×⍵}(,B∘.-⍸b<(1∊⊢)⌺3 3⊢b)~X←,B∘.-B←⍸b←(⍉0,⌽)⍣4⊢' '≠x←⍵}

Try it online!

A monadic dfn that takes a matrix of characters and returns the 30-by-30 matrix of a possible tiling with minimal blanks. Runs in 5 seconds for the smallest test case and in under a minute for the last one.

The idea

The task looks pretty straightforward at first glance, but it was surprisingly hard to derive a valid solution, and even harder to get one that "runs in a reasonable amount of time" (which somewhat explains why it was unanswered so far).

The first obstacle was that there are infinitely many possible tiling vectors. I solved this by limiting the vectors to the ones where the original tile and the moved tile share at least a point. If ab is the given tile, this means the following movements are considered as tiling vector candidates:

                                        AB   AB  AB  AB   AB
ABab    ab   ab  ab  ab   ab    abAB  ab    ab   ab   ab    ab
      AB    AB   AB   AB    AB

Then I filter out redundant ones (keeping only one of \$v\$ or \$w\$ when \$v = -w\$), generate all possible pairs of these candidate tiling vectors, and only keep the ones \$v, w\$ where neither \$v+w\$ nor \$v-w\$ movement overlaps with the original tile.

Reasoning: We know that the pairs of tiles at offsets \$(0, v)\$ and \$(0, w)\$ do not overlap, and therefore \$(v, v+w)\$ and \$(w, v+w)\$. Once it is known that \$(0, v+w)\$ and \$(v, w)\$ (alternatively \$(0, v-w)\$) pairs are safe, we know that \$(0, v, w, v+w)\$ are mutually safe, and by translation in four directions \$v, w, -v, -w\$, the entire infinite tiling is safe.

Given a full list of candidate vector pairs, I chose a naive way: for each vector pair, generate a large enough board of actual tiling, extract all 30-by-30 regions, and choose the one with the smallest number of blanks. For that, I used \$-30 \le a,b \le 30\$ for the formula \$av + bw\$. In order to prevent the memory (and execution time) blowing up, I apply this filtering twice, first within each vector pair, and then across all minimally chosen boards.

Ungolfed

The code changed a lot while golfing, but the core idea remains the same.

f←{
  ⍝ A boolean matrix where 1 means non-blanks, padded once to all directions
  bool←(⍉0,,∘0)⍣2⊢' '≠x←⍵
  ⍝ Spread 1s to adjacent cells (8 directions)
  padded←({1∊⍵}⌺3 3>⊢)bool
  ⍝ Extract the coordinates of ones
  cbool←⍸bool
  cpadded←⍸padded
  ⍝ badoffs: All offsets that move a cell to already occupied cell
  ⍝ offs: All offsets that move a cell to a cell adjacent to the tile,
  ⍝       badoffs removed and (negative, any) and (zero, negative) removed
  offs←∪{⍵/⍨0<2⊥¨×⍵}(,cbool∘.-cpadded)~badoffs←,cbool∘.-cbool
  ⍝ Pairs of valid offsets
  offpairs←,∘.,⍨⊂¨offs
  ⍝ Remove offset pairs (v,w) if v+w or v-w is bad
  filter←{⍱/(⍺+⍵)(⍺-⍵)∊badoffs}/¨offpairs
  pairs←filter/offpairs

  ⍝ Aux. function: Select the matrix with smallest number of blanks
  MinBlanks←{⍵⊃⍨⊃⍋(+/' '=,)¨⍵}
  ⍝ Aux. function: Given an offset pair, tile the floor using them and
  ⍝                extract the 30x30 region with minimum blanks
  GetResults←{
    somepair←⍵
    ⍝ -30 to 30, inclusive (the values of a and b)
    steps←30-⍳61
    ⍝ All values of av + bw, offset to the minimum coordinates of (0,0)
    alloffs←⊃{,(steps×⊂⍺)∘.+steps×⊂⍵}/somepair
    alloffs-←⌊/alloffs
    ⍝ Initialize a big enough blank grid
    dims←(⍴bool)+⊃⌈/alloffs
    grid←dims⍴''
    ⍝ Fill the grid with the tiles' cells moved accordingly
    filled←((≢alloffs)/⍪' '~⍨,x)@(cbool∘.+alloffs)⊢grid
    ⍝ Extract all 30x30 regions and return the one with minimum blanks
    results←,{⊂⍵}⌺30 30⊢filled
    MinBlanks results
  }
  ⍝ Map the above function over each of the pairs, and extract min blanks
  results←GetResults¨pairs
  MinBlanks results
}