Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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)

share|improve this question
    
We are talking 3D points here, right? –  gnibbler Mar 10 '11 at 22:34
1  
@gnibbler the "on the plane" part of the question make 3D points unlikely. –  J B Mar 10 '11 at 22:54
    
Are the points given in order? –  J B Mar 10 '11 at 23:03
    
@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 :) –  gnibbler Mar 10 '11 at 23:05
1  
@eBusiness: -1 that you have cast 11 votes: 7 of them being down. –  Eelvex Mar 11 '11 at 13:24

29 Answers 29

up vote 7 down vote accepted

Python 176 90 76 characters

def S(A):c=sum(A)/4.0;return set(A)==set((A[0]-c)*1j**i+c for i in range(4))

Function S takes a list of complex numbers as its input (A). If we know both the centre and one corner of a square, we can reconstruct the square by rotating the corner 90,180 and 270 degrees around the centre point (c). On the complex plane rotation by 90 degrees about the origin is done by multiplying the point by i. If our original shape and the reconstructed square have the same points then it must have been a square.

share|improve this answer
    
A few optimizations: 1) use "S" instead of "is_square" 2) put it all on one line using ; 3) iterate over the 4 directions directly "for i in(1,1j,-1,-1j)" 4) don't need [] in set argument. –  Keith Randall Mar 13 '11 at 5:29
    
Thanks Keith. (I left out (3) as it appears to be the same length as my code) –  paperhorse Mar 14 '11 at 22:52
2  
@Keith Randall - Why was this accepted when J B has a much shorter solution? –  eBusiness Mar 18 '11 at 13:21
1  
Two reasons. One, J would always win. So I like to normalize a bit by language. Also, I like this answer better because it doesn't suffer from the same problem as the distance-only answers where other figures (admittedly, only irrational ones) give false positives. –  Keith Randall Mar 18 '11 at 15:04
2  
@Keith Randall - Quotes from the question: "The points will have integral coordinates" "Shortest code wins.". It's perfectly fine if you choose different criteria for selecting an answer, even subjective criteria, but then you should state that in the question. –  eBusiness Mar 18 '11 at 19:23

J, 28 17 25 27

J doesn't really have functions, but here's a monadic verb that takes a vector of points from the complex plane:

4 8 4-:#/.~&(/:~&:|&,&(-/~))

