Forum Programmation.autre Avent du Code, jour 19

Posté par 🚲 Tanguy Ortolo (site web personnel) le 19 décembre 2022 à 10:05. Licence CC By‑SA.

Étiquettes :

déc.

2022

Suite de l'Avent du Code, jour 19.

Les fumées volcaniques n'ont pas fait du bien au Père Noël. Hier, au cœur de la nuée ardente, menacé par des blocs de lave qui filaient de toute part, il n'avait de cesse de calculer leur trajectoire pour les éviter. Ah non, il était occupé à calculer leur refroidissement pour voir si ça allait donner de l'obsidienne.

Bonne nouvelle, on a de l'obsidienne. Mauvaise nouvelle, on s'en est visiblement pris quelques coups sur la tête, ce qui n'a pas arrangé les choses. Les éléphants ont faim et commencent à se rebeller, mais pas de panique, il y a de l'argile, du minerai, de l'obsidienne et des géodes ! Tout ce qu'il faut pour ~~faire à manger~~ construire une armée de robots pour casser un maximum de géodes. Notre sac à dos contient tout ce qu'il faut pour ça, à croire que les lutins avaient prévu le coup.

J'ai du retard à rattraper, la solution attendra. :-)

# Modélisation trop longue à débugger

Posté par Yth (Mastodon) le 19 décembre 2022 à 11:42. Évalué à 4. Dernière modification le 19 décembre 2022 à 11:44.

J'ai passé un temps fou à débugger ma modélisation pourtant pas si complexe.
Après j'ai rapidement constaté que l'approche naïve était idiote et explosive, donc j'ai testé deux limitation de l'exploration des possibilités :

Si on peut construire un extracteur de géode, on le fait, c'est capital si on peut produire un robot-géode par tour, on ne fait plus que ça.
On limite le nombre de robot de chaque type au coût maximal d'un robot pour ce type de ressources.

C'est empirique, j'ai juste testé ces règles sans chercher plus loin : ça valide les données de test !
Donc j'ai testé les données réelles et bingo.

En terme de stats pour les données de test, le nombre de possibilités testées :

85 156 pour le premier schéma en 24s.
47 477 pour le second schéma en 24s.
14 042 636 pour le premier schéma en 32s.
3 778 241 pour le second schéma en 32s.

Et 2 minutes 20 pour trouver ça, yuk…
Sur les données réelles, j'explore au total 492 462 chemins sur l'exercice 1, avec 30 schémas, et 4 661 927 chemins sur l'exercice 2 avec 3 schémas (les éléphants ont bouffés les autres schémas).
Ce qui ne prend que 44 secondes, donc les données réelles sont plus cool que les données de test, pour une fois.

Yth, mélange d'intuition, et de mains gauches aujourd'hui.

[^] # Re: Modélisation trop longue à débugger

Posté par Yth (Mastodon) le 19 décembre 2022 à 12:05. Évalué à 3.

Et en optimisant un pouille mes structures de données (dataset immutable, ne pas recopier les données statiques dans les nouvelles instances de classes, mais les mettre en dur dans la classe, etc), je descends à 29 secondes pour les données de test et 10s pour les données réelles !

Yth.

[^] # Re: Modélisation trop longue à débugger

Posté par syj le 19 décembre 2022 à 12:37. Évalué à 1.

Gg, Perso, j'y ai passé 2h ce matin et je bloque sur le fait que je ne trouve pas comment arriver à 12 sur le 2ème du test unit.
Je dois avoir un bug qui m'echape.

Malheureusement, j'ai 2 truc urgent qui sont tombé aujourd'hui. Pas sur que je puisse y rebosser aujourd'hui.
et la fin de semaine risque d'être compliqué, je suis en vacances jeudi soir.

[^] # Re: Modélisation trop longue à débugger

Posté par syj le 19 décembre 2022 à 13:49. Évalué à 1.

Est ce qu'on peut construire plusieurs robots en un tour ?

C'est probablement çà mon erreur ?

