11
\$\begingroup\$

Given the coordinates of the upper left corners of two squares and their side lengths, determine whether the squares overlap. A square includes the top and left lines, but not the bottom and right lines. That is, a point (a,b) is inside a square with side length k that starts at (x,y) if and only if x <= a < x+k and y <= b < y+k. A square with side length 0 is degenerate and will not be considered here, thus, k will be positive.

As usual, all standard rules apply. Input and output may be in whatever form is convenient, so long as it's human readable and there is no precomputation. Be sure to specify what input format you use. Your code should take six numbers and output truthy if the squares overlap and falsy otherwise.

Test Cases

x1 y1 k1  x2 y2 k2  overlap?
 1  1  1   0  1  1  false
 0  0  3   1  1  1  true
 1  1  1   0  0  3  true
 0  0  3   2  1  2  true
 0  0  2   1  1  2  true
 1  1  2   0  0  2  true
 0  1  2   1  0  2  true
 1  0  2   0  1  2  true
 2  0  2   0  2  2  false
 1  0  3   0  1  1  false
 0  2  3   0  0  2  false

All inputs will be non-negative integers. That said, I expect that many or most solutions will also be able to handle negatives and floats.

\$\endgroup\$
  • \$\begingroup\$ related? \$\endgroup\$ – MickyT May 11 '16 at 23:58

11 Answers 11

22
\$\begingroup\$

Python, 33 bytes

lambda x,y,k,X,Y,K:k>X-x>-K<Y-y<k

Python supports chains of inequalities even when they point opposite directions.

The x-coordinate intervals [x,x+k) and [X,X+K) overlap as long as neither one is fully to the right of the other, which means that each interval's left endpoint is left of the other interval's right endpoint.

x<X+K
X<x+k

The can be combined into a joint inequality -K<X-x<k. Writing the same for y-coordinates and splicing them at -K gives the expression

k>X-x>-K<Y-y<k
\$\endgroup\$
10
\$\begingroup\$

MATL, 14 11 10 5 4 bytes

tP->

This solution accepts input in the form of two arrays:

  1. A 2 x 2 matrix that contains the coordinates of the corners [x1, y1; x2, y2]
  2. A 2 x 1 array containing the square dimensions [k2; k1]

Try it Online

Slightly modified version to run all test cases

Explanation

        % Implicitly grab the first input
t       % Duplicate the input
P       % Flip along the first dimension (columns)
-       % Subtract the two to yield [x1-x2, y1-y2; x2-x1, y2-y1]
        % Implicitly grab the second input
>       % Compare with [k2, k1] (automatically broadcasts)
        % Implicitly display the truthy/falsey result
\$\endgroup\$
5
\$\begingroup\$

MATLAB, 36 21 bytes

@(a,b)a-flip(a)<[b,b]

Creates an anonymous function which can be evaluated as ans(a,b). Accepts two inputs of the following format:

  1. 2 x 2 matrix containing the corner of each square as a row: [x1, y1; x2, y2].
  2. 2 x 1 array containing the size of the two squares: [k2; k1]

All test cases here.

Explanation

Here is a commented un-golfed solution

%// Example input
a = [1 1;
     0 1];

b = [1; 1];

%// Flip a along the first dimension and subtract from a to yield:
%// 
%// [x1-x2   y1-y2]
%// [x2-x1   y2-y1]
d = a - flip(a);

%// Compare this matrix element-wise with two horizontally concatenated copies 
%// of the second input [k2; k1]
result = d < [b,b];

%// Truthy values have all ones in the result and falsey values have at
%// least one 0 in the result.
\$\endgroup\$
  • \$\begingroup\$ I don't know MATLAB, so mind adding an explanation? \$\endgroup\$ – El'endia Starman May 12 '16 at 2:23
  • \$\begingroup\$ @El'endiaStarman Added an explanation. \$\endgroup\$ – Suever May 12 '16 at 2:54
4
\$\begingroup\$

JavaScript (ES6), 38 bytes

(a,b,c,d,e,f)=>d-a<c&a-d<f&e-b<c&b-e<f

If d - ac then the second square is to the right of the first. Similarly the other conditions check that it is not to the left, below or above.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 8 bytes

Ṫṗ2+µ€f/

