Advent of code

◂ 19 décembre 2022 ▸

  Not Enough Minerals : Construire des robots qui minent des trucs permettant de construire d'autres robots

Blueprint 1: Each ore robot costs 4 ore. Each clay robot … 

Blueprint 2: Each ore robot costs … 

1. code.py

### Solution plutôt lente (2'30), malgré certaines optimisations
import re
from functools import cache

f = open("input.txt", 'r')
lines = [line[:-1] for line in f.readlines()]


BLUEPRINTS = [None]   # décalage pour que l'indice corresponde au numéro du blueprint

nb = 0
for line in lines:
    entiers = list(map(int,filter(lambda x:x,re.split('-?[^0-9]+', line))))
    numBlueprint,  oreR_or,  clayR_or,  obsR_or,  obsR_cl,  geodR_or,  geodR_ob   =  entiers
    BLUEPRINTS.append(( (oreR_or,0,0,0), (clayR_or,0,0,0), (obsR_or, obsR_cl,0,0), (geodR_or, 0, geodR_ob,0) ))

TIME1 = 24
TIME2 = 32

ORE = 0
CLAY = 1
OBS = 2
GEODE = 3
TYPES = tuple(range(4))

TRESOR = (0,0,0,0)
ROBOTS = (1,0,0,0)

@cache
def calcMaxGeodes(blueprint, time, tresor, robots):
    global MAXIMUM_RESSOURCES_COSTS

    if time == 0:
        return (tresor[GEODE], [])

    maxGeodes = 0
    achats = []

    # On ne pourra pas utiliser plus que tant d'ore en un temps T, idem CLAY, etc.
    # Limiter ainsi ne change rien au résultat ni à la rapidité directe, mais permet d'avoir plus de chances de retomber sur une valeur mise en cache
    tresor = list(tresor)
    for ressources in [ORE, CLAY, OBS]:
        if tresor[ressources] > time*(MAXIMUM_RESSOURCES_COSTS[ressources]-robots[ressources]) + MAXIMUM_RESSOURCES_COSTS[ressources]:
            tresor[ressources] = time*(MAXIMUM_RESSOURCES_COSTS[ressources]-robots[ressources]) + MAXIMUM_RESSOURCES_COSTS[ressources]
    
    for typeRobot in range(3,-1,-1):
        if typeRobot != GEODE and robots[typeRobot] >= MAXIMUM_RESSOURCES_COSTS[typeRobot]:  # ne pas créer un type de robot quand on en a déjà assez pour créer le maximum utile
            continue

        if all(blueprint[typeRobot][typ] <= tresor[typ] for typ in range(3)):
            robotsCopie = list(robots)
            robotsCopie[typeRobot] += 1
            (maxGPotentiel, achatsPotentiels) = calcMaxGeodes(blueprint, time - 1, tuple([tresor[typ] - blueprint[typeRobot][typ] + robots[typ] for typ in TYPES]), tuple(robotsCopie))
            if maxGPotentiel > maxGeodes:
                maxGeodes = maxGPotentiel
                achats = [typeRobot] + achatsPotentiels

            # Supposition qui fait gagner 25% du temps: touours mieux d'acheter les robots qui font des géodes dès que possible
            if typeRobot == GEODE:
                return (maxGeodes, achats)

    (maxGPotentiel, achatsPotentiels) = calcMaxGeodes(blueprint, time - 1, tuple([tresor[typ] + robots[typ] for typ in TYPES]), robots)
    if maxGPotentiel > maxGeodes:
        maxGeodes = maxGPotentiel
        achats = [None] + achatsPotentiels
    return (maxGeodes, achats)






# parties en parallèle pour profiter du cache sur chaque blueprint
reponsePartie1 = 0  # addition des valeurs
reponsePartie2 = 1  # multiplication des valeurs

for iBlueprint in range(1, len(BLUEPRINTS)):
    MAXIMUM_RESSOURCES_COSTS = tuple(max(BLUEPRINTS[iBlueprint][typ][typeRobot] for typ in TYPES) for typeRobot in TYPES)

    (maxGeodes, achats) = calcMaxGeodes(BLUEPRINTS[iBlueprint], TIME1, TRESOR, ROBOTS)
    reponsePartie1 += iBlueprint * maxGeodes
    print("Partie 1:", str(iBlueprint) + '/' + str(len(BLUEPRINTS)-1))

    if iBlueprint <= 3:
        print("Partie 2:", str(iBlueprint) + '/3')
        (maxGeodes, achats) = calcMaxGeodes(BLUEPRINTS[iBlueprint], TIME2, TRESOR, ROBOTS)
        reponsePartie2 *= maxGeodes

    calcMaxGeodes.cache_clear()

print("Réponse partie 1:", reponsePartie1)
print("Réponse partie 2:", reponsePartie2)