[^] # Re: Modélisation trop longue à débugger

Posté par Yth (Mastodon) le 19 décembre 2022 à 15:22. Évalué à 2. Dernière modification le 19 décembre 2022 à 15:24.

Non, on n'a qu'une seule usine de robots, donc c'est un par tour…

À noter ici que la différence entre cpython et pypy est assez délirante.
J'ai nettoyé le code, je suis à 8 secondes avec pypy3, et 2 minutes 30 avec python3 !

Yth.

[^] # Re: Modélisation trop longue à débugger

Posté par syj le 19 décembre 2022 à 21:01. Évalué à 2. Dernière modification le 19 décembre 2022 à 21:01.

Au final, J'aurai mis 35min de plus.

Le problème venait que j'avais mis une règle qui réduisait le nombre d'action possible pendant mon parcours en profondeur

Il met 1min3s pour calculer le 2ème.

Pour une fois , mon code n'est pas trop moche :)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class A2022D19 {
    private static final String BUILD_ORE = "BUILD_ORE";
    private static final String BUILD_CLAY = "BUILD_CLAY";
    private static final String BUILD_OBSIDIAN = "BUILD_OBSIDIAN";
    private static final String BUILD_GEODE = "BUILD_GEODE";
    private static final String WAIT = "WAIT";

    static Map<BluePrint, Integer> bestMap = new HashMap<>();

    public static class Cost {
        int costOre;
        int costClay;
        int costObsidian;

        public String toString() {
            return costOre +";" + costClay + ";" + costObsidian;
        }                   
    }   

    public static class BluePrint {
        int index;
        Cost buildOreRobot;
        Cost buildClayRobot;
        Cost obsidianRobot; 
        Cost geodeRobot;

        public BluePrint(String row, int index) {
            this.index = index;
            String[] robots =  row.split("\\.");

            buildOreRobot = buildCost(robots[0]);
            buildClayRobot = buildCost(robots[1]);
            obsidianRobot = buildCost(robots[2]);
            geodeRobot = buildCost(robots[3]);

        }

        private Cost buildCost(String row) {
            Cost cost = new Cost();
            String regex;
            regex = ".* ([0-9]*) ore.*";
            if(row.matches(regex)) {
                String s = row.replaceAll(regex, "$1");
                cost.costOre = Integer.valueOf(s);
            }


            regex = ".* ([0-9]*) clay.*";
            if(row.matches(regex)) {
                String s = row.replaceAll(regex, "$1");
                cost.costClay = Integer.valueOf(s);
            }

            regex = ".* ([0-9]*) obsidian.*";
            if(row.matches(regex)) {
                String s = row.replaceAll(regex, "$1");
                cost.costObsidian = Integer.valueOf(s);
            }

            System.out.println(cost.toString());

            return cost;
        }
    }   

    public static class Action {
        int buildOreRobot = 0;
        int buildClayRobot = 0;
        int buildObsidianRobot = 0;
        int buildGeodeRobot = 0;
    }

    public static class State {


        BluePrint bp;
        int oreRobot = 1;
        int clayRobot = 0;
        int obsidianRobot = 0;
        int geodeRobot = 0;

        int ore = 0;
        int clay = 0;
        int obsidian = 0;
        int geode = 0;
        int index=0;

        public State(BluePrint bp) {
            this.bp = bp;
        }

        public boolean canPaid(Cost cost) {
            return ore >= cost.costOre
                && clay >= cost.costClay
                && obsidian >= cost.costObsidian;                                   
        }

        public void paid(Cost cost ) {
            ore -= cost.costOre;
            clay -= cost.costClay;
            obsidian -= cost.costObsidian;
        }

        public List<String> availablesAction() {
            List<String> actions  = new ArrayList<>();
            if(canPaid(bp.geodeRobot)) {                
                actions.add(BUILD_GEODE);
                return actions;
            }

            if(canPaid(bp.obsidianRobot)) {             
                actions.add(BUILD_OBSIDIAN);
                return actions;
            }

            if(canPaid(bp.buildClayRobot) && max(bp.buildOreRobot.costClay, bp.buildClayRobot.costClay, bp.obsidianRobot.costClay, bp.geodeRobot.costClay) >  this.clayRobot) {             
                actions.add(BUILD_CLAY);                
            }

            if(canPaid(bp.buildOreRobot) && max(bp.buildOreRobot.costOre, bp.buildClayRobot.costOre, bp.obsidianRobot.costOre, bp.geodeRobot.costOre) >  this.oreRobot) {               
                actions.add(BUILD_ORE);             
            }

            actions.add(WAIT);
            return actions;

        }

        private int max(int costOre, int costOre2, int costOre3, int costOre4) {
            return Math.max(Math.max(Math.max(costOre, costOre2), costOre3), costOre4);
        }

        public void transform(String command) {
            ++index;
            //System.out.println(index);
            //System.out.println(command);      
            this.ore += this.oreRobot;
            this.clay += this.clayRobot;
            this.obsidian += this.obsidianRobot;            
            this.geode += this.geodeRobot;      

            if(command.equals(BUILD_GEODE)) {
                paid(bp.geodeRobot);
                this.geodeRobot++;
            }

            if(command.equals(BUILD_OBSIDIAN)) {
                paid(bp.obsidianRobot);
                this.obsidianRobot++;
            }

            if(command.equals(BUILD_CLAY)) {
                paid(bp.buildClayRobot);
                this.clayRobot++;
            }

            if(command.equals(BUILD_ORE)) {
                paid(bp.buildOreRobot);
                this.oreRobot++;
            }

            //System.out.println("S:" + this.ore + ";"  + this.clay + ";" + this.obsidian + ";" + this.geode);
            //System.out.println("R:" + this.oreRobot + ";"  + this.clayRobot + ";" + this.obsidianRobot + ";" + this.geodeRobot);

        }

        public void copyInto(A2022D19.State newState) {
            newState.bp = this.bp;
            newState.oreRobot = this.oreRobot;
            newState.clayRobot = this.clayRobot;
            newState.obsidianRobot = this.obsidianRobot;
            newState.geodeRobot = this.geodeRobot;

            newState.ore = this.ore;
            newState.clay = this.clay;
            newState.obsidian = this.obsidian;
            newState.geode = this.geode;
            newState.index= this.index;

        }
    }

    public static void main(String[] args) {
        step1();
    }


    public static void executeDFS(State state) {
        if(state.index == 32) {
            if(bestMap.get(state.bp) == null || state.geode > bestMap.get(state.bp)) {              
                bestMap.put(state.bp, state.geode);                         
                System.out.println("Best:" + state.bp.index +";" + state.geode);                                            
            }
            return;
        }
        List<String> actions =state.availablesAction();
        State newState = new State(state.bp);
        for(String action : actions) {          
            state.copyInto(newState);
            newState.transform(action);
            executeDFS(newState);
        }
    }

    private static void step1() {
        try (Scanner in = new Scanner(A2022D19.class.getResourceAsStream("/res/i19.txt"))) {
            List<BluePrint> listBp = new ArrayList<>(); 
            while (in.hasNext()) {
                String row = in.nextLine();
                BluePrint bp = new BluePrint(row, listBp.size()+1);             
                listBp.add(bp);

            }

            State state;    
            for(BluePrint bp: listBp) {
                state =new State(bp);
                executeDFS(state);
            }               

            int sum  = 0;
            int prod = 1;
            for(Map.Entry<BluePrint, Integer> e : bestMap.entrySet()) {
                System.out.println("Final:" + e.getKey().index + "," + e.getValue());   
                prod *= e.getValue();
                sum += (e.getKey().index  * e.getValue());
            }

            System.out.println(sum);
            System.out.println(prod);


        }

    }

}

