How to make this recursive function more FP-like?-CodePudding

The question is, given the sequence S (|S| > 5) of integers (can be Array, List or whatever you want), break down this sequence into 3 non-empty sequences that has the least cost.

What are the costs? the corresponding element of the sequence. for instance:

[5, 3, 8, 2, 10932, 4, 1, 87, 1]
               ^
    The cost of breaking on this element would be 10932
And the solution to this problem would be:
[5, 3, 8] [10932, 4] [87, 1] -> cost = 2   1 = 3
         ^         ^          
These values are omitted as the costs

Obviously some implicit rules that should be considered are:

1. We need 2 breakpoints
1. We should not break on the first and the last element
1. We should not break on 2 adjacent elements, because it results into an empty seq

So this is the implementation I've come up with:

@tailrec
  def calculateCost(arr: Array[Int], currentIndex: Int = 1, acc: (Int, Int) = (Int.MaxValue, Int.MaxValue)): Int = {
    if (currentIndex >= arr.length - 1) acc._1   acc._2
    else {
      val next = arr.applyOrElse(currentIndex   1, (_: Int) => Int.MaxValue)
      val current = arr(currentIndex)
      val (firstSmallest, secondSmallest) = acc
      val min = next min current
      Array(firstSmallest, secondSmallest, min).max match {
        case value if value != min =>
          calculateCost(arr, currentIndex   2, (min, firstSmallest min secondSmallest))
        case _ =>
          calculateCost(arr, currentIndex   1, acc)
      }
    }
  }

Now I'm not totally happy with the Array thing and accessing by index. So I wanted to see some alternative implementation that is more Scala-ish.

CodePudding user response：

Not going to accept this unless this is the best solution, so please share your ideas :D

Just now I came up with the following implementation, that uses pattern matching over lists:

def calculateCost: List[Int] => Int = {
    @tailrec
    def calculateCostHelper(list: List[Int], acc: (Int, Int)): Int = {
      val (firstSmallest, secondSmallest) = acc
      list match {
        case List(preLast, _) =>
          firstSmallest   secondSmallest   preLast - Array(firstSmallest, secondSmallest, preLast).max
        case head :: tail =>
          Array(firstSmallest, secondSmallest, head).max match {
            case value if value != head =>
              calculateCostHelper(tail, (head, firstSmallest min secondSmallest))
            case _ =>
              calculateCostHelper(tail, (firstSmallest, secondSmallest))
          }
        case Nil => 0
      }
    }
      calculateCostHelper(_, (Int.MaxValue, Int.MaxValue))
  }

CodePudding user response：

How about this one:

def cost(ints: Seq[Int], parts: Int = 3): Int = parts match {
  case 1 => 0
  case n => ((2*n-3) until (ints.size-1)).map(i => cost(ints.take(i), parts-1)   ints(i)).min
}

scala> cost(Seq(5, 3, 8, 2, 10932, 4, 1, 87, 1), 3)
val res1: Int = 3