Challenge mathématique simple

[afranck64]

Alors, je suis tombé "accidentellement" aujourd'hui sur un Challenge dans les archives...

Ahh je voie le genre , je dois en avoir en stock ^^,
Du genre,

Soit un nombre composé de neufs chiffres distincts (de 1 à 9) disposés de telle sorte que:

- Le premier chiffre soit divisible par un,
-Le nombre formé des deux premiers chiffres soit divisible par deux,
-Le nombre formé par les trois premiers chiffres divisible par trois,
-Et ainsi de suite jusqu'à 9.

Quel est ce nombre ?

J'ai mis un petit moment à la trouver celle là ^^

Pour y aller plus vite j'ai bidouillé un script Python qui se charge d'en trouver un "aléatoirement". Alors, j'en ai des tonnes

import random

def force(base='1',mod=2):
    x = int(base)*10
    lst = list(range(9))
    random.shuffle(lst) #On donne la possibilite de trouver des sol diff.
    for i in lst:
        if (x+i)%mod == 0:
            return base+str(i)


def find():
    #On donne la possibilite de trouver des sol diff.
    res = str(random.randint(1,9))
    for i in range(2,10):
        res = force(res, i)
    print ("The found number is : ", res)

find()

[comaX]

Neuf chiffres distincts, ca veut pas dire qu'il ne doit pas y avoir de doublon ?

Du genre : 123456789 :
1 est divisible par un
12 est divisible par deux
123 est divisible par 3
1234 n'est pas divisible par 4, merde.
12345 est divisible par 5... etc.

Bref, tu m'as compris quoi ^^ Moi c'est ce que j'avais compris, sans quoi ajouter "distincts" est superfétatoire.

Amis de la poésie, notez comment j'ai calé ce mot de ouf. J'suis un peu fier là ; c'est pas tous les jours que j'arrive à le caler.

[afranck64]

Neuf chiffres distincts, ca veut pas dire qu'il ne doit pas y avoir de doublon ?

Du genre : 123456789 :
1 est divisible par un
12 est divisible par deux
123 est divisible par 3
1234 n'est pas divisible par 4, merde.
12345 est divisible par 5... etc.

Bref, tu m'as compris quoi ^^ Moi c'est ce que j'avais compris, sans quoi ajouter "distincts" est superfétatoire.

Amis de la poésie, notez comment j'ai calé ce mot de ouf. J'suis un peu fier là ; c'est pas tous les jours que j'arrive à le caler.

Je crois bien que cerveau avait skippé "distincts" :mouarf:
Il semble unique ce nombre "magique" alors là, on va faire du surmène-UC:

import random

def verify(lst=[]):
    for i in range(1,10):
        val = int("".join(lst[:i]))
        if val%i!=0:
            return False
    return True

def brute_force():
    import time
    t0 = time.time()
    print("Started")
    lst = list("123456789")
    while not(verify(lst)):
        random.shuffle(lst)
    print("The Magic number is : " + "".join(lst))
    print("Ended " + str(time.time()-t0) + " seconds")

brute_force()

>>>
Started
The Magic number is : 381654729
Ended 7.72900009155 seconds
>>>

Naturellement le temps pour trouver va et vient selon la volonté de votre bonne étoile.

[comaX]

Ca me parait bon tout ça ! Par contre, je pige pas du tout le code. Où sont les "règles" dans le code ? C'est pas verifiy() quand même, si ?

Started
The Magic number is : 381654729
Ended 6.732000112533569 seconds

Il semble en effet unique...

edit : avec 10 tests successifs. Effectivement le temps de génération est complètement aléatoire :

