La demande de bien a explosé, des nouveaux moyens de transport sont nécessaires, la plus grande corpo arasaka cherche à trouver un nouveaux moyen de délivrer le plus de bien, le plus vite et le moins cher possible.
La réponse: des cyber-drones.
Vous êtes chargé d’armer le cerveau de ce réseau de drônes d’une intelligence high-tech.
Projet basé sur le problème de qualification du google Hash Code de 2016.
En partant d'un ensemble de drones, d'une liste de commandes et de la disponibilité des produits dans les entrepôts, planifier les opérations des drones de sorte que les commandes soient complétées le plus rapidement possible.
- Esnault Valentin [email protected]
- Tchernychev Maxime [email protected]
- Roué Robinson [email protected]
- Klein Nael [email protected]
Il faut soit le télécharger à l'adresse suivante (lien de téléchargement), soit cloner le projet avec la commande suivante :
git clone https://gitlab.univ-nantes.fr/E218577J/polyhash2023.gitpython polyhash.py <fichier d'entrée> <fichier de sortie>
polyhash.py: Fichier principal, permet de lancer le programme en précisant le fichier d'entrée et le fichier de sortie.polyparser.py: Fichier contenant la fonction permettant de parser le fichier d'entrée et de renvoyer un tuple contenant toutes les informations contenus dans le fichier d'entrée.mesures_temps.py: Fichier contenant le décorateur permettant de mesurer le temps d'exécution d'une fonction.utils.py: Fichier contenant les fonctions utilitaires telles quecalculate_weigth(),check_b_in_a(),dict_add()etdict_subtract().polysolver.py: Fichier contenant la fonctionsolve()redirigeant vers les différentes stratégies de résolution ainsi que la fonctionsave_solution()/strategies: Dossier contenant les différentes stratégies de résolution./challenges: Dossier contenant les différents challenges./Doc: Dossier contenant plusieurs fichiers pense-bête et des pistes de reflexion.
- On trie trie les commandes par nombre d'item puis par distance à l'entrepôt de départ
- On séléctionne la première commande
- On sélectionne le premier item de la commande
- On trouve l'entrepôt le plus proche qui contient cet item puis en restant à cet entrepôt, elle va prendre le plus d'items possibles concernant la commande actuelle
- si le drone arrive à prendre tous les items permettant de finir la commande, il va passer à la commande suivante et prendre des items en plus et ce jusqu'à ce qu'il n'arrive plus à compléter la commande actuelle ou qu'il n'ai plus la place de transporter plus d'items
- une fois qu'il a été prendre ses items, il va les déposer aux commandes pour lesquelles les items ont été pris
- une fois qu'il a tout livré, il repart à 0 et recommence au début
| Challenge | Score | Classement | Temps d'execution | RAM utilisée |
|---|---|---|---|---|
| A | 238 | Top 1 ex equo | 0.002s | 23.0 MiB |
| B | 101373 | Top 9 | 1.750s | 27.8 MiB |
| C | 95310 | Top 12 | 2.145s | 27.2 MiB |
| D | 74249 | Top 7 | 1.423s | 26.0 MiB |
| Total | 271170 | Top 10 |
Il serait probablement possible de permettre aux drones de charger les produits des commandes sans forcément les faire dans l'ordre mais plutot de prendre tous les produits utiles sur les prochaines commandes.
Cela demmanderait un peu de restructuration pour pouvoir passer de commande en commande tout en revenant sur celles qui n'ont pas pu être complétées pour les finir grace aux drones suivants.