8
\$\begingroup\$

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 by N 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.

\$\endgroup\$
  • 7
    \$\begingroup\$ I would upvote you, but your reputation is perfect. (6666) :-P \$\endgroup\$ – Doorknob May 21 '14 at 18:11
  • \$\begingroup\$ As long as I have that reputation, I'm the devil :( \$\endgroup\$ – Joe Z. May 21 '14 at 18:12
  • \$\begingroup\$ Are we talking about squares or rectangles? You say the horizontal and vertical unit is both 1. But in your example, the dots are one unit apart vertically but 3 units apart horizontally. So how are those squares? Also could there be gaps in the input? If so, could you provide a more complex example? \$\endgroup\$ – Martin Ender May 21 '14 at 18:26
  • \$\begingroup\$ The dots in the question are only spaced out more widely for aesthetic purposes. They should be only one character apart for purposes of the actual question. \$\endgroup\$ – Joe Z. May 21 '14 at 18:29
  • \$\begingroup\$ What's the max possible value for M and N, and the max number of total points? And are we free to say how many points there are in any way we wish? (Either by taking an input at the beginning, or by stopping once some kind of EOF is reached.) \$\endgroup\$ – Level River St May 21 '14 at 18:32
7
\$\begingroup\$

Python, 95

Takes a list of coordinates from stdin.

l=input();print(sum((c-d+b,d+c-a)in l and(a-d+b,b+c-a)in l for a,b in l for c,d in l)-len(l))/4

Explanation:

For each pair of points (a,b) and (c,d), check if the square with additional points (c-d+b,d+c-a) and (a-d+b,b+c-a) is in the list. This counts each square 4 times, and each point once (when (a,b) = (c,d)), so subtracting the number of points and dividing by 4 gives the number of squares.

\$\endgroup\$
  • \$\begingroup\$ Clever, concise. \$\endgroup\$ – primo May 22 '14 at 4:44

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.