Started
The Magic number is : 381654729
Ended 6.621999979019165 seconds
Started
The Magic number is : 381654729
Ended 9.58899998664856 seconds
Started
The Magic number is : 381654729
Ended 2.6500000953674316 seconds
Started
The Magic number is : 381654729
Ended 0.11599993705749512 seconds
Started
The Magic number is : 381654729
Ended 1.7760000228881836 seconds
Started
The Magic number is : 381654729
Ended 4.63700008392334 seconds
Started
The Magic number is : 381654729
Ended 15.086999893188477 seconds
Started
The Magic number is : 381654729
Ended 2.441999912261963 seconds
Started
The Magic number is : 381654729
Ended 10.690999984741211 seconds
Started
The Magic number is : 381654729
Ended 3.4260001182556152 seconds

[afranck64]

Ca me parait bon tout ça ! Par contre, je pige pas du tout le code. Où sont les "règles" dans le code ? C'est pas verifiy() quand même, si ?

Les "règles" c'est effectivement la fonction verify.

import random

def verify(lst=[]):
    for i in range(1,10): #parcours 9 fois de la liste <lst>, pour vérifier les 9 "divisibilités"
        val = int("".join(lst[:i])) #produit un entier avec les élément o...i
        if val%i!=0:    #vérifie que cet entier est divisible par i
            return False    #Si c'est pas le cas pour toute la liste, cul de sac
    return True  #Si ca roule pour tout le monde, on a le Magic-Number

def brute_force():
    import time
    t0 = time.time()
    print("Started")
    lst = list("123456789")
    while not(verify(lst)): #On s'entête à trouve un nombre qui marche
        random.shuffle(lst) #On malaxe aléatoirement les 9 chiffres qu'on a et on reéssaie
    print("The Magic number is : " + "".join(lst))
    print("Ended " + str(time.time()-t0) + " seconds")

brute_force()

[comaX]

Hmm, ca s'éclaircie, mais je n'y suis toujours pas... En tout cas, merci beaucoup pour les commentaires !

