Contando gemas

Antecedentes

¡Mi joyero se cayó! Hay demasiadas gemas de diferentes formas en el suelo. Y su tarea es contar el número de un cierto tipo de gema.

I / O

Su código debe tener dos entradas Sy G, que podría ser una cadena con líneas nuevas, una matriz de líneas, una matriz bidimensional de caracteres, un archivo de texto o en cualquier formato razonable (si es así, indíquelo claramente).
Estas dos cadenas solo contendrán !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~(de 0x21a 0x7Een la tabla ASCII), espacio y nuevas líneas (forma binaria dependiendo de su plataforma).
En cada cadena, las líneas tienen la misma longitud.
Ses la gema que queremos contar. Hay dos circunstancias
1. Cerrado y no contiene ningún área cerrada anidada. (en el ejemplo 1/2)
2. No contiene ningún área cerrada. (en el ejemplo 3/4)
Los espacios circundantes no se consideran parte de la gema.
G Es la forma de gemas en el suelo.
Es aceptable que su código requiera una entrada adicional para especificar las dimensiones de SyG
Es aceptable que su código tome valores ASCII como entradas, en lugar de los propios caracteres. Sin embargo, usted debe no sustituir caracteres con números enteros simples (0,1,2,3). Su programa debe poder procesar caracteres o valores ASCII.

Ejemplo 1 (Carácter como entrada)

Entrada S:

+-+  
| +-+
| | |
| | |
| +-+
+-+

Entrada G:

    +-+       +-+
    | +-+   +-+ |
    | | |   | | |
    | | |   | | |
    | +-+   +-+ |
    +-+       +-+
         +-+     
+---+    | +-+   
|   |    | | |   
|   |    | | |   
|   |    | +-++  
|   |    +-+| +-+
+---+       | | |
            | | |
  +-+       | +-+
  | +-+     +-+  
  | |-|          
  | |-|          
  | +-+          
  +-+

Ouptut:

Ejemplo 2 (valor ASCII como entrada)

Entrada S:

32 32 32 32 32 32 32 32
32 32 32 32 99 32 99 32
32 32 32 99 32 99 32 99
32 32 32 99 32 32 32 99
32 32 32 99 32 32 32 99
32 32 32 99 32 32 32 99
32 32 32 32 99 32 99 32
32 32 32 32 32 99 32 32
32 32 32 32 32 32 32 32

Entrada G:

32 99 32 99 32 99 32 99 32 32 99 32
99 32 99 32 99 32 99 32 99 99 32 99
99 32 32 32 99 32 32 32 99 32 32 99
99 99 32 32 99 32 32 32 99 32 32 99
99 32 32 32 99 32 32 32 99 32 32 99
32 99 32 99 32 99 32 99 99 32 99 32
32 32 99 32 32 32 99 32 32 99 32 32

Salida:

Visualizado S(32 reemplazado con -):

-- -- -- -- -- -- -- --
-- -- -- -- 99 -- 99 --
-- -- -- 99 -- 99 -- 99
-- -- -- 99 -- -- -- 99
-- -- -- 99 -- -- -- 99
-- -- -- 99 -- -- -- 99
-- -- -- -- 99 -- 99 --
-- -- -- -- -- 99 -- --
-- -- -- -- -- -- -- --

Visualizado G:

-- 99 -- 99 -- 99 -- 99 -- -- 99 --
99 -- 99 -- 99 -- 99 -- 99 99 -- 99
99 -- -- -- 99 -- -- -- 99 -- -- 99
99 99 -- -- 99 -- -- -- 99 -- -- 99
99 -- -- -- 99 -- -- -- 99 -- -- 99
-- 99 -- 99 -- 99 -- 99 99 -- 99 --
-- -- 99 -- -- -- 99 -- -- 99 -- --

Ejemplo 3 (no incluido)

Gracias a @ Draco18s

Entrada S

AB

Entrada G

AAB BA CAB

Salida

Ejemplo 4 (2D no incluido)

Entrada S

ABCD
  GE
   F

Entrada G

ABCD 
BGGED
CDEFE
    F

Salida

Observaciones

Solo dos gemas de una forma exacta se consideran iguales.
La misma forma en diferentes direcciones no se considera igual.
Sin embargo, como se describe en el ejemplo de E / S, es posible la superposición. En tales circunstancias, solo se cuentan las completas.
+, -y |en el ejemplo no tienen significados especiales. No indican ninguna esquina o borde de la forma.
Puede suponer que la entrada siempre es válida.
Puede suponer que dos gemas objetivo nunca comparten exactamente el mismo borde.
Las lagunas estándar están prohibidas.
Este es un código de golf, por lo que gana el código más corto.

code-golf string array-manipulation Keyu Gan
fuente

No entiendo el segundo ejemplo, ¿cómo está Gcontenido dentro S?

LiefdeWen

@LiefdeWen Lo hice visualizado, puede encontrar Sen el medio de G.

Keyu Gan

Creo que se necesitan algunos ejemplos más simples aquí, tales como S = "AB", G=" AAB BA CAB", = salida?

Draco18s ya no confía en SE

@ Draco18s Gracias, lo agregaré.

Keyu Gan

Ese simple ejemplo realmente ayudó a comprender el comportamiento deseado. Genial

Draco18s ya no confía en SE

C (gcc) , 303305 326 bytes

Todas las optimizaciones deben desactivarse y solo funcionan en GCC de 32 bits.

#define r(z,k)for(z=0;z<k;z++)
#define c s[i][j]
x,y,o,p,t,i,j;char**s;h(i,j){!((i<0)+(j<0)+i/x+j/y+c-32)?h(i+1,j),h(i-1,j),h(i,j+1),h(i,j-1),c=0:0;}f(w,e,u,v,a,g)char**a,**g;x=w,y=e,s=a;r(o,x)h(o,0),h(o,y-1);r(p,y)h(0,p),h(x-1,p);w=0;r(o,u-x+1)r(p,v-y+1){t=1;r(i,x)r(j,y)t*=!(c*(c-g[i+o][j+p]));w+=t;}}

El código utiliza el relleno de inundación para reemplazar los espacios circundantes \0y busca coincidencias mientras se ignora \0.

sin golf y macros calculados (algunas letras son diferentes de la versión golfizada, pero la lógica sigue siendo la misma):

int x, y, o, p, c, d, t;
char **s, **g;
h(int i, int j) {                             // Floodfill function
    if(i<0 || j<0) return;                    // Boundary detection
    if(i>=x || j>=y) return;
    if(s[i][j] != ' ') return;                // Character detection

    s[i][j] = 0;                              // Replace it with \0
    h(i+1, j);
    h(i-1, j)
    h(i  , j+1);
    h(i  , j-1);
}
f(
    int w,    //1st dimension of S
    int e,    //2nd dimension of S
    int u,    //1st dimension of G
    int v     //2nd dimension of G
    char** i, //Input S
    char** j, //Input G
    );
{
    x=w,y=e,s=i,g=j;
    for(o=0; o<x; o++)                        // Replace all surrounding spaces using floodfill
    {
        h(o, 0);                               
        h(o, y-1);
    }
    for(p=0; p<y; p++)
    {
        h(0,   p);
        h(x-1, p);
    }
    w = 0;
    for(o=0; o<=u-x; o++)                     // Main O(w*e*u*v) matching process
        for(p=0; p<=v-y; p++) {
            t=1;
            for(c=0; c<x; c++)
                for(d=0; d<y; d++)
                if(s[c][d]*(s[c][d]-g[c+o][d+p]))
                    t=0;
            w+=t;
        }
}

Keyu Gan
fuente

Contando gemas en el suelo