Simplest Tiling of the Floor
C - 208 bytes
w,q,n,m,r,g,u;t(char*f){for(w=0;f[w++]-10;);for(q=1;;q++)for(n=1;m=q/n,n<=q;++n)if(n*m==q){char t[q];bzero(t,q);r=q;for(g=0;f[g];++g){u=g/w%m*n+g%w%n;r=t[u]+f[g]-195?r:0;if(f[g]&64)t[u]=f[g];}if(r)return r;}}
Equivalent code before golfing:
#include <stdio.h>
#include <strings.h>
int t(char* f) {
int w = 0;
for ( ; f[w++] - 10; );
for (int q = 1; ; q++) {
char t[q];
for (int n = 1; n <= q; ++n) {
int m = q / n;
if (n * m == q) {
bzero(t, q);
int r = q;
for (int g = 0; f[g]; ++g) {
int u = g / w % m * n + g % w % n;
if (t[u] + f[g] == 195) {
r = 0;
}
if (f[g] & 64) {
t[u] = f[g];
}
}
if (r) {
return r;
}
}
}
}
}
The algorithm is fairly brute force, so it should be reasonably obvious how it works based on the code. Here are a few comments anyway:
- Input is expected to have the form with trailing spaces so that all lines have the same length.
- First loop finds the width by looking for first newline character.
- Outer loop is over candidate meta-tile sizes
q. Exits with areturnwhen a meta-tile can cover the floor. Note that the loop does not need another exit condition since there is always a solution (worst case is size of input). - First nested loop and following
ifenumerates valid meta-tile width/height combinations for sizeq. - A character array matching the candidate meta-tile size is zero-initialized.
- Inner loop iterates over all tiles in the floor.
uis the index in the meta-tile that corresponds to the floor tile.- If both floor tile and meta-tile tile are
aorband different (sum ofa = 97andb = 98is195), there is a mismatch, and the meta-tile size with the attempted dimensions will not work. - Otherwise, if the floor tile is
aorb, the tile color is copied to the candidate meta-tile. - Returns size of meta-tile when successful match was made, i.e. if the attempted match was not marked as failed.
Test code used:
#include <stdio.h>
extern int t(char* s);
int main()
{
printf("%d\n", t(
"a\n"
));
printf("%d\n", t(
" aaaa\n"
"aaa \n"
"a \n"
));
printf("%d\n", t(
"aabaab\n"
"abaa \n"
"aaba \n"
));
printf("%d\n", t(
"aabaab\n"
"a a a\n"
"aabab \n"
));
printf("%d\n", t(
"ba \n"
"aaab\n"
));
printf("%d\n", t(
" aaaa\n"
"ababb\n"
"aaaa \n"
));
printf("%d\n", t(
" a aa\n"
"ab ba\n"
" aba \n"
));
printf("%d\n", t(
" aaaa\n"
"abab \n"
"aaaa \n"
));
printf("%d\n", t(
"ba \n"
" ba\n"
" b\n"
));
printf("%d\n", t(
"baa\n"
"aba\n"
"aab\n"
));
printf("%d\n", t(
" aaaa\n"
"aabaa\n"
"aaaa \n"
));
return 0;
}
Output:
1
1
6
18
8
10
6
4
4
9
6
APL (Dyalog Unicode), 53 bytes
{⌊/×/¨⍸{∧/,⍲/¨'ab'∘∊¨⊃{⍉,⌿↑⍺⊂⍵}/(⊂,⍨⍴⍴¨⍺↑¨≡)⍵}∘⍵¨⍳⍴⍵}
Try it online!
A function that takes a character matrix as the argument. Basically, tries all possible tile sizes, testing if partitioning by that size would give at most one of ab on every cell.
Illustration
Example input:
a aa
ab ba
aba
Example tile size: 2 rows, 2 columns
Partition:
+--+--+-+
| a| a|a|
|ab| b|a|
+--+--+-+
| a|ba| |
+--+--+-+
Cells collected into a tile:
+------+------+
| a b |aa aa |
+------+------+
|a a |bb |
+------+------+
Since top left cell has both a and b, this tile size is invalid.
How the code works
{⌊/×/¨⍸{∧/,⍲/¨'ab'∘∊¨⊃{⍉,⌿↑⍺⊂⍵}/(⊂,⍨⍴⍴¨⍺↑¨≡)⍵}∘⍵¨⍳⍴⍵}
⍝ ⍵ ← Char matrix
⍳⍴⍵ ⍝ Generate possible tile sizes as a matrix of length-2 vectors
{...}∘⍵¨ ⍝ Test if each tile size is valid...
⍝ ⍵ ← Input char matrix, ⍺ ← tile size
(⊂,⍨⍴⍴¨⍺↑¨≡)⍵ ⍝ Create partition vectors and join with ⍵ for RTL reduction
( ≡)⍵ ⍝ Depth of ⍵, which always gives 1 for valid input
⍺↑¨ ⍝ Overtake 1 to the length of each of ⍺, e.g. (1 0)(1 0 0)
⍴⍴¨ ⍝ Cycle each to the length of the dimensions of ⍵,
⍝ e.g. (1 0 1 0 1)(1 0 0 1 0)
⊂,⍨ ⍝ Append the enclosed ⍵
⊃{⍉,⌿↑⍺⊂⍵}/ ⍝ Partition and collect all cells at the same position in the tile
{ }/ ⍝ Reduce by...
⍺⊂⍵ ⍝ Partition ⍵ into consecutive columns at 1s of ⍺
↑ ⍝ Mix so that short partition is padded with spaces
,⌿ ⍝ Collect the cells at the same position
⍉ ⍝ Transpose to do the same for rows
⊃ ⍝ Disclose one level of nesting (which is a side effect of /)
∧/,⍲/¨'ab'∘∊¨ ⍝ Test if no tile position contains both a and b
'ab'∘∊¨ ⍝ For each tile position, evaluate (has a)(has b)
⍲/¨ ⍝ Reduce each by NAND; 1 if the tile position has at most one of ab
∧/, ⍝ Test if it is true for all positions
⌊/×/¨⍸ ⍝ Extract the answer (the smallest area)
⍸ ⍝ 1-based coordinates of ones; the tile sizes which passed the test
⌊/×/¨ ⍝ Minimum of the areas
Husk, 30 bytes
ḟ(SδV(ΛË←k→f←δṁz,¶⁰¤Ṫeo¢ḣ)↔Ḋ)1
Try it online!
Explanation
I loop through all nonnegative integers until I find one that, when split into two factors in some way, gives a horizontal and vertical period for the input patch. The period is checked by grouping the 2D indices of non-space characters by their values modulo the two numbers, and checking that each group contains equal characters.
ḟ(…)1 Starting from 1, find a number that satisfies (…).
SδV(…)↔Ḋ We're looking at a number, say n=6.
Ḋ Divisors: d = [1,2,3,6]
S ↔ Reverse and apply to both:
δV(…) does any pair from d and its reverse satisfy (…)?
For n=6, the pairs are (1,6), (2,3), (3,2), and (6,1).
ΛË←k→f←δṁz,¶⁰¤Ṫeo¢ḣ Check if (a,b) is a valid metatile.
¤ For both a and b:
ḣ take range from 1 to it
o¢ and cycle it infinitely.
Ṫ Combine these by taking outer product by
e pairing.
For (a,b)=(2,3), this gives the infinite 2D array
A=[[[1,1],[1,2],[1,3],[1,1],..],
[[2,1],[2,2],[2,3],[2,1],..],
[[1,1],[1,2],[1,3],[1,1],..],
..]
¶⁰ The input, split at newlines.
δṁ For each row of it and A:
z, zip them (discarding overflowing rows and pairs of A)
δṁ and concatenate the results.
Now we have a list of pairs like ('a',[2,3]) that contain
a character from the input and its coordinates mod (a,b).
f← Keep those whose left part is truthy, i.e. not a space.
k→ Classify (into separate lists) by right part.
Λ Does every class
Ë← have all equal left parts?