Find the combination of matches which are closest to each other

Question

Problem - Given three sorted arrays find combinations which are closest to each other.

example -

i/p - 3,8,18  7,11,16  10,15,19
o/p - (8,7,10)

i/p - 2,2,6  11,15,15  8,8,18
o/p - (6,11,8)

Kindly review this scala code and suggest improvements

import scala.math.Ordering._

object NearestMatch {

  def main(args: Array[String]) = {
    val size = args(0).toInt
    val range = args(1).toInt
    val (a,b,c) = (Array.fill(size)(scala.util.Random.nextInt(range)).sorted,
           Array.fill(size)(scala.util.Random.nextInt(range)).sorted,
           Array.fill(size)(scala.util.Random.nextInt(range)).sorted)

   println(a.mkString(","))
   println(b.mkString(","))
   println(c.mkString(","))

  var (i,j,k) = (0,0,0)
  var (pa,pb,pc) = (0,0,0)

  var curDiff = 12345 // a very large number
  while (i < a.size && j < b.size && k < c.size) {
    val min = Math.min(a(i), Math.min(b(j), c(k)))
    val max = Math.max(a(i), Math.max(b(j), c(k)))
    val newDiff = max-min

    if (curDiff > newDiff) {
      pa = i
      pb = j
      pc = k
      curDiff = newDiff
    }

    if (a(i) == min) i+=1
    else if (b(j) == min) j+=1
    else k+=1
  }
   println(a(pa), b(pb), c(pc))
  }
}

Answer 1

A few things I noticed while looking over the code:

1. You don't need the import scala.math.Ordering._ statement. It's not buying you anything.
2. It would be easier to read/follow the code if you used better variable names.
3. 12345 actually isn't a very big Int. Int.MaxValue would be better.
4. If this val size = args(0).toInt is zero then this println(a(pa), b(pb), c(pc)) will throw.
5. According to a hint from the IntelliJ IDE, array.length is more efficient than array.size because .size "requires an additional implicit conversion to SeqLike to be made."

But the real problem is that you're using Scala, a functional language, to write imperative code with many mutable variables, making the code more verbose.

Your algorithm is efficient and limits the number of while loop iterations, so how to express it in a functional manner: recursion.

def minDif[N:Numeric](x :Seq[N] ,y :Seq[N] ,z :Seq[N]
                     ,curSet :Seq[N] ,curDiff :N) :Unit = {
  import Numeric.Implicits._
  import Ordering.Implicits._

  if (x.isEmpty || y.isEmpty || z.isEmpty)
    println(curSet.mkString(","))  //done
  else {
    val newSet  = Seq(x.head, y.head, z.head)
    val newMin  = newSet.min
    val newDiff = newSet.max - newMin
    val (nxtSet, nxtDiff) = if (curDiff > newDiff) (newSet, newDiff)
                            else                   (curSet, curDiff)
    newSet match {
      case Seq(`newMin`,_,_) => minDif(x.tail, y, z, nxtSet, nxtDiff)
      case Seq(_,`newMin`,_) => minDif(x, y.tail, z, nxtSet, nxtDiff)
      case Seq(_,_,`newMin`) => minDif(x, y, z.tail, nxtSet, nxtDiff)
    }
  }
}

// a b and c have already been populated and sorted
minDif(a, b, c, Seq(), Int.MaxValue)

The minDif() method is tail recursive so it is compiled to an equivalent while loop under the hood.

Notice that I used Seq as the collection type. This allows minDif() to accept many different types as input: Array, Stream, Vector, etc. Since there is no indexing into any collection there is little advantage in restricting it to just arrays.

Also the element type is Numeric so this will work with Int, Float, Long, etc.