Method is a mix of Michael Spencer (work solely on inter-vertex lengths; but he's currently failing my rhombus2) and Eelvex's (check the sets' sizes) works. Reading right to left:

  • -/~ compute all point differences
  • , flatten
  • | extract magnitude
  • /:~ sort up
  • #/.~ nub and count
  • 4 8 4 -: must have exactly 4 equidistant (at 0), 8 a bit bigger (length 1, sides), 4 bigger yet (length sqrt 2, diagonals)

Demonstration:

   NB. give the verb a name for easier use
   f =: 4 8 4-:#/.~&(/:~&:|&,&(-/~))

   NB. standard square
   f 0 0j1 1j1 1
1

   NB. non-axis-aligned square
   f 0 2j1 3j_1 1j_2
1

   NB. different order
   f 0 1j1 0j1 1
1

   NB. rectangle
   f 0 0j2 3j2 3
0

   NB. rhombus 1
   f 0 3j4 8j4 5
0

   NB. rhombus 2
   f 0 1ad_60 1ad0 1ad60
0

For memory's sake, my previous method (required ordered vertices, but could detect regular polygons of any order):

*./&(={.)&(%1&|.)&(-1&|.)

See history for explanation and demo. The current method could probably be expanded to other polygons, that 4 8 4 does look a lot like a binomial distribution.

share|improve this answer
    
Can you link to this language? –  Sargun Dhillon Mar 11 '11 at 5:17
    
@Sargun Dhillon: jsoftware.com –  Hoa Long Tam Mar 11 '11 at 5:44
1  
@gnibbler: Why not? I'm pretty sure it does. –  Eelvex Mar 11 '11 at 13:10
1  
Actually, a non-square figure that satisfy the conditions that you check for does exist, a regular triangle plus one point a side-length from a tip of the triangle placed on the extended median. But the question called for integer input, so I guess the solution is ok. –  eBusiness Mar 11 '11 at 15:34
1  
Ah, ok. I was thinking of equilateral triangles with the 4th point being the centre, but that is ruled out by the integer co-ordinates –  gnibbler Mar 11 '11 at 18:17

Python, 7142

Update 1) to require 4 different points (would previously give false positives for repeated points - are there others?) 2) to define a function per spec

For a square, the vector between any two points must be 0 (the same point), a side, or a diagonal. So, the set of the magnitude of these vectors must have length 3.

# Accepts co-ordinates as sequences of complex numbers

SQUARES=[
 (0+0j,0+1j,1+1j,1+0j),  # standard square
 (0+0j,2+1j,3-1j,1-2j),  # non-axis-aligned square
 (0+0j,1+1j,0+1j,1+0j)   # different order
]

NONSQUARES=[
 (0+0j,0+2j,3+2j,3+0j),  # rectangle
 (0+0j,3+4j,8+4j,5+0j),  # rhombus
 (0+0j,0+1j,1+1j,0+0j),   # duplicated point
 (0+0j,1+60j,1+0j,1-60j)  # rhombus 2 (J B)
] 

test = "lambda A: len(set(A))==4 and len(set(abs(i-j)for i in A for j in A))==3"
assert len(test)==71

is_square=lambda A: len(set(A))==4 and len(set(abs(i-j)for i in A for j in A))==3    

for A in SQUARES:
    assert is_square(A)

for A in NONSQUARES:
    assert not is_square(A)
share|improve this answer
    
I think the question explicitly stated a list of points, and not a vector. –  Sargun Dhillon Mar 11 '11 at 10:17
    
False positives. –  eBusiness Mar 11 '11 at 13:13
    
So (0+0j,0+0j,1+0j,0+1j) is a square? –  mhagger Mar 11 '11 at 15:39
    
My rhombus 2 is not 1+/-60j, it's more like exp(ijpi/3) for values from -1, 0, 1. Note that as eBusiness pointed out they can't all be integral, so not really in the scope of the question. –  J B Mar 11 '11 at 17:00

Haskell, 100 characters

Here's how I'd write the JB's J solution in Haskell. With no attempt made to damage readability by removing nonessential characters, it's about 132 characters:

import Data.List
d (x,y) (x',y') = (x-x')^2 + (y-y')^2
square xs = (== [4,8,4]) . map length . group . sort $ [d x y | x<-xs, y<-xs]

You can scrape it down a bit to 100 by removing excess spaces and renaming some things

import Data.List
d(x,y)(a,b)=(x-a)^2+(y-b)^2
s l=(==[4,8,4]).map length.group.sort$[d x y|x<-l,y<-l]

Let's use QuickCheck to ensure that it accepts arbitrary squares, with one vertex at (x,y) and edge vector (a,b):

prop_square (x,y) (a,b) = square [(x,y),(x+a,y+b),(x-b,y+a),(x+a-b,y+b+a)]

Trying it in ghci:

ghci> quickCheck prop_square
*** Failed! Falsifiable (after 1 test):  
(0,0)
(0,0)

Oh right, the empty square isn't considered a square here, so we'll revise our test:

prop_square (x,y) (a,b) =
   (a,b) /= (0,0) ==> square [(x,y),(x+a,y+b),(x-b,y+a),(x+a-b,y+b+a)]

And trying it again:

ghci> quickCheck prop_square
+++ OK, passed 100 tests.
share|improve this answer
    
Save 11 chars by unrolling the function d. s l=[4,8,4]==(map length.group.sort)[(x-a)^2+(y-b)^2|(x,y)<-l,(a,b)<-l] –  Ray Jun 19 '13 at 20:06

OCaml, 145 164

let(%)(a,b)(c,d)=(c-a)*(c-a)+(d-b)*(d-b)
let t a b c d=a%b+a%c=b%c&&d%c+d%b=b%c&&a%b=a%c&&d%c=d%b
let q(a,b,c,d)=t a b c d||t a c d b||t a b d c

Run like this:

q ((0,0),(2,1),(3,-1),(1,-2))

Let's deobfuscate and explain a bit.

First we define a norm:

let norm (ax,ay) (bx,by) = (bx-ax)*(bx-ax)+(by-ay)*(by-ay)

You'll notice that there is no call to sqrt, it's not needed here.

let is_square_with_fixed_layout a b c d =
  (norm a b) + (norm a c) = norm b c
  && (norm d c) + (norm d b) = norm b c
  && norm a b = norm a c
  && norm d c = norm d b

Here a, b, c and d are points. We assume that these points are layed out like this:

a - b
| / |
c - d

If we have a square then all these conditions must hold:

  • a b c is a right triangle
  • b c d is a right triangle
  • the smaller sides of each right triangle have the same norms

Observe that the following always holds:

is_square_with_fixed_layout r s t u = is_square_with_fixed_layout r t s u

We will use that to simplify our test function below.

Since our input is not ordered, we also have to check all permutations. Without loss of generality we can avoid permuting the first point:

let is_square (a,b,c,d) =
  is_square_with_fixed_layout a b c d
  || is_square_with_fixed_layout a c b d
  || is_square_with_fixed_layout a c d b
  || is_square_with_fixed_layout a b d c
  || is_square_with_fixed_layout a d b c
  || is_square_with_fixed_layout a d c b

After simplification:

let is_square (a,b,c,d) =
  is_square_with_fixed_layout a b c d
  || is_square_with_fixed_layout a c d b
  || is_square_with_fixed_layout a b d c

Edit: followed M.Giovannini's advice.

share|improve this answer
    
Nice. We haven't seen much OCaml here :) –  Eelvex Mar 11 '11 at 17:46
    
Use an operator instead of n for a reduction in 20 characters: let t a b c d=a%b+a%c=b%c&&d%c+d%b=b%c&&a%b=a%c&&d%c=d%b. –  Matías Giovannini Apr 17 '11 at 14:26
    
Nice catch, thanks :) –  bltxd Apr 18 '11 at 14:04

