Déterminez si 4 points forment un carré

29

Écrivez une fonction qui prend 4 points sur le plan en entrée et renvoie vrai si les 4 points forment un carré. Les points auront des coordonnées intégrales avec des valeurs absolues <1000.

Vous pouvez utiliser toute représentation raisonnable des 4 points en entrée. Les points ne sont pas fournis dans un ordre particulier.

Le code le plus court gagne.

Exemples de carrés:

(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

Exemple de non-carrés:

(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

Vous pouvez retourner vrai ou faux pour le carré dégénéré (0,0),(0,0),(0,0),(0,0)

Keith Randall
la source
Nous parlons ici de points 3D, non?
gnibbler
3
@gnibbler la partie "dans l' avion" de la question rend les points 3D improbables.
JB
Les points sont-ils donnés dans l'ordre?
JB
@JB, je pensais que cela signifiait que les points étaient dans un avion, mais j'ai visualisé un avion dans l'espace 3D pour une raison quelconque :)
gnibbler
1
@eBusiness: -1 que vous avez émis 11 votes: 7 d'entre eux sont en baisse.
Eelvex

Réponses:

12

Python 176 90 79 octets

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

La fonction S prend une liste de nombres complexes comme entrée (A). Si nous connaissons à la fois le centre et un coin d'un carré, nous pouvons reconstruire le carré en tournant le coin de 90 180 et 270 degrés autour du point central (c). Sur le plan complexe, la rotation de 90 degrés autour de l'origine se fait en multipliant le point par i . Si notre forme d'origine et le carré reconstruit ont les mêmes points, cela doit être un carré.

cheval de papier
la source
Quelques optimisations: 1) utilisez "S" au lieu de "is_square" 2) mettez le tout sur une seule ligne en utilisant; 3) itérer directement sur les 4 directions "pour i dans (1,1j, -1, -1j)" 4) n'a pas besoin de [] dans l'argument set.
Keith Randall
Merci Keith. (J'ai
omis
2
@Keith Randall - Pourquoi cela a-t-il été accepté alors que JB a une solution beaucoup plus courte?
aaaaaaaaaaaa
1
Deux raisons. Premièrement, J gagnerait toujours. J'aime donc normaliser un peu par la langue. De plus, j'aime mieux cette réponse car elle ne souffre pas du même problème que les réponses à distance uniquement où d'autres chiffres (certes, seulement irrationnels) donnent de faux positifs.
Keith Randall
5
@Keith Randall - Citations de la question: "Les points auront des coordonnées intégrales" "Le code le plus court gagne.". C'est parfaitement bien si vous choisissez différents critères pour sélectionner une réponse, même des critères subjectifs, mais alors vous devez le dire dans la question.
aaaaaaaaaaaa
13

J, 28 17 25 27

J n'a pas vraiment de fonctions, mais voici un verbe monadique qui prend un vecteur de points du plan complexe:

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

La méthode est un mélange de Michael Spencer (travail uniquement sur les longueurs inter-vertex; mais il échoue actuellement à mon losange2) et Eelvex (vérifiez les tailles des ensembles). Lecture de droite à gauche:

  • -/~ calculer toutes les différences de points
  • , aplatir
  • | extraire la magnitude
  • /:~ Trier
  • #/.~ nub and count
  • 4 8 4 -:doit avoir exactement 4 équidistances (à 0), 8 un peu plus grandes (longueur 1, côtés), 4 plus grandes encore (longueur sqrt 2, diagonales)

Manifestation:

   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

Pour mémoire, ma méthode précédente (requis sommets ordonnés, mais pouvait détecter des polygones réguliers de n'importe quel ordre):

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

Voir l'historique pour l'explication et la démo. La méthode actuelle pourrait probablement être étendue à d'autres polygones, ce 4 8 4qui ressemble beaucoup à une distribution binomiale.

JB
la source
Pouvez-vous créer un lien vers cette langue?
Sargun Dhillon
1
@gnibbler: Pourquoi pas? Je suis presque sûr que oui.
Eelvex
1
En fait, il existe une figure non carrée qui remplit les conditions que vous vérifiez, un triangle régulier plus un point sur une longueur de côté à partir d'une extrémité du triangle placée sur la médiane étendue. Mais la question appelait une entrée entière, donc je suppose que la solution est correcte.
aaaaaaaaaaaa
1
Ah ok. Je pensais à des triangles équilatéraux avec le 4ème point étant le centre, mais cela est exclu par les coordonnées
entières
1
Vous pouvez couper 3 caractères en le changeant en une définition explicite: 3 :'4 8 4-:#/.~/:~|,-/~y'
isawdrones
5

Python, 71 42

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

Mise à jour 1) pour exiger 4 points différents (donnerait auparavant des faux positifs pour les points répétés - y en a-t-il d'autres?) 2) pour définir une fonction par spécification

Pour un carré, le vecteur entre deux points quelconques doit être 0 (le même point), un côté ou une diagonale. Ainsi, l'ensemble de la magnitude de ces vecteurs doit avoir une longueur de 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)
mbomb007
la source
Je pense que la question énonçait explicitement une liste de points, et non un vecteur.
Sargun Dhillon
Faux positifs.
aaaaaaaaaaaa
1
Donc (0 + 0j, 0 + 0j, 1 + 0j, 0 + 1j) est un carré?
mhagger
Mon losange 2 n'est pas 1 +/- 60j, il ressemble plus à exp (i j pi / 3) pour les valeurs de -1, 0, 1. Notez que comme eBusiness l'a souligné, ils ne peuvent pas tous être intégrés, donc pas vraiment dans la portée de la question.
JB
3

Haskell, 100 caractères

Voici comment j'écrirais la solution J de JB dans Haskell. Sans aucune tentative de nuire à la lisibilité en supprimant les caractères non essentiels, il s'agit d'environ 132 caractères:

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]

Vous pouvez le réduire à 100 en supprimant les espaces en excès et en renommant certaines choses

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]

