GenericCoinChange.sc

object GenericChange {
 
   // Part I: generic coin change algorithm
	
  // SICP count change algorithm, http://mitpress.mit.edu/sicp/full-text/sicp/book/node16.html
 
  def coin_change(sum: Int, coins: List[Int]): Int = {
    if (sum == 0) 1 else
      if (coins.isEmpty || sum < 0) 0 else
        coin_change(sum - coins.head, coins) + coin_change(sum, coins.tail)
  }                                         //> coin_change: (sum: Int, coins: List[Int])Int
 
  coin_change(4, List(1,2,3,5))             //> res0: Int = 4

  // can be genericized in terms of coin values, whether there is infinite supply of denominations (with
  // repetitions) or only one coin of each kind is available and what is collected: number of combinations
  // or list of combinations. Here is the generic version
 
  def cc[A, B, ColType](withRepetitions: Boolean) = {
    def internal(sum: Value[A, B], coins: List[A], path: Path[A, ColType], acc: Acc[A, ColType]): Acc[A, ColType] = {
      if (sum.isZero) acc + path.wrapped else {
        if (coins.isEmpty || sum.belowZero) acc else coins match {
          case option :: tail => {
            val so = if (withRepetitions) coins else tail
            val onehalf = internal(sum - option, so, path + option, acc)
            internal(sum, tail, path, onehalf)
          }
        }
      }

    }
    (internal _)
  }                                         //> cc: [A, B, ColType](withRepetitions: Boolean)(GenericChange.Value[A,B], Lis
                                                  //| t[A], GenericChange.Path[A,ColType], GenericChange.Acc[A,ColType]) => Gener
                                                  //| icChange.Acc[A,ColType]
  trait Value[A, B] {
    val wrapped: B
    def isZero(): Boolean
    def belowZero: Boolean
    def -(option: A): Value[A, B]
 
    // count combinations
    def ccCount(withRepetitions: Boolean) (coins: List[A]): Int = {
 
      class ISumPath(val wrapped: Int = -1) extends Path[A, Int] {
        def + (v: A) = this //{new ISumPath(wrapped + 1)} // will be ignored anyway
      }
 
      class ISumAcc(val wrapped: Int = 0) extends Acc[A, Int] {
 
        // ignores path accumulations, just count the num of pathes
        def + (path: Int) = new ISumAcc(wrapped + 1) //(path + wrapped)
      }
 
      cc(withRepetitions) (this, coins, new ISumPath(), new ISumAcc()).asInstanceOf[ISumAcc].wrapped
    }


    // enumerate combinations
    def ccList(b: Boolean)(coins: List[A]): List[List[A]]	= {
	
      class ListPath(val wrapped: List[A] = Nil) extends Path[A, List[A]] {
        def +(v: A) = new ListPath(v :: wrapped)
      }
	
      class ListAcc(val wrapped: List[List[A]] = Nil) extends Acc[A, List[A]] {
        def +(path: List[A]) = new ListAcc(path :: wrapped)
      }
	
      cc(b) (this, coins, new ListPath(), new ListAcc()).asInstanceOf[ListAcc].wrapped

    }

  }
 
  trait Path[ValType, ColType] {
    val wrapped: ColType
    def +(v: ValType): Path[ValType, ColType]
  }
 
  trait Acc[A, ColType] {
    def + (path: ColType): Acc[A, ColType]
  }


  // Part II: Integer values

  class IValue(val wrapped: Int) extends Value[Int, Int] {
    def isZero(): Boolean = wrapped == 0
    def belowZero: Boolean = wrapped < 0
    def -(option: Int): IValue = new IValue(wrapped - option)
  }



  val withRepetitions = true                //> withRepetitions  : Boolean = true
  val withoutRepetitions = false            //> withoutRepetitions  : Boolean = false
 
  val cntwith = new IValue(4).ccCount(withRepetitions) (List(1,2,3,5))
                                                  //> cntwith  : Int = 4
  val cntwo = new IValue(4).ccCount(withoutRepetitions) (List(1,2,3,5))
                                                  //> cntwo  : Int = 1
  val listwith = new IValue(4).ccList(withRepetitions) (List(1,2,3,5))
                                                  //> listwith  : List[List[Int]] = List(List(2, 2), List(3, 1), List(2, 1, 1), L
                                                  //| ist(1, 1, 1, 1))
  assert(listwith.length == cntwith)

 
 
   // Part III: anagram values
	
  type Word = String

  type Sentence = List[Word]

  type Occurrences = List[(Char, Int)]

  def wordOccurrences(w: Word): Occurrences = {
    w.groupBy(c => c).map({case (c, list) => (c -> list.length)}).toList
  }                                         //> wordOccurrences: (w: GenericChange.Word)GenericChange.Occurrences
 
  wordOccurrences("aabc")                   //> res1: GenericChange.Occurrences = List((b,1), (a,2), (c,1))
  def sentenceOccurrences(s: Sentence): Occurrences = {
    wordOccurrences(s.flatten mkString "")
  }                                         //> sentenceOccurrences: (s: GenericChange.Sentence)GenericChange.Occurrences

  sentenceOccurrences(List("aab", "aac"))   //> res2: GenericChange.Occurrences = List((b,1), (a,4), (c,1))
 
  // function used in the reduce step, notorious sum-c. I do not understand why Scala does not let me to put into the produce method.
  def subtract(x: Occurrences, y: Occurrences): Occurrences =   {{
      // this implementation admits negatives
      y.foldLeft(x.toMap.withDefaultValue(0)) {case (m, (k, v)) =>
        val res =  m(k) - v
        if (res == 0) m - k else m.updated(k, res) // filter out empty items
      }
    }.toList
  }                                         //> subtract: (x: GenericChange.Occurrences, y: GenericChange.Occurrences)Gener
                                                  //| icChange.Occurrences

  // For anagrams, value will store occurences, obtained by subtracting words instad of ints everywhere.
  // Accumulator and path collection however remain the same
  class AnagramValue(val wrapped: Occurrences) extends Value[Word, Occurrences] {
    def this(word: String) = this(wordOccurrences(word))
    def isZero(): Boolean = wrapped.length == 0
    def belowZero: Boolean = wrapped exists (_ . _2 < 0)
    def -(option: Word): AnagramValue = new AnagramValue(subtract(wrapped, wordOccurrences(option)))
 
  }

  // I cannot run these tests right afer Int counting declaration since of plugin bug https://scala-ide-portfolio.assembla.com/spaces/scala-ide/support/tickets/1002168#/activity/ticket:
	


  new AnagramValue("aab").ccList(withoutRepetitions)(List("a", "b"))
                                                  //> res3: List[List[GenericChange.Word]] = List()
  new AnagramValue("aab").ccList(withRepetitions)(List("a", "b"))
                                                  //> res4: List[List[GenericChange.Word]] = List(List(b, a, a))


  // Seems done, just permutate the combinations with code from https://gist.github.com/valtih1978/99d8b320e59fcde634ad
  // because "1+2" and "2+1" are different anagrams yet order does not count in the change.
	
//	val changes = new AnagramValue("aab").ccList(withRepetitions)(List("a", "b"))
//
//	var anagrams = changes flatMap (change => permute(change, change.length))
//
//
//	anagrams

  // Compare with Odersky-wanted result, https://gist.github.com/valtih1978/5983b7620798beeda317
  // That one seems more concise yet coin-change + permutations seem more generic and efficient.
  // I will compare efficiency in the next post
	
}