Python (105)

Points are represented by (x,y) tuples. Points can be in any order and only accepts squares. Creates a list, s, of pairwise (non-zero) distances between the points. There should be 12 distances in total, in two unique groups.

def f(p):s=filter(None,[(x-z)**2+(y-w)**2for x,y in p for z,w in p]);return len(s)==12and len(set(s))==2
share|improve this answer
    
You could leave out the filter and check if the len of the set is 3. This suffers from the same false positive problem as my answer though. –  gnibbler Mar 11 '11 at 5:29
    
>>> f([(0,0),(0,4),(2,2),(-2,2)]) = True –  Sargun Dhillon Mar 11 '11 at 6:17
2  
f([(0,0),(0,4),(2,2),(-2,2)]) is a square –  gnibbler Mar 11 '11 at 18:19

C# -- not exactly short. Abusing LINQ. Selects distinct two-combinations of points in the input, calculates their distances, then verifies that exactly four of them are equal and that there is only one other distinct distance value. Point is a class with two double members, X and Y. Could easily be a Tuple, but meh.

var points = new List<Point>
             {
                 new Point( 0, 0 ), 
                 new Point( 3, 4 ), 
                 new Point( 8, 4 ), 
                 new Point( 5, 0 )
              };    
var distances = points.SelectMany(
    (value, index) => points.Skip(index + 1),
    (first, second) => new Tuple<Point, Point>(first, second)).Select(
        pointPair =>
        Math.Sqrt(Math.Pow(pointPair.Item2.X - pointPair.Item1.X, 2) +
                Math.Pow(pointPair.Item2.Y - pointPair.Item1.Y, 2)));
return
    distances.Any(
        d => distances.Where( p => p == d ).Count() == 4 &&
                distances.Where( p => p != d ).Distinct().Count() == 1 );
share|improve this answer

PHP, 82 characters


//$x=array of x coordinates
//$y=array of respective y coordinates
/* bounding box of a square is also a square - check if Xmax-Xmin equals Ymax-Ymin */
function S($x,$y){sort($x);sort($y);return ($x[3]-$x[0]==$y[3]-$y[0])?true:false};

//Or even better (81 chars):
//$a=array of points - ((x1,y1), (x2,y2), (x3,y3), (x4,y4))
function S($a){sort($a);return (bool)($a[3][0]-$a[0][0]-abs($a[2][1]-$a[3][1]))};
share|improve this answer
    
But just because the bounding box is square doesn't mean the points lie in a square. Necessary but not sufficient condition. Consider (0,0), (5,5), (10,0), (0,-5). Bounding box is square (0:10, -5:5); figure is not. –  Floris Apr 26 at 1:13

OCaml + Batteries, 132 characters

