Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Actualités


Index du Forum » Actualités » Le Puzzle de l'Avent 2021
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

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


Eragon Hors ligne Gardien des bots Points: 483 Défis: 0 Message

Citer : Posté le 03/12/2021 09:46 | #


C'était trop simple oui… 4 min pour trouver
Dark storm Hors ligne Labélisateur Points: 11641 Défis: 176 Message

Citer : Posté le 03/12/2021 10:26 | #


Variation difficile : pareil, mais dans un espace 5D
Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Eragon Hors ligne Gardien des bots Points: 483 Défis: 0 Message

Citer : Posté le 03/12/2021 10:31 | #


AH ! easy… hum… ça ressemble a quoi du coup ?
Ne0tux Hors ligne Membre d'honneur Points: 3525 Défis: 265 Message

Citer : Posté le 03/12/2021 11:01 | #


Un espace 5D ? Ça ressemble à ça : https://fr.wikipedia.org/wiki/Yahtzee
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 03/12/2021 18:52 | #


Explication du problème du 2 Décembre

Le problème d'hier est un problème de couverture d'ensembles. Il n'est pas formulé comme un des grands classiques (Set Cover et Exact Cover sont légèrement différents), mais il est dans la même lignée.

Vous pouvez le formuler comme ceci : étant donné un ensemble de cases à couvrir (les 36 cases praticables) et des sous-ensembles (chaque façon de placer un personnage sur la plateau), utiliser les sous-ensembles pour maximiser la quantité de cases couvertes.

Pour être très rigoureux, les sous-ensembles qui vous sont proposés sont toutes les façons de placer un des personnages sur une des cases. Le plateau faisant 8×8 = 64 cases, vous avez 64 sous-ensembles proposés par personnage, pour un total de 256 sous-ensembles. Vous devez les combiner pour maximiser la couverture des cases praticables, avec la contrainte que vous ne pouvez placer chaque personnage qu'à un seul endroit (si vous utilisez deux sous-ensembles Scarlet c'est de la triche ! ).

J'ai mis en gras le «maximiser» pour montrer que c'est un problème d'optimisation, où on vous demande le résultat. Il existe un autre type de problèmes qu'on appelle des problèmes de décision, où il faut répondre vrai/faux. Un problème de décision similaire à celui d'hier aurait été par exemple «peut-on couvrir au moins 33 cases sur 36 ?». En général un même problème peut se formuler des deux façons, mais vous reconnaîtrez que si y'a que deux options pour décoder les pièces du puzzle ce sera pas un gros challenge.

Défense indépendante

Aujourd'hui je vous propose une variante difficile du problème d'hier, qui est cette fois un vrai problème de couverture. Voici le plateau :


Le ninja peut se clôner à l'infini, mais Alice, Scarlet et Delta non. Combien de personnages peut-on placer sur des cases praticables de la map sans qu'une cellule praticable ne soit couverte deux fois ?

Les personnages peuvent avoir des zones impraticables dans leur portée mais ils doivent se trouver sur des cases praticables. On peut mettre plusieurs personnages sur la même case tant que les portées ne s'intersectent pas. L'eau est impraticable évidemment...

Comme vous aurez probablement besoin de coder pour trouver la solution, voici le tableau écrit en Python.

WIDTH, HEIGHT = 15, 15
MAP = \
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0,
0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0,
0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0,
0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0,
0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0]

Pièces du puzzle



