Répondre à la discussion
Affichage des résultats 1 à 24 sur 24

Résoudre un vieux puzzle en Python



  1. #1
    Loosgin

    Résoudre un vieux puzzle en Python


    ------

    Bonjour à tous,

    Je monte en compétence en python, et je suis un ouvrage que je conseille à tous (surtout pour ses exercices ) : "A Practical Introduction to
    Python Programming".

    Je suis bloqué à un exercice, en effet, il me demande ( je ne traduis pas car je crains de ne pas avoir bien compris l'énoncé) :
    25. Here is an old puzzle question you can solve with a computer program. There is only one
    five-digit number n that is such that every one of the following ten numbers shares exactly
    one digit in common in the same position as n. Find n.
    01265, 12171, 23257, 34548, 45970, 56236, 67324, 78084, 89872, 99414
    Voilà ce que j'obtiens:
    "[0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,2 ,3 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,1 ,0]
    [0 ,0 ,0 ,0 ,1]
    [0 ,0 ,0 ,0 ,1]
    [0 ,1 ,0 ,0 ,0]
    [0 ,1 ,0 ,0 ,1]"

    Le problème ce que je n'ai pas trouvé le rang n. Quelqu'un peut m'aider ?

    Voici mon code source : (il y a normalement pas d'erreur => je n'ai pas résultat car je crois que je n'ai pas bien compris l'énoncé)
    Code:
    L=[[0,1,2,6,5],[1,2,1,7,1],[2,3,2,5,7],[3,4,5,4,8],[4,5,9,7,0],[5,6,2,3,6],[6,7,2,3,4],[7,8,0,8,4],[8,9,8,7,2],[9,9,4,1,4]]
    scoreRang=0
    suiteCommun=[[0 for j in range(5)] for i in range(10)]
    
    for i in range(len(L)):
        
        for j in range(len(L[0][:])):
            scoreRang=0
            ##parcours en bas
            if i != (len(L)-1):
                for k in range(i+1,len(L)):           
                    if(L[i][j] == L[k][j]):
                        scoreRang=scoreRang+1
            ##parcours en haut
            elif i!=0:
                 for k in range(i-1,0,-1):           
                    if(L[i][j] == L[k][j]):
                        scoreRang=scoreRang+1
            
            if scoreRang >= 1:
                suiteCommun[i][j]=1
            else:
                suiteCommun[i][j]=0
            scoreRang=0

    -----
    Dernière modification par Loosgin ; 15/09/2020 à 21h21.

  2. Publicité
  3. #2
    Jack
    Modérateur

    Re : Résoudre un vieux puzzel en Python

    si j'ai bien compris, n n'est pas rang, mais un nombre de 5 chiffres, partageant un de ses chiffres à la même position que chacun de ces 10 nombres. Il faut deviner la valeur de n.

    Pour le reste, je ne connais pas assez python pour t'être d'une grande aide.

  4. #3
    Loosgin

    Re : Résoudre un vieux puzzel en Python

    Très bien, merci.
    Pour moi, il y en a pas car si c'était le cas : n = [1,1,1,1,1] et là il y en a pas

  5. #4
    umfred

    Re : Résoudre un vieux puzzel en Python

    l'énoncé c'est de trouver un nombre à 5 chiffres dont la particularité est que les 10 nombres donnés ne partagent qu'un seul chiffre à leur position avec le nombre à trouver. c'est un peu comme au jeu du mastermind où tu aurais dix combinaisons qui ont tous une seule bonne couleur bien positionnée, et il faut que tu trouves la bonne combinaison.

    En fait, je pense que tu n'es pas loin de la solution (je peux me tromper):
    dans ton tableau de résultat, on remarque que la ligne 4 et la colonne 1 sont toutes à 0, donc en prenant le nombre à l'intersection, le chiffre devrait être unique; ensuite, on prend le chiffre qui donne le résultat 1 dans chaque colonne, et on devrait avoir la bonne combinaison au final

  6. A voir en vidéo sur Futura
  7. #5
    Jack
    Modérateur

    Re : Résoudre un vieux puzzel en Python

    J'ai mal formulé en effet:
    il faut trouver un nombre de n 5 chiffres tel que chacun des 10 nombres partage un et seul de ses chiffres avec n à la même position.

    PS : grillé par umfred

  8. #6
    polo974

    Re : Résoudre un vieux puzzle en Python

    une solution:
    30274
    Jusqu'ici tout va bien...

  9. Publicité
  10. #7
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    Oui, on peut la trouver sur le net. Les explication sont souvent un simple copier coller.

  11. #8
    pm42

    Re : Résoudre un vieux puzzle en Python

    Citation Envoyé par polo974 Voir le message
    une solution:
    30274
    Aucun intérêt. On peut trouver les solutions de la plupart des choses en faisant une recherche mais qu'est ce que cela apprend à quelqu'un qui cherche à faire marcher un algo ?

  12. #9
    umfred

    Re : Résoudre un vieux puzzle en Python

    Citation Envoyé par polo974 Voir le message
    une solution:
    30274
    cette solution n'est pas correcte (j'ai aussi trouvé sur un forum l'algo qui donne cette réponse)
    mais il n'y a aucune des 10 valeurs qui possède un zéro à la position des milliers.

  13. #10
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    Citation Envoyé par umfred Voir le message
    cette solution n'est pas correcte (j'ai aussi trouvé sur un forum l'algo qui donne cette réponse)
    mais il n'y a aucune des 10 valeurs qui possède un zéro à la position des milliers.
    Ca m'avait étonné également dans un premier temps, mais en relisant bien l'énoncé cette valeur est correcte car ce sont les 10 valeurs qui doivent partager un chiffre avec 30274 à la même position, pas l'inverse.

  14. #11
    umfred

    Re : Résoudre un vieux puzzle en Python

    arf j'ai le cerveau qui fait des bonds

  15. #12
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    En tout cas, je vous remercie pour vos précisions, vous m'avez bien aidé à déchiffrer l'énoncé du problème.
    Le tuplet [0,1,0,1,0] fonctionne ? Ou il faut que chacun des chiffres du tuplet n soit différent entre-eux ?
    Dernière modification par Loosgin ; 16/09/2020 à 17h58.

  16. Publicité
  17. #13
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    Citation Envoyé par Loosgin Voir le message
    Le tuplet [0,1,0,1,0] fonctionne ? Ou il faut que chacun des chiffres du tuplet n soit différent entre-eux ?
    En quoi 23257 par exemple a-t-il un chiffre commun avec 01010?

  18. #14
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    Je te remercie pour ta réponse Jack, je l'avais fait dans le mauvais sens.
    [9, 8, 2, 7, 8]

    [0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,2 ,3 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,0 ,1]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,1 ,0 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [1 ,0 ,0 ,0 ,0]
    Si le résultat est bon, je mets l'algorithme associé (je tiens à préciser, sous réserve de résultat juste, il ne fait pas dans la dentelle ^^).

    mon tableau ne prend pas en compte certain chiffre...
    Dernière modification par Loosgin ; 16/09/2020 à 20h35.

  19. #15
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    [9, 8, 2, 7, 8]

    [0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,2 ,3 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [0 ,0 ,1 ,0 ,0]-1
    [0 ,0 ,0 ,1 ,0]-1
    [0 ,0 ,1 ,0 ,0]-1
    [0 ,0 ,0 ,0 ,1]-1
    [0 ,0 ,0 ,1 ,0]-1
    [0 ,0 ,1 ,0 ,0]-1
    [0 ,0 ,1 ,0 ,0]-1
    [0 ,1 ,0 ,0 ,0]-1
    [0 ,0 ,0 ,1 ,0]-1
    [1 ,0 ,0 ,0 ,0]-1
    =1,1;4, 3 1
    Je confirme mon résultat [9, 8, 2, 7, 8]... VOus êtes d'accord avec moi ?

  20. #16
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    A vrai dire, je ne vois pas trop à quoi correspondent ces 0 et ces 1.
    Ton programme ne devrait-il pas simplement afficher tout simplement n, donc 30274 à priori?

  21. #17
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    30274 ne marche pas a priori.
    Affiche 1, quand au rang considéré (se situeentre 0 et 4 ), le chiffre est en commun avec le nombre testé.
    Affiche 0, quand au rang considéré (se seitue entre 0 et 4), le chiffre n'est pas en commun avec le nombre testé.
    Par exemple, si je prends [0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0]

    [0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,2 ,3 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [1 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,1]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,0 ,0]

  22. #18
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    Pour
    [3, 0, 2, 7, 4]

    [0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,2 ,3 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [0 ,0 ,1 ,0 ,0]-1
    [0 ,0 ,0 ,1 ,0]-1
    [0 ,0 ,1 ,0 ,0]-1
    [1 ,0 ,0 ,0 ,0]-1
    [0 ,0 ,0 ,1 ,0]-1
    [0 ,0 ,1 ,0 ,0]-1
    [0 ,0 ,1 ,0 ,1]-2
    [0 ,0 ,0 ,0 ,1]-1
    [0 ,0 ,0 ,1 ,0]-1
    [0 ,0 ,0 ,0 ,1]-1
    1, 0 ,3 ,3 ,3

    Mon programme n'a pas retenu cette solution car un nombre partage 2 chiffres avec la solution proposée

  23. Publicité
  24. #19
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    En quoi 30274 ne répond-il pas à l'énoncé du problème?

  25. #20
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    Comme tu l'as écrit : "il faut trouver un nombre de n 5 chiffres tel que chacun des 10 nombres partage un et seul de ses chiffres avec n à la même position."

    "un et seul "

    Le nombre 7 :[6 ,7 ,2 ,3 ,4] partage 2 chiffres avec le nombre testé : [3, 0, 2, 7, 4]

  26. #21
    Jack
    Modérateur

    Re : Résoudre un vieux puzzle en Python

    Je pense que tu as mal saisi les données: c'est 67324 et pas 67234

  27. #22
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    Ah oui, effectivement, merci !
    [3, 0, 2, 7, 4]

    [0 ,1 ,2 ,6 ,5]
    [1 ,2 ,1 ,7 ,1]
    [2 ,3 ,2 ,5 ,7]
    [3 ,4 ,5 ,4 ,8]
    [4 ,5 ,9 ,7 ,0]
    [5 ,6 ,2 ,3 ,6]
    [6 ,7 ,3 ,2 ,4]
    [7 ,8 ,0 ,8 ,4]
    [8 ,9 ,8 ,7 ,2]
    [9 ,9 ,4 ,1 ,4]

    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,0 ,0]
    [1 ,0 ,0 ,0 ,0]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,1 ,0 ,0]
    [0 ,0 ,0 ,0 ,1]
    [0 ,0 ,0 ,0 ,1]
    [0 ,0 ,0 ,1 ,0]
    [0 ,0 ,0 ,0 ,1]
    On retombe sur la solution soumise

  28. #23
    Loosgin

    Re : Résoudre un vieux puzzle en Python

    [3, 0, 2, 7, 4] est la seule et unique solution pour cette série de nombre.

    Voici ce que j'ai fait, je pense qu'il doit y avoir pas mal à optimiser.

    Code:
    L=[[0,1,2,6,5],[1,2,1,7,1],[2,3,2,5,7],[3,4,5,4,8],[4,5,9,7,0],[5,6,2,3,6],[6,7,3,2,4],[7,8,0,8,4],[8,9,8,7,2],[9,9,4,1,4]]
    
    increment=0
    scoreRang=0
    suiteCommun=[[0 for j in range(5)] for i in range(10)]
    #Création des 100 000 possibilités
    nombreN=[[0,0,0,0,0]]
    nombreTeste=[0,0,0,0,0]
    
    n=0
    suiteRang=[]
    sommeRang=0
    for i in range(10):
        for j in range(10):
            for k in range(10):
                for m in range(10):
                    for n in range(10):
                        nombreN.append([i,j,k,m,n])
    ##CREATION DE LA BOUCLE WHILE POur TOUTES LES POSSIBILITES POSSIBLES
    while n!=1 and increment<len(nombreN):
        suiteRang.clear()
        suiteCommun=[[0 for j in range(5)] for i in range(10)]
        
        nombreTeste=nombreN[increment][:]
        
        for i in range(len(L)):
            for j in range(len(L[0][:])):
                
                if(L[i][j] == nombreTeste[j]):
                    scoreRang=scoreRang+1           
            
                if scoreRang >= 1:
                   suiteCommun[i][j]=1
                else:
                    suiteCommun[i][j]=0
                scoreRang=0
        ##somme colonne
        for i in range(len(L)):
            for j in range(len(L[i][:])):
                sommeRang=sommeRang+suiteCommun[i][j]
            suiteRang.append(sommeRang)
            sommeRang=0
        
    
        ##Teste s'il y a un 1
        n=1
        for i in range(len(suiteRang)):
            if suiteRang[i]!=1:
                n=0
        increment=increment+1
    print('')
    print(suiteRang)
    print('')
    
    print(nombreTeste)
    print('')
           
    ##Suite, algo d'affichage...

  29. #24
    polo974

    Re : Résoudre un vieux puzzle en Python

    Citation Envoyé par pm42 Voir le message
    Aucun intérêt. On peut trouver les solutions de la plupart des choses en faisant une recherche mais qu'est ce que cela apprend à quelqu'un qui cherche à faire marcher un algo ?
    Mais si, il y avait un intérêt: dire qu'il existe une solution quand la personne pense qu'il n'y en a pas. Et ça a relancé le schmilblick.

    pour info, je l'ai cherché et trouvé façon bourrin en python:
    Code:
    l = ['01265', '12171', '23257', '34548', '45970', '56236', '67324', '78084', '89872', '99414']
    # nb colonnes
    nbcol=5
    
    #candidats
    nx = ["%05d" %i for i in range(100000)]
    
    # virer ceux qui n'ont pas au moins un digit
    for num in l:
        for i in range(len(nx) - 1, -1, -1):
            for col in range(nbcol):
                if num[col] == nx[i][col]:
                    break
            else:
                del nx[i]
        print (len(nx))
    
    
    # virer ceux qui on 2 digits en commun
    for num in l:
        for col in range(nbcol - 1):
            d1 = num[col]
            for col2 in range(col + 1, nbcol): 
                d2 = num[col2]
                for i in range(len(nx) - 1, -1, -1):
                    if nx[i][col] == d1 and nx[i][col2] == d2: 
                        del nx[i]
        print (len(nx), nx)
    de cette façon je m'assure de l'unicité de solution.
    car j'aurai pu faire plus court en ne cherchant que la première solution.

    truc du python: le else peut être utilisé en fin de boucle, il est exécuté si la condition de boucle n'est pas remplie donc exécuté en sortie de boucle normale et non exécuté si break...

    truc général: parcourir la liste à rebours pour pouvoir supprimer l'élément courant (sans avoir à bricoler l'index).
    Jusqu'ici tout va bien...

  30. Publicité

Discussions similaires

  1. Comment puis-je résoudre ce Puzzle?
    Par christine123 dans le forum Mathématiques du supérieur
    Réponses: 12
    Dernier message: 29/07/2020, 11h39
  2. [Python] Problème de lag de programme et essai de Timer python
    Par Loupsio dans le forum Programmation et langages, Algorithmique
    Réponses: 20
    Dernier message: 26/01/2018, 15h14
  3. puzzle géométrique
    Par ansset dans le forum Science ludique : la science en s'amusant
    Réponses: 4
    Dernier message: 11/09/2017, 10h01
  4. [Python] subprocess, lancer un autre programme avec python
    Par Loupsio dans le forum Programmation et langages, Algorithmique
    Réponses: 10
    Dernier message: 30/11/2016, 18h56
  5. en python le multi tache n'est pas possible alors pourquoi les threads existent sur python?
    Par docEmmettBrown dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 10/06/2015, 15h47