Forum Programmation.autre Advent of Code, jour 19

Posté par  . Licence CC By‑SA.
Étiquettes :
1
19
déc.
2023

Pour ce problème, nous avons deux choses.

Tout d'abord, des pièces de machine qui ont chacune 4 évaluations: une évaluation x, une évaluation m, un évaluation a et une évaluation s. Chaque évaluation est représenté par un entier.

Par exemple, une pièce peut avoir l'évaluation suivante:
{x=787,m=2655,a=1222,s=2876}

Ensuite, viennent les workflows. Un workflow est une série de tests sur les évaluations d'une pièce. Un résultat positif pour un test peut soit faire accepter la pièce, soit la faire rejeter, soit commencer un nouveau workflow. Si le test échoue, on passe au test suivant.

Exemple
px{a<2006:qkq,m>2090:A,rfg}
Le workflow s'appelle px.
Dans le premier test, on compare l'évaluation "a" de la pièce à 2006. Si a<2006, on commence le worflow nommé qkq. Sinon on passe au test suivant.
Dans le second test, on compare l'évaluation "m" de la pièce à 2090. Si m>2090, on accepte la pièce sinon on démarre le workflow rfg.

Voici l'exemple complet.

px{a<2006:qkq,m>2090:A,rfg}
pv{a>1716:R,A}
lnx{m>1548:A,A}
rfg{s<537:gd,x>2440:R,A}
qs{s>3448:A,lnx}
qkq{x<1416:A,crn}
crn{x>2662:A,R}
in{s<1351:px,qqz}
qqz{s>2770:qs,m<1801:hdj,R}
gd{a>3333:R,R}
hdj{m>838:A,pv}

{x=787,m=2655,a=1222,s=2876}
{x=1679,m=44,a=2067,s=496}
{x=2036,m=264,a=79,s=2244}
{x=2461,m=1339,a=466,s=291}
{x=2127,m=1623,a=2188,s=1013}

Les premières lignes sont des worflows et les dernières lignes sont des pièces avec leurs évaluations.

Le but de la partie 1, est de trouver les pièces qui sont acceptés par les worflows (en démarrant par le workflow "in"). On renvoit la somme des évaluations de chaque pièce acceptée.

Dans la partie 2, on fait varier chaque évaluation de 1 à 4000 et on veut compter le nombre de pièces avec ces évaluations qui seront acceptés.
Ca fait 40004 = 256 mille millards de possibilités. Donc, on ne peut pas s'amuser à générer toutes les possibilités de pièce.

  • # Optimisation insuffisante

    Posté par  (site web personnel) . Évalué à 3.

    La première partie ne pose pas de problème particulier. La seconde en revanche, c'est une autre paire de manches.

    Mon idée pour optimiser cela consiste à réduire le nombre de cas que l'on teste. En effet, les workflows ont des règles basées sur des seuils, et fondamentalement, il suffit de balayer l'ensemble des combinaisons de ces valeurs seuils pour pouvoir déterminer ce qui arrivera à l'importe quelle combinaison entre ces valeurs.

    Il faut faire attention à la façon dont on définit les seuils en question, parce que les définitions utilisent les opérateurs < et > qui ne sont pas l'opposé l'un de l'autre. Bref, il y a un détail important que je ne donnerai pas ici.

    Toujours est-il que, pour mes données, ça me ramène à 6,4 × 10⁹ = 6,4 milliards de possibilités. Et c'est un peu long à tester : à un rythme de l'ordre de 150.000 combinaisons par seconde, ça va me prendre une douzaine d'heures. Il faut que je trouve mieux que ça…

    • [^] # Re: Optimisation insuffisante

      Posté par  (site web personnel) . Évalué à 3.

      Bon, j'ai eu mon résultat en un peu moins d'une heure avec PyPy. Mais ça reste moche à mes yeux. À l'occasion, je m'essaierai à optimiser encore ça avec un découpage plus astucieux.

      • [^] # Re: Optimisation insuffisante

        Posté par  (Mastodon) . Évalué à 2.

        T'as découpé l'espace à 4 dimensions selon toutes les bornes possibles trouvées dans les règles, et traité chaque pavé à travers les règles pour savoir s'il était valide ou non ?

        Ça doit faire plus de traitements oui, mais c'est assez propre comme approche.

        Je n'y ai même pas pensé, je suis parti directement sur des découpage de pavés en deux, et bifurcation sur une règle ou une autre.

        D'ailleurs, à bien y réfléchir, plutôt que d'avoir des workflows à étapes on pourrait exploser en règles uniques nom#condition?vrai:faux} :

        px{a<2006:qkq,m>2090:A,rfg}
 -> px#a<2006?qkq:px1
 -> px1#m>2090?A:rfg