Input is the nested list [[x1, y1, k1], [x2, y2, k2]], output is the list of all incremented coordinates of points with integer coordinates that are common to both squares (falsy if empty, truthy if not).

Try it online! or verify all test cases.

How it works

Ṫṗ2+µ€f/  Main link. Argument: [[x1, y1, k1], [x2, y2, k2]]

    µ     Combine the chain to the left into a link.
     €    Apply it to each list [xi, yi, ki].
Ṫ           Tail; pop and yield ki.
 ṗ2         Second Cartesian power; yield the list of all pairs [a, b] such that
            1 ≤ a ≤ ki and 1 ≤ b ≤ ki.
   +        Add [xi, yi] to each pair, yielding the list of all pairs [c, d] such
            that xi + 1 ≤ c ≤ xi + ki and yi + 1 ≤ d ≤ yi + ki.
      f/  Reduce by filter, intersecting the resulting lists of pairs.
\$\endgroup\$
2
\$\begingroup\$

TI Basic, 36 bytes

Prompt X,Y,K,Z,θ,L:Z-X<K and X-Z<L and θ-Y<K and Y-θ<L
\$\endgroup\$
1
\$\begingroup\$

Java, 78 bytes

Object o(int a,int b,int c,int d,int e,int f){return d-a<c&a-d<f&e-b<c&b-e<f;}
\$\endgroup\$
  • 1
    \$\begingroup\$ Is the "algorithm" from @Neil? \$\endgroup\$ – Bálint May 12 '16 at 5:09
  • 1
    \$\begingroup\$ Object return type for -1 byte \$\endgroup\$ – Marv May 12 '16 at 13:04
  • \$\begingroup\$ @Marv Is that legal for code golf? \$\endgroup\$ – SuperJedi224 May 12 '16 at 19:12
  • \$\begingroup\$ @SuperJedi224 Why wouldn't it be? \$\endgroup\$ – Marv May 12 '16 at 19:54
  • \$\begingroup\$ Okay, if you say so. \$\endgroup\$ – SuperJedi224 May 12 '16 at 20:02
1
\$\begingroup\$

Octave, 17 bytes

@(a,b)a-flip(a)<b

Same logic as my MATLAB answer above, except that Octave supports automatic broadcasting of dimensions so we can replace [b,b] with simply b.

All test cases here

\$\endgroup\$
1
\$\begingroup\$

SmileBASIC, 76 57 bytes

INPUT X,Y,W,S,T,U
SPSET.,X,Y,W,W
SPCOL.?!SPHITRC(S,T,U,U)

Creates a sprite with the size/position of the first square, then checks if it collides with the second square.

\$\endgroup\$
1
\$\begingroup\$

x86-64 Machine code, Windows 22 bytes

C++ signature:

extern "C" uint32_t __vectorcall squareOverlap(__m128i x, __m128i y, __m128i k);

Returns 0 if the squares don't overlap and -1 (0xFFFFFFFF) otherwise. Inputs are vectors of 2 64-bit integers for x, y and k(_mm_set_epi64x(x1, x2) etc.).

squareOverlap@@48 proc
66 0F FB C8          psubq       xmm1,xmm0
0F 16 D2             movlhps     xmm2,xmm2
66 0F 38 37 D1       pcmpgtq     xmm2,xmm1
0F 12 CA             movhlps     xmm1,xmm2
0F 54 CA             andps       xmm1,xmm2
66 0F 7E C8          movd        eax,xmm1 
C3                   ret  
squareOverlap@@48 endp
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 5 bytes

Â-›˜P

Port of @Suever's MATL answer, with additional conversion to a truthy/falsey result. The input-format is therefore also the same:
First input as [[x1,y1],[x2,y2]] and second input as [k2,k1].

Try it online or verify all test cases.

Explanation:

       # Bifurcate (short for Duplicate & Reverse copy) the (implicit) input-matrix
 -      # Subtract each value (vectorized) from the input-matrix we duplicated
  ›     # Check for both values (vectorized) if it's larger than the (implicit) input-list
        # (We now have the same result as the MATL answer. In MATL a matrix/list consisting
        #  of only 1s is truthy. In 05AB1E this isn't the case however, so:)
    ˜   # Flatten the matrix to a single list
     P  # And take the product to check if all are truthy
        # (after which the result is output implicitly)  
\$\endgroup\$

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.