IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Langage Perl Discussion :

Programmation autours d'un jeu [KHALOU]


Sujet :

Langage Perl

  1. #1
    Candidat au Club
    Profil pro
    Inscrit en
    Février 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2013
    Messages : 3
    Points : 2
    Points
    2
    Par défaut Programmation autours d'un jeu [KHALOU]
    Bonjour,
    Je recherche un programmeur qui pourrait m’aider a faire tourner un ptit programme au sujet d’un jeu.
    Ce jeu se nomme KHALOU et est disponible gratuitement sur Itunes pour Iphone et Ipad.
    https://itunes.apple.com/fr/app/khalou/id589404904?mt=8
    Je vous laisse en lire les règles. Voici mes requêtes :
    Il existe pour ce jeu 2^16 = 65536 positions différentes.
    Les jetons de ce jeu peuvent se retourner de différentes façons. Je cherche un petit script a faire tourner qui pourrait me donner :
    *Pour chacune des positions : le nombre de retournement minimum pour rendre le damier du jeu tout blanc (le but du jeu). Cela est toujours faisable en 5 retournements minimum (démontré via théorie des groupes).
    *Trouver ainsi le nombre totale de positions résolvables en : 1, 2, 3, 4 et 5 retournements minimum.

    Qui pourrait m’aider pour cette programmation ?
    ****************************

    Regles : Le Khalou est un jeu de plateau 4X4 comportant des jetons bifaces (noires et blanches).

    Le principe du jeu est le suivant :

    *Le jeu débute par une répartition aléatoire des jetons (et de leurs faces visibles) sur le plateau
    *Le but est de parvenir en une succession de mouvements différents à un plateau de jeu tout blanc (tous les jetons avec leurs faces visibles blanches).

    *2 Types de mouvements principaux sont autorisés :

    *Retournement des faces visibles sur une ligne, colonne, ou grande diagonale. Dans ce cas chacun des 4 jetons sur toute la ligne, colonne ou diagonale sélectionnée voit sa face visible changer de couleur.




    *Retournement des faces visibles sur « un coude » : le coude est une position en « L » impactant 3 jetons dans n’importe quelle direction. Chacun des 3 jetons sélectionnés par ce retournement voit ainsi sa face visible changer de couleur.


    Le but du jeu du Khalou est donc de rendre blancs tous les jetons uniquement grâce à ces types de retournements. Cela est toujours possible en 5 retournements maximum.

    **************************************

    Idee d'algorithme :

    Il existe 2^16-1 positions = 65.535. En effet on ne compte pas la position avec jetons tout blancs.
    *On peut représenter chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et faire tourner toutes les possibilités. En ne comptant pas celle composée de 16 chiffres 0.
    *Il existe 46 mouvements possibles. Chaque mouvement permet de changer 3 ou 4 chiffres du nombre désignant la position initial. Par exemple si les couleurs des 16 jetons sont représentées dans le chiffres de gauche a droite et de haut en bas alors le retournement de la ligne du haut change les 4 premiers chiffres du nombre a 16 chiffres représentant la position d’origine.
    Ainsi si la position d’origine est : 1000.1100.0001.1010 retourner la première ligne aboutit à la position notée : 0111.1100.0001.1010
    Ou si la position d’origine est : 1000.1100.0001.1010 retourner le premier coude aboutit à la position notée : 0100.0100.0001.1010
    Le but étant avec un minimum de retournements d’aboutir au chiffre : 0000.0000.0000.0000
    *Il suffit alors de faire tourner les 65.535 positions et pour chacune d’elles de modifier le chiffre de cette position avec les 46 puis 46^2 puis 46^3 puis 46^4 retournements possibles.
    Quand le chiffre 0000.0000.0000.0000 apparait (cela arrivera plusieurs fois souvent) on note le nombre de retournements minimum utilisés. Sinon c’est qu’il eut fallu 5 retournements.
    Ce n’est de loin pas le meilleur algorithme mais selon moi le plus simple.

    D’autres idées ????

  2. #2
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Alors, à vue de nez, sur une position de départ donnée, il y a 5 puissance 46 parties possibles. C'est énorme (environ 1,4 x 10 puissance 32), il n'est sans doute pas possible d'examiner toutes les parties possibles dans un temps raisonnable. L'approche force brute ne marche donc sans doute pas. Il faut donc trouver des moyens d'élaguer rapidement et à chaque étape les mouvements non rentables, pour que l'arbre des possibilités reste raisonnable.

    Mais il faut se méfier, il semble très possible que, dans certains cas, la solution optimale passe par une augmentation initiale du nombre des pions noirs, en vue de les réorganiser pour rendre les coups suivants plus efficaces. Un peu comme le joueur de dames qui donne des pions "à manger" à son adversaire pour mieux le surprendre en fin de compte, ou comme les très bons joueurs de Rubik's Cube qui développent des stratégies "non progressives" (quatre coups avant la fin, on n'a pas vraiment l'impression d'avoir progressé).

    Hmmm, le sujet me paraît intéressant, et il y a même peut-être des aspects théoriques à creuser, mais je n'ai pas trop le temps de travailler sur ce genre de truc en-dehors des week-ends.

  3. #3
    Candidat au Club
    Profil pro
    Inscrit en
    Février 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2013
    Messages : 3
    Points : 2
    Points
    2
    Par défaut
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.

    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

  4. #4
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par lepatagon Voir le message
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Exact, je me suis misérablement planté.

    Mais ça fait tout de même presque 206 millions de possibilités.

    Citation Envoyé par lepatagon Voir le message
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.
    Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps pa.

    Citation Envoyé par lepatagon Voir le message
    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.

  5. #5
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par lepatagon Voir le message
    Je ne suis pas d'accord, je dirais plutot 46 puissance 5.
    Exact, je me suis misérablement planté.

    Mais ça fait tout de même presque 206 millions de possibilités (pour chacune des 65-k positions de départ).

    Citation Envoyé par lepatagon Voir le message
    Et en partant du principe nque 2 retournements identiques s'annulent il faut au max 46*45*44*43*42 retournements.
    Deux retournements identiques ne s'annulent réellement que s'ils sont consécutifs. Ils ne s'annulent pas si une ou plusieurs pièces concernées ont été retournées entre temps par un autre coup.

    Citation Envoyé par lepatagon Voir le message
    De plus comme on sait que tout est resoluble en 5 retournements max il ne faut pour chacune des 64.000 positions traiter que 46*45*44*43 enchainements possibles et retenir celui qui occasionne le moins de retournements.
    46*45*44*43 enchainements possibles? Pourquoi pas 46*45*44*43*42? Il est tout de même utile de savoir quel(s) enchaînement(s) conduisent à une solution, non? De plus, si l'on ne trouve pas de solution pour une position de départ donnée, alors on sait que le programme a un bug, ce qui n'est pas inutile à savoir. En revanche, il est vrai que l'on peut arrêter le parcours de l'arbre s'il reste plus de 4 pions noirs après le quatrième coup (ou plus de 8 après le troisième coup), ce qui peut alléger assez nettement le nombre de solutions à tester.

    L'algorithme peut être très simple en principe, la seule chose un peu casse-pieds est de coder la liste des coups possibles.

    Mais je persiste à penser qu'il faut penser à des stratégies d'optimisation pour réduire le nombre de solutions à visiter.

  6. #6
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Cependant, les 206 millions de combinaisons ne seront pas appliquées pour toutes les grilles, puisqu'un certains nombre ne nécessiterons que 1, 2, 3 ou même 4 retournements (206M est un max)

    La force brute se programme facilement : si le temps est trop long pour obtenir le résultat, il est possible d'envisager des heuristiques ou des stratégies de recherche (comme prioriser certains mouvement pouvant mener plus vite au résultat, notamment par exemple, choisir tout de suite le bon retournement pour des matrices où seul un retournement est nécessaire, ce qui élague des tas de cas/sous cas).
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  7. #7
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Bon, après quelques essais, la force brute trouve bien des résultats, mais les premiers trouvés ne sont pas optimaux... Si l'on ne veut donc pas parcourir toutes les combinaisons comme je l'indiquais dans mon post précédent, il est donc impératif d'utiliser une stratégie particulière pour trouver les mouvements minimaux.

    Donc j'ai dit n'importe quoi. Je suppose qu'il s'agit d'un exercice de math ou d'algorithmique ?
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

  8. #8
    Membre du Club
    Homme Profil pro
    BioInformaticien
    Inscrit en
    Décembre 2012
    Messages
    49
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : BioInformaticien
    Secteur : Service public

    Informations forums :
    Inscription : Décembre 2012
    Messages : 49
    Points : 63
    Points
    63
    Par défaut
    Une façone diminuer drastiquement le nombre de solutions dans ce jeu est de supprimer toutes les situations équivalentes par symétrie... Par exemple :

    1010
    0010
    0110
    0101

    est la même chose que :

    0001
    1100
    0111
    1000

    qui est la même chose que :
    1000
    0011
    1110
    0001

    etc...

    pour chaque plateau, on peu le tourner de 90°, ou faire des symétries horizontales et verticales.

    ça doit diminuer drastiquement ton nombre de cas.

    Dans le même genre, je me demande ce qui serait le plus rentable entre
    1/ tester tous les coups possibles afin de résoudre une étape
    2/ avoir en mémoire toutes les possibilités à 1 coups en mémoire

    Par exemple si tu as toutes les possibilités après un coup, tu n'as plus "qu'à atteindre une de ces possibilités en 4 coups etc...

    Tu as dis que tu avais très peu de coups possibles. Il me sembles assez facile de comparer 40 nombres.

  9. #9
    Candidat au Club
    Profil pro
    Inscrit en
    Février 2013
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2013
    Messages : 3
    Points : 2
    Points
    2
    Par défaut
    la deuxieme option me semble bien plus interessante

  10. #10
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Je verrais bien une attaque en sens inverse. Recenser (dans un hash, par exemple) toutes les situations solubles en un coup. Puis toutes les situations permettant d'arriver à ces situations en un coup, et ainsi de suite. Ainsi une heuristique des meilleurs coups pour chaque situation.

  11. #11
    Membre du Club
    Homme Profil pro
    BioInformaticien
    Inscrit en
    Décembre 2012
    Messages
    49
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : BioInformaticien
    Secteur : Service public

    Informations forums :
    Inscription : Décembre 2012
    Messages : 49
    Points : 63
    Points
    63
    Par défaut
    De manière générale il me semble que deux approches sont possibles pour la résolution de cet algorithme :

    La première serait de partir de la solution, de faire tous les mouvements possibles, recenser les solutions dans une hash, puis faire un deuxième mouvement. La difficulté serait ici de minimiser le nombre de mouvements que l'on tente aux tours suivants le premier. La hash permettrait par exemple de "mémoriser" les coups menant a cette solution. L'avantage, c'est que l'on a au maximum 65k arrangements au tour 4, donc 65k*42 opérations à faire pour analyser les arrangements au tour 5 (on a moins de 1 million d'opérations à faire au final, ce qui est acceptable je pense... Et ça peut se programmer assez salement )

    Une deuxieme approche serait un peu plus combinatoire. En gros l'idée serait d'utiliser les symétries des différents mouvements pour diminuer les calculs. Par exemple, tous les coups ont un correspondant en faisant une symétrie à 90°

    Ensuite il "suffit" de faire une matrice avec les différents mouvements, et de résoudre toutes les combinatoires etc... Ca n'est probablement pas très dur à programmer, et surement assez rapide, mais l'algo derrière demande des connaissances qui me dépassent un peu...

  12. #12
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Trouver des situations symétriques (ou équivalentes d'une autre façon) à une situation existante n'est pas trop difficile, détecter que deux situations données sont symétriques ou équivalentes est à mon avis plus ardu. C'est du moins ce que j'avais bien vite constaté quand j'avais eu le même problème à résoudre pour un solveur de Sudoku que je m'étais amusé à faire il y a quelques années. Les modélisations "computionellement" efficaces pour analyser les situations et parcourir les arbres de possibilités ne se prêtent généralement pas si facilement à l'étude des symétries et autres équivalences de situations. Mais il est peut-être possible de trouver une modélisation plus efficace que celles auxquelles j'ai pensé.

    Je reste sur l'idée que remonter depuis la solution vers les 65-k situations de départ doit je pense éviter l'explosion exponentielle d'autres méthodes envisageables.

  13. #13
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Je pense qu'il faut travailler en vrai binaire (et non avec des chaînes de caractères de 0 et de 1), le travail est bien plus simple. Comme on ne manipule pas trop souvent le binaire en Perl, voici quelques astuces obtenues après quelques essais.

    Les situations de départ possibles peuvent être simplement modélisées par les 2^16 premiers nombres. Exemple avec seulement les 32 premiers nombres:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    printf "%05b ", $_ foreach 0..31;
    Ce qui imprime:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111
    Pour afficher "proprement" avec 16 chiffres binaires, il suffit de remplacer "%05b " par "%016b ", ce qui donne:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    0000000000000000 0000000000000001 0000000000000010 0000000000000011 0000000000000100 (etc.)
    Les coups possibles doivent également être codés en binaire.

    Par exemple, les retournements de la première rangée, de la seconde, de la troisième et de la quatrième peuvent être respectivement codés ainsi:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    $coup[1] = 0b1111000000000000; # ou 61440
    $coup[2] = 0b0000111100000000; # ou 3840
    $coup[3] = 0b0000000011110000; # ou 240
    $coup[4] = 0b1111; # ou 15
    Si maintenant je prends la position 0000000000000100 (soit 4 en décimal) et que je lui applique le coup 3 ci-dessus, ceci se fait simplement en faisant un ou exclusif entre la position d'origine et le coup:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    $resultat = 0b0000000000000100 ^ $coup[3];
    Ce que je peux aussi bien écrire:

    Ce qui me donne dans ce cas la position 244:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    printf  "%016b", $resultat;
    Soit:

    .

    L'utilisation du ou exclusif est très intéressante puisque, outre sa rapidité, on peut l'utiliser aussi bien pour descendre l'arbre des coups que pour le remonter: si j'ai une position et un coup, le ou exclusif me donne aussi bien le résultat du coup sur la position donnée que la position de départ pour laquelle le coup donné me donnera la position donnée.

    Donc, si je pars de la solution (0000000000000000) et veux trouver toutes les positions d'origine pour lesquelles les quatre coups listés ci-dessus mènent à la solution, il me suffit de faire quelque chose comme cela:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    printf "%016b\n", $solution ^ $_ foreach @coup
    ;

    ce qui m'imprime:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    1111000000000000
    0000111100000000
    0000000011110000
    0000000000001111
    ce qui paraît tout-à-fait correct.

    Pour moi, une fois ces menues difficultés techniques clarifiées, la solution est maintenant évidente.

    Il faut encore:
    - coder le tableau des 46 coups possible (et pas seulement 4 comme ci-dessus); c'est sans doute ce qu'il y a de plus pénible, mais pour 46 coups, ça devrait aller;
    - Implanter un tableau des 65k+ positions possibles, afin de marquer au fur et à mesure toutes celles déjà trouvées (pour ne pas se répéter et s'arrêter à chaque fois dès que possible)
    - Implanter un tableau de tableaux pour répertorier la série de coups nécessaire pour chaque position de départ
    - Mettre en œuvre un algo de parcours en largeur d'abord de l'arbre des coups possibles.

    L'avantage de la solution est que l'on parcourt certes les 206 millions de possibilités, mais on ne le fait qu'une seule fois (et non 65.000 fois). C'est donc tout-à-fait jouable dans un temps très limité.

    Voilà, j'ai toutes les cartes en main, et vous aussi, pour coder la solution. A vue de nez, à part la définition des coups possible, ça tient facilement en moins de 30 lignes de code.

    Il se fait tard et j'arrête pour ce soir. Je n'aurai sans doute pas le temps de me pencher à nouveau là-dessus avant sans doute demain soir. Que celle ou celui qui veut proposer une solution basée sur mes propositions ci-dessus soit bienvenu(e), je n'ai pas de copyright là-dessus (ce que j'écris ici est du domaine public) et j'ai fait ce post dans le seul but d'aider celle ou celui qui désire s'y mettre. Si personne ne le fait, j'espère proposer la solution dès que j'aurais le temps de m'y remettre. A mon avis, une ou deux heures de codage devraient suffire, mais, bon, pas sûr, je suis parfois trop optimiste sur ce genre d'estimations.

  14. #14
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Je poursuis sur les opérations et les affichages, avec cette fois 10 coups (rangées, colonnes et diagonales).


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    my @coup =  (0b1111000000000000, 0b0000111100000000, 0b0000000011110000, 0b1111); # rangées
    push @coup, (0b1000100010001000, 0b0100010001000100, 0b0010001000100010, 0b0001000100010001); #colonnes
    push @coup, (0b1000010000100001, 0b0001001001001000); # diagonales 
    my @results;
    push @results, sprintf  "%016b\n", $solution ^ $_ foreach @coup;
    Ce qui me donne:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    1111000000000000
     0000111100000000
     0000000011110000
     0000000000001111
     1000100010001000
     0100010001000100
     0010001000100010
     0001000100010001
     1000010000100001
     0001001001001000
    Je peux obtenir un affichage plus "parlant" des positions obtenues avec un peu de reformatage:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    foreach (@results) {  s/(\d{4})/$1\n/g ; print}
    Ce qui me donne:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    1111
    0000
    0000
    0000
     
    0000
    1111
    0000
    0000
     
    0000
    0000
    1111
    0000
     
    0000
    0000
    0000
    1111
     
    1000
    1000
    1000
    1000
     
    0100
    0100
    0100
    0100
     
    0010
    0010
    0010
    0010
     
    0001
    0001
    0001
    0001
     
    1000
    0100
    0010
    0001
     
    0001
    0010
    0100
    1000

  15. #15
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Voici maintenant les 46 coups codés en binaire:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    my @coup =  (0b1111000000000000, 0b0000111100000000, 0b0000000011110000, 0b1111); # rangées
    push @coup, (0b1000100010001000, 0b0100010001000100, 0b0010001000100010, 0b0001000100010001); #colonnes
    push @coup, (0b1000010000100001, 0b0001001001001000); # diagonales
    push @coup, (0b1100100000000000, 0b1100010000000000, 0b0110010000000000, 0b0110001000000000, 
    		     0b0011001000000000, 0b0011000100000000); # L avec centre première rangée
    push @coup, (0b1000110000000000, 0b0100110000000000, 0b0100011000000000, 0b0010011000000000, 
    		     0b0010001100000000, 0b0001001100000000); # L avec centre deuxième rangée, vers haut
    push @coup, (0b0000110010000000, 0b0000110001000000, 0b0000011001000000, 0b0000011000100000, 
    		     0b0000001100100000, 0b0000001100010000); # L avec centre deuxième rangée, vers bas
    push @coup, (0b0000000011001000, 0b0000000011000100, 0b0000000001100100, 0b0000000001100010, 
    		     0b0000000000110010, 0b0000000000110001); # L avec centre troisième rangée, vers bas
    push @coup, (0b0000100011000000, 0b0000010011000000, 0b0000010001100000, 0b0000001001100000, 
    		     0b0000001000110000, 0b0000000100110000); # L avec centre troisième rangée, vers haut
    push @coup, (0b0000000010001100, 0b0000000001001100, 0b0000000001000110, 0b0000000000100110, 
    		     0b0000000000100011, 0b0000000000010011); # L avec centre dernière rangée, vers haut
    Un affichage du tableau trié et en décimal me permet de vérifier que je n'ai pas de doublons:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    15 19 35 38 49 50 70 76 98 100 140 196 200 240 304 560 608 784 800 1120 1216 1568 1600 2240 3136 3200 3840 4369 4680 4864 8738 8960 
    9728 12544 12800 17476 17920 19456 25088 25600 33825 34952 35840 50176 51200 61440
    Soit dit en passant, maintenant que j'ai l'expression décimale des 46 coups possibles, il est plus facile d'initialiser les 46 coups possibles:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    @coup = qw /15 19 35 38 49 50 70 76 98 100 140 196 200 240 304 560 608 784 800 1120 1216 
                 1568 1600 2240 3136 3200 3840 4369 4680 4864 8738 8960 9728 12544 12800 17476 
                 17920 19456 25088 25600 33825 34952 35840 50176 51200 61440 /;
    Si je fais un affichage plus "parlant" de mes 46 coups":

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    @e = map { sprintf "%016b\n", $_} @coup;
    s/(\d{4})/$1\n/g and print foreach @e;
    cela me donne:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    0000
    0000
    0000
    1111
     
    0000
    0000
    0001
    0011
     
    0000
    0000
    0010
    0011
     
    0000
    0000
    0010
    0110
     
    0000
    0000
    0011
    0001
     
    0000
    0000
    0011
    0010
     
    0000
    0000
    0100
    0110
     
    0000
    0000
    0100
    1100
     
    0000
    0000
    0110
    0010
     
    0000
    0000
    0110
    0100
     
    0000
    0000
    1000
    1100
     
    0000
    0000
    1100
    0100
     
    0000
    0000
    1100
    1000
     
    0000
    0000
    1111
    0000
     
    0000
    0001
    0011
    0000
     
    0000
    0010
    0011
    0000
     
    0000
    0010
    0110
    0000
     
    0000
    0011
    0001
    0000
     
    0000
    0011
    0010
    0000
     
    0000
    0100
    0110
    0000
     
    0000
    0100
    1100
    0000
     
    0000
    0110
    0010
    0000
     
    0000
    0110
    0100
    0000
     
    0000
    1000
    1100
    0000
     
    0000
    1100
    0100
    0000
     
    0000
    1100
    1000
    0000
     
    0000
    1111
    0000
    0000
     
    0001
    0001
    0001
    0001
     
    0001
    0010
    0100
    1000
     
    0001
    0011
    0000
    0000
     
    0010
    0010
    0010
    0010
     
    0010
    0011
    0000
    0000
     
    0010
    0110
    0000
    0000
     
    0011
    0001
    0000
    0000
     
    0011
    0010
    0000
    0000
     
    0100
    0100
    0100
    0100
     
    0100
    0110
    0000
    0000
     
    0100
    1100
    0000
    0000
     
    0110
    0010
    0000
    0000
     
    0110
    0100
    0000
    0000
     
    1000
    0100
    0010
    0001
     
    1000
    1000
    1000
    1000
     
    1000
    1100
    0000
    0000
     
    1100
    0100
    0000
    0000
     
    1100
    1000
    0000
    0000
     
    1111
    0000
    0000
    0000
    Un coup d'oeil rapide semble indiquer que tous les coups sont bien légaux. Donc, a priori, pas d'erreur dans l'initialisation des coups.

    Soit dit en passant, ces 46 coups représentent aussi accessoirement les 46 positions solubles en un seul coup.

  16. #16
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    @Lepatagon: deux petites questions.

    1. Voilà plus de trois jours que l'on ne t'a pas revu ici. Ça ne t'intéresse déjà plus?

    2. Tu veux vraiment explorer le jeu, ou c'est un devoir scolaire qui a été donné?

    Les réponses aux deux questions sont d'ailleurs peut-être liées. Tu devais peut-être rendre le devoir pour jeudi ou vendredi, du coup ça ne t'intéresse plus?

    Bien sûr, je me trompe peut-être complètement (et je souhaite que je me trompe), mais bon, admets qu'il y a lieu de se poser ces questions...

  17. #17
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Hum, bon, toujours pas de nouvelles ni de réponse du Patagon...

    Donc, en l'absence de réponse, je vais m'abstenir pour l'instant de fournir le code de ma solution, mais me contenterai de donner mes résultats:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    il y a 1 positions solubles en 0 coups.
    il y a 46 positions solubles en 1 coups.
    il y a 987 positions solubles en 2 coups.
    il y a 10680 positions solubles en 3 coups.
    il y a 39067 positions solubles en 4 coups.
    il y a 14755 positions solubles en 5 coups.
    Ce qui donne bien au total 65.536 solutions solubles entre 0 et 5 coups (y compris la solution triviale déjà résolue, soluble en 0 coup). L'algorithme utilisé garantissant que chaque position répertoriée est différente, tout indique que le programme est correct et qu'il confirme que toutes les positions de départ sont bien solubles en 5 coups maximum.

    Le programme s'exécute en moins de 3 secondes sur mon PC portable (pas une bête de course et pas un modèle particulièrement récent puisqu'il date de mi 2008), la solution retenue est donc largement assez efficace, me semble-t-il. Une méthode partant en sens inverse de toutes les positions de départ possibles aurait sans doute nécessité deux ou trois jours de calcul, je pense.

    Si l'on met de côté les initialisations et les déclarations initiales, la partie du programme exécutant l'ensemble des calculs comprend trois boucles imbriquées et tient en 11 lignes de code Perl (sans aucun effort de rendre le code particulièrement concis, au contraire, j'ai recherché la clarté).

    J'avais annoncé une ou deux heures de codage en précisant que j'étais peut-être optimiste; ben oui, j'étais optimiste puisque ça m'a pris environ 3 heures à cause de deux petites erreurs stupides qu'il m'a fallu du temps à corriger. A regarder la simplicité de la solution finale, franchement, j'ai un peu honte d'avoir pris autant de temps: en réfléchissant bien et en étant bien concentré, ça doit pouvoir être fait en moins d'une heure, je pense. En même temps, j'ai travaillé dessus en deux jours après 23h30 (et après, dans les deux cas, deux ou trois bons verres de vin au dîner). Le matin à jeun en une seule fois, ça aurait sans doute été plus efficace). ;-)

    Bien sûr, je fournirai sans problème mon code à quiconque inscrit sur ce forum avant la mi-février de cette année me le demande.

  18. #18
    Membre du Club
    Homme Profil pro
    BioInformaticien
    Inscrit en
    Décembre 2012
    Messages
    49
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : BioInformaticien
    Secteur : Service public

    Informations forums :
    Inscription : Décembre 2012
    Messages : 49
    Points : 63
    Points
    63
    Par défaut
    Jolie solution! La mienne était un peu plus sale vu que je n'ai pas l'habitude de faire du binaire... Je restais en décimal et je faisais un tr/2/0/.

    Tu as déjà fourni une bonne partie du code, et presque toute la réflexion qu'il y a derrière. Lepatagon devrait s'en sortir si c'était un projet sur plusieurs semaines .

  19. #19
    Rédacteur/Modérateur

    Avatar de Lolo78
    Homme Profil pro
    Conseil - Consultant en systèmes d'information
    Inscrit en
    Mai 2012
    Messages
    3 612
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Yvelines (Île de France)

    Informations professionnelles :
    Activité : Conseil - Consultant en systèmes d'information
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Mai 2012
    Messages : 3 612
    Points : 12 469
    Points
    12 469
    Billets dans le blog
    1
    Par défaut
    Le truc qui me satisfait réellement dans l'algorithme de ma solution, c'est qu'en remontant depuis la solution (tous les pions blancs, ou 0) vers les positions de départ possibles, je peux éliminer rapidement toutes les solutions non optimales (par exemple, si j'arrive à une position donnée en deux coups, pas besoin de voir si un autre chemin menant à cette même position en 3 coups a de l'intérêt pour la suite, je peux l'éliminer très tôt dans le processus et ne plus m'y intéresser). Résultat: sur les 206 millions de groupes de 5 coups possibles, mon algorithme n'en examine réellement que 2.335.926 (ce n'est pas un calcul théorique, j'ai ajouté un compteur pour le vérifier). Et, au final, l'algo n'examine réellement jusqu'au bout que 65535 chemins.

    L'algorithme élimine donc très efficacement le risque d'explosion combinatoire (malgré ses trois boucles imbriquées).

  20. #20
    Expert confirmé

    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2009
    Messages
    3 577
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 58
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Avril 2009
    Messages : 3 577
    Points : 5 753
    Points
    5 753
    Par défaut
    Bien joué, je dirais
    Plus j'apprends, et plus je mesure mon ignorance (philou67430)
    Toute technologie suffisamment avancée est indiscernable d'un script Perl (Llama book)
    Partagez vos problèmes pour que l'on partage ensemble nos solutions : je ne réponds pas aux questions techniques par message privé
    Si c'est utile, say

Discussions similaires

  1. Programmation pattern missile pour jeu style shoot'em up
    Par mixka13 dans le forum XNA/Monogame
    Réponses: 7
    Dernier message: 19/05/2012, 15h36
  2. programmer une carte d’un jeu de stratégie
    Par swo.line dans le forum Développement 2D, 3D et Jeux
    Réponses: 4
    Dernier message: 10/01/2008, 23h20
  3. Réponses: 1
    Dernier message: 15/03/2007, 21h16
  4. Programmer autour du wifi.
    Par johnnyjohnny dans le forum Développement
    Réponses: 2
    Dernier message: 07/09/2006, 18h20
  5. Help ! Programmer un jeu vidéo
    Par Jay Bee dans le forum DirectX
    Réponses: 7
    Dernier message: 18/03/2004, 19h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo