A well-known puzzle involves counting how many squares can be made using the points on a 3x3 grid:
. . .
. . .
. . .
The answer is 6 — four small squares, one large square, and one square formed from the top, left, bottom, and right pegs, with edges along the diagonals of the squares.
Your task is to build a program that counts the total number of squares that can be formed from a set of points.
Your program will take input in one of two formats (of your choosing):
An
M
byN
grid consisting of either.
or.
.
represents a point on the grid that a square can be a corner of, and all spaces on the grid are exactly one unit apart horizontally or vertically.A list of coordinate pairs representing points that a square can be on.
and return the number of distinct squares that can be formed using the points provided. Your program must return a correct solution for every possible input.
For example, take the input above but where the center square is missing:
...
. .
...
There are only two possible squares here (the big one and the diagonal one), so the program should return 2
.
The shortest code to do this in any language wins.