Rerank.scala

object Rerank {

  def score(l : Array[Int], c : List[(Int, Int, Double)]) : Double = {
    // Rank changes.
    var s = l.zipWithIndex.map{t => math.abs(t._1 - t._2)}.sum.toDouble
    // Constraints.
    val r = l.zipWithIndex.sortBy{_._1}.map{_._2}.toArray
    c.foreach{t =>
      if(r(t._1) > r(t._2)) {
        s += t._3
      } 
    }
    s
  }

  def exch(l : Array[Int], i : Int, j : Int) : Unit = {
    val tmp = l(i)
    l(i) = l(j)
    l(j) = tmp
  }

  def mov(l : Array[Int], i : Int, j : Int) : Unit = {
    val tmp = l(j)
    if(i < j){
      var x = j
      while(x > i) {
        l(x) = l(x-1)
        x -= 1
      }
    } else if(i > j){
      var x = j
      while(x < i) {
        l(x) = l(x+1)
        x += 1
      }
    }
    l(i) = tmp
  }

  def climb(l : Array[Int], c : List[(Int, Int, Double)]) : (Double, Array[Int]) = {
    var best_score = score(l, c)
    var best_array = l.clone
    var i = 0
    while(i < l.length) {
      var j = i + 1
      while(j < l.length) {
        // Exchange i and j and test.
        mov(l, i, j)
        val score_ij = score(l, c)
        if(score_ij < best_score) {
          best_score = score_ij
          best_array = l.clone
        }
        // Swap back
        mov(l, j, i)
        j += 1
      }
      i += 1
    }
    (best_score, best_array)
  }

  def main(args : Array[String]) : Unit = {
    var l = (0 to 15).toArray
    val c = List((5,3,10.0), (12,6,10.0), (12,5,10.0))
    var curr_score = score(l, c)
    println("data:        " + l.toList)
    println("constraints: " + c)
    println("score:       " + curr_score)
    var converged = false
    while(!converged) {
      val step = climb(l, c)
      if(step._1 == curr_score) {
        converged = true
      } else {
        curr_score = step._1
        l = step._2
        println("step: " + curr_score + " " + l.toList)
      }
    }
  }
}