Krdytkyu

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))

  }

}

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.