Ustal, czy 4 punkty tworzą kwadrat

29

Napisz funkcję, która pobiera 4 punkty na płaszczyźnie jako dane wejściowe i zwraca true, jeśli 4 punkty tworzą kwadrat. Punkty będą miały współrzędne całkowite o wartościach bezwzględnych <1000.

Jako danych wejściowych możesz wykorzystać dowolną rozsądną reprezentację 4 punktów. Punkty nie są podane w żadnej określonej kolejności.

Najkrótszy kod wygrywa.

Przykładowe kwadraty:

(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

Przykładowe kwadraty:

(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

Możesz zwrócić wartość true lub false dla zdegenerowanego kwadratu (0,0),(0,0),(0,0),(0,0)

Keith Randall
źródło
Mówimy tutaj o punktach 3D, prawda?
gnibbler
3
@gnibbler „on na płaszczyźnie” część make zapytania 3D wskazuje prawdopodobne.
JB
Czy punkty są podane w kolejności?
JB
@JB, myślałem, że to oznacza, że ​​punkty były na płaszczyźnie, ale z jakiegoś powodu wizualizowałem samolot w przestrzeni 3D :)
gnibbler
1
@eBusiness: -1, że oddałeś 11 głosów: 7 z nich nie działa.
Eelvex 11.03.11

Odpowiedzi:

12

Python 176 90 79 bajtów

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

Funkcja S przyjmuje listę liczb zespolonych jako swoje dane wejściowe (A). Jeśli znamy zarówno środek, jak i jeden narożnik kwadratu, możemy go zrekonstruować, obracając narożnik o 90,180 i 270 stopni wokół punktu środkowego (c). Na płaszczyźnie złożonej obrót o 90 stopni wokół punktu początkowego odbywa się przez pomnożenie punktu przez i . Jeśli nasz pierwotny kształt i zrekonstruowany kwadrat mają te same punkty, to musiał to być kwadrat.

koń papierowy
źródło
Kilka optymalizacji: 1) użyj „S” zamiast „is_square” 2) umieść wszystko w jednym wierszu za pomocą; 3) iteruj bezpośrednio w 4 kierunkach „dla i w (1,1j, -1, -1j)” 4) nie potrzebuje [] w ustawionym argumencie.
Keith Randall
Dzięki, Keith. (
Pominąłem
2
@ Keith Randall - Dlaczego zostało to zaakceptowane, gdy JB ma znacznie krótsze rozwiązanie?
aaaaaaaaaaaa
1
Dwa powody. Po pierwsze, J. zawsze wygrywał. Więc lubię normalizować trochę według języka. Również bardziej podoba mi się ta odpowiedź, ponieważ nie cierpi z powodu tego samego problemu, co odpowiedzi tylko na odległość, gdzie inne liczby (co prawda, tylko irracjonalne) dają fałszywe wyniki dodatnie.
Keith Randall
5
@ Keith Randall - Cytaty z pytania: „Punkty będą miały współrzędne całkowite” „Wygrywa najkrótszy kod”. Jest całkowicie w porządku, jeśli wybierzesz inne kryteria wyboru odpowiedzi, nawet kryteria subiektywne, ale powinieneś podać to w pytaniu.
aaaaaaaaaaaa
13

J, 28 17 25 27

J tak naprawdę nie ma funkcji, ale oto czasownik monadyczny, który pobiera wektor punktów ze złożonej płaszczyzny:

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

Metoda jest mieszanką Michaela Spencera (działa wyłącznie na długościach między wierzchołkami; ale obecnie zawodzi mój romb2) i działa Eelvex (sprawdź rozmiary zestawów). Czytanie od prawej do lewej:

  • -/~ oblicz wszystkie różnice punktowe
  • , spłaszczyć
  • | wyciągnij wielkość
  • /:~ Uporządkuj
  • #/.~ pocałować i policzyć
  • 4 8 4 -:muszą mieć dokładnie 4 jednakowe odległości (przy 0), 8 nieco większe (długość 1, boki), jeszcze 4 większe (długość sqrt 2, przekątne)

Demonstracja:

   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

Ze względu na pamięć moja poprzednia metoda (wymagała uporządkowanych wierzchołków, ale mogła wykryć regularne wielokąty dowolnego rzędu):

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

Zobacz historię dla wyjaśnienia i wersji demonstracyjnej. Obecną metodę można by prawdopodobnie rozszerzyć na inne wielokąty, co 4 8 4wygląda bardzo podobnie do rozkładu dwumianowego.

JB
źródło
Czy możesz link do tego języka?
Sargun Dhillon
1
@gnibbler: Dlaczego nie? Jestem prawie pewien, że tak.
Eelvex 11.03.11
1
W rzeczywistości istnieje figura niekwadratowa, która spełnia warunki, które sprawdzasz, regularny trójkąt plus jeden punkt długości boku od wierzchołka trójkąta umieszczonego na przedłużonej środkowej. Ale pytanie wymagało wprowadzenia liczb całkowitych, więc myślę, że rozwiązanie jest w porządku.
aaaaaaaaaaaa
1
Ach, okej Myślałem o trójkątach równobocznych, w których środkowy był czwarty punkt, ale wykluczają to współrzędne całkowite
gnibbler
1
Możesz wyciąć 3 znaki, zmieniając go na jawną definicję: 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

Zaktualizuj 1), aby wymagać 4 różnych punktów (dawałoby to fałszywie dodatnie wyniki dla powtarzających się punktów - czy są inne?) 2), aby zdefiniować funkcję według specyfikacji