Utilisons QuickCheck pour nous assurer qu'il accepte des carrés arbitraires, avec un sommet en (x, y) et un vecteur de bord (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)]

L'essayer dans ghci:

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

Oh oui, le carré vide n'est pas considéré comme un carré ici, nous allons donc réviser notre 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)]

Et réessayez:

ghci> quickCheck prop_square
+++ OK, passed 100 tests.

la source
1
Enregistrez 11 caractères en déroulant la fonction d. s l=[4,8,4]==(map length.group.sort)[(x-a)^2+(y-b)^2|(x,y)<-l,(a,b)<-l]
Ray
3

Facteur

Une implémentation dans le langage de programmation Factor :

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 ;

Et quelques tests unitaires:

[ 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
mrjbq7
la source
3

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

Courez comme ceci:

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

Désobfusquons et expliquons un peu.

Nous définissons d'abord une norme:

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

Vous remarquerez qu'il n'y a pas d'appel à sqrt, ce n'est pas nécessaire ici.

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

Ici a, b, c et d sont des points. Nous supposons que ces points sont présentés comme suit:

a - b
| / |
c - d

Si nous avons un carré, toutes ces conditions doivent être remplies:

  • abc est un triangle rectangle
  • bcd est un triangle rectangle
  • les petits côtés de chaque triangle rectangle ont les mêmes normes

Notez que ce qui suit est toujours valable:

is_square_with_fixed_layout r s t u = is_square_with_fixed_layout r t s u

Nous utiliserons cela pour simplifier notre fonction de test ci-dessous.

Puisque notre entrée n'est pas ordonnée, nous devons également vérifier toutes les permutations. Sans perte de généralité on peut éviter de permuter le premier 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

Après 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: suivi les conseils de M.Giovannini.

bltxd
la source
Agréable. Nous n'avons pas vu beaucoup d'OCaml ici :)
Eelvex
Utilisez un opérateur au lieu de nune réduction de 20 caractères: 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
2

Python (105)

