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 12/12/2023 17:45 | #
Tu coinces sur quoi ?
Citer : Posté le 12/12/2023 17:54 | #
Je ne comprend pas comment trouver les 128 combinaisons possibles pour les priorités (2^7 je pense non ?) avec un algo sans en oublier une. J'ai pensé à 7 boucles for imbriqué, mais ça me parait "grossier"
Citer : Posté le 12/12/2023 18:13 | #
Tu décomposes les chiffres 0 à 127 en binaire (0000000 à 1111111) et ensuite chaque jonction correspond à 1 bit particulier que tu récupères avec une opération AND.
Citer : Posté le 12/12/2023 20:53 | #
Je ne comprend pas comment trouver les 128 combinaisons possibles pour les priorités (2^7 je pense non ?) avec un algo sans en oublier une. J'ai pensé à 7 boucles for imbriqué, mais ça me parait "grossier"
En gros c'est ça ! Si tu veux éviter les boucles imbriquées, tu peux aussi écrire une fonction récursive.
if n >= 7:
print(bits)
else:
bits[n] = 0
print_all_configs(bits, n+1)
bits[n] = 1
print_all_configs(bits, n+1)
bits = [0, 0, 0, 0, 0, 0, 0]
print_all_configs(bits, 0)
La fonction prend en paramètre la liste de bits à modifier et le numéro du bit en cours d'énumération. Tu peux voir que je mets bits[n] à 0 puis à 1 et à chaque fois j'énumère ensuite toutes les options à partir du bit n+1.
Cette approche marche pour énumérer tout un tas de choses même si ici les 7 boucles sont très bien, et la solution avec le découpage binaire est encore plus expéditive.
Citer : Posté le 12/12/2023 22:02 | #
Ok merci beaucoup pour vos réponses
Citer : Posté le 12/12/2023 22:41 | #
Je suis un peu inquiet sur le backlog, j'ai pas envie de rendre le puzzle infinissable pour tous les gens qui ne sont pas là tout le mois de Décembre, donc pour aujourd'hui voici une continuation directe du problème précédent.
Investissement intelligent #2
Déterminer les revenus du mois avec la sélection optimale de modules (vous serez peut-être surpris·es d'apprendre que ce n'est pas nécessaire pour résoudre le problème d'hier !).
La solution de ce problème-ci est les 6 premiers chiffres significatifs du ratio entre le revenu du mois avec les modules et sans, arrondi.
Pièces du puzzle
Citer : Posté le 13/12/2023 07:35 | #
Paradoxalement ce problème qui est simple me résiste, ça décode pas chez moi
On est bien d'accord que les 40€ d'énergie c'est par four et par heure et le bénéfice de production de 50€/h c'est aussi par four.
Ensuite l'attendu c'est bénéfice mois optimisé divisé par bénéfice mois normal, donc un ratio >= 1 .
Si par exemple on obtient 1.65485723 on arrondi la décimale numéro 5 pour avoir 6 chiffres au total (donc ici 165486).
C'est bien cela ?
Edit, c'est bon, c'était un problème d'arrondi
Citer : Posté le 13/12/2023 09:06 | #
Oh la la je commence à prendre beaucoup de retard à cause du 6/12
Va falloir que je le résolve rapidement.
Citer : Posté le 13/12/2023 09:53 | #
Oh il faut faire l'arrondi ? C'est peut-être pour ça que ma résolution ne marche pas...
Caltos : G90+E, FX-92+ (x2)
Citer : Posté le 13/12/2023 21:17 | #
Salut, je pensais avoir résolu le problème du 6/12 mais apparament mon résultat n'est pas bon
Citer : Posté le 13/12/2023 21:35 | #
Envoie-moi un MP :3
Citer : Posté le 13/12/2023 21:42 | #
Ok c'est fait, merci
Citer : Posté le 14/12/2023 00:51 | #
On est bien d'accord que les 40€ d'énergie c'est par four et par heure et le bénéfice de production de 50€/h c'est aussi par four.
Surtout que vu qu'on calcule un rapport ça change rien en fait
Citer : Posté le 14/12/2023 06:32 | #
Si justement ça change si c’est cumulé pour les deux fours car le prix des modules lui est par four.
Donc le ratio OPEX / CAPEX sera différent et le ratio recherché aussi.
Citer : Posté le 16/12/2023 00:07 | #
Aïe aïe, j'ai oublié le problème d'hier et SlyVTT m'est tout de suite tombé dessus ! Désolé pour le raté. Pour me faire pardonner je vous ai préparé mon problème favori pour l'instant.
Travail manuel #1 et #2
À la suite d'un orage, les bras mécaniques utilisés pour sortir les plaques d'acier des fours et les placer sur les tapis roulants sont temporairement inopérants. Dans l'immédiat, il faut donc manuellement déplacer les plaques d'acier des fours vers le stockage. La configuration des lieux est visible ci-dessous ; les plaques d'acier sont stockées dans les coffres dont la capacité est très opportunément infinie parce qu'on ne pose pas de questions merci beaucoup.
Les deux fours fonctionnent en continu. Chaque four produit une plaque d'acier toutes les 10 minutes. Lorsqu'une plaque est produite elle peut rester en attente à la sortie du four pendant que le four produit une autre plaque. Le four peut donc travailler en autonomie pendant un maximum de 20 minutes avant qu'une intervention humaine ne soit nécessaire pour débarrasser les plaques. Si le four termine sa deuxième plaque sans que la première ait été retirée par l'opérateur, il s'arrête jusqu'à ce qu'une plaque ait été débarrassée. Le tapis roulant qui fournit les matériaux aux fours marche toujours donc la production est automatique.
La position des deux fours, deux coffres, et les caractéristiques des fours sont résumées ci-dessous. Les éléments de la liste STATIONS sont un four, un coffre, un four et un coffre respectivement.
SMELT_TIME = 10
FURNACE_CAPACITY = 2
L'opérateur navigue entre les différentes stations (fours ou coffres) et peut porter au maximum une plaque. Le temps de trajet entre deux stations est la distance euclidienne arrondie à l'entier supérieur ; par exemple entre le four de gauche et le coffre du gauche la distance euclidienne est √(3²+1²) = 3.16 donc le temps de trajet est de 4 minutes. L'opérateur navigue en continu entre les différentes stations. Chaque fois qu'il arrive à un four dans lequel une plaque est prête, s'il ne porte rien il prend la plaque. Chaque fois qu'il arrive à un coffre, s'il porte une plaque il la dépose. L'opérateur ne s'arrête jamais donc même s'il arrive les mains vides à un four 1 minute avant la production d'une nouvelle plaque, il n'attend pas et repart vers la prochaine station toujours les mains vides.
Plus précisément, le fonctionnement complet du système est le suivant. À chaque étape :
Initialement, l'opérateur est à la station #1 (le coffre de gauche) avec les mains vides et les fours sont sur le point de commencer leur première plaque.
On imagine que l'opérateur va suivre un circuit prédéfini en boucle et on se demande s'il y a des circuits plus optimaux que d'autre dans le sens ou l'opérateur parviendra à récupérer les plaques aux bons moments pour éviter aux fours de s'arrêter.
Problème #1 (facile) : on se donne d'abord le circuit [0, 1, 2, 3] dans lequel l'opérateur pass exactement une fois par chaque station dans son circuit. Déterminer combien de plaques auront été déposées dans les coffres au bout de 1000 minutes.
Problème #2 (difficile) : on s'intéresse à tous les circuits de longueur 8 ou moins. Déterminer quel circuit maximise le nombre de plaques déposées dans les coffres après 1000 minutes. En cas d'égalité, on prendra le premier circuit dans l'ordre lexicographique (l'ordre alphabétique avec des chiffres). La solution du problème est le nombre de plaques suivi des chiffres du circuit. Par exemple, si le circuit optimal est [0, 1, 2, 3, 0, 1, 2, 3] et il produit 105 plaques, la réponse sera 10501230123.
Pièces du puzzle
Problème #1 :
Problème #2 :
Citer : Posté le 16/12/2023 06:20 | #
Je suis un tirant
Citer : Posté le 17/12/2023 12:12 | #
Coucou, je voulais faire le point de nouveau. J'ai toujours un peu peur de perdre du monde avec le rythme. Est-ce que je continue pareil ou on souffle pour un moment ? La difficulté est le plus tendu à ajuster donc tout retour d'expérience m'aiderait beaucoup.
Sauf toi Sly
Citer : Posté le 17/12/2023 12:17 | #
J'ai pas pu vraiment avancer, ma résolution du 2nd est pas encore finie (
Caltos : G90+E, FX-92+ (x2)
Citer : Posté le 17/12/2023 12:18 | #
Quoi !!!
Honnêtement le 6/12 et la phase 2 d'hier c'est un peu chaud.
Je sais pas si les habitué(e)s sont là cette année (Afyu, Hackcell, ...) et peuvent commenter la difficulté, mais oui les épreuves difficiles portent bien leur nom.
Citer : Posté le 17/12/2023 13:14 | #
Ya le 6/12 où j'ai skip et bruteforce le truc.
Ensuite, le premier probléme sur les modules j'ai l'impression qu'il y a une autre option qu'essayé toutes les combinaisons de modules… Mais je ne l'ai pas trouvé.
Finalement je bloque aussi un peu sur le probléme manuel #2 car je cherche un moyen efficace de le bruteforce parce que ça à l'air vachement plus interessant que de le resoudre normalement
Citer : Posté le 17/12/2023 13:20 | #
Salut, moi je suis toujours bloqué sur le 6/12 et j'ai pas envie de continuer tant que je l'ai pas fini, donc je commence à prendre du retard. Mais j'avance et je pense que j'aurais fini le 6/12 ce weekend normalement.
Sinon, c'est vraiment incroyable Lephe'