Advent of code

◂ 17 décembre 2015 ▸

  No Such Thing as Too Much :

1. code.py

# ordre croissant pour que le code optimisé fonctionne
CONTAINERS = [1, 6, 13, 13, 14, 16, 18, 18, 20, 24, 30, 33, 35, 35, 41, 42, 44, 45, 48, 50]

def nbPossPart1(tot, nbs):
    if tot == 0:
        return 1
    if len(nbs) == 0:
        return 0
    if tot < nbs[0]:
        return 0
    return nbPossPart1(tot, nbs[1:]) + nbPossPart1(tot - nbs[0], nbs[1:])


def nbPossPart2(tot, nbs, liste=[]):
    if tot == 0:
        return (1, len(liste))
    if len(nbs) == 0:
        return (0, None)
    if tot < nbs[0]:
        return (0, None)

    nb1, min1 = nbPossPart2(tot, nbs[1:], liste)
    nb2, min2 = nbPossPart2(tot - nbs[0], nbs[1:], liste + nbs[0:1])

    if nb1 == 0 or (nb2 > 0 and min2 < min1):
        return (nb2, min2)
    elif min1 == min2:
        return (nb1 + nb2, min1)
    else:
        return (nb1, min1)

print("Partie 1:", nbPossPart1(150, CONTAINERS))
print("Partie 2:", nbPossPart2(150, CONTAINERS)[0])