29
\$\begingroup\$

Write a function that takes 4 points on the plane as input and returns true iff the 4 points form a square. The points will have integral coordinates with absolute values < 1000.

You may use any reasonable representation of the 4 points as input. The points are not provided in any particular order.

Shortest code wins.

Example squares:

(0,0),(0,1),(1,1),(1,0)    # standard square
(0,0),(2,1),(3,-1),(1,-2)  # non-axis-aligned square
(0,0),(1,1),(0,1),(1,0)    # different order

Example non-squares:

(0,0),(0,2),(3,2),(3,0)  # rectangle
(0,0),(3,4),(8,4),(5,0)  # rhombus
(0,0),(0,0),(1,1),(0,0)  # only 2 distinct points
(0,0),(0,0),(1,0),(0,1)  # only 3 distinct points

You may return either true or false for the degenerate square (0,0),(0,0),(0,0),(0,0)

\$\endgroup\$
  • \$\begingroup\$ We are talking 3D points here, right? \$\endgroup\$ – gnibbler Mar 10 '11 at 22:34
  • 3
    \$\begingroup\$ @gnibbler the "on the plane" part of the question make 3D points unlikely. \$\endgroup\$ – J B Mar 10 '11 at 22:54
  • \$\begingroup\$ Are the points given in order? \$\endgroup\$ – J B Mar 10 '11 at 23:03
  • \$\begingroup\$ @J B, I was thinking that it meant the points were on a plane, but I visualised a plane in 3D space for some reason :) \$\endgroup\$ – gnibbler Mar 10 '11 at 23:05
  • 1
    \$\begingroup\$ @eBusiness: -1 that you have cast 11 votes: 7 of them being down. \$\endgroup\$ – Eelvex Mar 11 '11 at 13:24

36 Answers 36

1 2
0
\$\begingroup\$

Smalltalk Squeak 4.x flavour, 91 char in the form of a block:

[:p||b|b:=Bag new.p do:[:x|p do:[:y|b add:(x dist:y)]].b valuesAndCounts asSet={4. 8}asSet]

Test it with:

{
"Example squares:"
    {0@ 0. 0@ 1. 1@ 1. 1@ 0}. " standard square"
    {0@ 0. 2@ 1. 3@ -1. 1@ -2}.  " non-axis-aligned square"
    {0@ 0. 1@ 1. 0@ 1. 1@ 0}. " different order"
"Example non-squares:"
    {0@ 0. 0@ 2. 3@ 2. 3@ 0}.  " rectangle"
    {0@ 0. 3@ 4. 8@ 4. 5@ 0}.  " rhombus"
    {0@ 0. 0@ 0. 1@ 1. 0@ 0}.  " only 2 distinct points"
    {0@ 0. 0@ 0. 1@ 0. 0@ 1}.   " only 3 distinct points"
}
collect:
[:p||b|b:=Bag new.p do:[:x|p do:[:y|b add:(x dist:y)]].b valuesAndCounts asSet={4. 8}asSet].

It's a variant of #(4 8 4)

  • Bag is collecting the pairs ( interdistance -> number_of_occurences )
  • valuesAndCounts send the bag contents (a Dictionary)
  • asSet apply to the values in the dictionary (number_of_occurences)

A degenerated (0,0)*4 is not considered as a valid square.

\$\endgroup\$
0
\$\begingroup\$

Python, 67 chars, complex and distance-based, and no false positives ...

S=lambda A:len(set(A))-1==len(set([abs(K-J)for K in A for J in A]))

(I hope;-).

The sqrt in abs() may cause some roundoff problems, but probably not - abs((K-J)**2) is more reliable but compresses domain as numbers can approach to within a few digits of double precision limits.

Combines Jagu's answer (len(set(Points))-1==len(set(distances)) - brilliant IMNSHO - which drops to 85 as outer pow(...,.5) calls are unnecessary, and (...)**2 is shorter anyway) and user932's (lambda instead of def).

Neither as elegant, nor as short, as paperhorse's rotation as modified by WolframH.

I had a solution that put only the squares of the side and diagonal lengths in the set L and tested "len(L)==2 and max(set(L))/2 in L" but it never went much below 90 chars.

Tests (all should print True):

print S([(0+1j),(1+0j),(0+0j),(1+1j)])
print S([(0+0j),(2+1j),(3-1j),(1-2j)])
print S([(0+0j),(1+1j),(0+1j),(1+0j)])
print S([(1000+1j),(-1+1000j),(1-1000j),(-1000-1j)])