in{s<1351:px,qqz}
 -> in#s<1351?px:qqz
qqz{s>2770:qs,m<1801:hdj,R}
 -> qqz#s>2770?qs:qqz1}
 -> qqz1#m<1801?hdj:R}
qs{s>3448:A,lnx}
 -> qs#s>3448?A:lnx}
hdj{m>838:A,pv}
 -> hdj#m>838?A:pv}
etc.

        Ça simplifierai les traitements derrière.
        J'ai aussi vu des règles simplifiables comme gd{a>3333:R,R} où en fait tu rejettes tout, mais je n'ai pas jugé utile d'essayer de simplifier par ce genre de cas, ça avait l'air d'être plus d'efforts qu'autre chose.

        • Yth.

  • # Solution en Haskell.

    Posté par  . Évalué à 2. Dernière modification le 19 décembre 2023 à 13:07.

    150 microsecondes pour la partie 1 et 600 microsecondes pour la partie 2.

    La partie 1 est facile, passons.

    J'ai rapidement eu l'idée pour la partie 2 mais j'ai galéré à débugger mon code.
    Je ne suis pas très satisfait de mon code, je pense qu'il peut être simplifié.

    L'idée est de considérer des ensembles de RatingRange deux à deux disjoints.
    Les RatingRange étant des intervalles de valeurs pour chaque évaluation (x, m, a ou s).
    On peut voir ça comme un rectangle en 4 dimensions.

    On démarre avec un ensemble composé d'un seul RatingRange avec x = [1..4000], m=[1..4000], a=[1..4000] et s=[1..4000]

    A chaque test effectué, on va séparer les RatingRange en deux catégories, ceux qui sont acceptés et ceux qui sont refusés. Pour cela, on devra parfois diviser un RatingRange en deux parties.
    C'est ce que fait la fonction suivante
    haskell
    splitRatings :: Test -> [RatingRange] -> ([RatingRange], [RatingRange])

    A partir de là, il est relativement facile de simuler les worflow en prenant en entrée des RatingRange et de calculer le nombre total de possibilités de pièces vu que les RatingRange sont deux à deux disjoints.

    Voici le code en entier.

    import           AOC.Prelude hiding (LT, GT)
import qualified Data.HashMap.Strict as Map
import           Lens.Micro (Lens', set, (^.))
import           Lens.Micro.TH (makeLensesFor)
import           AOC (aoc)
import           AOC.Parser (Parser, sepBy1,sepEndBy1, eol, choice, decimal, lowerChar, some, try)

data Rating a = Rating { _x :: !a, _m :: !a, _a :: !a, _s :: !a} deriving (Foldable)
data Category = X | M | A | S
data Test = LT Category Int | GT Category Int | Otherwise
data Instr = Accept | Reject | Goto String
data Step = Step !Test !Instr
type Workflows = HashMap String [Step]
data Input = Input !Workflows ![Rating Int]
type RatingRange = Rating (Int, Int)

makeLensesFor [("_x", "xL"), ("_m", "mL"), ("_a", "aL"), ("_s", "sL")] ''Rating

parser :: Parser Input
parser = Input . Map.fromList <$> workflows <* eol <*> ratings where
    workflows = workflow `sepEndBy1` eol
    ratings = rating `sepEndBy1` eol
    workflow = (,) <$> some lowerChar <* "{" <*> step `sepBy1` "," <* "}"
    step = try (Step <$> test <* ":" <*> instr) <|> (Step Otherwise <$> instr)
    test = do
        c <- category
        "<" *> (LT c <$> decimal) <|> ">" *> (GT c <$> decimal)
    instr = Accept <$ "A" <|> Reject <$ "R" <|> Goto <$> some lowerChar
    category = choice [X <$ "x", M <$ "m", A <$ "a", S <$ "s"]
    rating = do
        x <- "{x=" *> decimal
        m <- ",m=" *> decimal
        a <- ",a=" *> decimal
        s <- ",s=" *> decimal <* "}"
        pure $ Rating x m a s

catLens :: Category -> (forall a. Lens' (Rating a) a)
catLens = \case
    X -> xL
    M -> mL
    A -> aL
    S -> sL

part1 :: Input -> Int
part1 (Input workflows ratings) = sum . map sum $ filter accepts ratings where
    accepts rating = go "in" where
        go name = case passTests rating steps of
            Accept -> True
            Reject -> False
            Goto name' -> go name'   
            where steps = workflows Map.! name
    passTests _ [] = error "passTests: cannot happen"
    passTests rating ((Step test instr):steps) = case test of
        Otherwise -> instr
        LT cat n | rating ^. catLens cat < n -> instr
        GT cat n | rating ^. catLens cat > n -> instr 
        _  -> passTests rating steps

splitRatings :: Test -> [RatingRange] -> ([RatingRange], [RatingRange])
splitRatings test = partitionEithers . concatMap (splitRating test) where
    splitRating Otherwise rating = [Right rating]
    splitRating (LT cat n) rating =
        let (min_, max_) = rating ^. catLens cat in
        if | min_ >= n -> [Left rating]
           | max_ < n -> [Right rating]
           | otherwise -> [ Right $ set (catLens cat) (min_, n-1) rating
                          , Left $ set (catLens cat) (n, max_) rating
                          ]
    splitRating (GT cat n) rating = 
        let (min_, max_) = rating ^. catLens cat in
        if | max_ <= n -> [Left rating]
           | min_ > n -> [Right rating]
           | otherwise -> [ Right $ set (catLens cat) (n+1, max_) rating
                          , Left $ set (catLens cat) (min_, n) rating
                          ]

part2 :: Input -> Int
part2 (Input workflows _) = sum . map size $ go initRanges (workflows Map.! "in")
    where
    initRanges = [Rating (1, 4000) (1, 4000) (1, 4000) (1, 4000)]
    go _ [] = error "part2: cannot happen"
    go ratings (Step test instr : steps) = ratings' where
        (failed, succeeded) = splitRatings test ratings
        succeeded' = case instr of
            Accept -> succeeded
            Reject -> []
            Goto name -> go succeeded (workflows Map.! name)
        ratings' = if null failed then succeeded' else succeeded' ++ go failed steps

    size (Rating (xmin, xmax) (mmin, mmax) (amin, amax) (smin, smax)) =
        (xmax - xmin + 1) * (mmax - mmin + 1) * (amax - amin + 1) * (smax - smin + 1)

solve :: Text -> IO ()
solve = aoc parser part1 part2

    • [^] # Re: Solution en Haskell.

      Posté par  (site web personnel) . Évalué à 3.

      Je ne suis pas sûr de comprendre, et ne lisant pas la Haskell, je me demande si tu peux m'éclairer. Est-ce un genre de dichotomie que tu fais ? Sur quel critère découpes-tu ou non un pavé de valeurs ?

      • [^] # Re: Solution en Haskell.

        Posté par  . Évalué à 1.

        Par exemple si j'ai un pavé x = [1..200], m = [1..100], a = [1..100], s= [1..100] et que j'ai un test x<96, alors je divise mon pavé en
        - un pavé accepté x = [1..95], m = [1..100], a = [1..100], s= [1..100]
        - un pavé refusé x = [96..200], m = [1..100], a = [1..100], s= [1..100].

        • [^] # Re: Solution en Haskell.

          Posté par  (site web personnel) . Évalué à 3.

          Est-ce que tu découpes donc tout l'espace autour de chaque plan correspondant aux valeurs des seuils des critères des workflows ?

          • [^] # Re: Solution en Haskell.

            Posté par  (site web personnel) . Évalué à 3.

            Ah, je crois que je devine la subtilité. En descendant la chaîne des workflows, ou plutôt la chaîne des règles et des workflows, on peut découper sur chaque test, ce qui fait au final beaucoup moins de pavés qu'en quadrillant l'espace entier.

        • [^] # Re: Solution en Haskell.

          Posté par  . Évalué à 1. Dernière modification le 19 décembre 2023 à 13:51.

          Je maintiens une liste de pavés.

          J'ai une fonction go qui prend comme paramètre une liste de pavés et une liste de tests.
          Elle va me renvoyer la liste des pavés qu'il y aura au final.

          La fonction go fonctionne ainsi:
          Je regarde le prochain test à faire.
          Selon le résultat du test, je découpe ma liste de pavés en deux listes: les réussis et les échoués (en ayant éventuellement divisé des pavés).

          Pour les réussis, je regarde l'instruction à faire quand le test est réussi et je stocke le résultat suivant dans une variable réussis2
          - si l'instruction est "accepter": la liste des réussis.
          - si l'instruction est "refuser": la liste vide
          - si l'instruction est d'aller à un workflow x, j'appelle récursivement ma fonction go avec comme paramètre
          -- la liste des réussis
          -- la liste des tests pour le workflow x.

          Pour les refusés, j'appelle récursivement ma fonction go avec comme paramètre
          -- la liste des refusés
          -- la liste des tests privés du premier élément.
          et je stocke ça dans échoués2.

          Le résultat de la fonction go sera reussis2 concaténé à échoués2.

          Ca se fait bien en récursif. Je pense que c'est plus compliqué en itératif.

          • [^] # Re: Solution en Haskell.

            Posté par  (Mastodon) . Évalué à 2. Dernière modification le 19 décembre 2023 à 14:13.

            Mon algo est itératif, mais sur des ensembles de pavés.
            Mais bon, ça ou du récursif, ça revient au même, c'est parcours en profondeur ou en largeur, au final on explore la même chose.

            Je n'ai que 546 pavés au bout du compte, et j'en ai considéré 2700 au total : pavés en cours de route, ou pavés rejetés.

            • Yth.

    • [^] # Re: Solution en Haskell.

      Posté par  . Évalué à 1.

      600 microsecondes ?

      Tu es sur que ce n'est pas des millisecondes ?

  • # On aime les range, youpi, youpi !

    Posté par  (Mastodon) . Évalué à 3.

    Pour la première partie, je fais des jolies eval avec des fonction lambda, pour avoir une résolution simple et élégante.

    from sys import stdin
from dataclasses import dataclass
data = stdin.read().strip().splitlines()

class Workflow:
  def __init__(self, x):
    def dest(r):
      if r == 'A':
        return None  # No more rules, accepted
      if r == 'R':
        return False  # Rejected
      return r  # Next rule
    self.name, rules = line.strip("}").split("{")
    rules = [_.split(":") for _ in rules.split(",")]
    self.default = dest(rules.pop()[-1])
    self.rules = {eval(f"lambda x: x.{t}"): dest(d) for t, d in rules}
    self.infos = [(t[0], t[1], int(t[2:]), dest(d)) for t, d in rules]  # for ex2
  def __call__(self, part):  # Applying this whole workflow to a part
    for rule, dst in self.rules.items():
      if rule(part):
        return dst
    return self.default

@dataclass(frozen=True)
class Parts:
  x: int = 0
  m: int = 0
  a: int = 0
  s: int = 0
  @property
  def val(self):
    return self.x + self.m + self.a + self.s
  def __bool__(self):  # Following workflows until accepted or rejected
    next = 'in'
    while next:  # Neither None nor False
      next = workflows[next](self)
    return next is None  # Acepted

# Data analysis
workflows = {}
parts = False
for line in data:
  if not line:
    parts = []
    continue
  if parts is False:
    w = Workflow(line)
    workflows[w.name] = w
  else:
    parts.append(eval(f"Parts({line[1:-1]})"))

# 1st problem
ex1 = sum(part.val for part in parts if part)

    Pour le second, je suis tombé dans le piège : < et > ne sont pas l'inverse l'un de l'autre, j'ai souffert pour voir ça :(
    Là on considère des range, des intervalles. Comme on code en python, [1, 4000] ça va être range(1, 4001), d'où les 4001 dans le code.
    Pour l'algo, je considère un état : 4 ranges pour x, m, s et a, un workflow et une étape dans le workflow, ce qui donne donc une règle (rule).
    Je prends mes états courants, je leur applique une règle ce qui va diviser chacun de ces états en au mieux deux états : celui qui respecte la règle en cours, et celui qui ne la respecte pas. Chacun progressant, soit vers une nouvelle règle, soit vers l'étape suivante du workflow.
    Je trie les états ayant une règle à appliquer pour mon itération suivante, et je garde de côté les états étant au stade accepté. Les rejetés sont donc abandonnés là.

    Après il reste à bien lire l'énoncé : non, on ne cherche pas la valeur de toutes les pièces qui sont valables, mais juste à les dénombrer, donc il suffit de multiplier entre eux les tailles des 4 intervalles d'un état accepté.

    Comme on découpe toujours en deux morceaux disjoints, nos états ne se chevauchent jamais, donc on peut tous les dénombrer et additionner.

    @dataclass
class PartRange:
  x: tuple = (1, 4001)
  m: tuple = (1, 4001)
  a: tuple = (1, 4001)
  s: tuple = (1, 4001)
  rule: str = 'in'
  step: int = 0

  def split(self):
    rule = workflows[self.rule]
    if self.step == len(rule.infos):
      self.rule, self.step = rule.default, 0
      yield self
      return
    key, test, num, dest = rule.infos[self.step]
    if test == ">":  # ...
      num += 1
    a, b = getattr(self, key)
    if num > a:  # range before num
      new = self.__dict__.copy()
      new[key] = (a, num)
      new["rule"], new["step"] = (dest, 0) if test == "<" else (self.rule, self.step + 1)
      yield PartRange(**new)
    if num <= b:  # range after num
      new = self.__dict__.copy()
      new[key] = (num, b)
      new["rule"], new["step"] = (dest, 0) if test == ">" else (self.rule, self.step + 1)
      yield PartRange(**new)
  @property
  def value(self):
    x = len(range(*self.x))
    m = len(range(*self.m))
    a = len(range(*self.a))
    s = len(range(*self.s))
    return x * m * a * s

parts = [PartRange()]
accepted = []
while parts:
  parts = [part for _ in parts for part in _.split()]
  accepted.extend(_ for _ in parts if _.rule is None)  # Saving accepted
  parts = [_ for _ in parts if _.rule]  # Pruning accepted and rejected

ex2 = sum(_.value for _ in accepted)

    Le temps d'exécution est négligeable, ~90ms.
    J'ai quand même pas été super rapide pour débugger mes âneries.

    Yth.

  • # Encore des problèmes de tests au borne

    Posté par  . Évalué à 1.

    Je fatigue , il est temps que la saison se termine. J'ai encore perdu du temps sur des tests bête aux borne
    Environ ~3h00 au total.

    Encore obligé d'en arriver à écrire T.U. pour débuguer. Demain, je TDD, je vais probablement gagner du temps.

    Pour la partie 1, j'ai utilisé un evaluator JEXL pour les expressions.
    Pour la partie 2, je n'avais pas le choix. J'ai écris le "parseur" (En fait, c'est plutôt un split de l'expression) car il faut plus travailler sur des lots de pieces.

    Mon objet Piece a maintenant une propriété Range que je vais split à chaque expression en 0, 1 ou 2.

    Temps d'éxecution:123ms

    package aoc2023;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;

import org.apache.commons.jexl3.JexlBuilder;
import org.apache.commons.jexl3.JexlContext;
import org.apache.commons.jexl3.JexlEngine;
import org.apache.commons.jexl3.JexlExpression;
import org.apache.commons.jexl3.MapContext;

public class Aoc2023s19v2 {

    public static Random RANDOM = new Random(0L);
    public static JexlEngine jexl = new JexlBuilder().create();

    public static record Range(int start, int end) {

        public long count() {
            return end - start;
        }

        public Range[] split(int to) {          
            if(start >= to || to >= end) {
                return null;
            }
            return new Range[] { new Range(start, to), new Range(to, end) };
        }

        public Range random() {
            int i = start  + RANDOM.nextInt((int)count());
            return new Range(i, i+1);
        }
    }

    public static class Piece {
        public Range x;
        public Range m;
        public Range a;
        public Range s;

        Piece(Range x, Range m, Range a, Range s) {
            this.x = x;
            this.m = m;
            this.a = a;
            this.s = s;
        }

        public long prod() {
            return x.count() * m.count() * a.count() * s.count();
        }

        @Override
        public String toString() {
            return "Piece [x=" + x + ", m=" + m + ", a=" + a + ", s=" + s + "]";
        }

        public Range get(String key) {
            return switch (key) {
            case "x" -> x;
            case "m" -> m;
            case "a" -> a;
            case "s" -> s;
            default -> throw new RuntimeException();
            };
        }

        public Piece substitute(String key, Range r) {
            return switch (key) {
            case "x" -> new Piece(r, m, a, s);
            case "m" -> new Piece(x, r, a, s);
            case "a" -> new Piece(x, m, r, s);
            case "s" -> new Piece(x, m, a, r);
            default -> throw new RuntimeException();
            };
        }
    }

    static class Rule {
        String condition;
        String destination;

        String attributTest;
        boolean attributeGreaterThan;
        int valueTest;

        Rule(String condition, String destination) {
            this.condition = condition;
            this.destination = destination;

            if(! this.condition.equals("true")) {
                attributTest = "" + this.condition.charAt(0);
                attributeGreaterThan = this.condition.charAt(1) == '>';
                valueTest = Integer.parseInt(this.condition.substring(2));
            }

        }

        public boolean match(Piece piece) {
            // Create a JEXL expression object
            JexlExpression jexlExpression = jexl.createExpression(condition);

            // Create a JexlContext and add the 'part' variable to it
            JexlContext context = new MapContext();
            context.set("x", piece.x.start);
            context.set("m", piece.m.start);
            context.set("s", piece.s.start);
            context.set("a", piece.a.start);

            // Evaluate the expression
            boolean result = (boolean) jexlExpression.evaluate(context);

            //System.out.println("Evaluation result: " + result);
            return result;
        }

        public String toString() {
            return condition + "," + destination;
        }

        public boolean process(Piece piece, Workflow workflow, Map<String, Workflow> workflows, List<Piece> accepts) {
            if(condition.equals("true")) {
                System.out.println("Default move to " + destination);
                getDestination(workflows, accepts).add(piece);              
                return true;
            }

            Range range = piece.get(attributTest);  

            System.out.println(this.condition);
            System.out.println(range);

            Range split[] = range.split(attributeGreaterThan ? valueTest +1: valueTest);
            if(split != null) {

                System.out.println("Splited to "  + workflow.name + " & " + destination);
                System.out.println(split[0] + " <-> " + split[1]);
                if(attributeGreaterThan) {
                    getDestination(workflows, accepts).add(piece.substitute(attributTest, split[1]));
                    workflow.pieces.add(piece.substitute(attributTest, split[0]));
                } else {
                    getDestination(workflows, accepts).add(piece.substitute(attributTest, split[0]));
                    workflow.pieces.add(piece.substitute(attributTest, split[1]));                  
                }
                return true;
            } else {
                if(attributeGreaterThan) {
                    if(range.start > valueTest) {               
                        System.out.println("Greater move to ");
                        getDestination(workflows, accepts).add(piece.substitute(attributTest, range));
                        return true;
                    }
                } else {
                    if((range.end-1) < valueTest) {
                        System.out.println("Lower move to ");
                        getDestination(workflows, accepts).add(piece.substitute(attributTest, range));
                        return true;
                    }
                }
            }
            return false;
        }

        private Collection<Piece> getDestination(Map<String, Workflow> workflows, List<Piece> accepts) {        
            if("A".equals(destination)) {
                return accepts;
            }
            if("R".equals(destination)) {
                return new ArrayList();
            }

            return workflows.get(destination).pieces;
        }
    }

    static class Workflow {
        String name;
        List<Rule> rules;
        Stack<Piece> pieces = new Stack();

        Workflow(String name) {
            this.name = name;
            this.rules = new ArrayList<>();
        }

        void addRule(Rule rule) {
            this.rules.add(rule);
        }

        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (Rule rule : this.rules) {
                sb.append(rule.toString());
            }
            return sb.toString();
        }
    }

    static Map<String, Workflow> parseInput(Scanner in) {
        Map<String, Workflow> workflows = new HashMap<>();
        while (in.hasNext()) {
            String line = in.nextLine();
            line = line.trim();
            if (line.isEmpty()) {
                break;
            }

            String name = line.substring(0, line.indexOf('{')).trim();
            Workflow current = new Workflow(name);
            workflows.put(name, current);

            String[] parts = line.substring(line.indexOf('{') + 1, line.length() - 1).split(",");

            for (String part : parts) {
                String[] s = part.split(":");
                if (s.length == 1) {
                    current.addRule(new Rule("true", s[0]));
                } else {
                    current.addRule(new Rule(s[0], s[1]));
                }
            }

        }

        Range range = new Range(1, 4001);
        Piece base = new Piece(range, range, range, range);
        workflows.get("in").pieces.add(base);

        List<Piece> accepts = new ArrayList<>();

        computeAccepts(workflows, accepts);

        BigInteger sum = BigInteger.ZERO;
        for(Piece piece :accepts) {

            // uncomment to checkIndividual(piece, workflows);
            sum = sum.add(BigInteger.valueOf(piece.prod()));
        }
        System.out.println(sum);
        return workflows;
    }

    private static void checkIndividual(Piece rangePiece, Map<String, Workflow> workflows) {            
        for(int i=0;i < 1000;i++) {
            String currentName = "in";

            Piece piece = new Piece(
                    rangePiece.x.random(),
                    rangePiece.m.random(),
                    rangePiece.a.random(),
                    rangePiece.s.random()
                    );              
            //System.out.println("Piece:" + piece);             
            while(! currentName.equals("R") && !currentName.equals("A")) {
                //System.out.println("Current workflow:" + currentName);
                Workflow workflow = workflows.get(currentName);
                for(Rule rule : workflow.rules) {
                    //System.out.println("Match:" + rule.condition);
                    if(rule.match(piece)) {
                        currentName = rule.destination;                     
                        //System.out.println("=>:" + rule.destination);
                        break;
                    }
                }
            }

            if(! currentName.equals("A")) {
                System.err.println(rangePiece);
                throw new RuntimeException(piece.toString());
            }

        }

    }

    private static void computeAccepts(Map<String, Workflow> workflows, List<Piece> accepts) {
        while (workflows.values().stream().filter(w -> !w.pieces.isEmpty()).count() > 0) {
            Workflow workflow = workflows.values().stream().filter(w -> !w.pieces.isEmpty()).findFirst().orElse(null);
            System.out.println("Workflow:" + workflow.name);

            Piece piece = workflow.pieces.pop();
            for (Rule rule : workflow.rules) {
                if (rule.process(piece, workflow, workflows, accepts)) {
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        long  s = System.currentTimeMillis();
        try (Scanner in = new Scanner(Aoc2023s18v2.class.getResourceAsStream("res/t19.txt"))) {
            parseInput(in);
        }
        System.out.println("Durée:" + (System.currentTimeMillis() - s) + "ms");
    }
}

Suivre le flux des commentaires

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