W przypadku kwadratu wektor między dowolnymi dwoma punktami musi wynosić 0 (ten sam punkt), bok lub przekątną. Tak więc zestaw wielkości tych wektorów musi mieć długość 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
źródło
Myślę, że pytanie wyraźnie zawiera listę punktów, a nie wektor.
Sargun Dhillon
Fałszywe trafienia.
aaaaaaaaaaaa
1
Więc (0 + 0j, 0 + 0j, 1 + 0j, 0 + 1j) jest kwadratem?
mhagger,
Mój romb 2 nie ma wartości 1 +/- 60j, jest bardziej podobny do exp (i j pi / 3) dla wartości z -1, 0, 1. Zauważ, że jak wskazał eBiznes, nie wszystkie mogą być integralne, więc nie zakres pytania.
JB
3

Haskell, 100 znaków

Oto jak napisałbym rozwiązanie JB JB w Haskell. Bez próby zniszczenia czytelności poprzez usunięcie nieistotnych znaków, jest około 132 znaków:

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]

Możesz zeskrobać go trochę do 100, usuwając nadmiar spacji i zmieniając nazwy niektórych rzeczy

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]

Użyjmy QuickCheck, aby upewnić się, że akceptuje on dowolne kwadraty, z jednym wierzchołkiem w (x, y) i wektorem krawędzi (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)]

Próbowanie w ghci:

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

No tak, pusty kwadrat nie jest tutaj uważany za kwadrat, więc zmienimy nasz 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)]

I spróbuj ponownie:

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

źródło
1
Zapisz 11 znaków, rozwijając funkcję d. s l=[4,8,4]==(map length.group.sort)[(x-a)^2+(y-b)^2|(x,y)<-l,(a,b)<-l]
Ray
3

Czynnik

Implementacja w języku programowania 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 ;

I niektóre testy jednostkowe:

