probleme_31.groovy

import groovyx.gpars.*
import groovy.util.GroovyCollections

@Grab(group="org.codehaus.gpars", module="gpars", version="0.11")
def getMatchingCombos(target) {
	combos = [200, 100 , 50, 20, 10, 5, 2, 1]
	// Using sequences is far too time-consuming (brute-force is never the best option, contrary to Jeff Artwood thoughs ;-) )
	// def sequences = GroovyCollections.subsequences(combos)
	GParsPool.withPool(2) { pool ->
		combos = combos.collectParallel { n ->  
			// transforming range into list thanks to http://groovy.codehaus.org/api/groovy/lang/Range.html
			// Don't forget the as (no, not the ass, but the one defined by http://groovy.codehaus.org/Operators (asType operator)
			((0..(target/n)).step(1) as TreeSet).collect { p -> p*n }
		}
		// now come the tricky part, extract subsequences based upon a criteria
		// But it may be a job for Fork/Join : http://gpars.codehaus.org/ForkJoin
		// Unfortunatly, I can't come to write an efficient solution, so I gave up and go the recursive way
		return GParsPool.runForkJoin(combos, 0, 0, target) { usableCombos, comboIndex, sum, targetSum ->
			def offset = "\t"*comboIndex
			def results = 0
			if(sum<=targetSum) {
				if(comboIndex<combos.size()) {
					usableCombos[comboIndex].each { n ->
//						println offset+"now trying with $comboIndex element value $n (curent sum is $sum)"
						forkOffChild(usableCombos, comboIndex+1, sum+n, targetSum)
					}
				} else {
					if(sum==targetSum) {
						results +=1
//						println offset+"sum is target ! so we have $results"
					}
				}
			}
			return results+getChildrenResults().sum(0);
		}
	}
}

long start = System.currentTimeMillis();

println getMatchingCombos(200)

long end = System.currentTimeMillis();
println "duration "+((end-start)/1000.0)+" s";