print not S([(0+1j),(0-1j),(0+0j),(0+1j)])
print not S([(999+1j),(-1+1000j),(1-1000j),(-1000-1j)])
print not S([(0+1j),(1+0j),(0+0j),(0-1j)])
print not S([(0+0j),(0+2j),(3+2j),(3+0j)])
print not S([(0+0j),(3+4j),(8+4j),(5+0j)])
print not S([(0+0j),(0+0j),(1+1j),(0+0j)])
print not S([(0+0j),(0+0j),(1+0j),(0+1j)])
\$\endgroup\$
  • \$\begingroup\$ Shouldn't print be included in the function S and thus counted? \$\endgroup\$ – DavidC May 15 '13 at 3:25
0
\$\begingroup\$

Stax, 14 bytes

┐cÜ╦┤╖ó#┬├{%ì↔

Run and debug it

  • Calculate the square of the distance between each pair of points. This yields 6 numbers.
  • "Reduce" the 6-array by dividing each element by the array's gcd.
  • The shape is a square iff the product of the reduced array is 4.
2S{M{:sJF+m square of the distance between each pair of points
:_          "reduce"; divide each by the gcd of the array
:*4=        does the product of the array equal 4?

Run this one

\$\endgroup\$
0
\$\begingroup\$

C (gcc), 159 141 bytes

g;f(a,e)_Complex*a,e;{e=(*a+a[1]+a[2]+a[3])/4;for(g=0;a[g]-=e,g<4&cabs(a[g])==cabs(*a)&!fmod(carg(a[g++])-carg(*a),atan(1)););return g>4;}

-18 thanks to @G.Sliepen.

Try it online!

After subtracting the center point, checks that the absolute values of each complex number are equal, and that all the arguments are equal modulo π/2.

\$\endgroup\$
  • \$\begingroup\$ 146+3 bytes. After subtracting the center point, checks that the absolute values of each complex number are equal, and that all the arguments are equal modulo π/2. \$\endgroup\$ – G. Sliepen Aug 25 '19 at 11:38
0
\$\begingroup\$

Its not exactly shortest, but I dont think anyone proposed this strategy.

Scala, 152

def f(p:Seq[(Double,Double)])={p.map(b=>{math.sqrt(math.pow((p.map(_._1).sum/p.size)-b._1,2)+math.pow((p.map(_._2).sum/p.size)-b._2,2))}).toSet.size==1}

Basically we calculate average of all points across each axis to find presumably center of the square, and then validate that center has same distance from all points.

Properly formatted solution:

type Point = (Double, Double)
def isSquare(points: Seq[Point]): Boolean = {
  //finds center point along an axis
  def avg(axis: Seq[Double]): Double = {
    axis.sum / axis.size
  }

  //finds distance between 2 points
  def distance(a: Point, b: Point): Double = {
    val x = a._1 - b._1
    val y = a._2 - b._2
    math.sqrt((x * x) + (y * y))
  }

  //point in the center of square
  val center = (
    avg(points.map(_._1)),
    avg(points.map(_._2)))

  //find a set of distances from center to all points
  //and make sure only one is in the set
  points.map(distance(center, _)).toSet.size == 1
}
\$\endgroup\$
  • \$\begingroup\$ The solution is wrong. Any rectangle would pass this check. \$\endgroup\$ – Joel Aug 28 '19 at 2:13
-1
\$\begingroup\$

C++

Letting a,b,c,d,e,f,g,h be the coordinates of the vectors like such: (a,b),(c,d),(e,f),(g,h)

bool a(int a,int b,int c,int d,int e,int f,int g,int h){
    int x=abs(a-c)+abs(b-d),y=abs(a-e)+abs(b-f),z=abs(a-g)+abs(b-h);
    return (x==y||x==z)&(x==abs(e-g)+abs(f-h)&y==abs(c-g)+abs(d-h)&z==abs(c-e)+abs(d-f);
}

To explain: the points can be in any order. Let a,b,c,d be the points of the square. We only need to consider the three vectors made from a-b,a-c,a-d to exclude most shapes. If two of these vectors are equal length, then we have at a rhombus or square. Then we compare the length of the vectors made from opposite pairs of vertices: a-b with c-d, a-c with b-d, a-d with b-c. If all are equal we are a square.

We use the taxicab metric since it's computationally more tractable and produced the same result.

Edited to be a function. New length is longer. Oh well.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hello and welcome to PPCG. As it stands, your submission would be counted as a snippet, which is not allowed. Please change your answer to either be a full program or function definition. This meta question might be a good read. \$\endgroup\$ – Jonathan Frech Apr 20 '19 at 7:34
  • 1
    \$\begingroup\$ This unfortunately doesn't compile as it is. \$\endgroup\$ – G. Sliepen Aug 24 '19 at 22:03
1 2

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.