[ 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
źródło
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

Uruchom tak:

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

Odszyfrujmy i wyjaśnijmy trochę.

Najpierw określamy normę:

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

Zauważysz, że nie ma połączenia z sqrt, nie jest tu potrzebne.

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

Tutaj a, b, c i d są punktami. Zakładamy, że te punkty są przedstawione w następujący sposób:

a - b
| / |
c - d

Jeśli mamy kwadrat, wszystkie te warunki muszą obejmować:

  • abc jest trójkątem prostokątnym
  • bcd to trójkąt prostokątny
  • mniejsze boki każdego prawego trójkąta mają te same normy

Pamiętaj, że zawsze obowiązują następujące zasady:

is_square_with_fixed_layout r s t u = is_square_with_fixed_layout r t s u

Wykorzystamy to, aby uprościć naszą funkcję testową poniżej.

Ponieważ nasze dane wejściowe nie są uporządkowane, musimy również sprawdzić wszystkie permutacje. Bez utraty ogólności możemy uniknąć permutacji pierwszego punktu:

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

Po uproszczeniu:

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

Edycja: postępowała zgodnie z radą M. Giovanniniego.

bltxd
źródło
Miły. Nie widzieliśmy tu zbyt wiele OCaml :)
Eelvex
Użyj operatora zamiast ndo obniżenia 20 znaków: 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)

Punkty są reprezentowane przez (x,y)krotki. Punkty mogą być w dowolnej kolejności i akceptują tylko kwadraty. Tworzy listę sodległości parami (niezerowymi) między punktami. Łącznie powinno być 12 odległości, w dwóch unikalnych grupach.

def f (p): s = filtr (brak, [(xz) ** 2+ (yw) ** 2 dla x, yw p dla z, w w p]); zwróć len (s) == 12 i len ( set (s)) == 2
Hoa Long Tam
źródło
Możesz pominąć filtr i sprawdzić, czy długość zestawu wynosi 3. To cierpi z powodu tego samego fałszywie pozytywnego problemu, co moja odpowiedź.
gnibbler 11.03.11
>>> f ([(0,0), (0,4), (2,2), (- 2,2)]) = Prawda
Sargun Dhillon
2
f([(0,0),(0,4),(2,2),(-2,2)]) jest kwadratowy
gnibbler
2

Python - 42 znaki

Wygląda na to, że poprawiono użycie liczb zespolonych dla punktów

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

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

stara odpowiedź:

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

Punkty są określone w dowolnej kolejności jako lista, np

A = [(11, 13), (14, 12), (13, 9), (10, 10)]
gnibbler
źródło
>>> 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, to specjalny przypadek całej klasy danych wejściowych, które nie działają. Próbuję wymyślić poprawkę, która nie wydmuchuje rozmiaru odpowiedzi. Tymczasem, czy można wypracować ogólną klasę nieudanych spraw?
gnibbler 11.11.11
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: ten przykład jest kwadratem.
Keith Randall
aby pozbyć się zduplikowanych punktów, możesz dodać -set ([0])
Keith Randall
2

C # - niezupełnie krótki. Nadużywanie LINQ. Wybiera odrębne dwie kombinacje punktów na wejściu, oblicza ich odległości, a następnie sprawdza, czy dokładnie cztery z nich są równe i czy istnieje tylko jedna inna wyraźna wartość odległości. Point to klasa z dwoma podwójnymi członkami, X i Y. Z łatwością może być Tuple, ale 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
źródło
2

PHP, 82 znaki


//$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
źródło
Ale fakt, że obwiednia jest kwadratowa, nie oznacza, że ​​punkty leżą w kwadracie. Warunek konieczny, ale niewystarczający. Rozważ (0,0), (5,5), (10,0), (0, -5). Obwiednia jest kwadratowa (0:10, -5: 5); liczba nie jest.
Floris,
2

K - 33

Tłumaczenie rozwiązania J przez JB :

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

K cierpi tutaj z powodu zarezerwowanych słów ( _sqri _sqrt).

Testowanie:

  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
izawdrony
źródło
2

OCaml + Baterie, 132 znaki

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

(patrz, Ma, bez spacji!) Zrozumienie listy qtworzy listę kwadratowych norm dla każdej odrębnej nieuporządkowanej pary punktów. Kwadrat ma cztery równe boki i dwie równe przekątne, przy czym kwadratowe długości tego ostatniego są dwa razy większe od kwadratowych długości poprzedniego. Ponieważ w sieci liczb całkowitych nie ma trójkątów równobocznych, test nie jest tak naprawdę konieczny, ale uwzględniam go dla kompletności.