[^] # Re: Modélisation trop longue à débugger

Posté par syj le 19 décembre 2022 à 23:14. Évalué à 1.
Petite amélioration, je descends à 6s en modifiant mon DFS

L'idée est de ne pas aller jusqu'au bout si on sait déjà qu'on sera en-dessous du meilleur temps.
```
public static void executeDFS(State state) {
int leftTurn = NB_TURN_32- state.index;
int expGeode = state.geode+(NB_TURN_32-state.index) * (state.geodeRobot) + (leftTurn+1) * (leftTurn + 0) / 2;

if(bestMap.get(state.bp) != null && expGeode < bestMap.get(state.bp)) {
return;
}
```
if(state.index == NB_TURN_32) {
    if(bestMap.get(state.bp) == null || state.geode > bestMap.get(state.bp)) {              
        bestMap.put(state.bp, state.geode);                         
        System.out.println("Best:" + state.bp.index +";" + state.geode);                                            
    }
    return;
}
List<String> actions =state.availablesAction();
State newState = new State(state.bp);
for(String action : actions) {          
    state.copyInto(newState);
    newState.transform(action);
    executeDFS(newState);
}
```
}
```
- [^] # Re: Modélisation trop longue à débugger
  
  Posté par Yth (Mastodon) le 20 décembre 2022 à 15:53. Évalué à 2.
  C'est pas mal de ne pas aller jusqu'au bout si on sait déjà qu'on sera en-dessous du meilleur temps.
  J'ai ajouté un truc comme ça sur mon code, ça fonctionne nickel, et je divise le temps par deux, je suis à 5s pour les deux exercices.
  Je passe de 492 462 chemins à 46 859 sur l'exo 1.
  Et au total de 4 661 927 à 755 262 sur l'exo 2.
  
  Vu la réduction sévère du nombre de chemins, je me demande où le temps est perdu tout de même…
  - Yth.

