package ru.jcorp.coins

import java.util.Date
import collection.Set
import collection.mutable

object Runner {

  class CoinsCounter(components: Set[Int]) {
    val cache: mutable.Map[Int, Set[Map[Int, Int]]] = mutable.Map()
    var cacheLimit = 0

    def add(map: Map[Int, Int], i: Int): Map[Int, Int] = {
      val option = map.get(i)
      map + (i -> (if (None == option) 1 else option.get + 1))
    }

    def decompose(value: Int) : Set[Map[Int, Int]] = value match {
      case 0 => Set(Map[Int, Int]())
      case t if (t < 0) => Set()
      case t if (cache.contains(t)) => cache(value)
      case _ => {

        def getVariants(subtracted: Int): Set[Map[Int, Int]] = {
          val remain: Int = value - subtracted
          val variants: Set[Map[Int, Int]] = decompose(remain)
          if ((variants.size > 0) && ((cacheLimit > cache.size) || (cacheLimit <= 0)))
            cache.put(remain, variants)
          val result: Set[Map[Int, Int]] = variants.map(variant => add(variant, subtracted))
          result
        }

        val variants: Set[Set[Map[Int, Int]]] = components.map(component => getVariants(component))
        ((Set[Map[Int, Int]]() /: variants)(_ ++ _))
      }
    }

    def setCacheLimit(value : Int) = {
      cacheLimit = value
      this
    }

    def getCacheLimit = cacheLimit
  }

  def main(args: Array[String]) {

    print("Sum: ")
    val sum = readInt()

    print("Coins: ")
    var coins = Set[Int]()
    readLine().split(' ').foreach( f => { coins += f.toInt } )
    println()

    val now = new Date()
    val counts = new CoinsCounter(coins).setCacheLimit(720).decompose(sum)
    println("Time: " + (new Date().getTime - now.getTime) + " ms")
    println()

    for {variant <- counts} {
      print(variant)
      println()
    }
  }
}