Testy:

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
źródło
2

Mathematica 65 80 69 66

Sprawdza, czy liczba wyraźnych odległości między punktami (nie licząc odległości od punktu do siebie) wynosi 2, a krótsza z nich nie jest równa 0.

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

Stosowanie

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

Prawda
Prawda
Prawda
Fałsz
Fałsz
Fałsz
Fałsz Fałsz

NB: \[And]jest pojedynczą postacią w Mathematica.

DavidC
źródło
1
Mówisz mi, że Mathematica nie ma wbudowanej funkcji IsSquare?
goodguy,
2

Galaretki , 8 bajtów

_Æm×ıḟƊṆ

Wypróbuj online!

Pobiera listę liczb zespolonych jako argument wiersza poleceń. Odbitki 1lub 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.

To wydaje się być przyjemnym wyzwaniem, aby ożywić!

Lynn
źródło
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

Naiwna pierwsza próba. Sprawdza następujące dwa warunki dla wszystkich permutacji wejściowej listy punktów (gdzie dana permutacja reprezentuje, powiedzmy, uporządkowanie punktów zgodnie z ruchem wskazówek zegara):

  • wszystkie kąty są 90 stopni
  • wszystkie boki mają tę samą długość

Odszyfrowany kod i testy

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
źródło
1

Scala (146 znaków)

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
źródło
1

JavaScript 144 znaki

Matematycznie równa odpowiedzi J Bs. Generuje 6 długości i zapewnia, że ​​2 największe są równe, a 4 najmniejsze są równe. Dane wejściowe muszą być tablicą tablic.

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
źródło
1

PHP, 161 158 znaków

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

Dowód (1x1): http://codepad.viper-7.com/ZlBpOB

Jest to oparte na odpowiedzi JavaScript na eBuisness .

Kevin Brown
źródło
To jest trochę niejasne w opisie problemu, w którym punkty będą uporządkowane. Pójdę zapytać
JB
1
Nie sądzę, aby to poprawnie obsługiwało wiele spraw. Na przykład nieprawidłowo oznaczy romby jako kwadraty.
Keith Randall
Zaktualizowano to, aby pasowało do jednej z odpowiedzi JavaScript, powinno obsługiwać wszystkie przypadki.
Kevin Brown,
1

JavaScript 1.8, 112 znaków

Aktualizacja: zapisano 2 znaki, składając razem tablice.

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

Kolejne powtórzenie odpowiedzi JB. Wykorzystuje funkcje JavaScript 1.7 / 1.8 (zamykanie wyrażeń, interpretacja tablic, przypisywanie destrukcyjne). Nadużywają również ~~(podwójnie bitowe nie operatora) undefinedprzymusu do liczbowego, z przymusem tablic na ciąg i wyrażeniem regularnym, aby sprawdzić, czy liczy się długość [4, 8, 4](zakłada, że ​​przekazano dokładnie 4 punkty). Nadużycie operatora przecinka to stara zaciemniona sztuczka C.

Testy:

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
źródło
1

GoRuby - 66 znaków

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

rozszerzony:

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

Ten sam algorytm co odpowiedź JB .

Testuj jak:

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

Dane wyjściowe truedla true i puste dla false

Nemo157
źródło
Nigdy nie słyszałem o GoRuby. Czy jest coś oficjalnego na ten temat napisanego? stackoverflow.com/questions/63998/hidden-features-of-ruby/…
Jonas Elfström
@Jonas: Nie widziałem nic naprawdę oficjalnego na ten temat, najlepszy post na blogu, jaki widziałem, to ten . Właściwie nie byłem w stanie go zbudować i działać, ale alternatywą jest po prostu skopiowanie preludium do golfa do tego samego folderu i uruchomienie ruby -r ./golf-prelude.rb FILE_TO_RUN.rbgo, i będzie działało dokładnie tak samo.
Nemo157,
nie jest konieczne, aby sortprzed group_by. .sort.group_by {...}należy zapisać jako.group_by {...}
użytkownik102008,
1