let q l=match List.group(-)[?List:(x-z)*(x-z)+(y-t)*(y-t)|x,y<-List:l;z,t<-List:l;(x,y)<(z,t)?]with[[s;_;_;_];[d;_]]->2*s=d|_->false

(look, Ma, no spaces!) The list comprehension in q forms the list of squared norms for each distinct unordered pair of points. A square has four equal sides and two equal diagonals, the squared lengths of the latter being twice the squared lengths of the former. Since there aren't equilateral triangles in the integer lattice the test isn't really necessary, but I include it for completeness.

Tests:

q [(0,0);(0,1);(1,1);(1,0)] ;;
- : bool = true
q [(0,0);(2,1);(3,-1);(1,-2)] ;;
- : bool = true
q [(0,0);(1,1);(0,1);(1,0)] ;;
- : bool = true
q [(0,0);(0,2);(3,2);(3,0)] ;;
- : bool = false
q [(0,0);(3,4);(8,4);(5,0)] ;;
- : bool = false
q [(0,0);(0,0);(1,1);(0,0)] ;;
- : bool = false
q [(0,0);(0,0);(1,0);(0,1)] ;;
- : bool = false
share|improve this answer

Haskell (212)

import Data.List;j=any f.permutations where f x=(all g(t x)&&s(map m(t x)));t x=zip3 x(drop 1$z x)(drop 2$z x);g(a,b,c)=l a c==sqrt 2*l a b;m(a,b,_)=l a b;s(x:y)=all(==x)y;l(m,n)(o,p)=sqrt$(o-m)^2+(n-p)^2;z=cycle

Naive first attempt. Checks the following two conditions for all permutations of the input list of points (where a given permutation represents, say, a clockwise ordering of the points):

  • all angles are 90 degrees
  • all sides are the same length

Deobfuscated code and tests

