14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ @Ypnypn Every corner has to touch 3 other corners (except the meta-tiles on the edge of the tiling). I stated it as "if the sides of two meta-tiles are connected they should connect along their whole length". So your given example is illegal. \$\endgroup\$ – randomra May 15 '15 at 17:48
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
+200
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Pip -r, 52 bytes

MN:$*_M{$&{$*$Q*$.aDCs}M_UWa@1MMyUW@a}FI\,#gCP\,#@Yg

Takes input from lines of stdin, with trailing spaces as needed. Try it online!

Approach taken from Bubbler's APL answer: We try all possible meta-tile dimensions, filtering for the ones that have a unique non-space character at each position. UW (unweave) is very useful for grouping the input grid by tile positions. We then multiply each successful pair of dimensions to get the area of the tile, and take the minimum.

Leave a comment if you'd like a more detailed explanation.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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?
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Brachylog, 44 bytes

∧ℕf⟨≡z↔⟩∋[X,Y]×.&ṇġ↙Xz₁ġᵐ²↙Yz₁ᵐ²zᵐ{c;Ṣx=}ᵐ²∧

Try it online!

A port of Zgarb's Husk answer. Brachylog doesn't have infinite lists or cyclic indexing, so instead I'm using the "groups" predicate ġ ([1,2,3,4,5]ġ₂ -> [[1,2],[3,4],[5]]) and then zip z ([[1,2],[3,4],[5]]z₁ -> [[1,3,5],[2,4]]) to get lists of the characters at tile-equivalent positions.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.