Python 97 (bez punktów złożonych)

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

Spowoduje to pobranie list krotek punktowych w [(x, y), (x, y), (x, y), (x, y)] w dowolnej kolejności i może obsłużyć duplikaty lub niewłaściwą liczbę punktów. NIE wymaga złożonych punktów, takich jak inne odpowiedzi w języku Python.

Możesz to przetestować w następujący sposób:

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)

To wymaga trochę wyjaśnienia, ale ogólną ideą jest to, że istnieją tylko trzy odległości między punktami w kwadracie (bok, przekątna, zero (punkt w porównaniu do siebie)):

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]))
  • dla listy p krotek (x, y)
  • Usuń duplikaty za pomocą zestawu (p), a następnie przetestuj długość
  • Zdobądź każdą kombinację punktów (a, bw p dla c, dw p)
  • Uzyskaj listę odległości od każdego punktu do każdego innego punktu
  • Użyj zestawu, aby sprawdzić, czy istnieją tylko trzy unikalne odległości - zero (punkt w porównaniu do siebie) - długość boku - długość po przekątnej

Aby zapisać znaki kodowe, jestem:

  • używając nazwy funkcji 1 char
  • używając definicji funkcji 1-liniowej
  • Zamiast sprawdzać liczbę unikalnych punktów to 4, sprawdzam, że -1 to różne długości punktów (zapisy == 3 ==)
  • użyj listy i rozpakowywania krotek, aby uzyskać a, bw p dla c, d w p, zamiast używania [0], a [1]
  • używa pow (x, .5) zamiast matematyki, aby uzyskać sqrt (x)
  • nie wstawianie spacji po)
  • nie umieszczając wiodącego zera na pływaku

Obawiam się, że ktoś może znaleźć przypadek testowy, który to psuje. Więc proszę, zrób i źle. Na przykład fakt, że sprawdzam tylko trzy odległości, zamiast wykonywania abs () i sprawdzania długości boku i przeciwprostokątnej, wydaje się błędem.

Pierwszy raz próbowałem golfa kodowego. Bądź miły, jeśli złamałem jakieś zasady domu.

Jagu
źródło
1

Clojure, 159 znaków.

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

Edycja: aby trochę wyjaśnić.

  • Najpierw zdefiniuj normę, która zasadniczo określa odległość między dwoma podanymi punktami.
  • Następnie oblicz odległość pierwszego punktu do pozostałych trzech punktów.
  • Posortuj trzy odległości. (Pozwala to na dowolną kolejność punktów.)
  • Dwie najkrótsze odległości muszą być równe kwadratowi.
  • Trzecia (najdłuższa) odległość musi być równa pierwiastkowi kwadratowemu sumy kwadratów krótkich odległości według twierdzenia Pitagorasa.

(Uwaga: kwadratowe rootowanie nie jest potrzebne, a zatem w kodzie zapisanym powyżej.)

Meikel
źródło
1

C #, 107 znaków

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

Gdzie punkty to Lista Vector3D zawierająca punkty.

Oblicza wszystkie odległości do kwadratu między wszystkimi punktami, a jeśli istnieją dokładnie trzy różne typy (musi wynosić 0, niektóre wartości a, i 2 * a) i 4 różne punkty, wówczas punkty tworzą kwadrat.

TY
źródło
1

Python 2 , 49 bajtów

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

Wypróbuj online!

Pobiera na wejściu listę czterech liczb zespolonych. Obraca każdy punkt o 90 stopni wokół średniej i sprawdza, czy każdy wynikowy punkt znajduje się na oryginalnej liście.

Ta sama długość (choć krótsza przy użyciu Python 3 {*l}).

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

Wypróbuj online!

