Résoudre un vieux puzzle en Python

[Loosgin]

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é)

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

-----

[Jack]

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.

[Loosgin]

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

[umfred]

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

[A voir en vidéo sur Futura]

[Jack]

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

[polo974]

une solution:
30274

[Jack]

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

[pm42]

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 ?

[umfred]

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.

[Jack]

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.

[umfred]

arf j'ai le cerveau qui fait des bonds

[Loosgin]

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 ?

[Jack]

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?

[Loosgin]

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...

[Loosgin]

[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 ?

[Jack]

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?

[Loosgin]

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]

[Loosgin]

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

[Jack]

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

[Loosgin]

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]

[Jack]

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

[Loosgin]

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

[Loosgin]

[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.

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...

[polo974]

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:

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).