Les points sont représentés par des (x,y)tuples. Les points peuvent être dans n'importe quel ordre et n'acceptent que les carrés. Crée une liste s,, de paires (non nulles) de distances entre les points. Il devrait y avoir 12 distances au total, en deux groupes uniques.

def f (p): s = filtre (Aucun, [(xz) ** 2+ (yw) ** 2 pour x, y en p pour z, w en p]); renvoyer len (s) == 12et len ​​( ensemble (s)) == 2
Hoa Long Tam
la source
Vous pouvez laisser de côté le filtre et vérifier si le len de l'ensemble est 3. Cela souffre du même problème de faux positif que ma réponse.
gnibbler
>>> f ([(0,0), (0,4), (2,2), (- 2,2)]) = True
Sargun Dhillon
2
f([(0,0),(0,4),(2,2),(-2,2)]) est un carré
grignoteur
2

Python - 42 caractères

On dirait que c'est une amélioration d'utiliser des nombres complexes pour les points

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

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

ancienne réponse:

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

Les points sont spécifiés dans n'importe quel ordre sous forme de liste, par exemple

A = [(11, 13), (14, 12), (13, 9), (10, 10)]
grignoteur
la source
>>> 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
@Sargun, c'est un cas particulier de toute une classe d'entrées qui ne fonctionnent pas. J'essaie de penser à un correctif qui n'explose pas la taille de la réponse. Pendant ce temps, peut-on déterminer la classe générale des cas défaillants?
gnibbler
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
@Sargun: cet exemple est un carré.
Keith Randall
pour se débarrasser des points dupliqués, vous pouvez ajouter -set ([0])
Keith Randall
2

C # - pas exactement court. Abuser de LINQ. Sélectionne deux combinaisons distinctes de points dans l'entrée, calcule leurs distances, puis vérifie qu'exactement quatre d'entre eux sont égaux et qu'il n'y a qu'une seule autre valeur de distance distincte. Point est une classe avec deux membres doubles, X et Y. Pourrait facilement être un tuple, mais 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 );
Daniel Coffman
la source
2

PHP, 82 caractères


//$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]))};
arek
la source
Mais ce n'est pas parce que le cadre de sélection est carré que les points se trouvent dans un carré. Condition nécessaire mais non suffisante. Considérez (0,0), (5,5), (10,0), (0, -5). La boîte englobante est carrée (0:10, -5: 5); ce n'est pas le cas.
Floris
2

K - 33

Traduction de la solution J par JB :

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

K souffre ici de ses mots réservés ( _sqret _sqrt).

Essai:

  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
isawdrones
la source
2

OCaml + Batteries, 132 caractères

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

(regardez, Ma, pas d'espaces!) La compréhension de qla liste forme la liste des normes au carré pour chaque paire distincte de points non ordonnés. Un carré a quatre côtés égaux et deux diagonales égales, les longueurs carrées de ce dernier étant le double des longueurs carrées du premier. Puisqu'il n'y a pas de triangles équilatéraux dans le réseau entier, le test n'est pas vraiment nécessaire, mais je l'inclus pour être complet.

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
Matías Giovannini
la source
2

Mathematica 65 80 69 66

Vérifie que le nombre de distances inter-points distinctes (sans compter la distance d'un point à lui-même) est 2 et que la plus courte des deux n'est pas 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 *)

Vrai
Vrai
Vrai
Faux
Faux
Faux
Faux

NB: \[And]est un caractère unique dans Mathematica.

DavidC
la source
1
Êtes-vous en train de me dire que Mathematica n'a pas de fonction IsSquare intégrée?
goodguy
2

Gelée , 8 octets

_Æm×ıḟƊṆ

Essayez-le en ligne!

Prend une liste de nombres complexes comme argument de ligne de commande. Imprime 1ou 0.

_Æm        Subtract mean of points from each point (i.e. center on 0)
   ×ıḟƊ    Rotate 90°, then compute set difference with original.
       Ṇ   Logical negation: if empty (i.e. sets are equal) then 1 else 0.

Cela semble être un défi agréable à revivre!

Lynn
la source
1

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

Première tentative naïve. Vérifie les deux conditions suivantes pour toutes les permutations de la liste de points d'entrée (où une permutation donnée représente, disons, un ordre des points dans le sens horaire):

  • tous les angles sont de 90 degrés
  • tous les côtés sont de la même longueur

Code et tests désobfusqués

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)]
Dan Burton
la source
1