xnor
źródło
Dlaczego nie użyć Python 3, jeśli jest on krótszy? Ponadto, jeśli dozwolone jest zwracanie dowolnych wartości true / falsy w Pythonie, ^można użyć zamiast ==.
Joel
@Joel Python 2 jest przede wszystkim preferowany i jest to naprawdę stare wyzwanie z 2011 roku, kiedy Python 2 był prawie zakładany, że gra w golfa w Pythonie. Wyzwanie mówi, że należy zwrócić prawdę lub fałsz, więc utknąłem z tym. Gdyby został opublikowany dzisiaj, prawdopodobnie określałby wyprowadzanie truey / falsey lub jedną z dwóch odrębnych wartości, i może nawet OK założyć, że domyślnie.
xnor
1

Wolfram Language (Mathematica) , 32 31 bajtów

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

Wypróbuj online!

Pobiera listę punktów reprezentowanych przez liczby zespolone, oblicza drugi i trzeci centralny moment i sprawdza, czy oba są równe zero.

Bez golfa:

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

lub

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

dowód

To kryterium działa na całej płaszczyźnie złożonej, nie tylko na liczbach całkowitych Gaussa .

  1. Po pierwsze, zauważamy, że momenty centralne nie zmieniają się, gdy punkty są tłumaczone razem. Dla zestawu punktów

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

    wszystkie momenty centralne są niezależne c(dlatego nazywane są centralnymi ):

    {FreeQ[FullSimplify[CentralMoment[P, 2]], c], FreeQ[FullSimplify[CentralMoment[P, 3]], c]}
    (*    {True, True}    *)
    
  2. Po drugie, momenty centralne mają prostą zależność od ogólnego złożonego skalowania (skalowania i obrotu) zestawu punktów:

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

    Oznacza to, że jeśli moment centralny wynosi zero, wówczas skalowanie i / lub obracanie zestawu punktów utrzyma moment centralny równy zero.

  3. Po trzecie, udowodnijmy kryterium dla listy punktów, w której pierwsze dwa punkty są ustalone:

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

    W jakich warunkach rzeczywiste i urojone części drugiego i trzeciego centralnego momentu są zerowe?

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

    Wszystkie te sześć rozwiązań reprezentują kwadraty: wprowadź opis zdjęcia tutaj Dlatego jedynym sposobem, w jaki lista punktów formy {0, 1, x[3] + I*y[3], x[4] + I*y[4]}może mieć zero sekund i trzeci centralny moment, jest to, że cztery punkty tworzą kwadrat.

Ze względu na właściwości translacji, obrotu i skalowania przedstawione w punktach 1 i 2 oznacza to, że za każdym razem, gdy drugi i trzeci centralny moment są zerowe, mamy kwadrat w pewnym stanie translacji / obrotu / skalowania. ∎

uogólnienie

K-ty centralny moment zwykłego n-gonu wynosi zero, jeżeli k nie jest podzielne przez n. Wystarczającą liczbę tych warunków należy połączyć, aby stworzyć wystarczające kryterium wykrywania n-gonów. Dla przypadku n = 4 wystarczyło wykryć zera w k = 2 i k = 3; w celu wykrycia np. sześciokątów (n = 6) może być konieczne sprawdzenie k = 2,3,4,5 dla zer. Nie udowodniłem, co następuje, ale podejrzewam, że wykryje każdy regularny n-gon:

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

Wyzwanie kodu jest zasadniczo tym kodem specjalizującym się w listach o długości 4.

rzymski
źródło
Rozwiązanie wygląda dość interesująco. Czy możesz wyjaśnić, dlaczego daje prawidłową odpowiedź?
Joel
@Joel Dodałem dowód.
Rzym.
Wielkie dzięki. Idealnie byłoby, gdyby istniało bardziej intuicyjne matematyczne wyjaśnienie tego miłego rozwiązania.
Joel
@Joel Mogę dać Wątek, który doprowadził mnie do tego rozwiązania. Zacząłem od zauważenia, że ​​kwadraty (jako listy współrzędnych, a nie liczby zespolone) mają macierz kowariancji, która jest proporcjonalna do macierzy jednostek; jednak warunek ten nie jest wystarczający (fałszywie dodatnie). Trzeci moment centralny musi wynosić zero dla dowolnej struktury symetrii punktowej. Dlatego przełączyłem się na złożoną reprezentację, aby ustawić warunek na drugi i trzeci centralny moment, i ku mojemu zaskoczeniu okazało się, że drugi centralny moment wynosi zero dla kwadratów.
Rzym.
Świetny. Dziękujemy za wskazanie ścieżki do tego rozwiązania.
Joel
0

