Advent of code

◂ 24 décembre 2015 ▸

  It Hangs in the Balance :

1. code.py

from math import prod
PACKS = [1,3,5,11,13,17,19,23,29,31,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113]


### Partie 1 :
N = 3
### Partie 2 :
N = 4

TARGET = sum(PACKS) // N


def decomposition(target, values, nbMaxVal, oneIsEnough=False):
    if target == 0:
        return [[]]
    if len(values) == 0 or target < values[0] or nbMaxVal == 0:
        return []

    # Avec le premier element de la liste de valeurs
    r1 = [values[0:1] + t for t in decomposition(target - values[0], values[1:], nbMaxVal - 1, oneIsEnough)]    
    if oneIsEnough and len(r1) > 0:
        return r1

    # Sans le premier element de la liste de valeurs
    r2 = decomposition(target, values[1:], nbMaxVal, oneIsEnough)
    return r1 + r2



res = decomposition(TARGET, PACKS, len(PACKS) // N)

minLen = len(PACKS)
minQE = None
for r in res:
    if len(r) < minLen or len(r) == minLen and prod(r) < minQE:
        if len(decomposition(TARGET, [v for v in PACKS if v not in r], len(PACKS), True)) > 0:
            minLen = len(r)
            minQE = prod(r)

print(minQE)