Le Puzzle de l'Avent 2023
Posté le 01/12/2023 23:05
Bienvenue, cette année encore, dans le Puzzle de l'Avent de Planète Casio. 
Le Puzzle est presque une tradition maintenant, je n'en fais pas toutes les années (
2018,
2019,
2021) mais c'est un des événements que j'apprécie le plus. J'espère que c'est le cas pour vous aussi parce qu'il y a de quoi bien s'amuser !
Aux dernières éditions, on a exploré quelques problèmes d'informatique théorique — avec des graphes, des ensembles, de l'optimisation... cette année on va faire un peu différent : on va prendre un approche un peu plus pratique avec des problèmes que vous pouvez résoudre en
programmant. Parfois vous pourrez calculer la solution de tête, d'autres fois vous pourrez écrire un petit programme Python qui fera le calcul pour vous. On n'aura pas de problème très difficile cette année donc vous devriez vous en sortir même avec des programmes naïfs ou peu optimisés. Seul le tout dernier problème sera un peu dur, pour éviter que ce soit la course au premier connecté le 25 pour finir le puzzle. :3
Le but du jeu est de reconstituer un Puzzle dont les pièces seront données chaque jour. Le puzzle en lui-même est une image en pixel art de 198×112 pixels, juste ce qu'il faut pour tenir à l'écran d'une Graph 90+E. Comme dans la formule précédente, les pièces seront données chaque jour «brouillées» et pourront être débrouillées en calculant (ou faisant calculer à un programme) la solution d'un petit problème mathématico-informatique.
Conformément à la tradition, il y a un prix à gagner pour la première personne à reconstituer le puzzle : une
calculatrice Graph 90+E. Pour ceux d'entre vous qui n'ont pas le plaisir d'en posséder une, je ne peux que la recommander ; pour preuve depuis que j'ai commencé à jouer avec je suis pas revenu aux mono. :P
Ce lot provient de notre partenariat avec
CASIO Éducation.
Plus d'informations sur la Graph 90+E dans sa fiche « Tout sur ta CASIO ! ».
L'autre lot bien sûr c'est que toutes les personnes qui finissent le puzzle se voient attribuer le titre de
Maître du Puzzle.
Comme j'ai encore quelques détails à ajuster, le premier problème sera donné demain avec le premier ensemble de pièces. Préchauffez vos éditeurs d'images et de code Python !
---
Notes du futur :
Le puzzle a été résolu par :
Citer : Posté le 06/12/2023 09:27 | #
Je me trompe peut-être, mais je n'arrivais pas à trouver la réponse donc j'ai bruteforce la solution et je trouvé un resultat plus grands qui si je recouvrais toute la zone de 8×8 avec des panneaux, on est bien sur 6 panneau qui produisent 2kwh de 9h-18h comme dans la question 2?
Citer : Posté le 06/12/2023 11:22 | #
Pareil j’ai brute force aussi et j’arrive pas à comprendre la logique qui amène au résultat.
Citer : Posté le 06/12/2023 11:35 | #
Le nombre maximum de panneaux qu'on peut caser serait 8×8 / 2 = 32 panneaux. Ils produiraient ainsi (32/6)×2 = 10.67 kW d'énergie le jour. Si tu réinjectes ce nombre dans le calcul du 2 Décembre, tu obtiens une énergie totale de 135 kWh, ce qui est plus que la solution.
Une fois que tu inclus la contrainte des batteries, tu obtiens un nombre de panneaux plus faible qui doit te mener à la bonne réponse. La seule subtilité c'est qu'il faut trouver un arrangement optimal en nombre de batteries également.
Citer : Posté le 06/12/2023 11:57 | #
Pour la transparence : j'ai rajouté une miniature à la news (qui va aussi apparaître sur l'article bientôt), oui c'est une section du puzzle (que vous pouvez utiliser pour la reconstitution) mais attention ce n'est pas les pixels exacts parce que j'ai pas affiché tous les calques quand j'ai extrait cette capture.
PJA Invité
Citer : Posté le 06/12/2023 15:28 | #
Bonjour,
Je confirme ça marche sans passer par la brute force. Il suffit de prendre le nombre de KW trouvé aujourd'hui (sur les 8 m2) et de refaire le premier problème en remplaçant les 2 KW par cette valeur. J'ai un peu galéré aussi pour trouver la bonne méthode...
Citer : Posté le 06/12/2023 16:16 | #
avec slyvtt on avait compris qu'il fallait prendre juste les valeur de productivité des panneau solaire du jour 2, pas qu'il fallait refaire le jour 2 avec plus de panneau, c'est pour ça qu'on trouvais pas
Citer : Posté le 06/12/2023 16:35 | #
ah oui forcément, moi j'ai considéré que le jour 5 était complètement indépendant du reste
Citer : Posté le 06/12/2023 16:53 | #
Merci pour le retour et désolé pour la confusion. J'ai modifié l'énoncé du problème pour clarifier un peu.
Le problème d'aujourd'hui sera du Python.
Citer : Posté le 06/12/2023 18:20 | #
Je confirme que cette fois 'est bon, avec l'explication en plus on trouve bien la solution attendue. C'est pas grave, il arrive souvent qu'une explication donnée trouve une interprétation différente par d'autres.
Cela montre aussi que l'on peut dans certain cas se débrouiller en passant par les chemins de traverse.
Citer : Posté le 07/12/2023 00:47 | #
Le problème d'aujourd'hui (pour une définition généreuse de "aujourd'hui") est finalement plus subtil que je ne l'imaginais. Vous avez 2 jours pour celui-là, mais je pense que ce sera aussi l'un des plus difficiles (en tous cas c'est le niveau que je vise). J'espère qu'il vous plaira.
Embouteillages mécaniques
Le transport des matériaux et produits finis dans l'usine est très désorganisé. En ignorant toutes les machines (fours, moules, etc) le réseau de tapis roulants ressemble à la figure ci-dessous, avec 8 entrées sur les côtés gauche, haut et droit, et 1 sortie en bas.
Le fonctionnement des tapis peut être résumé de la façon suivante. Chaque section (case) de tapis peut contenir soit 0 soit 1 objet. À chaque minute, (1) tous les objets avancent dans la direction du tapis, puis (2) des objets apparaissent à certaines entrées. Les apparitions sont régulières : chaque entrée a une fréquence associée (qui correspond à la vitesse de la machine qui dépose les objets sur le tapis), par exemple "un objet tous les 5 minutes".
Par exemple, l'entrée tout en haut à gauche (x=0, y=1) produit un objet toutes les 5 minutes (triplet (0,1,5) dans ENTREES ci-après). À la fin des minutes numéro t=0, t=5, t=10, etc. un objet est donc déposé sur le tapis à la position x=0, y=1.
Le problème qu'on a c'est qu'il y a plusieurs points de jonction où deux tapis se rejoignent (il y a 7 points de jonction pour être précis). Il est impossible de poser deux objets en même temps sur la même section de tapis (contrairement aux tapis dans Factorio !) et donc si les deux entrées d'une jonction ont un objet, une seule peut avancer. On peut choisir laquelle en donnant une priorité a la jonction, par exemple la première jonction tout en haut à gauche peut avoir comme priorité soit "en cas de conflit l'objet provenant du tapis du haut avance" soit "en cas de conflit l'objet provenant du tapis du bas avance".
Dans ces situations, un des objets à l'entrée de la jonction ne peut donc pas avancer, ce qui peut se propager et créer des embouteillages. Le retard ne nous inquiète pas, mais si jamais l'embouteillage s'allonge jusqu'à une des entrées du réseau, alors on a un problème : certains objets qui devaient apparaître régulièrement pourraient être perdus faute de place.
Prenons par exemple l'entrée tout en haut à gauche, de nouveau. Si au début de la minute t=5 il y a un objet en (0,1) et qu'il ne peut pas avancer à cause d'un embouteillage, alors l'apparition prévue d'un nouvel objet en (0,1) à la fin de la minute 5 ne pourra pas se faire, et donc on perd un objet.
L'existence d'embouteillages et donc la perte d'objets dépend fortement de la façon dont les priorités sont assignées. Si les priorités sont bien choisies, le traffic sera fluide, réduisant les pertes. Comme il y a 7 jonctions et qu'il y a deux options pour chaque, ça nous fait 2⁷ = 128 configurations possibles des priorités.
En supposant que les arrivées commencent à la minute 0 et continuent jusqu'à la minute 50 incluse, déterminer combien d'objets seront perdus dans chacune des 128 configurations. La réponse à ce problème est la moyenne des 128 cas, sans la virgule ; par exemple, si le réseau perd en moyenne 1.328125 sur l'ensemble des 128 configurations, la réponse sera 1328125. Le code Python suivant est fourni pour traduire la description du problème dans une forme un peu plus formelle.
" v ",
">>>v v ",
" >>>v v<<<",
">>>^ v v ",
" v v v<",
">>v v<< v ",
" >>v<< v< ",
" ^ v v ",
">>^ >>v<<<v<",
" v v ",
" >>>v< ",
" v ",
]
ENTREES = [
# Liste de triplets (x, y, delai)
# Un objet apparaît à (x, y) à la fin de chaque instant t pour lequel
# t <= DERNIERES_ARRIVEES et t % delai == 0, sauf s'il y a déjà quelque chose
# sur le tapis en (x, y), auquel cas l'objet est perdu (cela ne peut se
# produire que si le tapis est bloqué)
(0, 1, 5),
(0, 3, 7),
(0, 5, 3),
(0, 8, 11),
(5, 0, 6),
(11, 2, 4),
(11, 4, 9),
(11, 8, 8),
]
# Position de la sortie du réseau
SORTIE = (9, 11)
# Avec t variant de 0 à 50, au total 76 objets doivent apparaître
DERNIERES_ARRIVEES = 50
Pièces du puzzle
N'hésitez pas à demander des clarifications. Pour ce problème il est important que vous simuliez les choses bien dans l'ordre qui est indiqué, sinon vous aurez pas le bon résultat même si vous avez le bon raisonnement, ce qui ne sera pas drôle... comme j'écris ça à minuit 30 j'imagine que ce sera certainement améliorable.
Citer : Posté le 07/12/2023 07:29 | #
Faut bien réfléchir à comment updater la grille avec les objets sous peine de créer de "faux embouteillages".
Les trucs simples du genre Gauche->Droite et Haut->Bas sont pas a priori les plus malins (je dis ça je dis rien
Citer : Posté le 07/12/2023 09:21 | #
Exactement ! Il est important de faire avancer les objets "en aval" avant de faire ceux "en amont". Et il se peut qu'avec un bon cadre pour déterminer l'ordre de mise à jour il soit également possible d'implémenter les priorités sans trop de problème.
Citer : Posté le 07/12/2023 09:43 | #
On peut même aller jusqu’à penser qu’une grille est pas la meilleure structure pour résoudre le problème 🤣🤣
Là encore je dis rien 🤓
Citer : Posté le 07/12/2023 10:12 | #
Je suis bloqué sur l'avant dernier problème
Je pense que je n'ai pas la solution pour les batteries et les panneaux mais je ne vois pas de solution plus optimisé.
Citer : Posté le 07/12/2023 10:14 | #
Je suis bloqué sur l'avant dernier problème
Je pense que je n'ai pas la solution pour les batteries et les panneaux mais je ne vois pas de solution plus optimisé.
Un indice : tu n'es pas obligé de remplir toutes les cases de la zone 8x8 ... il se peut que l'optimum ne soit pas avec toutes les cases remplies.
Citer : Posté le 07/12/2023 12:55 | #
Ben oui j'ai trouvé quelque chose ou toutes les cases ne sont pas remplies... En plus je suis sûr d'avoir la bonne méthode de calcul pour après puisque j'ai trouvé la même chose que Lephe' pour 32 panneaux
Citer : Posté le 07/12/2023 13:32 | #
Envoie-moi un MP je te dirai
Citer : Posté le 07/12/2023 14:09 | #
Ok merci, c'est fait
Citer : Posté le 07/12/2023 20:05 | #
Merci Lephe' j'ai réussi le problème
J'ai une question par rapport au dernier problème. Comment est-ce qu'on accède au valeur des triplets ?
Citer : Posté le 07/12/2023 20:24 | #
C'est des tuples classiques donc tu peux les indexer avec [] :
ENTREES[0][1] # 1
ENTREES[0][2] # 5
Mais si tu boucles tu peux plus élégamment écrire :
pass
Citer : Posté le 08/12/2023 23:35 | #
Ordonnancement #1
L'usine a reçu pour les quelques jours à venir un nombre relativement élevé de commandes, plutôt variées : visserie, plaques, produits finis... et il faut maintenant choisir dans quel ordre on veut les exécuter (ie. les ordonnancer) sur les deux machines disponibles.
On suppose une situation simple dans laquelle chaque commande prend un temps fixe à produire peu importe la machine utilisée, il n'y a pas d'ordre imposé, et on peut enchaîner les tâches instantanément. L'idéal c'est donc de répartir les tâches entre les deux machines pour que les deux machines aient exactement la même quantité de travail et terminent en même temps.
Les 8 commandes ont les durées d'exécution en heures suivantes : 1, 2, 5, 1, 2, 3, 7, 3.
Déterminer de combien de façons on peut couper cet ensemble en deux part égales pour l'assigner aux machines. (On pensera à éviter les doublons. Les différentes tâches de même durée sont considérées différentes.)
Pièces du puzzle