7
\$\begingroup\$

Taking in Input

Define a function f as follows:

IF x < 0:
    f(x) = -√|x|
ELSE:
    f(x) = √x

In your programs/functions, each point (x, y) given as input will correspond to the point (f(x), f(y)). For example, if the points (4, -2) and (-1, 5) are given as input, your program will be dealing with the points (2, -√2) and (-1, √5). From now on, we will be referring to points in this format, rather than points in the format given in the input.

You will take in a set/list of points as input which will then be converted to Cartesian points with the function f.

Balanced Sets of Points

Denote by PQ the Euclidean distance from point P to point Q.

A set of points S is balanced if, and only if, for all pairs of distinct points A and B in S, there exists a point C in S such that AC = BC. For example, the set of points {(0, 2), (-√3, -1), (√3, -1)} is balanced because the points in this set are the vertices of an equilateral triangle. Note that this set of points would be taken as input by the program/function as {(0, 4), (-3, -1), (3, -1)}.

Centre-Free Sets of Points

Again, denote by PQ the Euclidean distance from point P to point Q.

A set of points S is centre-free if, and only if, for all triples of distinct points A, B and C in S, there does not exist a point P in S such that AP = BP = CP. For example, the set of points {(0, 2), (-√3, -1), (√3, -1)} is centre-free, but if you add the point (0, 0) to this set, it is no longer centre-free.

Formatting the Output

The output will be in the form of a two-digit binary number. Suppose we are given the set of points S. After having applied the function f to each point (see section "Taking in Input"), the first digit of this binary number will indicate whether this set of points is balanced and the second digit of this binary number will indicate whether this set of points is centre-free. For example, 10 will indicate that the given set of points is balanced, but not centre-free.

Also note that the digits 1 and 0 may be replaced with any truthy and falsy values. As opposed to strings, arrays and ordered pairs are also acceptable.

Test Cases

> {(0, 4), (-3, -1), (3, -1)}
11

> {(0, 4), (3, 1), (3, -1), (0, -4), (-3, -1), (-3, 1)}
01

> {(0, 4), (-3, -1), (3, -1), (0, 0)}
00

> {(0, 4), (-3, -1), (3, -1), (0, -4), (0, 0)}
00

> {(0, 16), (-3, 1),(-12, -4), (0, -4), (12, -4), (3, 1)}
10

Winning Criterion

Make your code as short as possible.

Credits

This was inspired by Problem 1 from IMO 2015. (Great problem, by the way!)

\$\endgroup\$
  • 4
    \$\begingroup\$ Would an output like [True, False] instead of 10 be acceptable? \$\endgroup\$ – Stephen Sep 3 '17 at 14:04
  • \$\begingroup\$ @Stephen Yes. 10, [1, 0], [True, False] and TrueFalse are all examples of acceptable output. \$\endgroup\$ – 0WJYxW9FMN Sep 3 '17 at 17:21
  • \$\begingroup\$ If I am correct, the points given by the last test-case are (0,2),(-√3,-1),(√3,-1),(0,-2),(0,0). Furthermore the distance between (0,2) and each of (-√3,-1),(√3,-1),(0,2) are √12,√12,4 while the distance between (0,0) and each of (-√3,-1),(√3,-1),(0,2) are 2,2,2, but none of the pairs (√12,2),(√12,2),(4,2) contain equal elements. Does this not imply it is not a balanced set? \$\endgroup\$ – Jonathan Allan Sep 3 '17 at 19:58
  • \$\begingroup\$ @JonathanAllan Yargh! I made that one up on the spot by taking a rhombus made of two equilateral triangles and putting a dot in the middle. Fixed! \$\endgroup\$ – 0WJYxW9FMN Sep 3 '17 at 20:41
  • \$\begingroup\$ I guess you want a 10 test-case - would {(0,4),(-¾,¼),(-3,-1),(0,-1),(3,-1),(¾,¼)} work (making, I think, an equilateral triangle along with the midpoints of each of its edges)? \$\endgroup\$ – Jonathan Allan Sep 3 '17 at 20:54
