18
\$\begingroup\$

Divide the first quadrant (including the positive x-axis, the positive y-axis, and the origin) into 1x1 grids, with each grid labelled by the coordinates of its bottom-left corner, as demonstrated below:

Note that each grid contains its boundaries and its vertices. Using mathematical symbols, the grid labelled (m,n) would represent the square {(x,y) | m ≤ x ≤ m+1, n ≤ y ≤ n+1}.


Given a straight line in the form of ax+by+c=0 with integers a, b, and c, and a grid represented by (m,n), output whether the line passes through the grid, i.e. whether any point in the given grid is on the line.


a  b  c m n output
1  1  0 0 0 true
1  1  0 1 1 false
1  1  0 0 2 false
1  1 -3 0 1 true
1  1 -3 0 0 false
2 -1  0 1 1 true
2 -1  0 1 0 false
2 -1  0 0 2 true
2 -1  0 0 1 true
2 -1  0 1 2 true
2  0 -1 0 0 true
2  0 -1 0 1 true
2  0 -1 0 2 true
2  0 -1 1 0 false
2  0 -1 1 1 false
0  2 -1 0 0 true
0  2 -1 1 0 true
0  2 -1 2 0 true
0  2 -1 0 1 false
0  2 -1 1 1 false
1  0 -1 0 0 true
1  0 -1 0 1 true
1  0 -1 0 2 true
1  0 -1 1 0 true
1  0 -1 1 1 true

Please suggest more testcases in the comments.


This is . Shortest answer in bytes wins. Standard loopholes apply.

\$\endgroup\$
  • 1
    \$\begingroup\$ Of course we should be able to assume that not both a and b are 0, since then if c is zero there can be infinite lines while if c is non-zero there can be no line at all. \$\endgroup\$ – Erik the Outgolfer Jun 23 '17 at 11:16
  • \$\begingroup\$ Can I get input as two or more arrays, say [a, b, c] (the line) and [m, n] (the square)? \$\endgroup\$ – Erik the Outgolfer Jun 23 '17 at 11:42
  • \$\begingroup\$ @EriktheOutgolfer I'm surprised that isn't in meta. \$\endgroup\$ – Leaky Nun Jun 23 '17 at 12:25
  • \$\begingroup\$ Related \$\endgroup\$ – Not a tree Jun 23 '17 at 13:56
  • \$\begingroup\$ Strongly related. \$\endgroup\$ – Olivier Grégoire Jun 23 '17 at 14:16
5
\$\begingroup\$

Python 3, 84 66 bytes

First golf, first fail (maybe).

Thanks to Rod for shaving off 18 bytes by using a function instead of direct input.

def f(a,b,c,m,n):f=-(a*m+c)/b;g=f-a/b;print(min(f,g)<=n<=max(f,g))

Try it online!

Explanation:

Basically we calculate the value of the line function for m and m+1, if n is inbetween the values, then the list must pass through it at some point. Would be much better if the language had some simpler way to input multiple integers.

\$\endgroup\$
  • 2
    \$\begingroup\$ You can use a function instead input() \$\endgroup\$ – Rod Jun 23 '17 at 11:16
  • 2
    \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – betseg Jun 23 '17 at 12:18
  • 1
    \$\begingroup\$ Doesn't this need to check against n+1 as well as m+1? \$\endgroup\$ – Neil Jun 23 '17 at 12:40
  • 3
    \$\begingroup\$ Division by zero when b is 0. \$\endgroup\$ – Olivier Grégoire Jun 23 '17 at 12:47
  • \$\begingroup\$ Also, it doesn't pass several test cases highlighted by Leaky Nun. \$\endgroup\$ – Olivier Grégoire Jun 23 '17 at 14:28
4
\$\begingroup\$

Python 2, 59 bytes

lambda a,b,c,m,n:min(0,a,b,a+b)<=-a*m-b*n-c<=max(0,a,b,a+b)

Try it online!

We can tell which side of the line a point is by the sign of a*x+b*y+c. The line passes through the square (counting touching) unless all four vertices (m,n),(m,n+1),(m+1,n),(m+1,n+1) are strictly on the same side of the line. We can plug these values in an extract out the constant a*m+b*n+c that appears in all four:

a*m+b*n+c
a*m+b*n+c+a
a*m+b*n+c+b
a*m+b*n+c+a+b

So, the line passes through the square unless these four values are all positive or all negative. So, it suffices for their minimum to be <=0 and maximum to be >=0.

min(a*m+b*n+c,a*m+b*n+c+a,a*m+b*n+c+b,a*m+b*n+c+a+b)<=0<=max(a*m+b*n+c,a*m+b*n+c+a,a*m+b*n+c+b,a*m+b*n+c+a+b)

