Le Puzzle de l'Avent 2021
Posté le 01/12/2021 21:09
Salut à tous et bienvenue dans ce nouveau Puzzle de l'Avent ! 
Puzzle fini et résultats : article de Noël. 
Tileset et maps sont disponibles librement s'il y a des intéressés.
La première édition de ce puzzle était une
collection de petites énigmes, tandis que la seconde était faite de
petites curiosités mathématiques et informatiques. Cette année, je vous propose de refaire un tour sur des problèmes classiques d'informatique dans un contexte un peu vidéoludique !
J'ai eu un peu de mal à ajuster la difficulté la dernière fois, promis cette année les problèmes sont tous accessibles. Il y a même deux catégories : pour chaque petit problème je présenterai une version «facile» qui peut être résolue de tête ou avec un papier/crayon, et une version «difficile» qui nécessite un peu plus de réflexion, parfois du code. Il y aura des explications sur la nature des problèmes dans tous les cas, le but étant aussi de vous faire découvrir tout ce qu'on peut faire avec de l'informatique théorique.
Le but du jeu est de reconstituer le Puzzle dont les pièces seront données chaque jour. C'est un véritable puzzle séparé en deux parties. Chaque jour je vous donnerai une partie des pièces «brouillées» accompagnées d'un petit problème d'informatique. La solution du problème vous permettra de débrouiller les pièces et ainsi d'avancer le puzzle. À Noël, le puzzle sera complet !
Le puzzle est un pixel art de 198×112 pixels que j'ai fait pour l'occasion, et est séparé verticalement en deux comme ceci :
Il y a deux prix pour cet événement !
- Pour la reconstitution de la partie facile, une Graph 90+E est à remporter ;
- Pour la reconstitution de la partie difficile, une batterie portable CASIO est à remporter.
Ces lots sont généreusement offerts par
CASIO Éducation.
______
Pour plus d'informations sur la Graph 90+E (une machine magnifique !), regarde sa fiche « Tout sur ta CASIO ! ».
La batterie se charge par USB et fournit l'énergie par micro-USB ; capacité 2200 mAh.
Ah oui, et pendant que j'y pense tous les gens qui finissent (une moitié du) puzzle ont droit au titre de
Maître du Puzzle !
Voilà qui conclut l'exposé des règles pour cette année. On commence dès demain. Il y aura du puzzle, de l'informatique, du storytelling, et même un poil de pixel art et de jeu vidéo. Ne le manquez pas !
Liste des puzzles
Pour décoder les pièces, utilisez le script
decode_pieces.py. Enregistrez les images
Avent2021_Dec*r.png dans un dossier à côté de
decode_pieces.py, puis modifiez le script pour indiquer les solutions dans les tableaux
SOLUTION_EASY et
SOLUTIONS_HARD. Ensuite, lancez le script, et vous aurez les images décodées dans le même dossier.
Fichier joint
Citer : Posté le 11/12/2021 13:48 | #
Dans cet événement le but est de reconstituer un puzzle, dont je donne quelques pièces tous les jours (tu peux en voir juste au-dessus de ton message).
Les pièces que je donne sont brouillées, et pour les «dé-brouiller» il faut résoudre des petits problèmes d'informatique. Pour chaque problème la solution est un nombre ; quand tu as la solution tu peux la saisir dans un programme Python (qui est donné dans le post principal) et obtenir les pièces «dé-brouillées».
ll y a deux types de problèmes : des faciles et des difficiles, qui alternent tous les jours. Les pièces des problèmes faciles forment la moitié gauche du puzzle, tandis que les pièces des problèmes difficiles forment la moitié droite. Il y a un prix à gagner pour la première personne qui reconstituera la moitié gauche du puzzle et un autre pour la première qui reconstituera la moitié droite.
C'est plus clair comme ça ?
Citer : Posté le 11/12/2021 15:44 | #
Explication du problème du 6 Décembre
Le problème d'hier est un programme linéaire, un type de problème abstrait où on a plusieurs variables et on doit maximiser une «fonction linéaire» sous des «contraintes linéaires». En gros, le problème c'est ça :
Maximiser 2×soldats + 1×delta + 8×alice + 25×scarlet + 13×ninja (la surface défendue).
Avec comme contraintes sur le nombre de personnes :
0 ≤ soldats
0 ≤ delta ≤ 1
0 ≤ alice ≤ 1
0 ≤ scarlet ≤ 1
0 ≤ ninja ≤ 1
Comme contrainte sur le nombre de rations par semaine :
4×soldats + 1×delta + 6×alice + 6×scarlet + 6×ninja ≤ 50
Et sur le nombre de véhicules disponibles :
delta + alice + scarlet + ninja ≤ 2
En plus de ça on demande ici que les valeurs soient des entiers (on va pas découper les soldats !), ce qui en fait un problème de programmation linéaire entière. Pour des raisons que je détaille pas trop c'est plus difficile que si les variables sont des nombres réels (intuition : les nombres réels on peut toujours les ajuster très finement pour améliorer le score, mais les nombres entiers on ne peut pas, on est obligés de sauter de 1 en 1).
Logistique de guerre
Aujourd'hui on passe donc à l'échelle supérieure. Les «principautés» se réveillent en constatant que le danger existe et que vous, le gouvernement, ne les avez pas abandonnées. Elles vous fournissent des provisions, des soldats, et des cavaliers. Vous décidez donc de déployer des troupes sur l'ensemble du pays, mais comme les routes sont quasi-inexistantes les véhicules sont abandonnées au profit de chevaux. La situation est donc la suivante :
Et voici ce que fait chaque type d'unité :
Même question qu'hier : quelle est la surface maximale qu'on peut défendre ?
Notez que vous n'êtes pas obligés d'utiliser une méthode de résolution de programme linéaire entier pour ça (c'est beaucoup trop dur !), vous pouvez juste coder les règles et bruteforcer.
Pièces du puzzle
Pour cette très intéressante énigme, j'ai utilisé le Solveur de problèmes linéaires de LibreOffice et je me suis inspiré d'un exemple créé et résolu par un de mes collègues (une histoire de livraison de troupes pour Sauron) et j'ai trouvé la réponse directement. Je vous expliquerai tout ça
Citer : Posté le 11/12/2021 15:46 | #
Ah pas mal ! Je ne savais pas qu'il y avait un tel solveur dans LibreOffice. xD J'ai utilisé lp_solve de mon côté, ce qui passe bien aussi. Les explications sont bienvenues !
... wait, maintenant que j'y pense, j'ai jamais fait l'article récapitulatif pour Synchro-Donjon. Flûte ! o_o
Citer : Posté le 12/12/2021 21:52 | #
Je doute que ça vous ait échappé mais hier je n'ai pas pu poster de puzzle - je me suis retrouvé à court de temps pour préparer (désolé). Je crois aussi que le rythme est assez brutal pour la résolution, donc je peut-être que ça ne ferait pas de mal de ralentir un peu. ^^"
Je vais de plus essayer de donner les dernières pièces le 24 Décembre (de préférence tôt) plutôt que le 25, parce que vous serez occupés à ce moment-là.
Explication du problème du 10 Décembre
Le problème précédent s'appelle un problème d'arbre couvrant ; ici, «couvrant» signifie que toutes les villes sont reliées et «arbre» implique qu'il n'y a pas de routes inutiles (ie. il n'y a qu'un seul chemin entre toute paire de villes).
Les arbres couvrants de poids minimaux sont très, très faciles à trouver même quand les réseaux sont immenses. La méthode la plus classique est l'algorithme de Kruskal, et ça se passe comme ça : on prend toujours la route avec la durée la plus faible. Si cette route relie deux villes qui ne sont pas encore reliées par un autre chemin on la prend, sinon la jette. Et on continue jusqu'à ce que tout le monde soit relié. Plus simple il n'y a pas !
Les algorithmiciens qui ont pu réviser leur cours avec ça pourront s'amuser à refaire la preuve. :P
Guide touristique
Le pays est en phase de s'unifier, et avec les projets de routes relancés la communication entre les villes reprend son cours. Une opération se met en place pour acheminer des vivres, chevaux, véhicules et hommes des cités reculées à l'Ouest vers le front. Dans le même temps, le commerce redémarre doucement, puisqu'en temps de guerre l'économie n'attend pas et il y a des opportunités à prendre...
Un marchant en particulier chercher comment il peut faire la tournée de tous les points d'intérêt du pays de façon efficace. Je vous redonne la carte, qui n'a pas changé depuis la dernière fois :
Trouvez, en partant d'une ville quelconque, en combien de temps on peut passer une fois par toutes les villes et revenir à son point de départ.
Pièces du puzzle
Pour m'assurer que tout tombe juste le 24, je vous donne deux images aujourd'hui. Pour les décoder, mettez deux fois de suite la solution dans SOLUTIONS_HARD dans le script. (En cas de doute regardez le noms des images pour clarifier.)
Citer : Posté le 13/12/2021 15:09 | #
C'est un peu stupide de ma part, mais le mélange des pièces n'était pas correctement déterminisé dans les scripts. Du coup, il y avait dans les pièces que j'ai données jusqu'ici des doublons (en gros le script remélangeait les pièces tous les jours avant de faire les paquets x_x).
J'ai corrigé ce problème et régénéré les images de pièce qui sont données dans chaque problème. Je vous invite à re-télécharger les images ; les solutions n'ont pas changé, donc vous avez juste à remplacer les fichiers Avent2021_Dec**r.png et à relancer le script decode_pieces.py.
Je vous conseille de reprendre la constitution du puzzle sur un autre fichier/calque, parce que si vous mélangez toutes les pièces vous en aurez plus que le nombre total en arrivant à la fin du mois et c'est pas pratique. Cela ne vous empêche pas de garder votre solution partielle pour positionner les nouvelles pièces.
Je suis vraiment désolé pour la confusion. L'image finale en vaut la peine cependant, la qualité a vraiment monté par rapport aux dernières fois.
Citer : Posté le 14/12/2021 21:43 | #
Connais ton ennemi...
La défense du pays étant maintenant assurée, l'heure est à la contre-attaque. Et la première étape, comme chacun sait, est dans la collecte d'informations et l'évaluation des menaces posées par l'ennemi. Ici, vous savez des précédentes escarmouches que l'opposant a 3 types de soldats : les soldats à pied, les cavaliers, et le support logistique.
Des registres ont été perdus dans le repli lors de la première bataille, et ils vous apprennent que dans les rangs des antagonistes, l'avant-garde devait être suivi d'un assaut sur la ville la plus proche de la frontière. Les documents font les comptes des ressources nécessaires pour mener la bataille. Aucune date n'est indiquée, mais il va sans dire qu'il faut prévenir toute agression sérieuse.
D'après les documents, chaque personne consomme une ration de nourriture par jour, et les livraisons comptabilisées sont pour les 7 premiers jours d'un siège. Du foin est fourni ; chaque mini-botte sert soit de lit pour un homme (réutilisable) ou à nourrir un cheval (pour un jour). Enfin, il y a une radio par ingénieur logistique et une par bataillon (16 personnes, soldats classiques et cavaliers confondus, sans compter les ingénieurs).
Au total, 952 rations de nourriture, 248 mini-bottes de foin et 16 radios doivent être acheminées.
La question est combien d'hommes devrez-vous affronter durant la bataille ?
Pièces du puzzle
Il y a moins de pièces sur certaines images pour équilibrer (le total ne divisant pas la répartition initiale).
Indice sur le problème du 12 Décembre
Ce problème s'appelle le problème du voyageur de commerce, c'est un grand classique de problème difficile (NP-complet) et aussi un sujet récurrent du concours de rentrée, dans différentes variations.
Vu la taille de l'instance (12 points), il n'est pas raisonnable d'énumérer les permutations, mais il y a quand même des algorithmes exacts qui donnent la solution immédiatement. Sinon on peut chercher à la main, surtout que pas mal d'étapes sont obligatoires : il suffit de voir par quels voies on peut rentrer et sortir de chaque ville.
Citer : Posté le 16/12/2021 22:57 | #
Explication du problème du 14 Décembre
Ici on a une question de gestion de ressources. Vous remarquerez le parallèle avec les programmes linéaires du 6 Décembre et du 7 Décembre : là aussi les relations entre les individus et les ressources sont linéaires, ie. chaque type d'individu consomme une quantité fixe de chaque type de ressources.
Mais là, c'est même plus fort, parce que non seulement on doit respecter les contraintes (ie. la consommation totale doit être plus faible que les ressources disponibles), mais en plus on doit les atteindre (la consommation totale doit être égale aux ressources disponibles). Dans la vraie vie ça n'arrive pas ça, mais ces idiots ont visé vraiment tout pile pour leur siège. On peut être sûr qu'avec les imprévus ils ne tiendront pas les 7 jours sans ravitaillement...
Dès qu'il y a des choses linéaires d'impliquées, il y a des matrices. Il n'y a pas assez de place dans ce message pour expliquer les raisons en détail, mais les contraintes se modélisent par une matrice (disons A), et si on note dans un vecteur x la quantité qu'il y a de chaque type de soldat alors le produit Ax nous donne la quantité de ressources consommées.
Dans le cas d'un problème linéaire, on dispose d'une quantité limitée de ressources qu'on peut exprimer dans un vecteur y, et le fait de respecter les contraintes s'écrit Ax ≤ y. C'est une équation «compliquée» avec plein d'implications géométriques, et pour trouver le maximum de soldats qu'on peut mettre sans dépasser les contraintes c'est très subtil. Dans le problème précédent, c'est plus facile, car comme on utilise exactement toutes les ressources on veut directement Ax = y et donc il suffit d'«inverser» A et de calculer, ce que les programmes savent faire tous seuls
Sinon vous pouvez résoudre à la main avec un papier et un crayon, ce n'est pas très difficile.
Heure de pointe
C'est l'heure de la contre-attaque ! Les troupes sont prêtes à traverser la forêt qui s'étend sur la frontière, au point prédéterminé qui attirera le moins l'attention de l'ennemi pendant la nuit. Vos quatre héros sont prêts à guider les soldats vers le territoire adverse au travers de la forêt dense et parfois marécageuse.
Le problème que vous rencontrez est simple. Dans cette forêt frontalière, hostile, nocturne et un peu difficile à pratiquer, il va y avoir des bouchons ; eh oui, parce que les soldats vont se retrouver embouteillés avec d'autres soldats.
Vous avez identifié que la section critique du trajet est le passage ci-dessous.
Les caractéristiques du terrain sont les suivantes :
En supposant qu'il y a une infinité d'hommes à faire passer et en négligeant le temps qu'il faut pour remplir initialement la zone, combien d'hommes peut-on faire traverser par heure en moyenne ?
Voici le code Python modélisant la map.
HEIGHT = 18
MAP = \
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
2, 2, 2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0,
1, 1, 0, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0,
1, 1, 1, 2, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0,
0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 0, 0, 0, 0, 1, 1, 0,
0, 0, 1, 2, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 0,
0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 1, 1, 1, 2, 1, 1, 1, 0,
0, 0, 1, 0, 2, 1, 0, 0, 0, 1, 1, 1, 1, 2, 1, 1, 0, 0,
0, 0, 1, 1, 2, 1, 1, 0, 0, 1, 1, 1, 1, 2, 1, 0, 0, 0,
0, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 0, 1, 2, 2, 0, 0, 0,
0, 1, 1, 1, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0,
0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1,
0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 2, 2, 2, 2, 2, 2, 2, 1,
0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 2, 1,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
START = [0, 1, 2, 3, 1*HEIGHT, 2*HEIGHT, 3*HEIGHT, 4*HEIGHT, 5*HEIGHT]
END = [ 17+13*HEIGHT, 17+14*HEIGHT, 17+15*HEIGHT, 17+16*HEIGHT,
13+17*HEIGHT, 14+17*HEIGHT, 15+17*HEIGHT, 16+17*HEIGHT, 17+17*HEIGHT]
Les éléments de MAP indiquent la capacité de chaque case ; on peut passer d'une case à l'une des 4 cases adjacentes, et la formulation des règles signifie qu'un déplacement entre les cases i et j peut se faire à raison de min(MAP[i],MAP[j]) soldats/minute.
Les éléments de START et END indiquent les cases de départ et d'arrivée. N'hésitez pas à demander des détails si la formalisation n'est pas claire.
Pièces du puzzle
Ajouté le 17/12/2021 à 09:12 :
J'avais oublié le code Python pour ce problème, je l'ai ajouté.
Citer : Posté le 19/12/2021 00:08 | #
Couverture de service
Cliquez pour agrandir.
Pendant que les soldats se préparent dans la forêt à affronter les troupes envoyées assiéger les défenses frontalières, le quartier général nouvellement créé prépare un plan d'invasion pour mettre un terme au conflit.
Ce plan prévoie une conquête éclair qui prenne de surprise toutes les principautés ennemies, réellement désunies pour le coup, sur deux jours seulement. Bien sûr, même avec l'union sacrée il n'y a pas assez de troupes pour attaquer tout le monde en même temps, mais le plan consiste à paralyser le réseau de transport qui supporte les mouvements d'hommes et de provisions.
Le but est de prendre juste assez de cités pour que celles qui ne seront pas tombées au crépuscule du deuxième jour soient isolées de leurs alliées. En d'autres termes, chaque fois qu'une route relie deux principautés, il faut en attaquer au moins une des deux.
La question est combien de principautés au minimum devez-vous attaquer pour accomplir cet objectif ?
Note du futur : personne ne m'a fait remarquer que j'étais bourré quand j'ai résolu le problème ; le code de décodage de l'image est le nombre minimum + 1. Désolé ! ^^"
Pièces du puzzle
Indice sur le problème du 16 Décembre
Probablement le problème le plus subtil jusqu'ici ! C'est un problème de flot maximal. Il y a un million de façons de le résoudre à la main sans programmer la solution (qui est un algorithme pas évident), la plus intuitive étant de chercher le goulet d'étranglement
Citer : Posté le 21/12/2021 00:31 | #
Explication du problème du 18 Décembre
Ce problème s'appelle Vertex Cover ; le but est de trouver un ensemble de sommets (vertex) qui couvre (cover) toutes les arêtes. C'est un problème difficile bien connu (un autres des problèmes NP-complets ultra-classiques), ce qui signifie que pour des réseaux très grands tout calcul qui détermine la solution optimale devient très long. Mais Vertex Cover est de plus «non-approximable», dans le sens où ne peut pas non plus calculer de bonnes approximations rapidement (avec «bonnes» signifiant à un facteur constant quelconque près et «rapidement» signifiant en temps polynomial. Voir PTAS et APX). C'est donc un problème vraiment profond !
Assurance tous risques
Le siège de la cité frontalière a commencé. À la dernière minute la lecture des documents volés a révélé que des bombardements étaient possibles, et le Ninja a été dépêché sur place pour parer à la menace. La ville n'est protégée que par une douve et est donc très vulnérable depuis les airs :
Les projectiles ne sont pas explosifs donc les dégâts individuels ne seraient pas très grands. L'ennemi en a de plus assez peu, et ils n'en gaspilleront pas ; tous les tirs viseront des bâtiments. L'image ci-dessous montre l'impact d'un tir et la région dans laquelle un clone du Ninja peut intercepter les intrus (la région d'un tir ne peut pas être tournée, c'est toujours la même direction Ouest/Sud).
La question est combien de clones du Ninja seront nécessaires pour défendre toutes les habitations ?
À l'origine je voulais poser un problème plus subtil ; d'abord prendre des projectiles en forme de croix, et ensuite la question suivante : sachant que l'ennemi va tirer de façon à toucher au moins une fois chaque bâtiment, mais en ce faisant minimisant le nombre de tirs, combien de clones du ninja seront nécessaires pour défendre tous les tires, sachant que l'ennemi choisira une configuration rendant ce travail le plus difficile possible ?
Cette variante a un soupçon de TQBF dedans, avec le côté "je sais que tu sais que je sais que...", puisqu'on sait que l'ennemi va minimiser le nombre de tirs, et l'ennemi sait qu'on va minimiser le nombre de ninjas sachant qu'il va minimiser le nombre de tirs, et donc il s'arrange pour choisir parmi les options minimisant le nombre de tirs une qui maximise le nombre de ninjas... algorithmiquement il n'y a de rien de dur à part l'explosion combinatoire, mais je trouve ça fun
Cependant j'ai pas réussi à résoudre ce problème plus subtil assez rapidement, donc je vous laisse une autre couverture d'ensembles bien plus facile, à peine un problème difficile
Pièces du puzzle
Citer : Posté le 21/12/2021 01:42 | #
wow la 3eme piece du jour 6 et la 8eme du 11 se ressemble tellement que j'ai eu un doute à un moment
Citer : Posté le 21/12/2021 09:30 | #
Attends Alice ne commence pas à me faire douter encore, j'ai triple-vérifié quand j'ai refait la distribution
Citer : Posté le 22/12/2021 18:22 | #
Le problème ci-dessous est le dernier problème facile de cet événement. Après l'avoir résolu et obtenu les pièces, vous aurez donc tout ce qu'il faut pour finir la première moitié du puzzle. Il y a 3 barres de pièces au lieu de 2 parce que pour une raison qui m'échappe initialement j'avais prévu de finir le 25... ce qui est pas pratique, vous serez occupés le 25
Pour soumettre votre participations, envoyez-moi votre puzzle ayant sa moitié gauche reconstituée :
Le premier envoi qui reproduit correctement l'image gagne. S'il y a quelques pixels d'écart c'est pas grave ; on m'a aussi fait remarquer que certaines touffes d'herbe étaient quasiment impossibles à positionner de façon certaine ; en gros si vous avez reconstitué le puzzle de façon legit ce sera accepté.
Vendredi (après-demain, le 24) je posterai le dernier puzzle difficile et pièce finale de cet événement, et vous pourrez alors m'envoyer l'autre moitié du puzzle.
Arrivée discrète
La défense de la cité frontalière est un succès ; les troupes ennemies se sont majoritairement dispersées. Cependant, vous avez appris de quelques transfuges que la capitale ennemie est prête à être défendue. En fait, les négociations entre le gouvernement adverse et les principautés locales se sont assez mal passées, ce qui a produit beaucoup de délais d'organisation et une méfiance générale du public. C'est la raison pour laquelle il y a eu un tel silence entre les premières escarmouches et cette véritable attaque à la frontière.
Du coup, une bonne moitié des troupes réquisitionnées n'a simplement pas participé à l'attaque et sont directement restées à la capitale pour se préparer à défendre. Toute la stratégie est essentiellement une diversion pour mieux préparer un futur siège... les troupes envoyées attaquer se sont naturellement senties sacrifiées, une autre erreur qui vous a permis de recruter de précieuses informations.
Vous avez donc mis votre plan de capture à exécution en toute confiance, et contrôler les routes ne sera clairement pas un problème. Vous avez donc l'opportunité de planifier l'approche que vous ferez sur la capitale dans deux jours.
Il y a 6 routes qui bordent la capitale, et il y aura 4 voies d'approche :
Compte tenu des murailles de la ville, il est estimé qu'au plus 12 hommes pourront rentrer dans la ville chaque minute en moyenne. Si plusieurs bataillons arrivent en même temps, ils devront donc étaler leurs entrée sur plusieurs minutes.
1644 soldats vont participer à l'attaque pour envahir la ville. Sachant que les les voies sont synchronisées pour que les premiers bataillons arrivent tous en même temps à la minute 0 de l'assaut, combien de bataillons en moyenne attendront devant les portes à la fin de chaque minute ?
Pour résoudre ce problème je vous conseille fortement d'écrire un programme Python. Commencez par trouver combien de soldats arrivent et attendent à chaque minute. Pour vous aider à ajuster, je vous indique que :
Le nombre moyen de bataillons en attente est décimal ; prenez les 6 premières décimales (sans arrondir). Par exemple, si la valeur est 0.834576234, la solution d'aujourd'hui sera 834576.
Pièces du Puzzle
Il y en a 3 parce que j'en avais prévu une pour le 25... quel fou xD
Ajouté le 22/12/2021 à 19:32 :
Précisions : les personnes ayant résolu le puzzle et les gagnants seront annoncés à Noël pour pas trop tuer le suspense... je reviens vers vous si vos soumissions sont incorrectes dans tous les cas
Citer : Posté le 23/12/2021 13:22 | #
AH ! Comment ça on en donne 3 d'un coup ?
Moi qui m'attendais à voir ça le 24, date du dernier problème facile (ou même le 23, vu qu'un calendrier de l'avent se finit le 24 - en laissant place au problème difficile le 24)... Du coup j'ai du retard par rapport aux autres...
Sait-on jamais, peut-être suis-je le premier à répondre ? (M'enfin ça m'étonnerait...)
On se reverra, calculatrice Casio, ce n'est qu'un au revoir !
Je tenais tout de même à remercier LephenixNoir (et toute autre personne s'il y a) pour ce calendrier de l'avent qui était bien construit, et bien dessiné !
À quand la sortie d'un jeu inspiré par cette aventure ?
Citer : Posté le 23/12/2021 13:30 | #
Oui, désolé pour les questions de timing/délai... c'est pas pratique avec le format, parce que tout le monde la même solution ; tu ne peux pas classer les participants. :x Si tu as des suggestions sur un format qui marcherait un peu mieux, je suis preneur.
Sait-on jamais, peut-être suis-je le premier à répondre ? (M'enfin ça m'étonnerait...)
On se reverra, calculatrice Casio, ce n'est qu'un au revoir !
Tu n'es pas le premier à répondre, mais à défaut il y aura d'autres occasions de gagner des lots... j'ai encore une Graph 90+E en stock après ça, probablement pour un CPC ou un autre concours plus traditionnel dans ce style.
À quand la sortie d'un jeu inspiré par cette aventure ?
Merci ! Je me suis pas mal dépassé sur les dessins. Pour un jeu, euh... servez-vous
Citer : Posté le 23/12/2021 20:30 | #
Si tu as des suggestions sur un format [...]
Alors j'ai réfléchi un peu et je pense avoir une idée, par contre j'ai volontairement enlevé "un peu mieux" de la citation car je ne sais absolument pas si ça marchera bien ^^'
L'idée serait : proposer des énigmes à résoudre, pour en demander des implémentations en Basic Casio (je pense que c'est le langage le plus répandu sur ce forum
Un classement possible, dès lors, serait basé sur la vitesse d'exécution (trop dur à mesurer ?) et/ou le poids du code.
Des avantages (absolus, sans comparaison avec ce format-ci) que je vois :
- une date butoir, et donc pas besoin de rafraîchir la page Planet-Casio pour avoir de nouvelles énigmes, ni répondre au plus vite
- vérification de bonne réponse semi-automatique : un programme spécialement pour le correcteur du concours, affichant simplement "correct" ou "incorrect"
Inconvénients :
- vérification semi-automatique : il faut tout de même (enfin je pense) que le correcteur importe le programme manuellement dans un émulateur (ou autre)
- et à coup sûr plein d'autres
P.S. : Faut vraiment pas croire que je critique le format du concours. Je ne me permettrais vraiment pas.
Citer : Posté le 23/12/2021 20:42 | #
C'est intéressant, mais comme il faut coder un programme par énigme l'investissement est très conséquent... je sais par exemple que j'aurais eu moins de participations ici s'il n'y avait pas un raccourci pour sauter des problèmes (que peut-être tu as vu ?). Et c'est difficile aussi d'attirer du public pour un événement si c'est du Basic Casio, qu'essentiellement seul nous maîtrisons (il faut en plus une calculatrice pour résoudre, personne n'ira taper sur émulateur et le combo BIDE + émulateur est bien trop obscur).
Note aussi que pour les énigmes ici les instances sont fixées donc la solution c'est juste un nombre, tu peux écrire un programme qui fait <ce nombre>→A et avoir fini. Pour que soumettre un programme comme solution marche, il faut tester sur plusieurs instances "secrètes" (pour vérifier que le programme résout bien le problème) ce qui est assez chronophage
C'est tout à fait faisable, mais je suis pas sûr que ça trouve beaucoup de public vue la difficulté :x
Citer : Posté le 23/12/2021 20:53 | #
C'est vrai que ça donne pas très envie comme ça
J'avais pas du tout pensé à "vérifier que le programme résout bien le problème", et encore moins à l'accessibilité des problèmes au public.
Autant pour moi !
Citer : Posté le 24/12/2021 16:33 | #
Le problème ci-dessous est le dernier problème difficile de cet événement. Après l'avoir résolu et obtenu les pièces, vous aurez donc tout ce qu'il faut pour finir le puzzle entier. Pour soumettre votre participation, envoyez-moi le puzzle complètement reconstitué :
Le premier envoi qui reproduit correctement l'image gagne. S'il y a quelques pixels d'écart c'est pas grave ; on m'a aussi fait remarquer que certaines touffes d'herbe étaient quasiment impossibles à positionner de façon certaine ; en gros si vous avez reconstitué le puzzle de façon legit ce sera accepté.
Fête en ville
Nous y voilà - les portes de la capitale. Le dernier obstacle qui vous sépare encore d'une victoire glorieuse et de votre chapitre bien mérité dans les livres d'histoire futurs.
Le plan d'invasion a été perfectionné pour permettre à vos troupes de s'engager en continu dans la ville, une fois la herse levée par l'action de quelques agents doubles recrutés après le siège défendu avec succès à la frontière.
Mais la facilité par laquelle la capitale a été atteinte n'est contrastée que par l'excellente préparation de la défense. Tous les soldats ennemis sont prêts à tenir la porte, et il y en a beaucoup ! Le nombre exact n'a pas pu être estimé en avance, et c'est seulement maintenant que les agents doubles qui n'étaient pas occupés à ouvrir la herse ont pu faire le compte.
La carte de la capitale est présentée ci-dessous. Les bâtiments en forme de ville ont été réquisitionnés pour les troupes, tout comme le château. Ils ont déjà commencé à déverser des soldats qui tentent de vous contenir dans la zone marquée en rouge.
Ce problème est similaire à heure de pointe. Chaque bâtiment réquisitionné peut envoyer un soldat équipé toutes les 6 secondes, et le château un toutes les 3 secondes. Tous ces soldats se dirigent vers la zone rouge, et le but de ce problème et de calculer quel flot arrive aux portes.
Le pavage est très pratique pour marcher, et chaque case supporter le passage de 4 soldats par minute. C'est assez peu parce que la ville est encombrée de chariots, sacs et matériaux laissés prévus par un plan de renforcement des fortifications qui n'a pas pu être fini faute de temps. Les zones d'herbe supportent 2 soldats par minute, et la route devant le château, qui a été complètement nettoyée, pas moins de 25 soldats/minute.
Le code Python ci-dessous résume cette information de façon numérique. Les sources sont données dans START et correspondent aux 10 et 20 dans la carte. Pour toutes les autres cases, la indiquée est le flot supporté. ; la façon de les interpréter est que le passage de la case i à la case j supporte min(MAP[i],MAP[j]) soldats par minute. Les cases de la zone rouge sont listées dans END.
HEIGHT = 26
x, R = 0, 0
MAP = \
[x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,
x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,
x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,
x, x, x, x, x, x, x, x, R, R, R, R, R, R, R, R, R, R, R, x, x, x, x, x,
x, x, x, x, x, x, x, x, R, 4, 4, 4, 4,25, 4, 4, 4, 4, R, x, x, x, x, x,
x, x, x, R, R, R, R, R, R, 4, x, 4, 4, 4, 4, 4, x, 4, R, x, x, x, x, x,
x, x, x, R, 4, 4, 4, 4, 4, 4, x, 4, 4, 4, 4, 4, x, 4, R, R, R, R, x, x,
x, x, x, R, 4,10,10, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, R, x, x,
x, x, x, R, 4, 4, 4, 4, 4, x, 2, 4, 4, 4, 4, 4, 4, 4, 4, x, 4, R, x, x,
x, x, x, R, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, x, x, 4, x, 4, R, R, x,
x, x, x, R, 4,10,10, 4, 4, 4, 4, 4, 4, 4, 4, 4, x, 2, 4, x, 4, 4, R, x,
x, x, x, R, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,10, 4, R, x,
x, x, x, R, R, R, R, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,10, 4, R, x,
x, x, x, x, x, x, R, 4, x, 4, 4, R, R, R, 2,25,25, 4, 4, 4, 4, 4, R, x,
x, x, x, x, x, x, R, 4, x, 4, 4, R,10,25,25,25, R, R, 4, 4, 4, 4, R, x,
x, x, x, x, x, x, R, 4, x, 4, 4, R, x, x, 2,25, x, R, 4, 4,10, 4, R, x,
x, x, x, x, x, x, R, 4, x, 4, 4, R, x,20,25,25, x, R, 4, 4,10, 4, R, x,
x, x, x, x, x, x, R, 4, x, 4, 4, R, x, x, x, x, x, R, 4, 4, 4, 4, R, x,
x, x, x, x, x, R, R, 4, 4, 4, 4, R, R, R, R, R, R, R, 4, 4, R, R, R, x,
x, x, x, x, x, R, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, R, x, x, x,
x, x, x, x, x, R, 4, x, 4, x, 4, x, 4, 4, 4, 4, 4, 4, 4, 4, R, x, x, x,
x, x, x, x, x, R, 4, x, 4, x, 4, x, 4, 4,10, 4, 4, R, R, R, R, x, x, x,
x, x, x, x, x, R, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, R, x, x, x, x, x, x,
x, x, x, x, x, R, R, R, R, R, R, R, R, R, R, R, R, R, x, x, x, x, x, x,
x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x,
x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x]
START = [i for i in range(len(MAP)) if MAP[i]==10 or MAP[i]==20]
END = [WIDTH*y + x for y in range(4,8+1) for x in range(9,17+1)]
CASTLE = MAP.index(20)
La question est la suivante : de quelle proportion sera réduit le flot si δ, Alice, Scarlet et Ninja arrivent à capturer ou bloquer tous les bâtiments réquisitionnés ? En d'autres termes, si on ne compte plus dans START que le château, de combien le flot se réduit-il ?
La solution au problème d'aujourd'hui est composée des 9 premières décimales de ce nombre.
Les toutes dernières pièces du puzzle
Citer : Posté le 25/12/2021 22:12 | #
Cet événement est maintenant fini, une variation du puzzle recomposé ainsi que les gagnants sont donnés dans l'article de Noël. Merci à tous les participants !