[^] # Re: Modélisation trop longue à débugger

Posté par 🚲 Tanguy Ortolo (site web personnel) le 21 décembre 2022 à 18:05. Évalué à 4.

On limite le nombre de robot de chaque type au coût maximal d'un robot pour ce type de ressources.

Ce n'est pas empirique ça, c'est prouvable. Comme on ne peut construire qu'un robot par tour, récolter plus d'unités de n'importe quelle ressource que la quantité qu'on peut en dépenser ne sert à rien.
- [^] # Re: Modélisation trop longue à débugger
  
  Posté par Yth (Mastodon) le 21 décembre 2022 à 21:41. Évalué à 2.
  Oui, je l'ai fait instinctivement, mais après c'est apparu évident.
  En pratique on maximise toujours l'ore dans les chemins gagnants, mais pas en construisant tout d'un coup.
  - Yth.

# Du code, du code, du code !

Posté par Yth (Mastodon) le 19 décembre 2022 à 15:40. Évalué à 4.

D'abord la modélisation, avec des opérations sur triplets de matière Matters(ore, clay, obsidian). Dans un premier temps j'avais aussi geode, mais en vrai on ne produit, ne consomme, ni ne stocke de geode : c'est le score, on le gère à part.
En vrai ça change pas grand chose…
Un frozen dataclass, et les opérations retournent une nouvelle instance, ça permet d'éviter des risques de modifier un truc référencé ailleurs, et on y gagne en bugs et en perfs au bout du compte.

Chaque blueprint génère une Factory qui ne sert pas à grand chose, c'est des données, c'est figé, ça bouge pas.

Ensuite une classe d'état, State, qui stocke le temps restant, les stocks, la production, et le nombre de géodes à la fin si on touche plus à rien, donc le score actuel de cet état à la fin du temps imparti. Aussi un dataclass, je découvre, j'en mets partout, selon le biais bien connu de waooouh-nouveauté !

import sys
import re
import math
from dataclasses import dataclass
from functools import cached_property

@dataclass(frozen=True)
class Matters():
    ore: int = 0
    clay: int = 0
    obsidian: int = 0
    def __add__(self, other):
        return Matters(
            self.ore + other.ore,
            self.clay + other.clay,
            self.obsidian + other.obsidian,
        )
    def __sub__(self, other):
        return Matters(
            self.ore - other.ore,
            self.clay - other.clay,
            self.obsidian - other.obsidian,
        )
    def __mul__(self, t):
        # Calculate production in t minutes
        return Matters(
            self.ore * t,
            self.clay * t,
            self.obsidian * t,
        )
    def __call__(self, name):
        return self.__dict__[name]