Subtracting the common a*m+b*n+c from each part gives the code.

A slightly longer approach is to check whether the set of signs (+,0,-) has length at least 2.

Python 2, 62 bytes

lambda a,b,c,m,n:len({cmp(a*m+b*n+c,-d)for d in(0,a,b,a+b)})>1

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 10 bytes

ż‘{Œpæ.ṠE¬

Try it online!

Background

Like other answers before mine, this relies on the fact that a straight line divides the plane into two semi-planes. The rectangle is either contained in one of these semi-planes (no intersection with the line) or intersects both semiplanes (and thus the line that separates them.

How it works

ż‘{Œpæ.ṠE¬  Main link. Left argument: [m, n]. Right argument: [a, b, c]

 ‘{         Increment left; yield [m+1, n+1].
ż           Zipwith; yield [[m, m+1], [n, n+1]].
   Œp       Cartesian product; yield [[m, n], [m, n+1], [m+1, n], [m+1, n+1]].
     æ.     Take the dot products with [a, b, c], mapping each [x, y] to ax+by+c.
       Ṡ    Take the signs.
        E   Test the signs for equality.
         ¬  Logical NOT.
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 60 55 bytes

Solve[m#+n#2==-#3&&#4<=m<=#4+1&&#5<=n<=#5+1,{m,n}]!={}&

-5 bytes thanx to @MartinEnder

input form

[a,b,c,m,n]

\$\endgroup\$
  • 2
    \$\begingroup\$ Ah, I wish every language had a Solve function... \$\endgroup\$ – Erik the Outgolfer Jun 23 '17 at 10:36
3
\$\begingroup\$

Batch, 66 bytes

@cmd/cset/a"q=%1*%4+%2*%5+%3,((-(q+%1)*(q+%2)&-q*(q+%1+%2))>>31)+1

Explanation: We consider the values taken by the equation at the four corners of the cell. If the line does not intersect the cell, then all four values have the same sign, but if it does intersect the cell, then at least one value will be zero or the opposite sign. The comparison is simplified by multiplying pairs of opposite corners, then if both values are positive then the line does not intersect the cell. Some bit-twiddling then converts the multiplications into an overall result.

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

Mathematica, 50 bytes

-4<Tr@Sign[Tuples@{{#,#+1},{#2,#2+1}}.{##4}+#3]<4&

Try it online!

Takes m, n, c, a, b as input in that order.

Explanation: Tuples@{{#,#+1},{#2,#2+1}} makes a list of the coordinates of the four corners of the square, then taking the dot product with .{##4} (which means {#4, #5}) and adding +#3 computes ax + by + c for x,y at each corner. If the line passes through the point, this is zero; if the line is further from the origin, it's negative; and if the line is nearer to the origin, it's positive — therefore we check the Signs of these four values. The line passes outside the square if and only if all four values are 1 or all four are -1, so we check that their sum is strictly between -4 and 4.

(This answer is vaguely inspired by my answer to this question.)

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

Java (OpenJDK 8), 113 108 93 79 bytes

(a,b,c,x,y)->(0<a?0<b?0:b:0<b?a:a+b)<=(x=-a*x-b*y-c)&x<=(0>a?0>b?0:b:0>b?a:a+b)

Try it online!

Port of xnor's Python solution.

Original solution, using Java's shape/line intersection built-in (108 bytes)

(a,b,c,x,y)->b==0?x<=-c/a&-c/a<=x+1:new java.awt.Rectangle(x,y,1,1).intersectsLine(x,c=(c+a*x)/-b,x+1,c-a/b)

Try it online!

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

Python 2, 147 110 bytes

def f(a,b,c,m,n):
 if b:d=sorted((-a*x-c)/float(b)for x in(m,m+1));return d[0]-1<=n<=d[1]
 return m<=-c/a<=m+1

And a huge thanks to Leaky Nun!

TIO.

\$\endgroup\$
0
\$\begingroup\$

Python, 54 bytes

lambda a,b,c,m,n:abs(2*(a*m+b*n+c)+a+b)<=abs(a)+abs(b)

Try it online!

(Thanks to xnor for the testing script.)

How it works

The line goes through m + 1/2 + x, n + 1/2 + y if and only if

a⋅(m + 1/2 + x) + b⋅(n + 1/2 + y) + c = 0
⇔ 2⋅(am + bn + c) + a + b = −2⋅ax − 2⋅by.

This is possible for some |x|, |y| ≤ 1/2 if and only if |2⋅(am + bn + c) + a + b| ≤ |a| + |b|.

\$\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.