Najprostsze płytki podłogowe

Powinieneś napisać program lub funkcję, która odbiera ciąg opisujący podłogę jako dane wejściowe i wyjściowe lub zwraca obszar najprostszego metapłytki, który mógłby stworzyć dany wzór podłogi.

Podłoga jest częścią kwadratowej siatki. Każda kwadratowa płytka ma kolor lazurowy lub czarny (reprezentowany przez ai bna wejściu).

Przykładowa podłoga:

  aaaa
ababab
aaaaa

Meta-płytki

• zbudowana jest ze związku No Mprostokątnym meta-dachówki lazur i czarne kwadraty
• używane metapłytki są identyczne do tłumaczenia (nie można ich obracać ani kopiować)
• jeśli boki dwóch metapłytek są połączone, powinny łączyć się na całej długości (tj. metapłytki kafelkami przestrzeń w sposób podobny do siatki)

Przykładowy metapłytek:

ba
aa

i utworzony przez niego metapłytek:

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

Ten metapłytek tworzy pokazaną górną podłogę, ponieważ lewe litery pokazują:

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

Metapłytek jest prostszy niż inny, jeśli powierzchnia jego metapłytki jest mniejsza. Nasz przykład ma powierzchnię, 2*2 = 4która jest najmniejszą możliwą dla przykładowej podłogi. Wynik powinien być 4na przykład.

Wejście

• Ciąg składający się ze znaków a b spacei newlinezawierający co najmniej jeden alub b.
• Litery ( ab) tworzą jeden 4-połączony (połączony obok siebie) kształt.
• Z przodu wierszy nie będzie niepotrzebnych miejsc, tzn. Co najmniej jeden rząd będzie zaczynać się od alub b.

• Możesz wybrać dwa formaty wejściowe:

  • Brak niepotrzebnych białych znaków na końcu wierszy (jak pokazano w przykładach).
  • Odstępy po prawej stronie rzędów, aby wszystkie rzędy miały taką samą długość jak najdłuższy rząd.

• Końcowy znak nowej linii jest opcjonalny.

Wynik

• Pojedyncza liczba całkowita, obszar najmniejszej możliwej metapłytki, której kafelki zawierają podłogę wejściową.

Przykłady

Przykłady są rozdzielane myślnikami. Trzy części przykładu to wejście, wyjście i jedna z najmniejszych możliwych metapłytek.

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

To jest golf golfowy, więc wygrywa najkrótszy wpis.

C - 208 bajtów

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;}}

Kod ekwiwalentny przed golfem:

#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;
                }
            }
        }
    }
}

Algorytm jest dość brutalny, więc powinno być dość oczywiste, jak działa na podstawie kodu. Oto kilka komentarzy:

• Oczekuje się, że dane wejściowe będą miały formę ze spacjami końcowymi, dzięki czemu wszystkie linie będą miały tę samą długość.
• Pierwsza pętla znajduje szerokość, szukając pierwszego znaku nowej linii.
• Pętla zewnętrzna jest ponad potencjalnymi rozmiarami metapłytek q. Wychodzi z returnmeta-płytką, która może pokryć podłogę. Zauważ, że pętla nie potrzebuje innego warunku wyjścia, ponieważ zawsze istnieje rozwiązanie (najgorszym przypadkiem jest rozmiar danych wejściowych).
• Pierwsza zagnieżdżona pętla, a następnie ifwylicza prawidłowe kombinacje szerokości / wysokości metapłytki dla rozmiaru q.
• Tablica znaków pasująca do rozmiaru potencjalnego meta-kafelka jest inicjowana zerem.
• Wewnętrzna pętla przechodzi przez wszystkie płytki w podłodze.
• u to indeks meta płytki, który odpowiada kafelkowi podłogi.
• Jeśli zarówno płytka podłogowa, jak i płytka z metapłytkami są alub są bróżne (suma a = 97i b = 98jest 195), występuje niezgodność, a rozmiar metapłytki z próbowanymi wymiarami nie będzie działać.
• W przeciwnym razie, jeśli płytka podłogowa jest alub b, kolor płytki jest kopiowany do kandydującej metapłytki.
• Zwraca rozmiar metapłytki po pomyślnym dopasowaniu, tj. Jeśli próba dopasowania nie została oznaczona jako nieudana.

Zastosowany kod testowy:

#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;
}

Wynik:

1
1
6
18
8
10
6
4
4
9
6