Mosaico más simple del piso

Debe escribir un programa o función que reciba una cadena que describa el piso como entrada y salida o que devuelva el área del meta-mosaico más simple que podría crear el patrón dado del piso.

El piso es parte de una cuadrícula cuadrada. Cada mosaico cuadrado tiene un color azul o negro (representado por ay ben la entrada).

Un ejemplo de piso:

  aaaa
ababab
aaaaa

Un meta-mosaico

• se construye a partir de una Npor Mrectangular meta-baldosas de cuadrados azules y negros
• los meta-mosaicos utilizados son idénticos hasta la traducción (no puede rotarlos ni reflejarlos)
• Si los lados de dos meta-mosaicos están conectados, deben conectarse a lo largo de toda su longitud (es decir, los meta-mosaicos recubren el espacio en forma de cuadrícula)

Un ejemplo de meta-mosaico:

ba
aa

y el meta-mosaico creado por él:

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

Este meta-mosaico crea el piso superior que se muestra como muestran las letras de la izquierda:

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

Un meta-mosaico es más simple que otro si el área de su meta-mosaico es más pequeña. Nuestro ejemplo tiene un área 2*2 = 4que es la más pequeña posible para el piso de ejemplo. Entonces la salida debería ser 4para el ejemplo.

Entrada

• Una cadena que consta de los caracteres a b spacey que newlinecontiene al menos uno ao b.
• Las letras ( ab) forman una forma de 4 conectados (uno al lado del otro).
• No habrá espacios innecesarios al frente de las filas, es decir, habrá al menos una fila que comience con ao b.

• Puede elegir entre dos formatos de entrada:

  • Sin espacios en blanco innecesarios al final de las filas (como se ve en los ejemplos).
  • Espacios en el lado derecho de las filas para hacer que todas las filas tengan la misma longitud que la fila más larga.

• La nueva línea final es opcional.

Salida

• Un solo entero, el área del meta-mosaico más pequeño posible cuyo mosaico contiene el piso de entrada.

Ejemplos

Los ejemplos están delimitados por guiones. Las tres partes de un ejemplo son entrada, salida y uno de los meta-mosaicos más pequeños posibles.

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

Este es el código de golf por lo que gana la entrada más corta

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

Código equivalente antes de jugar al golf:

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

El algoritmo es bastante fuerza bruta, por lo que debería ser razonablemente obvio cómo funciona según el código. Aquí hay algunos comentarios de todos modos:

• Se espera que la entrada tenga el formulario con espacios finales para que todas las líneas tengan la misma longitud.
• El primer bucle encuentra el ancho buscando el primer carácter de nueva línea.
• El bucle externo está sobre los tamaños de meta-mosaico candidatos q. Sale con un returncuando un meta-mosaico puede cubrir el piso. Tenga en cuenta que el bucle no necesita otra condición de salida ya que siempre hay una solución (el peor de los casos es el tamaño de la entrada).
• El primer bucle anidado y a continuación ifenumera combinaciones válidas de ancho / alto de meta-mosaico para el tamaño q.
• Una matriz de caracteres que coincide con el tamaño del meta-mosaico candidato se inicializa a cero.
• El bucle interno itera sobre todas las baldosas del piso.
• u es el índice en el meta-mosaico que corresponde al piso.
• Si tanto la loseta de piso como la loseta de meta-loseta son ao son bdiferentes (suma de a = 97y b = 98es 195), hay una falta de coincidencia y el tamaño de la meta-loseta con las dimensiones intentadas no funcionará.
• De lo contrario, si la baldosa del piso es ao b, el color de la baldosa se copia en la metaplaca candidata.
• Devuelve el tamaño del meta-mosaico cuando se realizó una coincidencia exitosa, es decir, si el intento de coincidencia no se marcó como fallido.

Código de prueba utilizado:

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

Salida:

1
1
6
18
8
10
6
4
4
9
6