3
\$\begingroup\$

Jelly, 36 bytes

ạþE€Ṁ
®Œc瀮Ạ
A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢,

A full program printing the representation of a list of two ones/zeros.

This relies on theoretical infinite-precision floating point arithmetic, which is, of course, not the case. So here is a (43 byte) version which uses a 1e-10 leeway for the pair-wise distance comparisons it makes:

ạþI€×ȷ10ỊẠ€Ṁ
®Œc瀮Ạ
A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢,

Try It Online!

How?

(I'll include the replacement code used in place of E - equals to allow the leeway here)

ạþI€×ȷ10ỊẠ€Ṁ - Link 1: any all-equal distance complex numbers?: list of lists; list
ạþ           - outer-product with absolute difference
  I€         - incremental differences for €ach
    ×ȷ10     - multiply by 10^10
        Ị    - insignificant (abs(z)<=1) (vectorises)
         Ạ€  - all? for €ach
           Ṁ - maximum

®Œc瀮Ạ - Link 2: isBalanced? no-arguments (requires register to be populated - see Main)
®       - recall from register (the points as a list of complex numbers)
 Œc     - pairs
     ®  - recall from register (the points as a list of complex numbers)
   ç€   - call the last link (1) as a dyad for €ach pair
      Ạ - all truthy?

A½×Ṡ×1,ıSµ€©œc3ñ€®Ṁ¬¢, - Main link: list of (x, y) inputs
         µ€            - for €ach (x,y) pair, p:
A                      -   absolute value of p (vectorises)
 ½                     -   square root (vectorises)
   Ṡ                   -   sign of p (vectorises)
  ×                    -   multiply (vectorises)
     1,ı               -   literal [1, 0+1i]
    ×                  -   multiply (vectorises)
        S              -   sum
           ©           - (copy the result to the register)
            œc3        - combinations of length 3
                 ®     - recall from register
               ñ€      - call the next link (1) as a dyad for €ach triple
                  Ṁ    - maximum (1 if any triple has a centre)
                   ¬   - not (0 if any triple has a centre - hence isCentreFree?)
                    ¢  - call the last link as a nilad
                     , - pair with the calculated isCentreFree?
                       - implicit print
\$\endgroup\$
  • \$\begingroup\$ The whole reason I added the function f is so that people could store the coordinates as pairs of surds without issues arising with floating point arithmetic. Good job, though! \$\endgroup\$ – 0WJYxW9FMN Sep 3 '17 at 21:58
2
\$\begingroup\$

Python 2, 303 302 bytes

Edit: -1 byte thanks to @Mr.Xcoder

lambda x,y:f((x[0]-y[0])**2+(x[1]-y[1])**2)
f=lambda x:x<0and-f(-x)or x**.5
v=lambda a,b,p:abs(d(a,p)-d(b,p))<1e-9
def e(k):k=[(f(a),f(b))for a,b in k];print+all(any(v(a,b,c)for c in k)for a in k for b in k if a!=b),1-any(any(v(a,b,p)*v(b,c,p)for p in k)*len({a,b,c})>2for a in k for b in k for c in k)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ -1e-9<d(a,p)-d(b,p)<1e-9 means abs(d(a,p)-d(b,p))<1e-9 (302 bytes) \$\endgroup\$ – Mr. Xcoder Sep 4 '17 at 6:43
  • \$\begingroup\$ I do Python golf a lot, but I've never come across the all and any functions. What do they do? \$\endgroup\$ – 0WJYxW9FMN Sep 5 '17 at 21:16
  • \$\begingroup\$ @J843136028 all returns true if all the values in the argument (which must be iterable) are true, while any returns true if at least on of the values in the argument are true. \$\endgroup\$ – Halvard Hummel Sep 6 '17 at 5:37
  • \$\begingroup\$ @HalvardHummel Thank you! \$\endgroup\$ – 0WJYxW9FMN Sep 6 '17 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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