Ajouté le 03/12/2021 à 23:01 :
J'ai ajouté les pièces. J'étais un peu optimiste sur la taille de la map (c'est NP-complet cette broutille quand même !) donc j'ai réduit un peu, ça vous simplifiera la vie. Pour info mon script Python qui calcule la solution optimale prend 12 secondes... donc ça se fait
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 04/12/2021 17:35 | #


La patrouille

Malgré tes efforts pour maximiser la surface couverte du champ de bataille, il reste encore pas mal d'options à des attaquants potentiels pour se faufiler entre les défenses. Il suffit d'un jour de mauvaise visibilité pour rater des bataillons, et tu ne doutes pas que l'ennemi en profitera.

Pour prendre ces fourbes par surprises, tu envoies δ faire des rondes dans toutes les cases non couvertes et attaquer les intrus sur son passage. Pour maximiser la protection, δ doit passer sur toutes les cases de forêt une seule fois et se retrouver à la fin de sa ronde à son point de départ, de sorte à pouvoir immédiatement recommencer son tour.

Voici la zone à parcourir :


Le but de ce problème est de trouver un chemin de ronde. Mais la solution ne serait pas un nombre entier, alors en plus de ça je vous demande de trouver le nombre minimal d'étapes pour atteindre Scarlet sur un chemin de ronde.

Il y a bien sûr plusieurs chemins possibles, et tous ne croisent pas Scarlet au même moment. Il faut bien trouver un chemin qui passe par Scarlet le plus tôt possible.

Pièces du puzzle



Indice sur le problème du 3 Décembre

Ce problème s'appelle Maximum Set Packing. Dans ce cas particulier, on peut prouver (en étudiant un peu ce à quoi ressemblent les solutions) que le nombre maximum de personnages qu'on peut caser est facilement trouvable à partir du nombre maximum de ninjas qu'on peut caser en ignorant Scarlet, Alice et δ.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Tituya Hors ligne Administrateur Points: 2156 Défis: 26 Message

Citer : Posté le 04/12/2021 19:10 | #


J'attends le jeu sur 90+E pour placer les différents personnages et voir le champ d'action

Le puzzle a l'air très beau, j'ai pu réussir les 3 jours pour l'instant. Comme d'habitude tu fais un boulot de malade, bravo !
Bretagne > Reste du globe
(Et de toute façon, vous pouvez pas dire le contraire)
Projet en cours : Adoranda

Mes programmes
Hésite pas à faire un test !


Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 05/12/2021 15:08 | #


Explication du problème du 4 Décembre

Le problème d'hier consiste à trouver un chemin qui est un «cycle hamiltonien» ; «cycle» veut dire qu'on revient au point de départ et «hamiltonien» veut dire qu'on passe exactement une fois sur chaque case.

On pourrait croire à première vue que cette histoire de distance avec Scarlet complexifie le problème, parce qu'en principe il faut trouver tous les cycles hamiltoniens pour savoir lequel atteint Scarlet le plus tôt. C'est vrai. Mais pour un problème aussi simple où on cherche à la main, ça guide la résolution en privilégiant une direction, donc c'est plus une aide qu'autre chose

Le problème de déterminer s'il existe un cycle hamiltonien est difficile à lui tout seul, dans le sens où quand la map devient très grande il n'y a pas d'algorithme qui trouve la réponse rapidement. Plus spécifiquement, on le qualifie de «NP-difficile» ; ce que ça veut dire exactement est compliqué mais en gros le temps de calcul augmente exponentiellement avec la taille du graphe (ie. chaque fois qu'on rajoute une case ça démultiplie le temps de calcul !).

Pour le problème d'aujourd'hui j'ai fait l'erreur de vouloir donner le même qu'hier avec une map plus grosse, ce qui est une très mauvaise idée parce que le problème étant NP-difficile je n'arrivais pas à calculer la solution. J'ai changé d'idée du coup.

Tous les chemins mènent à Scarlet

