Basket à New-York
Bonjour, j'ai un petit jeu dont je voudrais si possible connaître une solution.
On dispose de 3 paniers de basket : 1 panier pouvant contenir au maximum 2 ballons, 2 paniers pouvant contenir au maximum 3 ballons. On dispose de 5 ballons. Les 5 ballons sont disposés dans les paniers librement : cela donne une configuration (les ballons ne peuvent pas sortir par le bas des paniers et on ne peut pas insérer ni sortir un ballon par le bas). Le but du jeu est de trouver le nombre minimal de déplacements de ballons pour passer d'une configuration des ballons à l'autre...
Bien sur, cela dépend des configurations...
Mais quel algorithme appliquer pour connaître ce nombre ?
Un dénombrement montre que le nombre de configurations est : N=8*7=56. Il y a donc C=56*55=3080 couples de configurations différentes ça fait un peu beaucoup.
Je pense qu'il faut intégrer dans une stratégie de résolution le fait de commencer à placer les ballons en bas de chaque panier. Dénombrer ça en fonction des configurations et après faire de même avec les 2emes ballons des 2 gros paniers...
Qu'en pensez-vous ?
Merci d'avance de vos réponses.
On dispose de 3 paniers de basket : 1 panier pouvant contenir au maximum 2 ballons, 2 paniers pouvant contenir au maximum 3 ballons. On dispose de 5 ballons. Les 5 ballons sont disposés dans les paniers librement : cela donne une configuration (les ballons ne peuvent pas sortir par le bas des paniers et on ne peut pas insérer ni sortir un ballon par le bas). Le but du jeu est de trouver le nombre minimal de déplacements de ballons pour passer d'une configuration des ballons à l'autre...
Bien sur, cela dépend des configurations...
Mais quel algorithme appliquer pour connaître ce nombre ?
Un dénombrement montre que le nombre de configurations est : N=8*7=56. Il y a donc C=56*55=3080 couples de configurations différentes ça fait un peu beaucoup.
Je pense qu'il faut intégrer dans une stratégie de résolution le fait de commencer à placer les ballons en bas de chaque panier. Dénombrer ça en fonction des configurations et après faire de même avec les 2emes ballons des 2 gros paniers...
Qu'en pensez-vous ?
Merci d'avance de vos réponses.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Les ballons sont indifférenciés?
Les paniers contenant 3 ballons sont différenciés?
Si tel est le cas, je trouve juste 7 9 configurations différentes et pas 58 (simplement on regardant où sont les 3 espaces libres, cela va vite).
Quand les gens auront compris ton 56, ils pourront peut-être comprendre ton 3080, puis comprendre ce que tu veux faire.
Si 1 vide dans le panier à 2, il en reste 2 pour les 2 autres: 3 cas (2;0) (1;1) et 0;2)
Si 0 vide dans le panier à 2, il en reste 3 pour les 2 autres: 4 cas: (3;0) (2;1) (1;2) et (0;3)
Au total 9 cas (et non pas 7 comme je disais).
La question était : Pourquoi le nombre de dispositions serait $\binom{8}{5}$ ?
Tu as 8 emplacements, mais mettre un ballon dans le 1er emplacement du panier 1, et un autre au 3ème emplacement, et aucun au 2ème emplacement, c'est possible ?
S'il y avait 8 paniers avec un ballon maximum par panier, tu aurais aussi 56 ?
Et s'il y avait 2 paniers, avec 7 ballons maximum dans le premier et 1 ballon maximum dans le 2ème , tu aurais aussi 56 ?
Mais avec 2 paniers, avec 8 ballons maximum dans le premier et 1 ballon maximum dans le 2ème , tu aurais 72 ?
Un exemple sera plus parlant.
b=ballon suivi du numéro du ballon
Panier 1: (b4,b2,b3)
Ici je veux dire que le ballon 4 est à l'emplacement le plus bas du panier 1 suivi du ballon 2 à l'emplacement du milieu puis du ballon 3 à l'emplacement le plus haut.
Panier 2 (ne peut contenir que 2 ballons): (b1,rien)
Le ballon 1 est à l'emplacement le plus bas, et il n'y a rien à l'emplacement du haut.
Panier 3: (b5,rien,rien)
L'emplacement du bas contient le ballon 5 et rien au dessus.
A présent on note P=panier
On veut savoir combien de déplacements au minimum de ballons pour obtenir une autre configuration.
Exemple:
On veut obtenir la configuration:
P1:(b4,b2,b3)
P2:(rien,rien)
P3:(b5,b1,rien)
Solution: il suffit de prendre le ballon 1 du panier 2 et de le mettre dans le panier 3. Le nombre de déplacements de ballons minimum est donc 1.
nombre de cas possible = 9 x factorielle (5) = 9 x 120 =1080.
Quelles stratégies mettre en place pour déplacer le moins de ballons possibles d'une configuration à l'autre?
Tu veux trouver un majorant du nombre minimum de coups? Le meilleur majorant?
Tu veux pour chaque position trouver le minimum de coups?
Tu veux un algorithme pour trouver comment passer d'une configuration à l'autre?
Je pense par contre que la réponse va être compliquée dans tous les cas. Peut-être que des spécialistes du Rubik's cube peuvent t'aider à avancer
Merci pour ta réponse.
Donc 1080*1079 exercices. Ou 2 fois moins, parce que trouver le plus court chemin de A vers B revient à trouver le plus court chemin de B vers A.
Il y aurait un autre exercice ambitieux : partant d'une situation quelconque, quel est le plus court chemin qui passe par les 1080 positions, et qui revient à la situation de départ. Le choix de la situation de départ est donc sans impact sur la solution.
Je cherche des formules, des stratégies ou des algorithmes qui permettent de faire ça...
https://fr.wikipedia.org/wiki/Problème_de_plus_court_chemin
Ne pas lancer Djikstra 1080*1079/2 fois, mais beaucoup moins.
Identifier en particulier que les 2 paniers avec 3 emplacements sont interchangeables.
Et en fait, ramener les problèmes à des problèmes plus simples. Dès qu'un ballon est au bon emplacement, et au fond de son panier, on se ramène à un exercice avec 4 ballons seulement.
On doit donc recenser les solutions pour les problèmes avec 1 seul ballon mal placé, puis 2 ballons mal placés etc etc...
Pour réutiliser au maximum les résultats obtenus... et ne pas répéter plein de calculs un million de fois.
convl<-function(l){n<-0 for(i in 1:8){n<-6*n+l[i]} return(n+1)} convn<-function(n){l<-c(0,0,0,0,0,0,0,0);i<-8 while(n>0){l[i]<-n%%6;n<-n%/%6;i<-i-1} return(l)} pk<-function(aa,bb){l<-array(100,(6**8));na<-convl(aa);l[na]<-0;nb<-convl(bb);i<-(-1) while(l[nb]==100){i<-i+1;m<-which(l==i) for(k in m){a<-convn(k) if(a[1]>0){y<-max(which(a[1:3]>0)) if(a[5]==0){z<-3+min(which(a[4:5]==0)) a1<-a;a1[y]<-0;a1[z]<-a[y] l[convl(a1)]<-min(l[convl(a1)],i+1)} if(a[8]==0){z<-5+min(which(a[6:8]==0)) a2<-a;a2[y]<-0;a2[z]<-a[y] l[convl(a2)]<-min(l[convl(a2)],i+1)}} if(a[4]>0){y<-3+max(which(a[4:5]>0)) if(a[3]==0){z<-min(which(a[1:3]==0)) a3<-a;a3[y]<-0;a3[z]<-a[y] l[convl(a3)]<-min(l[convl(a3)],i+1)} if(a[8]==0){z<-5+min(which(a[6:8]==0)) a4<-a;a4[y]<-0;a4[z]<-a[y] l[convl(a4)]<-min(l[convl(a4)],i+1)}} if(a[6]>0){y<-5+max(which(a[6:8]>0)) if(a[3]==0){z<-min(which(a[1:3]==0)) a5<-a;a5[y]<-0;a5[z]<-a[y] l[convl(a5)]<-min(l[convl(a5)],i+1)} if(a[5]==0){z<-3+min(which(a[4:5]==0)) a6<-a;a6[y]<-0;a6[z]<-a[y] l[convl(a6)]<-min(l[convl(a6)],i+1)}}}} return(l[nb])} > pk(c(1,2,3,4,5,0,0,0),c(1,2,3,4,0,5,0,0)) [1] 1 > pk(c(1,2,3,4,5,0,0,0),c(3,2,1,5,4,0,0,0)) [1] 13@lourrran ce que tu dis suggère du récursif mais il faut faire attention: les paniers ont des emplacements en moins.
A vous 2: Je vais essayer de regrouper les configurations. L'idée est plus de faire du calcul mental que de la programmation mais je vais faire les 2... Les 2 sont un bon exercice intellectuel.
Pour un départ en (3,2,0) :
C'est bizarre parce que dans ce jeu, je n'ai jamais eu des configurations espacées de plus de 10... Tu es sur de ce que tu as fait?
L'algo part avec une liste de toutes les positions. Il remplit inscrit petit à petit dans la liste la distance de celles qui sont à une distance 1, puis 2, puis 3, jusqu'à obtenir la distance de la position finale. C'est un des algos les plus efficaces pour ce problème !
Edit : (P1 de taille 3, P2 de taille 2, P3 de taille 3)
Comment passes-tu en 10 coups de
P1 : 1,2,3 (la 1 étant "au fond")
P2 : 4,5
P3 : vide
à
P1 : 4,5,1
P2 : vide
P3 : 2,3
?
Moi j'ai, en 14 déplacements :
[1] 1 2 3 4 5 0 0 0
[1] 1 2 3 4 0 5 0 0
[1] 1 2 3 0 0 5 4 0
[1] 1 2 0 3 0 5 4 0
[1] 1 0 0 3 2 5 4 0
[1] 1 4 0 3 2 5 0 0
[1] 1 4 5 3 2 0 0 0
[1] 1 4 5 3 0 2 0 0
[1] 1 4 0 3 0 2 5 0
[1] 1 0 0 3 0 2 5 4
[1] 0 0 0 3 1 2 5 4
[1] 4 0 0 3 1 2 5 0
[1] 4 5 0 3 1 2 0 0
[1] 4 5 1 3 0 2 0 0
Je suggérais du récursif, oui, mais ça se gère.
Une position peut être décrite par '12x.3x.45x' : chaque panier a une case vide.
Le problème (12x.3x.45x ; 134.xx.25x ) se ramène en fait au problème (2x.3x.45x : 34.xx.25x ) Toujours 3 paniers , mais de taille 2, 2 et 3
Avec quand même des réserves.
Le problème (12x.34.5xx ; 25x.34.1xx ) ne peut pas se ramener au problème (12x.5xx ; 25x.1xx ). Il faut qu'il y ait toujours 3 paniers utilisables.
Quand je parlais de familles de configurations, je pensais plutôt à (12x.3x.45x ; 134.xx.25x) et (21x.3x.45x : 234.xx.15x) : ces 2 problèmes sont les mêmes.
Quand on a résolu 1 problème, on en a en fait résolu 120. Et même quasiment le double, vu que les paniers 1 et 3 sont interchangeables.
Le premier qui convertit une liste (que je considere comme un entier en base 6) et un entier en base 10
Le second qui fait le travail inverse, qui transforme un entier en base 10 en une liste avec des nombres de 0 à 5.
De telle sorte que chaque position possible soit associé à un entier entre 0 et 6^8. Bien évidemment, ce n'est pas une bijection, car il y a seulement 1080 positions possibles, mais ce n'est pas un soucis.
Mon programme veut relier la liste a à la liste b
Du coup, je pars avec une liste L 6^8 éléments remplie de nombres 100.
J'initialise en mettant l'élément a de la liste L à 0. (Car a est à une distance 0 de lui même)
Et ensuite, en boucle :
Je cherche toutes les positions accessibles à partir de la position a (il y en a au plus 6). Je leur donne la valeur 1 dans la liste L (distance 1)
Je cherche toutes les positions accessibles à partir des positions ayant une valeur 1. Je leur donne la valeur 2 si elles n'ont pas encore eu de valeur (autre que 100)
Je cherche toutes les positions accessibles à partir des positions ayant une valeur 2...
Puis quand le nombre associé à b a une valeur autre que 100, c'est fini.
Remarques : Si on veut juste la distance entre a et toutes les positions, on fait la boucle 14 fois, et toutes les positions accessibles auront une valeur (distance)
Si on veut connaître le chemin, il faut le faire en remontant. Je pars de b, et je cherche toutes les positions accessibles de b ayant une valeur juste plus petite de 1, et ainsi de suite. Cela me donnera un des chemins minimaux jusque a.
J'espère que c'est clair !
Mais je me rends compte que j'aurais pu faire plus efficient, remplir la liste avec les distances jusqu'à ce que la distance maximale (hormis les 100) soit plus petite que le nombre d'itérations (ce qui voudrait dire que on a pas trouvé de nouvelles positions à explorer, i.e. on les as toutes explorées)
Ben si tu regarde les paniers de droite à gauche ou bien de gauche à droite, sans s'occuper du numéro des ballons tu tomberas forcément sur une de ces configurations :
(En gros je renommé le panier le plus rempli entre le 1 et le 3 panier 3, et je renomme les ballons de 1 a 5 en commençant par celui au fond du nouveau panier 1)
(3,2,0)
(3,1,1)
(3,0,2)
(2,2,1)
(2,1,2)
Du coup, ce sont les 5 configurations de "base". Après pas le choix malheureusement, il faut calculer la distance de ces 5 chemins a toutes les possibilités, cette fois ci je ne peux pas réduire les cas par symétrie ou en changeant les numéros de ballons.
Après, au lieu de faire la liste des distances pour 1080 positions, je la fais pour 5.
Mais si tu ne veux la distance qu'au cas de base, ben pas besoin de faire 5 positions, il suffit de partie d'une seule (le cas de base)
Toutes les positions de départ peuvent se ramener à une de ces 5 positions, par une renumérotation des paniers (inverion des paniers 1 et 3) et/ou par une permutation des 5 ballons.
Pour un exercice donné ( position de départ et position d'arrivée imposées), on peut se ramener à cette position de départ, ... et donc recoder aussi la position d'arrivée visée, en appliquant les mêmes permutations.
A partir de ces 5 positions de bases, il recense toutes les positions (1080 max) qu'on peut atteindre en 1 mouvement, puis en 2 mouvements , puis en 3 mouvements.
En éliminant les doublons à chaque fois.
Partant de 123.4x.5xx , on peut faire 12x.43.5xx puis 12x.4x.53x ...mais ça n' pas d'intérêt . La position 12x.4x.53x pouvait aussi être atteinte par un seul mouvement.
Il calcule les chemins en partant des 5 positions de bases du départ, mais il cherche comment atteindre les 1080 positions finales, pas uniquement les 5 positions de bases.
Ton problème est un problème cousin.
Et donc, on peut avoir 2 techniques : commencer par atteindre une position du type ---.--.1-- ou bien commencer par atteindre une position du type 4--.--.---
Ou bien faire en sorte d'atteindre ---.--.1-- puis très vite, 4--.--.1--
Les pires configurations nécessitent 14 mouvements. Et j'imagine que les configurations qui nécessitent 10 mouvements ou plus sont majoritaires.
Dérouler un process, partant de 123.45.xxx, je vois quels mouvements il faut faire pour emmener le 1 en bas du panier 3, puis une série de mouvements pour emmener le 4 en bas du panier 1 ... tout ça en aveugle, c'est un exploit.
Et on n'a pas du tout l'assurance que le chemin obtenu soit le plus court.
https://www.scientificbraintrainingpro.fr/nos-programmes/presco?module=Fonctions-Executives
Tu veux devenir meilleur à ce jeu, de tête. Pour cela, pas de miracle, Je te conseille un entrainement bête et méchant.
Tu choisis une situation de départ, d'arrivée, et tu essaies de faire au mieux.
Puis tu regarde via un algo (je peux te filer le mien) si il y avait un chemin plus court, et surtout quel est ce chemin, et tu l'analyses.
Je pense que tu devrais vite voir les bons coups, et être aussi performant que l'algo.
En revanche, je pense que malheureusement, je pense que ce jeu est trop spécifique pour être réellement intéressant cognitivement ! Tu vas juste apprendre par cœur les meilleurs coups et ne plus réfléchir, comme on le ferait pour jouer au morpion.
Je me demandais pourquoi ce titre 'Basket à New-York', pourquoi ces questions autour du calcul mental, et tu as trouvé la réponse.