Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?

parallel lines

There are different ways to express the equation of a line. Here's one way:

2x + 4y = 1
 x + 2y = 1

The x and the y are always the same, but we can sub out variables for the three numbers:

ax + by = c

Now, we can just make a tuple with a, b, and c:

[a b c]

The first two lines represented in this form:

[2 4 1]
[1 2 1]

Okay! Now that we have a way to represent lines, your task is to write a function that takes two lines and tells us if they're parallel. Here's an example:

(parallel? [2 4 1] [1 2 1])   ;=> true
(parallel? [2 4 1] [4 2 1])   ;=> false
(parallel? [0 1 5] [0 1 5])   ;=> false ;; lines are not parallel to themselves

I'm looking forward to seeing the variety of answers.

Thanks to this site for the challenge idea where it is considered Medium level in Python.

Email submissions to eric@purelyfunctional.tv before July 5, 2020. You can discuss the submissions in the comments below.

(ns tst.demo.core
(:use tupelo.core tupelo.test))
(defn theta [[a b -c-]]
(Math/atan2 (double a) (double b)))
(defn radius [[a b c]]
; this uses the assumption that it is illegal for both a and b to be zero
(let [n2 (double (+ (* a a) (* b b)))
n (Math/sqrt n2)
r (/ (- c) n)]
r))
(defn parallel?
[x y]
(let [same-theta (rel=
(theta x)
(theta y)
:digits 8)
different-radius (not (rel= (radius x) (radius y) :digits 9))]
(and same-theta
different-radius)))
(dotest
(let [pi-ovr-4 (/ Math/PI 4)]
(is (rel= pi-ovr-4 (theta [1 1 1]) :digits 9))
(is (rel= pi-ovr-4 (theta [1 1 2]) :digits 9)))
(is (parallel? [1 1 1] [1 1 2]))
(isnt (parallel? [1.00001 1 1] [1 1 2]))
(is (parallel? [1 2 1] [2 4 9]))
(is (parallel? [2 4 1] [1 2 1]))
(isnt (parallel? [2 4 1] [4 2 1]))
(is (parallel? [0 1 5] [0 1 5.0000001])) ; slightly offset => parallel
(isnt (parallel? [0 1 5] [0 1 5.000000000001])) ; within rounding error => non-parallel
(isnt (parallel? [1 2 5] [100 200 500]))
)
(ns parallel?)
(require '[clojure.test :as test])
(defn parallel? [[a1 b1 c1][a2 b2 c2]]
(and
(= (* a1 b2) (* a2 b1)) ;; slopes must be equals, and
(not= (* b1 c2) (* b2 c1)))) ;; y-intercept must be different
(test/deftest parallel?-test
(test/is (= true (parallel? [2 4 1][1 2 1])))
(test/is (= false (parallel? [2 4 1][4 2 1])))
(test/is (= false (parallel? [0 1 5][0 1 5]))))
(test/run-tests 'parallel?)
(defn same-slope? [[ax ay _] [bx by _]]
(= (* ax by) (* bx ay)))
(defn different-y-intercept? [[_ ay ac] [_ by bc]]
(not= (* ay bc) (* by ac)))
(defn different-x-intercept? [[ax _ ac] [bx _ bc]]
(not= (* ax bc) (* bx ac)))
(defn parallel? [a b]
(and (same-slope? a b)
(or (different-y-intercept? a b)
(different-x-intercept? a b))))
;; tests
(require '[clojure.test.check :as tc]
'[clojure.test.check.generators :as gen]
'[clojure.test.check.properties :as prop])
(def int-line (->> (gen/tuple gen/small-integer
gen/small-integer
gen/small-integer)
(gen/such-that (fn [[a b]]
(not= 0 a b)))))
(tc/quick-check 100 ;; no errors
(prop/for-all [a int-line
b int-line]
(parallel? a b)
true))
(tc/quick-check 100 ;; lines not parallel to themselves
(prop/for-all [a int-line]
(not (parallel? a a))))
(tc/quick-check 100 ;; lines not parallel to themselves
(prop/for-all [a int-line
x (gen/such-that pos? gen/small-integer)]
(not (parallel? a (mapv #(* % x) a)))))
(tc/quick-check 100 ;; parallel when shifted
(prop/for-all [a int-line
x (gen/such-that pos? gen/small-integer)]
(let [b (update a 2 + x)]
(parallel? a b))))
(tc/quick-check 100 ;; commutative
(prop/for-all [a int-line
b int-line]
(= (parallel? a b)
(parallel? b a))))
(tc/quick-check 100 ;; verticals
(prop/for-all [a (->> int-line
(gen/such-that #(not= 0 (get % 0)))
(gen/fmap #(assoc % 1 0.0) ))
x (gen/such-that pos? gen/small-integer)]
(let [b (update a 2 + x)]
(parallel? a b)))
)
(tc/quick-check 100 ;; horizontals
(prop/for-all [a (->> int-line
(gen/such-that #(not= 0 (get % 1)))
(gen/fmap #(assoc % 0 0.0) ))
x (gen/such-that pos? gen/small-integer)]
(let [b (update a 2 + x)]
(parallel? a b)))
)
(tc/quick-check 100 ;; verticals and horizontals
(prop/for-all [a (->> int-line
(gen/such-that #(not= 0 (get % 0)))
(gen/fmap #(assoc % 1 0.0) ))
b (->> int-line
(gen/such-that #(not= 0 (get % 1)))
(gen/fmap #(assoc % 0 0.0) ))]
(not (parallel? a b)))
)
(ns functional-tv-puzzles.-2020.parallel-384)
(defn parallel? [[a1 b1 c1 :as line1] [a2 b2 c2 :as line2]]
(when (not-any?
(fn [[a b _]] (= 0 a b)) ;; not a line
[line1 line2])
(cond
(= 0 a1 a2) ;; both horizontal
(not= (* b1 c2) (* b2 c1))
(= 0 b1 b2) ;; both vertical
(not= (* a1 c2) (* a2 c1))
(some zero? [a1 a2]) ;; one horizontal only
false
(some zero? [b1 b2]) ;; one vertical only
false
(= (* a1 b2) (* a2 b1)) ;; same slope diagonals
(not= (* b2 (- a1 c1))
(* b1 (- a2 c2)))
:else
false)))
(defn parallel?
[& coeffs]
(and (->> coeffs
(map (fn [[a b _]] (/ a b)))
(apply =)) ; Slopes must be equal
(->> coeffs
(map (fn [[_ b c]] (/ c b)))
(apply not=)))) ; Y-intercepts must differ
(defn parallel? [[a b c] [a1 b1 c1]]
(and (= (* a b1) (* b a1)) ; same slope: -a/b = -a1/b1
(not= (* c b1) (* b c1)))) ; different intercept c/b != c1/b1
(defn parallel? [[a b c] [a' b' c']]
(and (= (* a b') (* a' b))
(or (not= (* a c') (* a' c))
(not= (* b c') (* b' c)))))
(defn parallel?
[[a1 b1 c1] [a2 b2 c2]]
(if (and (= a1 a2) (= b1 b2))
(not= c1 c2)
(= (/ a1 a2) (/ b1 b2))))
@ninjure
Copy link

ninjure commented Jun 29, 2020

(defn parallel? [[a b c] [a' b' c']]
 (and (= (* a b') (* a' b))
      (or (not= (* a c') (* a' c))
          (not= (* b c') (* b' c)))))

@KingCode
Copy link

KingCode commented Jun 30, 2020

Here is a gist with properties tests for anyone interested, which include:

  • verifying generated parallel and non-parallel lines, including both horizontal and vertical ones
  • any points across non-vertical parallel lines sharing an X coordinate have the same vertical distance
  • pairs of parallel lines must have either both or none of their constituents vertical
  • no line can be parallel to itself; two lines with the same slope but different coords are the same if any x yields the same y for both.

Also, worth noting is that not all tuples are lines: specifically [0, 0, c] which is for 0x + 0y = c which doesn't mean anything that can be represented in a 2D graph.

@KingCode
Copy link

KingCode commented Jun 30, 2020

Wow...Thanks @ericnormand for your properties test - I will learn from them :)

Most solutions fail against some of the properties tests, mostly due to divide-by-zero errors I think. The only solutions which passed all properties tests (Eric's and mine), are @ninjure's and @ericnormand - congrats!

My own solutions also failed against Eric's horizontal/vertical checks, which happen to inject 0.0 to generate such a line: the innocuous looking statement (= 0 a b) fails when passed a float. The lesson here is to constantly be aware of potential mixed numeric types, or even better, to use logic which behaves uniformly across types. Also, I suspect most solutions (mine certainly does) fail against some mixed type inputs, e.g.

(parallel? [1 2 3] [2 4 0])
 ;;=> true
(parallel? [1 2.0 3] [2 4 0])
;;=> false

so perhaps the input could be constrained to integers only.

I think it would be an interesting topic of discussion or blog post on the best way to cope uniformly with mixed types and under which conditions etc.

I patched this solution below to use (== 0 ..) to make it pass all tests:

(defn  same-slope [[a1 b1 c1] [a2 b2 c2]]
  (= (* a1 b2) (* a2 b1)))

(defn  y<-1 [[a b c]]
  (-> a (/ b) (- (/ c b))))

(defn parallel? [[a1 b1 c1 :as line1] [a2 b2 c2 :as line2]]
  ;; reject non-lines 
  (assert (not-any? (fn [[a b c]] (= 0 a b)) [line1 line2]))
  (cond 
    (== 0 a1 a2) ;; both horizontal
    (not= (* b1 c2) (* b2 c1))  
    (== 0 b1 b2) ;; both vertical
    (not= (* a1 c2) (* a2 c1))  
    (some zero? [a1 a2]) ;; one horizontal only
    false   
    (some zero? [b1 b2]) ;; one vertical only 
    false  
    (same-slope line1 line2)  ;; same slope diagonals
    (not= (y<-1 line1) (y<-1 line2))
    :else  
    false))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment