8
\$\begingroup\$

Counting Gems

Background

My jewel box just fell down! There're too many gems of different shape on the ground. And your task is to count number of a certain type of gem.

I/O

  • Your code should take two inputs S and G, which could be a string with newlines, an array of lines, a two-dimensional array of characters, a textfile or in any reasonable format (if so, please state it clearly).
  • These two strings will only contain !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ (from 0x21 to 0x7E in ASCII table), space and newlines (binary form depending on your platform).
  • In each string, lines are in same length.
  • S is the gem we want to count. There're two circumstances.
    1. Enclosed and doesn't contain any nested enclosed area. (in example 1/2)
    2. Doesn't contain any enclosed area. (in example 3/4)
  • Surrounding spaces are not regarded as a part of the gem.
  • G is the shape of gems on the ground.
  • It is acceptable that your code requires extra input to specify the dimension(s) of S and G
  • It is acceptable that your code take ASCII values as inputs, instead of characters themselves. But you should not substitute characters with simpler integers (0,1,2,3). Your program should be able to process characters, or ASCII values.

Example 1 (Character as input)

Input S:

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

Input G:

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

Ouptut:

2

Example 2 (ASCII value as input)

Input 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

Input 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

Output:

1

Visualized S (32 replaced with --):

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

Visualized 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 -- --

Example 3 (Not enclosed)

Thanks to @Draco18s

Input S

AB

Input G

AAB BA CAB

Output

2

Example 4 (Not enclosed 2D)

Input S

ABCD
  GE
   F

Input G

ABCD 
BGGED
CDEFE
    F

Output

1

Remarks

  • Only two gems of exact one shape are considered the same.
  • Same shape in different directions are not considered the same.
  • However, as is described in example I/O, overlapping is possible. Under such circumstances, only complete ones are counted.
  • +, - and | in the example have no special meanings. They do not indicate any corner or edge of the shape.
  • You may assume input is always valid.
  • You may assume two target gems never share an exactly same edge.
  • Standard loopholes are forbidden.
  • This is a code-golf, so shortest code wins!
\$\endgroup\$
  • 2
    \$\begingroup\$ I don't understand the second example, how is G contained within S? \$\endgroup\$ – LiefdeWen Jun 22 '17 at 13:58
  • \$\begingroup\$ @LiefdeWen I made it visualized, you may find S in the middle of G. \$\endgroup\$ – Keyu Gan Jun 22 '17 at 14:36
  • \$\begingroup\$ I think some simpler examples are needed here, such as S = "AB",G=" AAB BA CAB", output = ? \$\endgroup\$ – Draco18s Jun 22 '17 at 20:23
  • \$\begingroup\$ @Draco18s Thank you, i will add it. \$\endgroup\$ – Keyu Gan Jun 23 '17 at 5:11
  • \$\begingroup\$ That simple example really helped understand the desired behavior. Cool \$\endgroup\$ – Draco18s Jun 23 '17 at 13:38
1
\$\begingroup\$

C (gcc), 303 305 326 bytes

All optimizations need to be turned off and only work on 32-bit GCC.

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

The code uses floodfill to replace surrounding spaces with \0 and looks for matches while ignoring \0.

ungolfed and macros calculated (some letters are different from the golfed version, but logic stays the same):

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;
        }
}
\$\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.