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 🚲 Tanguy Ortolo (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 🚲 Tanguy Ortolo (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 Yth (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}
:Ç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.# Solution en Haskell.
Posté par Guillaume.B . É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.
[^] # Re: Solution en Haskell.
Posté par 🚲 Tanguy Ortolo (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 Guillaume.B . É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 testx<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 🚲 Tanguy Ortolo (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 🚲 Tanguy Ortolo (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 Guillaume.B . É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
serareussis2
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 Yth (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.
[^] # Re: Solution en Haskell.
Posté par syj . Évalué à 1.
600 microsecondes ?
Tu es sur que ce n'est pas des millisecondes ?
# On aime les range, youpi, youpi !
Posté par Yth (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.
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 êtrerange(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.
Le temps d'exécution est négligeable, ~90ms.
J'ai quand même pas été super rapide pour débugger mes âneries.
Yth.
[^] # Re: On aime les range, youpi, youpi !
Posté par steph1978 . Évalué à 2.
J'avais fait la partie 1.
Mais ton code est tellement clean, j'ai repris tel quel :)
# Encore des problèmes de tests au borne
Posté par syj . É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
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.