J, 31 29 27 26

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

sprawdza, czy 8 najmniejszych odległości między punktami jest takich samych. sprawdza, czy istnieją dokładnie trzy rodzaje odległości między punktami (zero, długość boku i długość po przekątnej).

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 $ jest sposobem na napisanie tablicy w J.

Eelvex
źródło
To nie przejdzie testu rombowego.
JB
@JB: Miałem literówkę. I tak zmieniłem metodę.
Eelvex 11.03.11
Eeew ... używasz tej samej metody, którą kradłem. Z wyjątkiem krótszej wersji mojej wersji: p
JB
@JB: naprawdę? Nie zauważyłem tego. Kto jeszcze sprawdza (3 == #dystansy)?
Eelvex 11.03.11
@JB: oic ... niektóre sprawdzają kombinacje 2.: - /
Eelvex
0

Smalltalk na 106 znaków

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

gdzie p jest zbiorem punktów, np

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

Myślę, że matematyka jest zdrowa ...


źródło
Sprawdzanie 2 odrębnych produktów punktowych nie pozwala go wyciąć. Punkty umieszczone w tej samej pozycji mogą dawać fałszywe wyniki dodatnie.
aaaaaaaaaaaa
0

Mathematica, 123 znaki (ale możesz zrobić to lepiej):

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

Gdzie „a” to dane wejściowe w formie listy Mathematica, np .: a={{0,0},{3,4},{8,4},{5,0}}

Kluczem jest przyjrzenie się iloczynom kropkowym między wszystkimi wektorami i zauważeniu, że muszą mieć dokładnie trzy wartości: 0, x i 2 * x dla pewnej wartości x. Produkt w kropki sprawdza zarówno prostopadłość, jak i długość w jednym pęczniejącym źdźble.

Wiem, że istnieją skróty matematyczne, które mogą uczynić to krótszymi, ale nie wiem, jakie są.

bariera
źródło
Myślę, że ten też jest zły, ale nie mogę zrozumieć, co robi kod.
aaaaaaaaaaaa
Oblicza wszystkie wektory między 4 punktami, bierze wszystkie iloczyny punktowe (wartość bezwzględna) i oczekuje, że wynik będzie składał się dokładnie z 0, x, 2 * x dla pewnej wartości x.
bariera karty
Tak więc 16 wektorów -> 256 produktów kropkowych i sprawdzasz, że wysoka wartość jest 2 razy niższa, ale nie wiesz, ile jest każdej z nich. Czy to dobrze zrozumiane?
aaaaaaaaaaaa
Tak, to poprawnie opisuje mój algorytm. I myślę, że masz rację: możesz skonstruować scenariusz, w którym wystąpiły wszystkie 3 wartości, ale nie we właściwej ilości. Szczury Czy powinno to być naprawialne?
barrycarter
@barrycarter Możesz zapisywać postacie, używając Unionzamiast Sort@DeleteDuplicates. #[[1]] == 0 && #[[3]]/#[[2]] == 2 &[ Union@Abs@Flatten[Table[c.d, {c, #}, {d, #}]] &[ Flatten[Table[x - y, {x, a}, {y, a}], 1]]]
Złożyłem
0

Haskell, „wc -c” zgłasza 110 znaków. Nie sprawdza, czy wejście ma 4 elementy.

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

Testowałem na

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
źródło
Zauważ, że powyższe nigdy nie otrzymuje odległości od punktu do siebie, więc obecność odległości 0 wskazywałaby na powtarzający się punkt na liście wprowadzania, a to pokaże się na posortowanej liście jako k [0, b], więc 2 * 0 == b zawsze zawiedzie, ponieważ b nie może być takie samo jak 0.
Chris Kuklewicz