Sha256: 37038d99d6bc980edbacf82e5fabe23f484375838a6830b4dd679c0182d7327a

Contents?: true

Size: 1.25 KB

Versions: 396

Compression:

Stored size: 1.25 KB

Contents

object Change {
  type Coin = Int
  type Coins = List[Coin]
  type Amount = Int

  def findFewestCoins(target: Amount, coins: Coins): Option[Coins] = {
    def minChange(target: Amount, coins: Coins, candidate: Coins,
          bestResult: Option[Coins]): Option[Coins] =
    {
      def isWorseResult: Boolean =
        bestResult map (_.length <= candidate.length) getOrElse false

      if (target < 0 || isWorseResult) bestResult
      else if (target == 0) Some(candidate)
      else {
        val newBestResult = addCoin(target, coins, candidate, bestResult)
        dropCoin(target, coins, candidate, newBestResult)
      }
    }

    def addCoin(target: Amount, coins: Coins, candidate: Coins,
          bestResult: Option[Coins]): Option[Coins] =
      coins match {
        case coin :: _ if target - coin >= 0 =>
          minChange(target - coin, coins, coin :: candidate, bestResult)
        case _ => bestResult
      }

    def dropCoin(target: Amount, coins: Coins, candidate: Coins,
          bestResult: Option[Coins]): Option[Coins] =
      coins match {
        case _ :: restCoins =>
          minChange(target, restCoins, candidate, bestResult)
        case _ => bestResult
      }

    minChange(target, coins.sorted(Ordering.Int.reverse), List(), None)
  }
}

Version data entries

396 entries across 396 versions & 1 rubygems

Version Path
trackler-2.2.1.180 tracks/scala/exercises/change/example.scala
trackler-2.2.1.179 tracks/scala/exercises/change/example.scala
trackler-2.2.1.178 tracks/scala/exercises/change/example.scala
trackler-2.2.1.177 tracks/scala/exercises/change/example.scala
trackler-2.2.1.176 tracks/scala/exercises/change/example.scala
trackler-2.2.1.175 tracks/scala/exercises/change/example.scala
trackler-2.2.1.174 tracks/scala/exercises/change/example.scala
trackler-2.2.1.173 tracks/scala/exercises/change/example.scala
trackler-2.2.1.172 tracks/scala/exercises/change/example.scala
trackler-2.2.1.171 tracks/scala/exercises/change/example.scala
trackler-2.2.1.170 tracks/scala/exercises/change/example.scala
trackler-2.2.1.169 tracks/scala/exercises/change/example.scala
trackler-2.2.1.167 tracks/scala/exercises/change/example.scala
trackler-2.2.1.166 tracks/scala/exercises/change/example.scala
trackler-2.2.1.165 tracks/scala/exercises/change/example.scala
trackler-2.2.1.164 tracks/scala/exercises/change/example.scala
trackler-2.2.1.163 tracks/scala/exercises/change/example.scala
trackler-2.2.1.162 tracks/scala/exercises/change/example.scala
trackler-2.2.1.161 tracks/scala/exercises/change/example.scala
trackler-2.2.1.160 tracks/scala/exercises/change/example.scala