Greedy algorithm for abudhabi

abudhabi_greedy.py

from collections import Counter

def abudhabi_greedy(target, candidates):
	true_candidates = sorted(candidates + candidates, reverse=True)
	signatures = set()
	for result in greedy_algorithm(target, true_candidates):
		count = Counter(result)
		signature = tuple(count[k] for k in candidates)
		if signature not in signatures:
			yield signature
			signatures.add(signature)

def greedy_algorithm(target, candidates):
#	print(target,candidates)
	for i,n in enumerate(candidates):
		if n == target:
            # we got it!  we don't need to recurse deeper.
			yield [n]
		elif n > target:
            # too much? skip it
			continue
		elif n + sum(candidates[i+1:]) < target:
            # not enough left? skip it.
			break
		else:
            # we'll need some more 
			for result in greedy_algorithm(target - n, candidates[i+1:]):
				yield [n] + result

for i,result in enumerate(abudhabi_greedy(389, [80,95,63,97,67,42,18,48,20])):
	print(i,result)