@dataclass(frozen=True)
class Factory:
    id: int
    robots: dict[Matters]
    @cached_property
    def maxproduction(self):
        return Matters(*(
            max(x)
            for x in zip(*[
                (m.ore, m.clay, m.obsidian)
                for m in self.robots.values()
            ])
        ))

@dataclass
class State:
    timeleft: int
    stock: Matters = Matters()
    production: Matters = Matters(1, 0, 0)
    geode: int = 0

    def __lt__(self, other):
        return self.geode < other.geode

    def buildable(self):
        return [
            (robot, self.factory.robots[robot], self.test_build_time)
            for robot in ["geode", "obsidian", "clay", "ore"]
            if self.isbuilduseful(self.factory.robots[robot])
        ]

    def isbuilduseful(self, cost):
        t = self.timetobuild(cost)
        if t is False:
            return False
        # This robot should have the time to produce something
        if t >= self.timeleft:
            return False
        self.test_build_time = t
        return True

    def timetobuild(self, cost):
        t = 0
        if cost.ore > self.stock.ore:
            t = max(math.ceil((cost.ore - self.stock.ore) / self.production.ore), t)
        if cost.clay > self.stock.clay:
            if not self.production.clay:
                return False
            t = max(math.ceil((cost.clay - self.stock.clay) / self.production.clay), t)
        if cost.obsidian > self.stock.obsidian:
            if not self.production.obsidian:
                return False
            t = max(math.ceil((cost.obsidian - self.stock.obsidian) / self.production.obsidian), t)
        return t + 1  # Time to collect enough resources, +1 to build the robot

    def buildrobot(self, robot, cost, time):
        stock = self.stock + self.production * time - cost
        time = self.timeleft - time
        if robot == "geode":
            return State(time, stock, self.production, self.geode + time)
        return State(time, stock, self.production + Matters(**{robot: 1}), self.geode)

    def __str__(self):
        return f"State Score={self.geode}, TimeLeft={self.timeleft}, "\
            f"Production={self.production}, Stocks={self.stock}"

Ensuite le code en lui-même :

def iteration(state):
    buildable = state.buildable()
    if not buildable:  # end of the line !
        return state, 1
    explored = 0
    r = state
    if buildable[0][0] == "geode" and buildable[0][2] == 1:
        buildable = buildable[:1]
    for robot, cost, time in buildable:
        if robot != "geode" and state.production(robot) >= state.factory.maxproduction(robot):
            continue
        s, e = iteration(state.buildrobot(robot, cost, time))
        explored += e
        r = s if r < s else r
    if not explored:  # robot limit attained
        state, 1
    return r, explored


def input():
    rematter = r"ore|clay|obsidian|geode"
    rerobot = re.compile(fr"Each ({rematter}) robot costs (.*)")
    recost = re.compile(fr"(\d+) ({rematter})")
    for blueprint in sys.stdin:
        id, blueprint = blueprint.strip().split(":")
        yield Factory(
            int(id.split()[-1]), {
                build: Matters(**{b: int(a) for a, b in recost.findall(cost)})
                for robot in blueprint.strip(".").split(".")
                for build, cost in (rerobot.match(robot.strip()).groups(),)
            })


def ex1(factories):
    score = 0
    expl = 0
    for f in factories:
        State.factory = f
        beststate, explored = iteration(State(timeleft=24))
        print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")
        score += f.id * beststate.geode
        expl += explored
    print(f"Score final = {score} (33, 1599) {expl} chemins explorés")


def ex2(factories):
    score = 1
    expl = 0
    for f in factories:
        State.factory = f
        beststate, explored = iteration(State(timeleft=32))
        print(f"Blueprints#{f.id} Best of {explored} State {str(beststate)}")
        score *= beststate.geode
        expl += explored
    print(f"Score final = {score} ({56*62}, {49*18*16}) {expl} chemins explorés")