Scala (146 caractères)

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)}
Gareth
la source
1

JavaScript 144 caractères

Mathématiquement égal à la réponse J Bs. Il génère les 6 longueurs et affirme que les 2 plus grandes sont égales et que les 4 plus petites sont égales. L'entrée doit être un tableau de tableaux.

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])
}
aaaaaaaaaaaa
la source
1

PHP, 161 158 caractères

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

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

Ceci est basé sur la réponse JavaScript d' eBuisness .

Kevin Brown
la source
Il n'est pas clair d'après l'énoncé du problème que les points seraient ordonnés. Je vais demander.
JB
1
Je ne pense pas que cela traitera correctement de nombreux cas. Par exemple, il étiquetera incorrectement les losanges comme des carrés.
Keith Randall
Mis à jour pour correspondre à l'une des réponses JavaScript, devrait gérer tous les cas.
Kevin Brown
1

JavaScript 1.8, 112 caractères

Mise à jour: enregistré 2 caractères en repliant les compréhensions de tableau ensemble.

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

Une autre réimplémentation de la réponse de JB. Exploite les fonctionnalités JavaScript 1.7 / 1.8 (fermetures d'expressions, compréhensions de tableaux, affectation de déstructuration). Abuse également ~~(double opérateur pas au niveau du bit) pour contraindre undefinedau numérique, avec une contrainte tableau-chaîne et une expression rationnelle pour vérifier que le nombre de longueurs est [4, 8, 4](il suppose que exactement 4 points sont passés). L'abus de l'opérateur virgule est un vieux truc C obscurci.

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
ecatmur
la source
1

GoRuby - 66 caractères

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

étendu:

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

Même algorithme que la réponse de JB .

Testez comme:

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

Sorties truepour vrai et vide pour faux

Nemo157
la source
Jamais entendu parler de GoRuby. Y a-t-il quelque chose d'officiel écrit à ce sujet? stackoverflow.com/questions/63998/hidden-features-of-ruby/…
Jonas Elfström
@ Jonas: Je n'ai rien vu de vraiment officiel à ce sujet, le meilleur article de blog que j'ai vu est celui-ci . Je n'ai pas pu le faire construire et fonctionner, mais une alternative est de simplement copier le golf-prélude dans le même dossier et de l'exécuter ruby -r ./golf-prelude.rb FILE_TO_RUN.rbet cela fonctionnera exactement de la même manière.
Nemo157
ce n'est pas nécessaire sortavant group_by. .sort.group_by {...}devrait être écrit comme.group_by {...}
user102008
1

Python 97 (sans points complexes)

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

Cela prendra des listes de tuples de points dans [(x, y), (x, y), (x, y), (x, y)] dans n'importe quel ordre, et peut gérer les doublons ou le mauvais nombre de points. Il ne nécessite PAS de points complexes comme les autres réponses python.

Vous pouvez le tester comme ceci:

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)

Cela prendra un peu d'explication, mais l'idée générale est qu'il n'y a que trois distances entre les points d'un carré (Side, Diagonal, Zero (point par rapport à lui-même)):

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]))
  • pour une liste p de tuples (x, y)
  • Supprimez les doublons à l'aide de set (p), puis testez la longueur
  • Obtenez chaque combinaison de points (a, b en p pour c, d en p)
  • Obtenez la liste de la distance de chaque point à chaque autre point
  • Utilisez l'ensemble pour vérifier qu'il n'y a que trois distances uniques - Zéro (point par rapport à lui-même) - Longueur latérale - Longueur diagonale

