Advent of code

◂ 15 décembre 2015 ▸

  Science for Hungry People :

1. code.py
2. codeRepartitionNonRecursif.py
3. codeRepartitionOneLiner.py
4. maths.py

import itertools
import numpy.linalg

TOT_QUANTITES = 100
NB_CALORIES_VOULUES = 500
STATS_INGREDIENTS = {
    'Sprinkles':    {'capacity':2, 'durability':0,  'flavor':-2, 'texture':0 , 'calories':3},
    'Butterscotch': {'capacity':0, 'durability':5,  'flavor':-3, 'texture':0 , 'calories':3},
    'Chocolate':    {'capacity':0, 'durability':0,  'flavor':5 , 'texture':-1, 'calories':8},
    'Candy':        {'capacity':0, 'durability':-1, 'flavor':0 , 'texture':5 , 'calories':8}
}

# Trouver domaine, si x=Sprinkles, y=Butterscotch, z=Chocolate, t=Candy = TOT_QUANTITES - x - y -z

# contraintes de quantité max 100
inequations = [    # [a,b,c,d] => ax + by + cz ≤ d 
        [-1,0,0,0],  # x ≥ 0
        [0,-1,0,0],  # y ≥ 0
        [0,0,-1,0],  # z ≥ 0
        [1,1,1,TOT_QUANTITES],  # t ≥ 0 <=> TOT_QUANTITES - x - y - z ≥ 0
    ]

# contraintes de score non négatif
for spec in ['capacity', 'durability', 'flavor', 'texture']:
    a = STATS_INGREDIENTS['Sprinkles'][spec]
    b = STATS_INGREDIENTS['Butterscotch'][spec]
    c = STATS_INGREDIENTS['Chocolate'][spec]
    e = STATS_INGREDIENTS['Candy'][spec]
    if any([v < 0 for v in [a,b,c,e]]):    # pas de contrainte si aucun ingrédient n'a d'effet négatif, car jamais de somme en dessous de zéro
        inequations.append([e-a, e-b, e-c, e*TOT_QUANTITES])     # ax + by + cz + e(TOT-x-y-z) ≥ 0  (la somme des qualités n'est pas négative)

def resoudre(equations):
    try:
        sol = numpy.linalg.solve([ equ[:-1] for equ in equations ], [ equ[-1] for equ in equations ])
        return list(sol)
    except numpy.linalg.LinAlgError:
        return None

def okContraintes(valeurs, inequation):
    return sum([valeurs[i] * inequation[i] for i in range(len(valeurs))]) <= inequation[-1] + 0.0000001

print("Sommets du domaine:")
sommets = []
for triplet in itertools.combinations(range(len(inequations)), 3):
    solution = resoudre([inequations[i] for i in triplet])
    if solution and all([okContraintes(solution, inequ) for inequ in inequations]):
        print("   ", [round(v,5) for v in solution])
        sommets.append(solution)




# Partir du milieu du domaine (les bords correspondant aux contraintes de score non négatifs donnent forcément un score de 0, donc pas optimal comme départ)   
depart = [round(numpy.average([s[i] for s in sommets])) for i in range(3)]

# Le milieu est déjà la solution… c'est en partie une coïncidence, donc on se pose au milieu de la face correspondant à une contrainte de quantité)
depart = [round(numpy.average([s[i] for s in sommets[0:3]])) for i in range(3)]
print("Depart en", depart)


def pointToQuantites(point):
    return {'Sprinkles':point[0], 'Butterscotch':point[1], 'Chocolate':point[2], 'Candy':TOT_QUANTITES-sum(point)}

def scorePoint(point):
    return score(pointToQuantites(point))

def score(quantites):
    score = 1
    for propriete in ['capacity', 'durability', 'flavor', 'texture']:
        somme = 0
        for ingredient in quantites:
            somme += quantites[ingredient] * STATS_INGREDIENTS[ingredient][propriete]
        score *= max(0, somme)
    return score

point = depart
maxScore = scorePoint(point)
mieuxAilleurs = True
while mieuxAilleurs:
    mieuxAilleurs = False
    for numAxe in range(3):
        for deplacement in [-1, 1]:
            newPoint = point[:]
            newPoint[numAxe] += deplacement
            if newPoint[numAxe] < 0 or sum(newPoint) > TOT_QUANTITES:
                continue
            newScore = scorePoint(newPoint)
            if newScore > maxScore:
                mieuxAilleurs = True
                maxScore = newScore
                point = newPoint
                print("Trouvé meilleur point:", point)
                break
        if mieuxAilleurs:
            break

print(pointToQuantites(point), maxScore)