12
\$\begingroup\$

Given a non-empty 2D array consisting of 0 and 1, find the number of squares whose 4 corners are all 1. The squares do not need to be "upright". All the rows are guaranteed to have the same length.

Reasonable input/output methods are allowed.

Testcases:

0001000
1000000
0000000
0000100
0100000

This returns 1.

10101
00000
10100
00000
10001

This returns 2.

1111
1111
1111
1111

This returns 20.

This is . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
  • \$\begingroup\$ Another interpretation, if I'm understanding the intent: 4 1s on a square, such that each 1 is equidistant along the perimeter from its two neighbors. \$\endgroup\$ – feersum May 15 '17 at 8:42
  • \$\begingroup\$ @feersum The latter condition is true for every square, isn't it? \$\endgroup\$ – Wojowu May 15 '17 at 11:52
18
\$\begingroup\$

JavaScript (ES6), 127 124 119 bytes

Saved 3 bytes thanks to nderscore

m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n

How?

This function iterates on all pairs of cells (x, y), (X, Y) of the input matrix m such that:

  • m[ x, y ] = m[ X, Y ] = 1
  • x < X
  • y ≤ Y

Each matching pair describes the coordinates of a potential edge of a square. The inequations guarantee that each edge is tested only once.

We use the vector [ dx, dy ] = [ X - x, Y - y ] rotated 90° clockwise to test the cells located at [ x - dy, y + dx ] and [ X - dy, Y + dx ]. If they both contain a 1, we've found a valid square.

square

Test cases

let f =

m=>(F=(x,y)=>m.map((r,Y)=>r.map((i,X)=>i?1/y?n+=x<X&y<=Y&(g=(a,b)=>(m[b+X-x]||0)[a-Y+y])(x,y)&g(X,Y):F(X,Y):0)))(n=0)|n

console.log(f([
  [0,0,0,1,0,0,0],
  [1,0,0,0,0,0,0],
  [0,0,0,0,0,0,0],
  [0,0,0,0,1,0,0],
  [0,1,0,0,0,0,0]
]));

console.log(f([
  [1,0,1,0,1],
  [0,0,0,0,0],
  [1,0,1,0,0],
  [0,0,0,0,0],
  [1,0,0,0,1]
]));

console.log(f([
  [1,1,1,1],
  [1,1,1,1],
  [1,1,1,1],
  [1,1,1,1]
]));

\$\endgroup\$
  • \$\begingroup\$ -2 bytes: g=(a,b)=>(m[b+X-x]||0)[a-Y+y] -1 byte: use |n instead of &&n \$\endgroup\$ – nderscore May 15 '17 at 18:34
6
\$\begingroup\$

MATL, 20 bytes

&fJ*+4XN!"@&-|un3=vs

Input is a matrix.

Try it online!

How it works

This finds all coordinates of nonzero entries in the input grid, and represents them as complex numbers, such that row and column indices correspond to real and imaginary parts respectively.

The code then generates an array of all combinations (order doesn't matter) of these numbers taken 4 at a time. Each combination represents a candidate square. For each combination, the 4×4 matrix of pair-wise absolute differences (i.e. distances in the complex plane) is computed. This is a symmetric matrix with zeros along its main diagonal. The current combination forms a square if and only if the matrix contains exactly 3 distinct values (these will be the square side, the square diagonal, and zero):

enter image description here

On the other hand, for example, a non-square rectangle would give rise to 4 distinct values (two sides, one diagonal value, and zero);

enter image description here

and a general quadrilateral can have up to 7 values (four sides, two diagonals, and zero):

enter image description here

&f      % Input (implicit). Push vectors of row and column indices of nonzero entries
J*      % Multiply by imaginary unit
+       % Add the two vectors. Gives a vector of complex coordinates
4XN     % Matrix of combinations of these complex numbers, taken 4 at a time. Each
        % row is a combination
!       % Transpose
"       % For each column
  @     %   Push current column: candidate set of four points
  &-    %   All pair-wise differences
  |     %   Absolute value
  u     %   Unique entries
  n3=   %   Does the number of elements equal 3? Gives true (1) or false (0)
  vs    %   Concatenate vertically with previous accumulated result, and sum
        % End (implicit). Display (implicit)
\$\endgroup\$
  • \$\begingroup\$ How does it work? \$\endgroup\$ – Leaky Nun May 15 '17 at 16:19
  • \$\begingroup\$ @LeakyNun Explanation added \$\endgroup\$ – Luis Mendo May 15 '17 at 16:27

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.