factories = list(input())
ex1(factories)
ex2(f for f in factories if f.id <= 3)

Voilà voilà…

Yth.

# Erreur bete

Posté par Eric P. le 20 décembre 2022 à 01:14. Évalué à 1.

Je suis un peu degoute sur celui-ci, j'ai perdu un temps fou pour une erreur bete.
J'avais du code qui me donnait les bonnes reponses 9 et 12 sur l'exemple, mais beaucoup trop lent.
Du coup je commence a ajouter des heuristiques d'optimisation. J'arrive a faire descendre le temps d'execution dans la minute, je commence a tester et je ne trouve plus que 7 et 10. Je me dis que mes optims sont trop brutales et je perd litteralement des heures a essayer de trouver des optims qui me redonnent le nombre correct… avant de realiser que j'avais introduit un bug et je ne collectais plus les ressources lors de la minute 24…

Bon apres fix de ce probleme, j'ai un algo suffisemment rapide qui me donne les bonnes reponses pour la partie 1, et aussi pour la partie 2.
Je ne garde qu'un nombre fixe d'options a chaque minute, je trie les options par score et je garde le top 200000 (j'aurais pu descendre beaucoup plus bas), donc le temps d'execution est a peu pres lineaire, et la partie 2 ne posait pas de probleme.

Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.
- [^] # Re: Erreur bete
  
  Posté par Eric P. le 20 décembre 2022 à 05:09. Évalué à 2.
  
  En fait je peux descendre mon top d'options a garder a chaque minute jusqu'a 100 et les resultats sont toujours corrects:
  part1_quality_with_mult=2193 part2_quality_product=7200 pypy3.9-v7.3.10-linux64/bin/pypy day19.py 0.26s user 0.05s system 52% cpu 0.593 total0.26s elapsed pour l'ensemble des deux parties!
  
  Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.
  - [^] # Re: Erreur bete
    
    Posté par Yth (Mastodon) le 20 décembre 2022 à 16:28. Évalué à 2.
    Parcourir en largeur et virer les chemins pourraves, c'pas mal.
    Mon algo parcours en profondeur, j'ai pas cette possibilité sauf à le refaire…
    
    Une idée de comment être raisonnablement sûr que tu as la meilleure solution en limitant à 100 ?
    - Yth.
    - [^] # Re: Erreur bete
      
      Posté par steph1978 le 21 décembre 2022 à 03:58. Évalué à 2.
      
      Je dirai qu'il n'y a pas de règle car cela dépend de l'input.
      Le code que j'ai pour la partie deux donne la bonne réponse en gardand le top 1000, ne marche pas à 700. Mais sur un autre input que j'ai testé, il a fallu monter à 2000.
    - [^] # Re: Erreur bete
      
      Posté par Eric P. le 21 décembre 2022 à 12:16. Évalué à 1.
      
      En fait j'avais commence par un DFS (en profondeur), et je l'ai reecrit completement en un BFS (en largeur) pour justement pouvoir comparer les chemins et garder les meilleurs.
      Au final la partie algo est assez simple et standard, c'est assez simple de convertir un DFS en BFS.
      
      C'est vrai que c'est impossible de savoir quand tu as la meilleure solution.
      Pour moi, j'ai commence a 100 000, Advent of code m'a confirme que c'etait le bon resultat, et je suis descendu petit a petit jusqu'a 100. A 50 ca me trouvait moins de geodes.
      
      J'aurais pu faire le contraire, commencer bas, tester dans Advent of Code, puis monter si le resultat etait trop bas.
      
      Comme le dit le commentaire precedent, tout depend des inputs, mais ca depend aussi de la fonction de scoring et si tu as des heuristiques en plus de la fonction de scoring.
      
      Excusez l'absence d'accents dans mes commentaires, j'habite en Australie et n'ai pas de clavier francais sous la main.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.