『ある金額になるコインの組み合わせ』 に挑戦

お題：ある金額になるコインの組み合わせ - No Programming, No Life

Javaで「ある金額になるコインの組み合わせ」 - terazzoの日記 を Groovy に翻訳しようといろいろ調べていたら Tree iterator が簡単そうだったので実装してみた*1。
参考

• General design concerns for a tree iterator

@Grab(group='com.google.guava', module='guava', version='r09')
import com.google.common.base.Function
import com.google.common.base.Predicate
import static com.google.common.collect.Iterators.transform
import static com.google.common.collect.Iterators.filter


def cc(amount, coins) {
  def root = [amount, coins, []]
  iterator([root] as LinkedList)
}

def iterator(stack) {
  def next = {
    def node = stack.removeLast()
    def (amount, coins, path) = node
    if (!coins.empty) {
      def (coin, rest) = [coins.head(), coins.tail()]
      // right-subtree は coin を使用しない場合
      if (amount != 0 && !rest.empty)
        stack.addLast([amount, rest, path])
      // left-subtree は coin を使用する場合
      if (amount-coin >= 0)
        stack.addLast([amount-coin, coins, [*path, coin]])
    }
    return node
  }
  def iter = [hasNext: { !stack.empty }, next: next] as Iterator
  def pred = { amount, coins, path -> amount == 0 } as Predicate
  def tran = { amount, coins, path -> path } as Function
  // node が leaf の場合に絞込み path を出力する
  transform(filter(iter, pred), tran)
}


cc(10,[1,5,10,50,100,500]).with {
  assert it.next() == [1,1,1,1,1,1,1,1,1,1]
  assert it.next() == [1,1,1,1,1,5]
  assert it.next() == [5,5]
  assert it.next() == [10]
  assert it.hasNext() == false
}

Tree iterator は stack を使い iterate する毎に stack からノードを取り出して返している。
ノードに子ノードがあれば取り出したときに stack に格納する。
今回は親ノードから子ノードを作成できるので iterate しながら tree を作成している感じになった。

*1:TODO 継続を理解する