407 - PurelyFunctional.tv Newsletter

00 overlapping rectangles.md

Area of overlapping rectangles

Write a function that takes two rectangles and returns the area of the overlap. Sometimes the overlap is zero!

(overlap-area [{:top-left {:x 0 :y 0}
                :bottom-right {:x 10 :y 10}}
               {:top-left {:x 5 :y 5}
                :bottom-right {:x 15 :y 15}}]) ;=> 25

;; 2 identical rectangles
(overlap-area [{:top-left {:x 0 :y 0}
                :bottom-right {:x 1 :y 1}}
               {:top-left {:x 0 :y 0}
                :bottom-right {:x 1 :y 1}}]) ;=> 25

;; no overlap
(overlap-area [{:top-left {:x 0 :y 0}
                :bottom-right {:x 1 :y 1}}
               {:top-left {:x 6 :y 6}
                :bottom-right {:x 8 :y 8}}]) ;=> 0

;; enclosing rectangles
(overlap-area [{:top-left {:x 0 :y 0}
                :bottom-right {:x 1 :y 1}}
               {:top-left {:x -1 :y -1}
                :bottom-right {:x 2 :y 2}}]) ;=> 1

Thanks to this site for the challenge idea where it is considered Very Hard in JavaScript.

Please submit your solutions as comments on this gist.

@sztamas @steffan-westcott and @mainej, nice multi-rectangle enabled solutions!

@sztamas and @steffan-westcott that is really nice insight, using the natural ordering of :top-left and :bottom-right together with the use of merge-with to keep track of the smallest common rectangles, for a super compact solution - I wish I had though of that 👍

Way late to the party, but I found the challenge recently and couldn't stop thinking about it. So here is my solution with an attempt to optimise for readability:

(defn- overlap-axis [l1 l2]
  (let [[[a1 a2] [b1 b2]] (sort-by first [l1 l2])]
    (cond
      ;; a1   a2
      ;; |----|  b1   b2
      ;;         |----|
      (>= b1 a2) 0

      ;; |---------------|
      ;;         |----|
      (>= a2 b2) (- b2 b1)

      ;; |----------|
      ;;         |----|
      :else      (- a2 b1))))

(defn overlap-area
  [[r1 r2]]
  (* (overlap-axis (map :x (vals r1))
                   (map :x (vals r2)))
     (overlap-axis (map :y (vals r1))
                   (map :y (vals r2)))))

A version that uses sets and works on any number of rectangles.

(require '[clojure.set :as set])

(defn spots [rect]
  (let [startx (:x (:top-left rect))
        starty (:y (:top-left rect))
        endx (:x (:bottom-right rect))
        endy (:y (:bottom-right rect))]
    (flatten
     (map (fn [x]
            (map (fn [y]
                   (symbol (str x "," y)))
                 (range starty endy)))
          (range startx endx)))))

(defn overlap-area [rectangles]
  (->>
   rectangles
   (map spots)
   (map set)
   (reduce set/intersection)
   (count)))