Tell me, how many squares are there?

Question

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 code-golf. Shortest answer in bytes wins. Standard loopholes apply.

Answer 1

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.

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]
]));

Answer 2

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):

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

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

&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)