Sur la map ci-dessous (même qu'hier), déterminer combien de chemins différents mènent à Scarlet. On veut des chemins simples, ie. on s'interdit de passer deux fois sur la même case.


Voici un petit code Python formalisant la map ; indice, vous aurez besoin de programmer, la réponse est un nombre à 6 chiffres

WIDTH, HEIGHT = 12, 12
MAP = \
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0,
0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0,
0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0,
0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0,
0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0,
0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0,
0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0,
0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0,
0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

INITIAL = 2+5*WIDTH
SCARLET = 10+4*WIDTH

Pièces du puzzle


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 06/12/2021 20:42 | #


Distribution des rations

Avec les tours de ronde, vous savez maintenant que la région est sécurisée. Pas d'attaque en vue, c'est presque comme si l'armée ennemie était à court de moyens - ou alors elle prépare un gros coup, mais on espère que non.

Pour l'instant, le plan est de maintenir la défense tout en préparant une contre-attaque. Il faut donc laisser des troupes sur places, et gérer correctement la logistique pour qu'elles soient approvisionnées. Vu les moyens disponibles, il ne sera pas possible de tout protéger, mais on peut essayer de s'en approcher le plus possible.

La limitation principale est la nourriture. Un soldat consomme 4 rations de nourriture par semaine (les rations font plusieurs repas évidemment !) et peut défendre 2 cases du plateau. δ consomme 1 ration de nourriture par semaine et défend 1 case ; Alice, Scarlet et Ninja consomment chacun 6 rations par rations et ils défendent 8, 25 et 13 cases respectivement.

δ, Alice, Scarlet et Ninja peuvent rester en défense pour l'instant mais ils seront tous nécessaires à la future contre-attaque ; si on les laisse derrière, il faudra les rapatrier par véhicule le moment venu (chacun un véhicule, pour transporter leurs effets personnels x3).

Notre système d'approvisionnement peut fournir 50 rations de nourriture par semaine et 2 véhicules sont disponibles. Quelle est la surface maximale qu'on peut défendre ?

Pièces du puzzle


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Thebigbadboy Hors ligne Maître du Puzzle Points: 455 Défis: 16 Message

Citer : Posté le 07/12/2021 14:02 | #


Juste pour savoir, vous me conseilleriez quoi comme utilitaire pour refaire le puzzle ? (Je suis sous Linux)

À part ça, l'avent est très bien construit je trouve
Un problème sans solution est un problème mal posé — Albert Einstein
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 07/12/2021 14:06 | #


Perso je conseille de charger toutes les pièces dans des calques dans GIMP (Fichier » Ouvrir en tant que calques) et ensuite de les déplacer avec l'outil de déplacement de calque. Bon par contre faut découper les pièces initialement, peut-être qu'on peut faire plus pratique...

Je réalise que j'ai oublié de les faire tourner de façon aléatoire, je suppose que vous grattez ça pour cette année.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 07/12/2021 23:08 | #


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 :

Les variables : soldats, delta, alice, scarlet, ninja.
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 :

  • Vous avez accès à tous les soldats disponibles et 100 cavaliers.
  • Vous avez δ, Alice, Scarlet comme précédemment.
  • Vous avez jusqu'à 12 clônes principaux du Ninja, et autant de clônes secondaires que nécessaire.
  • Les provisions atteignent 650 rations par semaine.
  • Il y a 30 chevaux disponibles dans l'immédiat.

Et voici ce que fait chaque type d'unité :

  • Les soldats couvrent chacun 2 cases, et consomment 4 rations par semaine.
  • Les cavaliers couvrent 15 cases, consomment 18 rations et 1 cheval chacun.
  • δ, Alice et Scarlet couvrent 1, 8 et 25 cases et consomme 1, 6 et 6 rations, comme précédemment.
  • Les clônes du ninja couvrent 13 cases chacun ; les principaux consomment 6 rations et les secondaires 18 (non qu'ils soient gourmands mais c'est de là qu'ils tirent l'énergie pour se maintenir, le ninja étant limité à 12 sur ses propres réserves).
  • Enfin, δ, Alice, Scarlet et chaque clône principal du ninja auront besoin d'un cheval pour participer à la contre-attaque s'ils sont laissés en défense.

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


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 08/12/2021 12:47 | #


Diplomatie de région (1/2)

L'absence de mouvement de l'ennemi est perçu par les dirigeants locaux comme un calme avant la tempête. Ils sont inquiets — ils l'ont toujours été — et voient en vous une organisation centrale peut-être capable de les défendre, ou en tous cas digne d'intérêt. Après des années de gestion indépendante, ils vous pensaient tous incapables de gouverner, mais en repoussant stratégiquement une première attaque vous avez bien défendu vos compétences.

Maintenant est le moment de recueillir, à défaut d'allégeance, leur coopération. Il a été décidé d'envoyer δ et Alice au à la Cité des falaises calcaires, un château surplombant la mer possédant un port en eau profonde, et donc de facto une «principauté» d'influence.

Le chemin est cependant assez ardu, comme vous pouvez le voir sur la carte ci-dessous. Les forêts sont relativement clairsemées donc praticables (de toute façon on n'a pas le choix), par contre les montagnes sont hors de question. Il y aussi beaucoup de marécages à cause des nombreux petits cours d'eau qui sillonnent les montagnes, alimentés par les précipitations du bord de mer.


Il faut à δ et Alice 1 heure pour parcourir une case de plaine, 3 heures pour parcourir une case de forêt, et 4 heures pour parcourir un marécage.

La question est la suivante : après combien de temps pourront-t-elles toute les deux entrer au château ?

Pièces du puzzle


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Slyvtt Hors ligne Maître du Puzzle Points: 2403 Défis: 17 Message

Citer : Posté le 08/12/2021 13:15 | #


C'est vraiment dommage que j'ai pas de temps en ce moment pour le puzzle car tu t'es vraiment arraché Lephé.
Aussi bien l'histoire que les énigmes individuelles sont géniales.
Super !! Et bonne chance aux participants...

PS : pour les "SynchroDonjontistes", ca devrait être facile pour l'épreuve d'aujourd'hui
There are only 10 types of people in the world: Those who understand binary, and those who don't ...
Massena Hors ligne Ancien rédacteur Points: 2244 Défis: 11 Message

Citer : Posté le 08/12/2021 18:54 | #


Envoyer δ en mission diplomatique est une très mauvaise idée
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 08/12/2021 20:24 | #


Massena a écrit :
Envoyer δ en mission diplomatique est une très mauvaise idée

Oups. Euh, c'est pas grave, tout va bien se passer. Elle est avec Alice, qui est très communicat- wait
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Hackcell Hors ligne Maître du Puzzle Points: 1532 Défis: 11 Message

Citer : Posté le 08/12/2021 20:54 | #


Lephenixnoir a écrit :
Oups. Euh, c'est pas grave, tout va bien se passer. Elle est avec Alice, qui est très communicat- wait


Comment rater une mission diplomatique en trois étapes avec la mage Alice :
*entre timidement dans la salle du trône*
*trébuche et tombe à terre*
*quite la salle en pleurant*
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 09/12/2021 19:21 | #


Explication du problème du 8 Décembre

Slyvtt a écrit :
PS : pour les "SynchroDonjontistes", ca devrait être facile pour l'épreuve d'aujourd'hui

Comme SlyVTT l'a vite remarqué, le problème d'hier est un problème de plus court chemin, consistant simplement à trouver par quels chemins δ et Alice peuvent atteindre le château le plus vite.

C'est un problème ultra-classique de théorie des graphes, qui a des applications à peu près partout du GPS au routage d'Internet, et tout une variété d'algorithmes qui présentent tous des variations utiles dans différents contextes, parmi lesquels :

  • Le parcours en largeur est le plus simple et marche uniquement quand tous les déplacements ont le même coût.
  • L'algorithme de Dijkstra généralise ça en autorisant des déplacements ayant des coûts différents pourvu qu'il n'y ait pas de coûts négatifs. C'est l'algo le plus simple pour résoudre le problème d'hier.
  • L'algorithme de Bellman-Ford permet de calculer de façon distribuée, et il peut efficacement prendre en compte l'apparition ou la disparition de nouveaux chemins. C'est lui qui est utilisé par les routeurs d'Internet pour choisir le chemin que prennent vos communications réseau.
  • L'algorithme de Floyd-Warhsall calcule les plus courts chemins de tout point de départ à tout point d'arrivée (et détecte les cycles négatifs).
  • L'algorithme A* étend Dijkstra avec un système d'heuristique qui permet de "viser" la destination pour chercher plus vite, et parfois de trouver très rapidement des chemins qui ne sont pas les plus courts, mais pas trop loin.

On pourrait passer des heures dessus, mais vous pouvez aussi chercher le chemin à la main, sur cet exemple ça va beaucoup plus vite.

Diplomatie de région (2/2)

Aujourd'hui je vous propose une variation de ce problème. La mission diplomatique est limitée, en plus des caractères particuliers de δ et Alice (x3), par la météo : il pleut. La pluie attendrit le sol en plaine, crée de la boue en forêt, et inonde les marécages, ce qui augmente le temps de trajet :

  • Pour chaque mm d'eau qui tombe, le temps de parcours en plaine augmente de 1/24 heure ;
  • Pour chaque mm d'eau qui tombe, le temps de parcours en forêt augmente de 15 minutes ;
  • Pour chaque mm d'eau qui tombe, le temps de parcours en marécage augment de 1/8 heure.

Le chemin est le même qu'hier :


Je vous demande de trouver deux valeurs. La première est la plus petite quantité d'eau (en mm) qui doit tomber pour que ni δ ni Alice ne passe par le col montagneux au centre de la map.

La seconde est l'unique quantité d'eau (en mm) pour laquelle δ et Alice se séparent et ne se retrouvent qu'au château.

La solution du puzzle est la concaténation de ces nombres, par exemple si la première réponse est 35 et la seconde 78 la solution sera 3578.

Pièces du puzzle


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

Citer : Posté le 10/12/2021 22:36 | #


Union sacrée

Alice et δ ont impressionné le duc des falaises calcaires ; c'est surtout la magie d'Alice qui les a cloués pour être honnête. Malgré leur économie maritime, ils sont très terre-à-terre... et quelques petites démonstrations les ont vite convaincu qu'ils seraient déjà en danger si le gouvernement venait taper à la porte, achevant l'opposition qui n'a pas trouvé mieux que de se moquer des invités trempés par la pluie.

Une coalition est en train de se mettre en place, et le bruit court qu'une «union sacrée» de toutes les principautés pourrait bien se profiler. D'ailleurs ça commence à être mal vu de dire «principauté» puisqu'un sens national commence doucement à renaître. L'opération est un succès, le pays reprend des couleurs !


Mais la coopération des villes et château ne suffit pas ; il faut aussi le support logistique derrière. Et l'état des routes sur tout le territoire est assez désastreux, avec seulement quelques-unes encore en état de fonctionner proprement. Le chemin qui sillonne les montagnes pour atteindre le village au Sud-Est, près de la frontière où a eu lieu la première bataille de cette épopée, est presque impraticable à cause de parties éboulées.

Avec tout ça, les temps de trajet entre les centres de population, les îles et les points stratégiques se comptent souvent en jours !

Un plan d'infrastructure est donc en discussion pour faire la liaison plus rapidement entre toutes les villes. Le but est de réduire le temps de trajet au nombre d'heures indiqué sur le plan suivant.


Bien sûr, toutes ces routes ne peuvent pas être construites ou rénovées en mêmes temps ; une fois les soldats réquisitionnés il ne reste clairement pas assez de main d'oeuvre. Le but est donc de connecter toutes les villes entre elles avec juste un minimum de routes. Comme du coup il faudra parfois faire des détours pour se rendre d'une ville à l'autre, on décide de se concentrer sur les routes les plus rapides.

Parmi tous les choix de routes qui connectent tous les points d'intérêt, trouvez-en un qui minimise la somme des durées. Cette somme est la solution au problème d'aujourd'hui.

Pièces du puzzle


Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Gladosse Hors ligne Membre Points: 229 Défis: 2 Message

Citer : Posté le 11/12/2021 12:59 | #


est-ce que je peux avoir un recapitulatif
je n'ai pas tout suivi
Lephenixnoir Hors ligne Administrateur Points: 24635 Défis: 170 Message

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 ?
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 76 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd