Forum de mathématiques - Bibm@th.net

Alexis_Sgn

Membre

Inscription : 29-06-2022

Messages : 1

Défi : Optimisation de la position de verres sur un Plateau

Bonjours à tous mes petits matheux chéris !

Aujourd'hui je vous présente un petit casse-tête qui devrait vous donner du fil à retordre :)
L'énoncé est le suivant :

__________________
|OOO || OOO || OOO |   arrière
|OOO || OOO || OOO |
|OOO || OOO || OOO |   avant
__________________

Ceci est un magnifique plateau. Il peut porter jusqu'à 27 verres ! Mais lorsqu'il s'agit de poser les verres correctement, le serveur s'emmêle souvent les pinceaux… En effet, le serveur va parfois mettre les verres d'un même client de façon complètement aléatoire sur le plateau, ce qui lui fait multiplier les allers-retours au comptoir pour le même client (car le serveur prend 3 verres côtes à côte | OOO | et les amènes au comptoir) et fait en somme attendre les clients plus longtemps (Tous les clients partent quand leur dernier verre est servi, donc si on sert complètement un client dès le début, il pourra partir plus vite). Ce serait moins frustrant pour les clients si le serveur donnait tous les verres à un client d'abord, puis au suivant, puis au suivant, etc.

Pratique :                                                      Pas pratique :
__________________                                   __________________
|CDD || EEF || GGG |                                    |ABC || CDD || AAG |
|CCC || CCC || BBB |                                      |BBF || CCC || CEG |
|AAA || AAA || BBB |                                    |ABG || ABC || ABC |
__________________                                   ___________________

Je précise que le serveur ne peut accéder à la deuxième ligne de la première colonne qu'après avoir vidé la première de cette même colonne et idem pour la ligne 2 et 3.
Le nombre de clients peut être compris entre 1 et 27.
Le plateau peut être complètement rempli, ou, certaines places peuvent être laissées vides.

On mesure la proximité des verres ainsi : Si deux verres du même client sont sur le même groupe de trois verres côtes à côtes : 2 points de proximité. Si deux verres du même client sont sur deux groupe de trois verres adjacent (gauche-droite, haut bas, mais pas en diagonale) : 1 point de proximité.

La question est : Comment agencer les verres sur le plateau pour augmenter le plus possible le score de proximité ?

On attend comme réponse une fonction (ou un programme) qui prenne en entrée une liste contenant le nombre de boisson de chaque client. (Exemple pour un client_1 ayant pris 2 boissons et un client_2 ayant pris 3 boissons, la liste sera [2,3]) et qui retourne en sortie un code des positions des boissons de chaque client. (1.1.0|2.2.2|0.0.0|…|0.0.0).

J'espère que ce problème vous amusera. Bonne chance à tous !