Pour enregistrer les caractères du code, je suis:

  • en utilisant un nom de fonction de 1 caractère
  • en utilisant une définition de fonction 1 ligne
  • Au lieu de vérifier que le nombre de points uniques est de 4, je vérifie qu'il vaut -1 les différentes longueurs de points (sauvegarde == 3 ==)
  • utilisez la décompression de liste et de tuple pour obtenir a, b en p pour c, d en p, au lieu d'utiliser a [0], a [1]
  • utilise pow (x, .5) au lieu d'inclure des mathématiques pour obtenir sqrt (x)
  • ne pas mettre d'espaces après le)
  • ne pas mettre un zéro de tête sur le flotteur

Je crains que quelqu'un ne trouve un test qui casse cela. Alors s'il vous plaît, faites-le et je vais corriger. Par exemple, le fait que je vérifie simplement trois distances, au lieu de faire un abs () et de vérifier la longueur du côté et l'hypoténuse, semble être une erreur.

La première fois que j'ai essayé le golf à code. Soyez gentil si j'ai enfreint les règles de la maison.

Jagu
la source
1

Clojure, 159 caractères.

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: Pour expliquer aussi un peu.

  • Définissez d'abord une norme qui donne essentiellement la distance entre deux points donnés.
  • Calculez ensuite la distance du premier point aux trois autres points.
  • Triez les trois distances. (Cela permet n'importe quel ordre des points.)
  • Les deux distances les plus courtes doivent être égales à un carré.
  • La troisième distance (la plus longue) doit être égale à la racine carrée de la somme des carrés des courtes distances par le théorème de Pythagore.

(Remarque: l'enracinement carré n'est pas nécessaire et donc dans le code enregistré ci-dessus.)

Meikel
la source
1

C #, 107 caractères

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

Où points est la liste de Vector3D contenant les points.

Calcule toutes les distances au carré entre tous les points, et s'il existe exactement trois types distincts (doit être 0, une valeur a et 2 * a) et 4 points distincts, alors les points forment un carré.

TOI
la source
1

Python, 66

Amélioration de la réponse de Paperhorse de 76 à 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)
Réintégrer Monica
la source
1

Python 2 , 49 octets

lambda l:all(1j*z+(1-1j)*sum(l)/4in l for z in l)

Essayez-le en ligne!

Prend une liste de quatre nombres complexes en entrée. Fait pivoter chaque point de 90 degrés autour de la moyenne et vérifie que chaque point résultant figure dans la liste d'origine.

Même longueur (mais plus courte en Python 3 avec {*l}).

lambda l:{1j*z+(1-1j)*sum(l)/4for z in l}==set(l)

Essayez-le en ligne!

xnor
la source
Pourquoi ne pas utiliser Python 3 si c'est plus court? De plus, s'il est autorisé à renvoyer des valeurs arbitraires de vérité / fausse en Python, ^peut être utilisé à la place de ==.
Joel
@Joel Python 2 est la préférence, et que c'est un très vieux défi de 2011 lorsque Python 2 était à peu près supposé jouer au golf Python. Et le défi dit de retourner vrai ou faux, alors je suis resté avec ça. Si cela était publié aujourd'hui, cela spécifierait probablement la sortie de truey / falsey ou l'une des deux valeurs distinctes, et il pourrait même être OK de supposer cela par défaut.
xnor
1

Wolfram Language (Mathematica) , 32 31 octets

Tr[#^2]==Tr[#^3]==0&[#-Mean@#]&

Essayez-le en ligne!

Prend une liste de points représentés par des nombres complexes, calcule les deuxième et troisième moments centraux et vérifie que les deux sont nuls.

Non-golfé:

S[p_] := Total[(p - Mean[p])^2] == Total[(p - Mean[p])^3] == 0

ou

S[p_] := CentralMoment[p, 2] == CentralMoment[p, 3] == 0

preuve

Ce critère fonctionne sur tout le plan complexe, pas seulement sur les entiers gaussiens .

  1. Tout d'abord, nous notons que les moments centraux ne changent pas lorsque les points sont traduits ensemble. Pour un ensemble de points

    P = Table[c + x[i] + I*y[i], {i, 4}]
    

    les moments centraux sont tous indépendants de c(c'est pourquoi ils sont appelés centraux ):

    {FreeQ[FullSimplify[CentralMoment[P, 2]], c], FreeQ[FullSimplify[CentralMoment[P, 3]], c]}
    (*    {True, True}    *)
    
  2. Deuxièmement, les moments centraux dépendent simplement de la mise à l'échelle complexe globale (mise à l'échelle et rotation) de l'ensemble de points:

    P = Table[f * (x[i] + I*y[i]), {i, 4}];
    FullSimplify[CentralMoment[P, 2]]
    (*    f^2 * (...)    *)
    FullSimplify[CentralMoment[P, 3]]
    (*    f^3 * (...)    *)
    

    Cela signifie que si un moment central est nul, la mise à l'échelle et / ou la rotation de l'ensemble de points maintiendra le moment central égal à zéro.

  3. Troisièmement, prouvons le critère pour une liste de points où les deux premiers points sont fixes:

    P = {0, 1, x[3] + I*y[3], x[4] + I*y[4]};
    

    Dans quelles conditions les parties réelle et imaginaire des deuxième et troisième moments centraux sont-elles nulles?

    C2 = CentralMoment[P, 2] // ReIm // ComplexExpand // FullSimplify;
    C3 = CentralMoment[P, 3] // ReIm // ComplexExpand // FullSimplify;
    Solve[Thread[Join[C2, C3] == 0], {x[3], y[3], x[4], y[4]}, Reals] // FullSimplify
    (*    {{x[3] -> 0, y[3] -> -1, x[4] -> 1, y[4] -> -1},
           {x[3] -> 0, y[3] -> 1, x[4] -> 1, y[4] -> 1},
           {x[3] -> 1/2, y[3] -> -1/2, x[4] -> 1/2, y[4] -> 1/2},
           {x[3] -> 1/2, y[3] -> 1/2, x[4] -> 1/2, y[4] -> -1/2},
           {x[3] -> 1, y[3] -> -1, x[4] -> 0, y[4] -> -1},
           {x[3] -> 1, y[3] -> 1, x[4] -> 0, y[4] -> 1}}    *)
    

    Toutes ces six solutions représentent des carrés: entrez la description de l'image ici Par conséquent, la seule façon dont une liste de points de la forme {0, 1, x[3] + I*y[3], x[4] + I*y[4]}peut avoir zéro seconde et troisième moments centraux est lorsque les quatre points forment un carré.

En raison des propriétés de translation, de rotation et de mise à l'échelle démontrées aux points 1 et 2, cela signifie que chaque fois que les deuxième et troisième moments centraux sont nuls, nous avons un carré dans un état de translation / rotation / mise à l'échelle. ∎

généralisation

Le k-ième moment central d'un n-gon régulier est nul si k n'est pas divisible par n. Il faut combiner suffisamment de ces conditions pour constituer un critère suffisant pour détecter les n-gons. Pour le cas n = 4, il suffisait de détecter des zéros dans k = 2 et k = 3; pour détecter, par exemple, des hexagones (n = 6), il peut être nécessaire de vérifier k = 2,3,4,5 pour les zéros. Je n'ai pas prouvé ce qui suit, mais je soupçonne qu'il détectera tout n-gon régulier:

isregularngon[p_List] :=
  And @@ Table[PossibleZeroQ[CentralMoment[p, k]], {k, 2, Length[p] - 1}]

Le défi du code est essentiellement ce code spécialisé pour les listes de longueur 4.

romain
la source
La solution semble assez intéressante. Pourriez-vous expliquer pourquoi cela donne la bonne réponse?
Joel
@Joel J'ai ajouté une preuve.
Roman
Merci beaucoup. Il serait idéal qu'il puisse y avoir une explication mathématique plus intuitive de cette belle solution.
Joel
@Joel Je peux vous donner le fil qui m'a conduit à cette solution. J'ai commencé par remarquer que les carrés (sous forme de listes de coordonnées et non de nombres complexes) ont une matrice de covariance proportionnelle à la matrice unitaire; cependant, cette condition n'est pas suffisante (faux positifs). Le troisième moment central doit être nul pour toute structure de symétrie ponctuelle. Je suis donc passé à une représentation complexe pour poser une condition sur les deuxième et troisième moments centraux, et à ma grande surprise, il s'est avéré que le deuxième moment central est nul pour les carrés.
Roman
Génial. Merci d'avoir montré le chemin vers cette solution.
Joel
0

J, 31 29 27 26

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

vérifie si les 8 plus petites distances entre les points sont identiques. vérifie s'il existe exactement trois types de distances entre les points (zéro, longueur latérale et longueur diagonale).

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 $ est une façon d'écrire un tableau en J.

Eelvex
la source
Cela échoue au test du losange.
JB
@JB: J'ai eu une faute de frappe. J'ai quand même changé la méthode maintenant.
Eelvex
Eeew ... vous prenez la même méthode que je volais. Sauf ma version la plus courte: p
JB
@JB: vraiment? Je ne l'ai pas remarqué. Qui d'autre vérifie (3 == #distances)?
Eelvex
@JB: oic ... certains vérifient les combinaisons de 2.: - /
Eelvex
0

Smalltalk pour 106 caractères

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

où p est un ensemble de points, par exemple

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

Je pense que les maths sont solides ...


la source
La vérification de 2 produits à points distincts ne suffit pas. Les points placés dans la même position peuvent produire des faux positifs.
aaaaaaaaaaaa
0

Mathematica, 123 caractères (mais vous pouvez faire mieux):

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

Où 'a' est l'entrée sous forme de liste Mathematica, par exemple: a={{0,0},{3,4},{8,4},{5,0}}

La clé est de regarder les produits scalaires entre tous les vecteurs et de noter qu'ils doivent avoir exactement trois valeurs: 0, x et 2 * x pour une valeur de x. Le produit scalaire vérifie à la fois la perpendicularité ET la longueur en un seul gonflement.

Je sais qu'il existe des raccourcis Mathematica qui peuvent rendre cela plus court, mais je ne sais pas ce qu'ils sont.

barrycarter
la source
Je pense que celui-ci est faux également, mais je ne peux pas comprendre ce que fait le code.
aaaaaaaaaaaa
Il calcule tous les vecteurs entre les 4 points, prend tous les produits scalaires (valeur absolue) et s'attend à ce que le résultat se compose exactement de 0, x, 2 * x pour une certaine valeur de x.
barrycarter
Donc, 16 vecteurs -> 256 produits scalaires, et vous vérifiez que la valeur élevée est 2 fois la valeur faible, mais vous ne savez pas combien il y a de chaque valeur. Est-ce bien compris?
aaaaaaaaaaaa
Oui, cela décrit correctement mon algorithme. Et je pense maintenant que vous avez raison: vous pouvez construire un scénario dans lequel les 3 valeurs se sont produites, mais pas dans la bonne quantité. Les rats. Doit être réparable cependant?
barrycarter
@barrycarter Vous pouvez enregistrer des caractères en utilisant Unionau lieu de Sort@DeleteDuplicates. J'ai mis vos 3 lignes ensemble également:#[[1]] == 0 && #[[3]]/#[[2]] == 2 &[ Union@Abs@Flatten[Table[c.d, {c, #}, {d, #}]] &[ Flatten[Table[x - y, {x, a}, {y, a}], 1]]]
DavidC
0

Haskell, "wc -c" rapporte 110 caractères. Ne vérifie pas que l'entrée a 4 éléments.

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

J'ai testé sur

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
Chris Kuklewicz
la source
Notez que ce qui précède n'obtient jamais la distance d'un point à lui-même, donc la présence d'une distance de 0 indiquerait un point répété dans la liste d'entrée, et cela apparaîtra dans la liste triée comme k [0, b] donc 2 * 0 == b échouera toujours car b ne peut pas être identique à 0.
Chris Kuklewicz