Simplest Tiling of the Floor

Question

You should write a program or function which receives a string describing the floor as input and outputs or returns the area of the simplest meta-tiling which could create the given pattern of the floor.

The floor is a part of a square grid. Every square tile is colored either azure or black (represented by a and b in the input).

An example floor:

  aaaa
ababab
aaaaa

A meta-tiling

• is built from an N by M rectangular meta-tile of azure and black squares
• the used meta-tiles are identical up to translation (you cannot rotate or mirror them)
• if the sides of two meta-tiles are connected they should connect along their whole length (i.e. meta-tiles tile the space in a grid-like fashion)

An example meta-tile:

ba
aa

and the meta-tiling created by it:

       .
       .
       .
    babababa
    aaaaaaaa
... babababa ...
    aaaaaaaa    
    babababa
    aaaaaaaa
       .
       .
       .

This meta-tiling creates the upper shown floor as the left letters show:

       .
       .
       .
    ********
    ***aaaa*
... *ababab* ...
    *aaaaa**    
    ********
    ********
       .
       .
       .

A meta-tiling is simpler than another if the area of its meta-tile is smaller. Our example has an area of 2*2 = 4 which is the smallest possible for the example floor. So the output should be 4 for the example.

Input

• A string consisting of the characters a b space and newline containing at least one a or b.
• The letters (ab) form one 4-connected (side-by-side connected) shape.
• There will be no unnecessary spaces at the front of the rows i.e. there will be at least one row starting with a or b.

• You can choose of two input format:

  • No unnecessary whitespace at the end of rows (as seen in the examples).
  • Spaces on the right side of the rows to make all rows the same length as the longest row.

• Trailing newline is optional.

Output

• A single integer, the area of the smallest possible meta-tile whose tiling contains the input floor.

Examples

Examples are delimited by dashes. The three parts of an example are input, output and one of the possible smallest meta-tiles.

a

1

a
-----------------
 aaaa
aaa
a

1

a
-----------------
aabaab
abaa
aaba

6

aab
aba
-----------------
aabaab
a  a a
aabab

18

aabaab
aaaaaa
aababa
-----------------
ba
aaab

8

baaa
aaab
-----------------
 aaaa
ababb
aaaa

10

aaaaa
ababb
-----------------
 a aa
ab ba
 aba

6

aa
ab
ba
-----------------
 aaaa
abab
aaaa

4

aa
ab
-----------------
ba
 ba
  b

4

ba
ab
-----------------
baa
aba
aab

9

baa
aba
aab
-----------------
 aaaa
aabaa
aaaa

6

aaa
aab

This is code golf so the shortest entry wins.

Answer 1

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 a return when 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 if enumerates valid meta-tile width/height combinations for size q.
• A character array matching the candidate meta-tile size is zero-initialized.
• Inner loop iterates over all tiles in the floor.
• u is the index in the meta-tile that corresponds to the floor tile.
• If both floor tile and meta-tile tile are a or b and different (sum of a = 97 and b = 98 is 195), there is a mismatch, and the meta-tile size with the attempted dimensions will not work.
• Otherwise, if the floor tile is a or b, 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