TheCoinChangeProblem2.scala

/**
  * Created by janis on 09/01/2017.
  */
object TheCoinChangeProblem2 extends App {
  val requiredCoinSum = io.StdIn.readLine().split(" ")(0).toInt
  val coins = io.StdIn.readLine().split(" ").toList map (_.toInt)

  //val requiredCoinSum = 4
  //val coins = List(1,2,3)
  // 1111 112 22 13

  //val requiredCoinSum = 10
  //val coins = List(2,5,3,6)
  // output: 5

  //val requiredCoinSum = 240
  //val coins = List(23,20,35,42,19,3,34,9,28,38,13,41,26,14,27,39,24,37,46,29,43,1,21)
  // output: 127101770

  //val requiredCoinSum = 245
  //val coins = List(16,30,9,17,40,13,42,5,25,49,7,23,1,44,4,11,33,12,27,2,38,24,28,32,14,50)
  // output: 64027917156


  val coinsSorted = coins.sorted
  val rangeOfSums = 1 to requiredCoinSum

  case class MaxCoinGroup(maxCoin: Int, numberOfCombinations: Long)

  case class CoinLevel(maxCoinGroups: List[MaxCoinGroup])
  val EmptyCoinLevel = CoinLevel(List())

  val coinLevels: Array[CoinLevel] = (1 to requiredCoinSum).toArray map (_ => EmptyCoinLevel)

  def calculateLevel(coinLevels: Array[CoinLevel], currentLevel: Int): CoinLevel = {
    val maxCoinGroups: List[MaxCoinGroup] = coinsSorted map
      (
        coin => {
          if (currentLevel+1 - coin == 0)
            MaxCoinGroup(coin, 1)
          else if (currentLevel+1 - coin < 0)
            MaxCoinGroup(coin, 0)
          else {
            val totalCombinationSources = coinLevels(currentLevel - coin).maxCoinGroups filter (mcg => (mcg.maxCoin <= coin))
            val totalCombinations = if (totalCombinationSources == Nil) 0 else totalCombinationSources map (mcg => mcg.numberOfCombinations) sum

            MaxCoinGroup(coin, totalCombinations)
          }
        }
      ) filter (_.numberOfCombinations != 0)

    if (maxCoinGroups == Nil) EmptyCoinLevel else CoinLevel(maxCoinGroups)
  }

  (0 until coinLevels.length) foreach (lvl => coinLevels(lvl) = calculateLevel(coinLevels, lvl) )

  val result = coinLevels.last.maxCoinGroups map (_.numberOfCombinations) sum

  println(result)
}