CommonAreaRects.scala

// find common area of given list of rectangles

object CommonAreaRects extends App {

  type Coord = (Int, Int)

  class Rect(val bottomLeft: Coord, val topRight: Coord) {
    override def toString: String = s"Rect($bottomLeft, $topRight)"
    def ==(other: Rect): Boolean = bottomLeft == other.bottomLeft && topRight == other.topRight

    def width: Int = topRight._1 - bottomLeft._1
    def height: Int = topRight._2 - bottomLeft._2
    def horizontal: Range = bottomLeft._1 until topRight._1
    def vertical: Range = bottomLeft._2 until topRight._2
    def area: Int = width * height

    def intersection(other: Rect): Rect = {
      val newBottomLeft = (
        Math.max(bottomLeft._1, other.bottomLeft._1),
        Math.max(bottomLeft._2, other.bottomLeft._2)
      )
      val newTopRight = (
        Math.min(topRight._1, other.topRight._1),
        Math.min(topRight._2, other.topRight._2)
      )
      val result = Rect(newBottomLeft, newTopRight)
      if (result.area < 0) Rect((0, 0), (0, 0))
      else result
    }
  }

  object Rect {
    def apply(bottomLeft: Coord, topRight: Coord): Rect = new Rect(bottomLeft, topRight)

    def intersectionArea(rects: List[Rect]): Int = {
      val (h, t) = rects.splitAt(1)
      val inters: Rect = t.foldLeft(h.head) { case (a, b) => {
        b.intersection(a)
      }}
      inters.area
    }

    def intersectionsArea(rects: List[Rect], ns: Range): Int = {
      ns.flatMap { (i: Int) => { rects.combinations(i) } }
        .map { (xs: List[Rect]) => { Rect.intersectionArea(xs) } }
        .sum
    }
  }

  object Range {
    def intersect(a: Range, b: Range): Range = {
      val result = Math.max(a.min, b.min) to Math.min(a.max, b.max)
      result
    }
  }

  def commonArea(rects: List[Rect]): Int = {
    val n = rects.length
    val union: Int = rects.map { _.area }.sum
    val intersectionsEven: Int = Rect.intersectionsArea(rects, (2 to n by 2))
    val intersectionsOdd: Int = Rect.intersectionsArea(rects, (3 to n by 2))
    val result = union - intersectionsEven + intersectionsOdd
    result
  }

  assert(Rect.intersectionArea(List(Rect((0,0), (3,2)), Rect((0,1), (2,3)))) == 2)

  {
    val rects = List(
      Rect((0, 0), (1, 2)),
      Rect((2, 0), (3, 2))
    )
    assert(commonArea(rects) == 4)
  }

  {
    val rects = List(
      Rect((0, 0), (3, 2)),
      Rect((0, 1), (2, 3))
    )
    assert(commonArea(rects) == 8)
  }

  {
    val rects = List(
      Rect((0, 0), (3, 2)),
      Rect((0, 1), (2, 3)),
      Rect((1, 1), (3, 4))
    )
    assert(commonArea(rects) == 11)
  }

  {
    val rects = List(
      Rect((0, 0), (1, 2)),
      Rect((2, 0), (3, 2)),
      Rect((0, 0), (3, 1))
    )
    assert(commonArea(rects) == 5)
  }
}