j' = any satisfyBothConditions . permutations
          --f
    where satisfyBothConditions xs = all angleIs90 (transform xs) && 
                                     same (map findLength' (transform xs))
          --t
          transform xs = zip3 xs (drop 1 $ cycle xs) (drop 2 $ cycle xs)
          --g
          angleIs90 (a,b,c) = findLength a c == sqrt 2 * findLength a b
          --m
          findLength' (a,b,_) = findLength a b
          --s
          same (x:xs) = all (== x) xs
          --l
          findLength (x1,y1) (x2,y2) = sqrt $ (x2 - x1)^2 + (y2 - y1)^2


main = do print $ "These should be true"
          print $ j [(0,0),(0,1),(1,1),(1,0)]
          print $ j [(0,0),(2,1),(3,-1),(1,-2)]
          print $ j [(0,0),(1,1),(0,1),(1,0)]
          print $ "These should not"
          print $ j [(0,0),(0,2),(3,2),(3,0)]
          print $ j [(0,0),(3,4),(8,4),(5,0)]
          print $ "also testing j' just in case"
          print $ j' [(0,0),(0,1),(1,1),(1,0)]
          print $ j' [(0,0),(2,1),(3,-1),(1,-2)]
          print $ j' [(0,0),(1,1),(0,1),(1,0)]
          print $ j' [(0,0),(0,2),(3,2),(3,0)]
          print $ j' [(0,0),(3,4),(8,4),(5,0)]
share|improve this answer

Scala (146 characters)

def s(l:List[List[Int]]){var r=Set(0.0);l map(a=>l map(b=>r+=(math.pow((b.head-a.head),2)+math.pow((b.last-a.last),2))));print(((r-0.0).size)==2)}
share|improve this answer

JavaScript 144 characters

Mathematically equal to J Bs answer. It generates the 6 lengths and assert that the 2 greatest are equal and that the 4 smallest are equal. Input must be an array of arrays.

function F(a){d=[];g=0;for(b=4;--b;)for(c=b;c--;d[g++]=(e*e+f*f)/1e6)e=a[c][0]-a[b][0],f=a[c][1]-a[b][1];d.sort();return d[0]==d[3]&&d[4]==d[5]} //Compact function
testcases=[
[[0,0],[1,1],[1,0],[0,1]],
[[0,0],[999,999],[999,0],[0,999]],
[[0,0],[2,1],[3,-1],[1,-2]],
[[0,0],[0,2],[3,2],[3,0]],
[[0,0],[3,4],[8,4],[5,0]],
[[0,0],[0,0],[1,1],[0,0]],
[[0,0],[0,0],[1,0],[0,1]]
]
for(v=0;v<7;v++){
    document.write(F(testcases[v])+"<br>")
}

function G(a){ //Readable version
    d=[]
    g=0
    for(b=4;--b;){
        for(c=b;c--;){
            e=a[c][0]-a[b][0]
            f=a[c][1]-a[b][1]
            d[g++]=(e*e+f*f)/1e6 //The division tricks the sort algorithm to sort correctly by default method.
        }
    }
    d.sort()
    return (d[0]==d[3]&&d[4]==d[5])
}
share|improve this answer

Python - 42 chars

Looks like its an improvement to use complex numbers for the points

len(set(abs(x-y)for x in A for y in A))==3

where A = [(11+13j), (14+12j), (13+9j), (10+10j)]

old answer:

from itertools import*
len(set((a-c)**2+(b-d)**2 for(a,b),(c,d)in combinations(A,2)))==2

Points are specified in any order as a list, eg

A = [(11, 13), (14, 12), (13, 9), (10, 10)]
share|improve this answer
    
>>> A=[(0,0),(0,0),(1,1),(0,0)] >>> len(set((a-c)**2+(b-d)**2 for(a,b),(c,d)in combinations(A,2)))==2 True –  Sargun Dhillon Mar 11 '11 at 3:30
    
@Sargun, that's a special case of a whole class of inputs that don't work. I'm trying to think of a fix that doens't blow out the size of the answer. Meanwhile, Can work out the general class of failing cases? –  gnibbler Mar 11 '11 at 5:26
    
A=[(0,0),(0,4),(2,2),(-2,2)]; len(set((a-c)**2+(b-d)**2 for(a,b),(c,d)in combinations(A,2)))==2 –  Sargun Dhillon Mar 11 '11 at 6:15
    
@Sargun: that example is a square. –  Keith Randall Mar 11 '11 at 15:59
    
to get rid of duplicated points you can add -set([0]) –  Keith Randall Mar 11 '11 at 16:00

PHP, 161 158 characters

function S($a){for($b=4;--$b;)for($c=$b;$c--;){$e=$a[$c][0]-$a[$b][0];$f=$a[$c][1]-$a[$b][1];$d[$g++]=$e*$e+$f*$f;}sort($d);return$d[0]==$d[3]&&$d[4]==$d[5];}

Proof (1x1): http://codepad.viper-7.com/ZlBpOB

This is based off of eBuisness's JavaScript answer.

share|improve this answer
    
It's a bit unclear from the problem statement the points would come in ordered. I'll go ask. –  J B Mar 10 '11 at 23:01
1  
I don't think this will properly handle lots of cases. For example, it will incorrectly label rhombuses as squares. –  Keith Randall Mar 10 '11 at 23:31
    
Updated this to match one of the JavaScript answers, should handle all cases. –  Kevin Brown Mar 11 '11 at 21:09

JavaScript 1.8, 112 characters

Update: saved 2 characters by folding the array comprehensions together.

function i(s)(p=[],[(e=x-a,f=y-b,d=e*e+f*f,p[d]=~~p[d]+1)for each([a,b]in s)for each([x,y]in s)],/8,+4/.test(p))

Another reimplementation of J B's answer. Exploits JavaScript 1.7/1.8 features (expression closures, array comprehensions, destructuring assignment). Also abuses ~~ (double bitwise not operator) to coerce undefined to numeric, with array-to-string coercion and a regexp to check that the length counts are [4, 8, 4] (it assumes that exactly 4 points are passed). The abuse of the comma operator is an old obfuscated C trick.

Tests:

function assert(cond, x) { if (!cond) throw ["Assertion failure", x]; }

let text = "function i(s)(p=[],[(e=x-a,f=y-b,d=e*e+f*f,p[d]=~~p[d]+1)for each([a,b]in s)for each([x,y]in s)],/8,+4/.test(p))"
assert(text.length == 112);
assert(let (source = i.toSource()) (eval(text), source == i.toSource()));

// Example squares:
assert(i([[0,0],[0,1],[1,1],[1,0]]))    // standard square
assert(i([[0,0],[2,1],[3,-1],[1,-2]]))  // non-axis-aligned square
assert(i([[0,0],[1,1],[0,1],[1,0]]))    // different order

// Example non-squares:
assert(!i([[0,0],[0,2],[3,2],[3,0]]))  // rectangle
assert(!i([[0,0],[3,4],[8,4],[5,0]]))  // rhombus
assert(!i([[0,0],[0,0],[1,1],[0,0]]))  // only 2 distinct points
assert(!i([[0,0],[0,0],[1,0],[0,1]]))  // only 3 distinct points

// Degenerate square:
assert(!i([[0,0],[0,0],[0,0],[0,0]]))   // we reject this case
share|improve this answer

GoRuby - 66 characters

f=->a{z=12;a.pe(2).m{|k,l|(k-l).a}.so.go{|k|k}.a{|k,l|l.sz==z-=4}}

expanded:

f=->a{z=12;a.permutation(2).map{|k,l|(k-l).abs}.sort.group_by{|k|k}.all?{|k,l|l.size==(z-=4)}}

Same algorithm as J B's answer.

Test like:

p f[[Complex(0,0), Complex(0,1), Complex(1,1), Complex(1,0)]]

Outputs true for true and blank for false

share|improve this answer
    
Never heard of GoRuby. Is there anything official written about it? stackoverflow.com/questions/63998/hidden-features-of-ruby/… –  Jonas Elfström Mar 18 '11 at 12:05
    
@Jonas: I haven't seen anything really official about it, the best blog post I have seen is this one. I wasn't actually able to get it built and working but an alternative is to just copy the golf-prelude into the same folder and run ruby -r ./golf-prelude.rb FILE_TO_RUN.rb and it will work exatcly the same. –  Nemo157 Mar 18 '11 at 21:55
    
Thanks for the links and info! –  Jonas Elfström Mar 18 '11 at 22:30
    
it is not necessary to sort before group_by. .sort.group_by {...} should be written as .group_by {...} –  user102008 Aug 25 '11 at 21:43

Python 97 (without complex points)

def t(p):return len(set(p))-1==len(set([pow(pow(a-c,2)+pow(b-d,2),.5)for a,b in p for c,d in p]))

This will take lists of point tuples in [(x,y),(x,y),(x,y),(x,y)] in any order, and can handle duplicates, or the wrong number of points. It does NOT require complex points like the other python answers.

You can test it like this:

S1 = [(0,0),(1,0),(1,1),(0,1)]   # standard square
S2 = [(0,0),(2,1),(3,-1),(1,-2)] # non-axis-aligned square
S3 = [(0,0),(1,1),(0,1),(1,0)]   # different order
S4 = [(0,0),(2,2),(0,2),(2,0)]   #
S5 = [(0,0),(2,2),(0,2),(2,0),(0,0)] #Redundant points

B1 = [(0,0),(0,2),(3,2),(3,0)]  # rectangle
B2 = [(0,0),(3,4),(8,4),(5,0)]  # rhombus
B3 = [(0,0),(0,0),(1,1),(0,0)]  # only 2 distinct points
B4 = [(0,0),(0,0),(1,0),(0,1)]  # only 3 distinct points
B5 = [(1,1),(2,2),(3,3),(4,4)]  # Points on the same line
B6 = [(0,0),(2,2),(0,2)]        # Not enough points

def tests(f):
    assert(f(S1) == True)
    assert(f(S2) == True)
    assert(f(S3) == True)
    assert(f(S4) == True)
    assert(f(S5) == True)

    assert(f(B1) == False)
    assert(f(B2) == False)
    assert(f(B3) == False)
    assert(f(B4) == False)
    assert(f(B5) == False)
    assert(f(B6) == False)

def t(p):return len(set(p))-1==len(set([pow(pow(a-c,2)+pow(b-d,2),.5)for a,b in p for c,d in p]))

tests(t)

This will take a little explaining, but the overall idea is that there are only three distances between the points in a square (Side, Diagonal, Zero(point compared to itself)):

def t(p):return len(set(p))-1==len(set([pow(pow(a-c,2)+pow(b-d,2),.5)for a,b in p for c,d in p]))
  • for a list p of tuples (x,y)
  • Remove duplicates using set(p) and then test the length
  • Get every combination of points (a,b in p for c,d in p)
  • Get list of the distance from every point to every other point
  • Use set to check there are only three unique distances -- Zero (point compared to itself) -- Side length -- Diagonal length

To save code characters I am:

  • using a 1 char function name
  • using a 1 line function definition
  • Instead of checking the number of unique points is 4, I check that it is -1 the different point lengths (saves ==3==)
  • use list and tuple unpacking to get a,b in p for c,d in p, instead of using a[0],a[1]
  • uses pow(x,.5) instead of including math to get sqrt(x)
  • not putting spaces after the )
  • not putting a leading zero on the float

I fear someone can find a test case that breaks this. So please do and Ill correct. For instance the fact I just check for three distances, instead of doing an abs() and checking for side length and hypotenuse, seems like an error.

First time I've tried code golf. Be kind if I've broken any house rules.

share|improve this answer

Clojure, 159 chars.

user=> (def 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
#'user/squares
user=> (def non-squares
         [[[0,0] [0,2] [3,2] [3,0]]    ; rectangle
          [[0,0] [3,4] [8,4] [5,0]]])  ; rhombus
#'user/non-squares
user=> (defn norm
         [x y]
         (reduce + (map (comp #(* % %) -) x y)))
#'user/norm
user=> (defn square?
         [[a b c d]]
         (let [[x y z] (sort (map #(norm a %) [b c d]))]
           (and (= x y) (= z (* 2 x)))))
#'user/square?
user=> (every? square? squares)
true
user=> (not-any? square? non-squares)
true

Edit: To also explain a little bit.

  • First define a norm which basically gives the distance between two given points.
  • Then calculate the distance of the first point to the other three points.
  • Sort the three distances. (This allows any order of the points.)
  • The two shortest distances must be equal to be a square.
  • The third (longest) distance must be equal to the square root of the sum of the squares of the short distances by the theorem of Pythagoras.

(Note: the square rooting is not needed and hence in the code saved above.)

share|improve this answer

Factor

An implementation in the Factor programming language:

USING: kernel math math.combinatorics math.vectors sequences sets ;

: square? ( seq -- ? )
    members [ length 4 = ] [
        2 [ first2 distance ] map-combinations
        { 0 } diff length 2 =
    ] bi and ;

And some unit tests:

[ t ] [
    {
        { { 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
        { { 0 0 } { 0 4 } { 2 2 } { -2 2 } }  ! rotated square
    } [ square? ] all?
] unit-test

[ f ] [
    {
        { { 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
    } [ square? ] any?
] unit-test
share|improve this answer

C#, 107 characters

return p.Distinct().Count()==4&&
(from a in p from b in p select (a-b).LengthSquared).Distinct().Count()==3;

Where points is List of Vector3D containing the points.

Computes all distances squared between all points, and if there are exactly three distinct types (must be 0, some value a, and 2*a) and 4 distinct points then the points form a square.

share|improve this answer

K - 33

Translation of the J solution by J B:

{4 8 4~#:'=_sqrt+/'_sqr,/x-/:\:x}

K suffers here from its reserved words(_sqr and _sqrt).

Testing:

  f:{4 8 4~#:'=_sqrt+/'_sqr,/x-/:\:x}

  f (0 0;0 1;1 1;1 0)
1

  f 4 2#0 0 1 1 0 1 1 0
1

  f 4 2#0 0 3 4 8 4 5 0
0
share|improve this answer

Python, 66

Improving paperhorse's answer from 76 to 66:

def U(A):c=sum(A)/4;d=A[0]-c;return{d+c,c-d,d*1j+c,c-d*1j}==set(A)
share|improve this answer

Mathematica 65 80 69 66

Checks that the number of distinct inter-point distances (not including distance from a point to itself) is 2 and the shorter of the two is not 0.

h = Length@# == 2 \[And] Min@# != 0 &[Union[EuclideanDistance @@@ Subsets[#, {2}]]] &;

Usage

h@{{0, 0}, {0, 1}, {1, 1}, {1, 0}}       (*standard square *)
h@{{0, 0}, {2, 1}, {3, -1}, {1, -2}}     (*non-axis aligned square *)
h@{{0, 0}, {1, 1}, {0, 1}, {1, 0}}       (*a different order *)

h@{{0, 0}, {0, 2}, {3, 2}, {3, 0}}       (* rectangle *)
h@{{0, 0}, {3, 4}, {8, 4}, {5, 0}}       (* rhombus   *)
h@{{0, 0}, {0, 0}, {1, 1}, {0, 0}}       (* only 2 distinct points *)
h@{{0, 0}, {0, 1}, {1, 1}, {0, 1}}       (* only 3 distinct points *)

True
True
True
False
False
False
False

N.B.: \[And] is a single character in Mathematica.

share|improve this answer

J, 31 29 27 26

3=[:#[:~.[:,([:+/*:@-)"1/~

checks if the 8 smallest distances between the points are the same. checks if there are exactly three kinds of distances between the points (zero, side length and diagonal length).

f 4 2 $ 0 0 2 1 3 _1 1 _2
1
f 4 2 $ 0 0 0 2 3 2 3 0
0

4 2 $ is a way of writing an array in J.

share|improve this answer
    
This fails the rhombus test. –  J B Mar 11 '11 at 9:13
    
@JB: I had a typo. I changed the method anyway now. –  Eelvex Mar 11 '11 at 9:18
    
Eeew... you're taking the same method I was stealing. Except my version's shorter :p –  J B Mar 11 '11 at 9:33
    
@JB: really? I didn't notice that. Who else checks (3 == #distances)? –  Eelvex Mar 11 '11 at 9:39
    
@JB: oic... some check for combinations of 2. :-/ –  Eelvex Mar 11 '11 at 9:40

Smalltalk for 106 characters

s:=Set new.
p permutationsDo:[:e|s add:((e first - e second) dotProduct:(e first - e third))].
s size = 2

where p is a collection of points, e.g.

p := { 0@0. 2@1. 3@ -1. 1@ -2}. "twisted square"

I think the math is sound...

share|improve this answer
    
Checking for 2 distinct dot products doesn't cut it. Points placed in the same position may produce false positives. –  eBusiness Mar 11 '11 at 15:52

Mathematica, 123 characters (but you can do better):

Flatten[Table[x-y,{x,a},{y,a}],1]
Sort[DeleteDuplicates[Abs[Flatten[Table[c.d,{c,%},{d,%}]]]]]
%[[1]]==0&&%[[3]]/%[[2]]==2

Where 'a' is the input in Mathematica list form, eg: a={{0,0},{3,4},{8,4},{5,0}}

The key is to look at the dot products between all the vectors and note that they must have exactly three values: 0, x, and 2*x for some value of x. The dot product checks both perpendicularity AND length in one swell foop.

I know there are Mathematica shortcuts that can make this shorter, but I don't know what they are.

share|improve this answer
    
I think this one is wrong as well, but I can't figure what the code does. –  eBusiness Mar 11 '11 at 15:55
    
It calculates all the vectors between the 4 points, takes all of the dot products (absolute value), and expects the result to consist exactly of 0, x, 2*x for some value of x. –  barrycarter Mar 11 '11 at 16:00
    
So 16 vectors -> 256 dot products, and you check that the high value is 2 times the low, but you don't how many there is of each value. Is that correct understood? –  eBusiness Mar 11 '11 at 16:25
    
Yes, that correctly describes my algorithm. And I now think you're right: you could construct a scenario in which all 3 values occurred, but not in the right quantity. Rats. Should be fixable though? –  barrycarter Mar 11 '11 at 17:10
    
@barrycarter You can save characters by using Union instead of Sort@DeleteDuplicates. I put your 3 lines together also:#[[1]] == 0 && #[[3]]/#[[2]] == 2 &[ Union@Abs@Flatten[Table[c.d, {c, #}, {d, #}]] &[ Flatten[Table[x - y, {x, a}, {y, a}], 1]]] –  David Carraher May 15 '13 at 3:21

Haskell, "wc -c" reports 110 characters. Does not check that the input has 4 elements.

import Data.List
k [a,b]=2*a==b
k _=0<1
h ((a,b):t)=map (\(c,d)->(a-c)^2+(b-d)^2) t++h t
h _=[]
j=k.nub.sort.h

I tested on

test1 = [(0,0),(3,4),(-4,3),(-1,7)] -- j test1 is True
test2 = [(0,0),(3,4),(-3,4),(0,8)]  -- j test2 is False
share|improve this answer
    
Note the above never gets the distance from a point to itself, so the presence of a distance of 0 would indicate a repeated point in the input list, and this will show up in the sorted list as k [0,b] so 2*0==b will always fail since b cannot be same the as 0. –  Chris Kuklewicz Mar 11 '11 at 16:58

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.

share|improve this answer

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)])
share|improve this answer
    
Shouldn't print be included in the function S and thus counted? –  David Carraher May 15 '13 at 3:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.