Si j'avais du coder ça, j'aurais d'abord défini toutes les combinaisons possibles d'un nombre de neuf chiffres sans répétition.
Je n'ai plus les formules de combinatoires en tête (au pif, quelque chose comme 10!, soit 3 628 800), mais il ne doit pas y en avoir des masses. Ensuite je n'aurais gardé que les nombres avec un 0 ou un 5 en 5° position, ce qui devrait déjà grandement réduire la liste... Et ainsi de suite, selon les restrictions décroissantes de la divisibilité (donc on termine par le premier divisible par un, puisqu'ils le seront tous.

Bref, si j'ose, ce serait plus un algorithme... J'essayerai en bash ou awk à l'occasion !

Edit : d'après mes rapides vérifications, le nombre de possibilités est bien 10!. 3 ans sans faire de maths, et je me souviens de ça. "Like a boss".

[afranck64]

Edit : d'après mes rapides vérifications, le nombre de possibilités est bien 10!. 3 ans sans faire de maths, et je me souviens de ça. "Like a boss".

En fait, un nombre de 9 chiffres distincts (1..9), ca fait : A(9 dans 9) == 9! == 362880

Ta méthode est en fait la meilleure et la plus rapide, et démontre bien que cet élément est unique.

import itertools

def verify(lst=[]):
    for i in range(1,10): #parcours les 9 éléments de la liste <lst>
        val = int("".join(lst[:i])) #produit un entier avec les élément o...i
        if val%i!=0:    #vérifie que cet entier est divible par i
            return False    #Si c'est pas le cas pour toute la liste, cul de sac
    return True  #Si ca roule pour tout le monde, on a le Magic-Number

#production de la liste avec les elements voulus
lst = list("123456789") 

#productiond de toutes les permutations possibles :9!
cLst = list(itertools.permutations(lst))
print("remaining items : ", len(cLst))

##Les suppressions des ici sont facultatives
#suppression des non multiples de 2 en position 2
cLst = [i for i in cLst if i[1] in "2468"]
print("remaining items : ",len(cLst))
#suppression des non multiples de 5 en position 5
cLst = [i for i in cLst if i[4] == "5"]
print("remainig items : ", len(cLst))


res = [i for i in cLst if verify(i)]
print("remaining items: ")
for i in res:
    print ("\t" + "".join(i))

[comaX]

Effectivement, 9!... Va savoir pourquoi 10 m'est passé par la tête !

Ravi de voir que ma méthode est plus rapide et meilleure, je suis flatté !

Ceci-dit, est-ce qu'il ne serait pas encore plus rapide d'éliminer les 5 en premier ?

[afranck64]

Effectivement, 9!... Va savoir pourquoi 10 m'est passé par la tête !

Ravi de voir que ma méthode est plus rapide et meilleure, je suis flatté !

Ceci-dit, est-ce qu'il ne serait pas encore plus rapide d'éliminer les 5 en premier ?

Dans le mil, car pour l'élimination des 2 on aurait beaucoup moins d'éléments. :hola:

[comaX]

Oh yeah

J'ai grandement modifié le code *hum hum, menteur* pour afficher le temps, et en effet, c'est sans appel :

remaining items : 362880
remaining items : 161280
remainig items : 20160
remaining items:
381654729
Ended 0.29537987709 seconds

Je vais essayer avec les 5 en premier et je réédite !

remaining items : 362880
remainig items : 40320
remaining items : 20160
remaining items:
381654729
Ended 0.270968914032 seconds

Bon, c'est quand même pas très significatif à deux centièmes de seconde près...

Ceci dit, on passe quand même de 161K à traiter à 40K à traiter

[afranck64]

Oh yeah

J'ai grandement modifié le code *hum hum, menteur* pour afficher le temps, et en effet, c'est sans appel

Je crois que toute modif de plus d'un caractère est une grande modification alors...

Bon, c'est quand même pas très significatif à deux centièmes de seconde près...

peut-être, mais pour un nombre magique à 3 chiffres de plus, ca ferait beaucoup (et vraiment) de secondes en moins

[comaX]

J'ai essayé avec 20, et ca a pris deux secondes (donc effectivement, beaucoup plus de temps, même si ca reste court), mais pas de chiffre trouvé. J'imagine qu'il n'y en a peut être simplement pas !

[afranck64]

J'ai essayé avec 20, et ca a pris deux secondes (donc effectivement, beaucoup plus de temps, même si ca reste court), mais pas de chiffre trouvé. J'imagine qu'il n'y en a peut être simplement pas !

Je crois que le pétard est dû au fait qu'il prend "10", "11", "12", ..."19" pour des chiffres alors... que le problème n'est pas "posable" pour plus de 9 chiffres

[comaX]

Je n'ai pas allongé la liste, seulement la taille du nombre final ! Ceci-dit, selon comment est foutu le code, comme je n'ai pas bien fait attention, ca peut revenir au même, in deed.

[afranck64]

Je n'ai pas allongé la liste, seulement la taille du nombre final ! Ceci-dit, selon comment est foutu le code, comme je n'ai pas bien fait attention, ca peut revenir au même, in deed.

Pour ce qui est d'allongé la liste... la méthode employé n'est pas RAM-friendly vu qu'on n! listes de n éléments en mémoire... j'ai fait un test en ajoutant 0, c'est passé, 3 solutions(moyennant un léger édit du code):

def verify(lst=[]):

    for i in range(1,len(lst)): #parcours les 9 éléments de la liste <lst>
        val = int("".join(lst[:i])) #produit un entier avec les élément o...i
        if val%i!=0:    #vérifie que cet entier est divible par i
            return False    #Si c'est pas le cas pour toute la liste, cul de sac
    return True  #Si ca roule pour tout le monde, on a le Magic-Number

3 soluces (pas dispo car...)
Pour le test avec 11 éléments, j'ai eu au bout de ... peut-être 1 min 49 secondes une belle: MemoryERROR mes 2Go de RAM
étaient parties en fumées pour la production de permutations. Faut dire que ca fait tout de même 11!*liste_de_11_chars