[Parenthese Defi info]

Salut a tous,
Pour une fois ceci n'est pas une question mais une petite pub pour un site que j'ai découvert hier totalement par hasard. Il y a bien une note a ce sujet dans le Forum Parent de devellopez.net mais en tant qu'utilisateur exclusif du Forum Python, j'aurai pu passer totalement a coté.

Bref, donc si les modos estiment que ce post n'a pas de raison d'être n"hésitez pas a le deplacer/supprimer.

Il s'agit d'une suite de défi mathématique a résoudre a l'aide de programme que chacun doit développer soit même.
Style de question:
Calculer la somme des entiers divisible par 3 ou par 5 inferieur a 1000.

Evidemment ca c'est la premiere question, la difficulté allant croissant.

On pourrai meme faire un petit post la dessus qu'on puisse en discuter entre utilisateur de Python : Ca permettrai une analyse bien poussé et interessante en terme d'optimisation

Le site:
http://projecteuler.net/

Effectivement on sort de Python, là (même si j'y ai résolu 28 problèmes en pur Python :D ... plus que 234 à résoudre ! :oops: ): le choix du langage n'est pas imposé. C'est vrai que leur phrase "tous ces problèmes peuvent se résoudre en moins d'une minute de calcul" est stimulante, mais n'incite pas forcément à choisir notre langage favori.
En même temps, je dois avouer que j'y ai appris pas mal de choses concernant l'écriture d'un code Python qui tourne vite (et, généralement, qui est aussi simple et court).

Par contre, pythonchallenge, lui, incite fortement à utiliser Python, car les solutions à ses énigmes sont inclues dans un module de la librarie standard ou d'une librairie tierce.

Toutefois, qu'il s'agisse de l'un ou de l'autre de ces forums, je déconseille fortement d'établir un thread ici pour en discuter, étant donné que le but du jeu est de trouver une solution tout seul : évitons les spoilers.

Surtout que l'un comme l'autre, une fois l'énigme résolue, permettent d'accéder aux solutions des autres utilisateurs (c'est là que j'ai vraiment appris à "penser Python" et que j'ai découvert des optimisations).

En bref : allez-y, suez sang et eau pour trouver les réponses, étudier les réponses des autres une fois que vous avez résolu le challenge mais surtout, surtout, ne spoilez pas, please.

Enfin, on peut toujours me répondre "si tu ne veux pas être spoilé, ne lis pas ce thread" et je dirais que c'est dommage, car je veux bien discuter d'optimisation, mais bon, vous avez raison : After all, we're all consenting adults here.

Dans le site pythonchallenge, je n'ai toujours pas trouvé le moyen en étant inscrit bien sur de pouvoir regarder un seul challenge.

Je ne sais pas comment y accéder, si tu sais peux-tu m'expliquer?

Merci par avance,

Bonjour à tous,

J'avais pourtant trouvé l'intention de ju-bicycle parfaitement louable même si ces défis ne sont pas spécialement faits pour être relevés via Python...
Il m'aurait intéressé au plus haut point de découvrir d'autres "productions", de les comparer avec les miennes, et de voir comment les optimiser au maximum.
Mais nardo47 semble penser (et son argumentation mérite qu'on s'y arrête) que ce n'est pas une bonne idée que de proposer ses solutions ici.
On peut pourtant avoir envie de résoudre ces problèmes pour le fun, sans vouloir s'inscrire pour participer au concours, non ?

Bon, j'avais posté un de mes codes, comme je ne veux heurter personne, je viens d'éditer et le retirer en attendant de voir l'évolution de la pensée sur le sujet...
Dommage !

Cordialement.

Hello a tous
Sinon on pourra ajouter un sous forum au forum python (aprés tout il y en a pas mal alors pk pas?)
qui s'intitulerai "Défi info".
Ensuite il suffirait de créer encore un sous forum par défi différent:
PythonChallenge
Eulerproject

Puis lorsqu'on post dans ces forum ils suffit de mettre le numéro de l'énigme concerné et hop: Plus de probleme de spoiler...

Bonne idée, je suis pour!

Citation:

---

Envoyé par fred1599

Dans le site pythonchallenge, je n'ai toujours pas trouvé le moyen en étant inscrit bien sur de pouvoir regarder un seul challenge.

Je ne sais pas comment y accéder, si tu sais peux-tu m'expliquer?

Merci par avance,

---

Le challenge commence ici. Il s'agit vraiment d'une énigme. A toi de comprendre la page affichée, et comment Python peut t'aider à résoudre l'énigme.
Si tu arrives à la résoudre, tu auras accès à une url listant les solutions des différents participants, et ainsi de suite. A chaque nouvelle énigme, tu peux consulter les solutions de l'énigme précédente.
Pour ProjectEuler, c'est différent car tu n'es pas obligé de les résoudre dans l'ordre, mais au fond, ça revient au même : tu ne peux voir que les solutions des challenges/énigmes/problèmes que tu as résolus.

Citation:

---

Envoyé par yoshik

J'avais pourtant trouvé l'intention de ju-bicycle parfaitement louable même si ces défis ne sont pas spécialement faits pour être relevés via Python...

---

C'est effectivement tout à fait louable de vouloir proposer des astuces/conseils/idées pour "mieux" coder (+ vite, + clair, + robuste, + tout-ce-que-tu-veux).
Et tu serais surpris de voir à quelle vitesse peut s'exécuter un programme Python, pour peu que tu réfléchisses à ton algo et que tu aies un style Pythonique.

C'est juste que je n'ai pas envie de voir la solution d'un problème que je n'aurai pas encore résolu, mais, comme je l'ai écrit :

Citation:

---

Envoyé par nardo47

on peut toujours me répondre "si tu ne veux pas être spoilé, ne lis pas ce thread" et je dirais que c'est dommage, car je veux bien discuter d'optimisation, mais bon, vous avez raison : After all, we're all consenting adults here.

---

Si je n'ai pas envie de voir une solution et qu'il y en a de postés, il me suffit de ne pas les lire !

Citation:

---

Envoyé par yoshik

Il m'aurait intéressé au plus haut point de découvrir d'autres "productions", de les comparer avec les miennes, et de voir comment les optimiser au maximum.

---

Moi aussi, et j'en ai vu, des productions superbes dans les solutions des énigmes que j'avais résolues.
Des solutions où je me suis dit "Woaw, je savais pas qu'on pouvait faire ça !" et des solutions où je me suis dit "Mais c'est pas possible que je sois aussi c*n, pourquoi j'ai pas fait comme ça, je suis vraiment un âne bâté !". :mouarf:

Citation:

---

Envoyé par yoshik

Mais nardo47 semble penser (et son argumentation mérite qu'on s'y arrête) que ce n'est pas une bonne idée que de proposer ses solutions ici.

---

Je te remercie d'accorder autant de considération à ma remarque.

Citation:

---

Envoyé par yoshik

On peut pourtant avoir envie de résoudre ces problèmes pour le fun, sans vouloir s'inscrire pour participer au concours, non ?

---

Au niveau de l'inscription, elle est gratuite, n'engage à rien du tout : pour une fois qu'on nous propose quelque chose comme ça sans aucune démarche commerciale ou autre derrière, ça serait dommage de ne pas en profiter, mais vous faites comme vous voulez.

Ce sera mon dernier mot sur le sujet : décidez ce que vous voulez, je vous ai fait part de mon avis, je ne prétends pas qu'il soit le meilleur, ni celui de la majorité.

Qui plus est, peut-être qu'il n'y aura aucune solution publiée, juste des bouts de code + génériques, démontrant bien l'optimisation sans spoiler quoi que ce soit. Je suis peut-être dans un mode "jeune vierge effarouchée" ! :mouarf:

Et même si des solutions sont publiées, sachez que je regarderais quand même, ne serait-ce que pour voir si je peux m'améliorer ou aider les autres à s'améliorer. ;)

Citation:

---

Le challenge commence ici. Il s'agit vraiment d'une énigme. A toi de comprendre la page affichée, et comment Python peut t'aider à résoudre l'énigme.

---

ok merci, il est résolu assez facilement, je passe au 1

:ccool:

Bonsoir,

Citation:

---

ok merci, il est résolu assez facilement, je passe au 1

---

Résolu ? Chapeau ! Moi, je n'ai toujours pas compris : ça ne m'inspire absolument rien (et de toutes façons s'il s'agit via python de modifier une url, chaispasfaire ! Donc time out !)
Assez facilement 8O... boufre ! J'ai eu tort de vouloir jouer dans la cour des grands, je retourne donc jouer aux billes avec les gamins de ma rue :P
et au défi Euler.

Flap ! Flap ! Flap ! (Un ange passe)

Bon, en fait, j'ai quand même trouvé... :mouarf:

@+

par contre le 1 je comprend pas, mais alors pas du tout avec quoi il faut jouer pour le mettre dans la barre d'adresse.

Oui dans le 0 fallait surtout regarder la position du 2 par rapport au 38

bah la 1 c'est une substitution monalphabetique toute simple (dite de cesar) et en plus il donne la clef!!
alors il reste plus grand chose a faire !! :)

D'accord j'avais donc bien compris, mais la réponse, je la met ou?

Citation:

---

Envoyé par fred1599

D'accord j'avais donc bien compris, mais la réponse, je la met ou?

---

Une réponse facile me vient à l'esprit, mais bon... :mouarf:

Le conseil de l'énigme 0 reste valide.

Citation:

---

Hint: try to change the URL address.

---

P.S. Je vous avais bien dit que je suivrais quand même ce thread ! ;)

il me semble que quand tu traduit le texte, il te dit de faire la meme chose a l'url
(uniquement au mot "map" of course)

A qui on demande de créer le nouveau forum???

Bon j'y arrive pas.

Pourtant dans la clef, faut bien remplacer

k-->m
o-->q
e-->g

Ce qui donne :

Citation:

---

g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr ammnsrcpq ypc dmp. bmglg gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmlg. sqglg qrpglg.myicrpylq() gq pcammmclbcb. lmu ynnjw ml rfc spj.

---

Ce résultat je le colle dans l'url à la place du map et ça ne fonctionne pas.

http://www.pythonchallenge.com/pc/def/g fmnc wms bgblr rpylqjyrc gr zw fylb. rfyrq ufyr ammnsrcpq ypc dmp. bmglg gr gl zw fylb gq glcddgagclr ylb rfyr'q ufw rfgq rcvr gq qm jmlg. sqglg qrpglg.myicrpylq() gq pcammmclbcb. lmu ynnjw ml rfc spj..html

Ci-dessus il y a 2 points dans l'url, je les ai écris en rouge, c'est normal?

Me suis-je gouré dans la compréhension du sujet?

Il ne faut pas remplacer que ces trois lettres, mais toutes les lettres avec le meme décalage !!
(+3 je crois, de mémoire). Ce qui donne un texte (que je n'ai pas ici, désolé).

Puis tu fais le meme décalage a "map" qui te donnce "ocr"
et tu remplace map par ocr dans l'url...Et voili!

Le but du jeux étant de réaliser le script en python qui t'effectue le décalage des lettres!

Salut,

Oui, tu t'es gouré... On t'incite à coder le mot map...
J'ai accédé à l'énigme suivante, je pense avoir mis la main sur le texte à "passer à l'OCR"...
J'ai cru que c'était du ook modifié, apparemment, non !
Je continue mes investigations.

Défi euler n°8 : Dans un nombre de 1000 chiffres qui est donné, trouver le plus produit de 5 "chiffres" consécutifs, un bout de mon code :

Code:

---

prod = eval('*'.join(nombre[i:i+5]))

---

Sur mon, PC 2Go RAM avec proc. Phenom X3 et psyco importé dans mon script, temps pour trouver la réponse : 0.0310001373291 s

@+

Hello a tous
Alors voila. Aprés avoir eu besoins de 11h30 de temps d'execution pour résoudre la question 12, j'ai (enfin) décidé de m'attaquer a un algo propre et efficace de décomposition en nombre premier.
Il semblerai que l'algo de rho-pollard soit pas mal, mais mes notions de math ont pas mal baissé ces derniers temps, et je voudrais comprendre ce que je fais.
Avez vous des algos peut etre moins performant (correct quand meme!!) mais plus simple?
Sinon une petite explication..... Hein Yoshi ;)

Salut,

Désolé, rho-pollard efficace, rapide mais pas fiable à 100% : gênant !
Un algo de crible d'Eratosthène très rapide trouve le 10001e nombre premier en 16/1000e de s.
Tu prends ?

Je pense m'y prendre à l'envers : je suis en train de chercher à optimiser le nombre de facteurs min et les exposants nécessaires, établir la liste des nomres premiers jusqu'à un certain niveau et tester les nombres triangulaires à partir d'une certaine valeur.
Sinon j'ai encore d'autres pistes...

@+

Citation:

---

Un algo de crible d'Eratosthène très rapide trouve le 10001e nombre premier en 16/1000e de s.
Tu prends ?

---

oui je prend. mais avec des commentaires pour etre sur de bien piger le tout!!! :P

SAlut,

OK ! Voilà :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

# usr/bin/env python # -*- coding: utf-8 -*-   def eratosthene(n,premiers): nombres = [] for i in xrange(2,n+1): nombres.append(True) # affecte True à tous les nombres de 2 à n for i in xrange(2,n+1): if nombres[i-2]: # décalage de 2, entre l'indice et le nombre, donc son état # Si le nombre i, d'indice i-2, est à TRUE premiers.append(i) # C'est un premier for j in xrange(2*i,n+1,i): # On boucle donc sur tous ses multiples jusqu'à la imite n fixée nombres[j-2] = False # Et on les passe à False return premiers,nombres   n,premiers=100,[] premiers,z=eratosthene(n,[])   # Pour te faire une idée du fonctionnement print premiers print print z

---

Résultat :

Citation:

---

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

[True, True, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, True, False, False, False, False, False, True, False, False, False, True, False, False, False, False, False, True, False, False, False, False, False, False, False, True, False, False, False]

---

C'et beau, surprenant... et très rapide ! Hélas, ça n'est pas de moi...
En fait, l'algo commence par affecter TRUE à 2,3,4,5,6... n etc (dans l'exemple n = 100), ce qui est vrai déjà pour 2 et 3 : la pompe est amorcée.
On interroge 2 sur son état en cherchant nombres(2-2) on trouve TRUE, on le stocke dans premiers, et on parcourt la liste des nombres à partir de 2 et pas par de 2, et on les passe à FALSE : 4,6,8,10,12.... sont donc devenus FALSE.
Idem pour 3, sauf que 6 est déjà FALSE pas besoin de le retraiter...
On arrive à 4 : il a été passé à FALSE, on continue...
Quand on arrive à 17 (par ex.), puisqu'il resté à TRUE, c'est qu'il n'est pas multiple des nombres premiers qui le précèdent, il est donc bien premier.

En utilisation "normale", tu te contentes :
1. d'écrire : return premiers
2. de récupérer premiers et laisser z : premiers = eratosthene(n, [])

C'est clair ?
Bon j'espère que cette "publication" ne gêne personne...

@+

Citation:

---

Envoyé par yoshik

Bon j'espère que cette "publication" ne gêne personne...

---

Pas moi, d'autant + que je l'avais déjà :mrgreen:

Par contre, je n'ai jamais sorti la liste des nombres premiers, j'ai toujours gardé le tableau sieve = [False, False, True, True, False, True, ...] tel que, et je regardais la primalité d'un nombre n en faisant simplement :

Code:

---

1 2 3 4 5 6

if sieve[n]: print n, 'est premier!'   # ce qui me fait penser qu'on peut avoir la liste des n nombres premiers en faisant : [i for i, p in enumerate(sieve) if p]

---

Ah si, je commence l'initialisation du tableau différemment :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13

# n est la limite du crible sieve = [False] * (n + 1) # N'oublions pas qu'un tableau commence par l'indice 0. sieve[0] = sieve[1] = False # 0 et 1 ne sont pas premiers. for x in xrange(4, n + 1, 2): sieve[x] = False # Les nombres pairs ne sont pas premiers, 2 excepté. # le reste étant peu ou prou ce qu'a écrit Yoshik.   # Et, maintenant que j'y pense, j'aurais pu initialiser mon tableau comme ceci : sieve = [False, True] * (n / 2 + 1) # (n // 2 + 1) en Python 3 sieve[1] = False sieve[2] = True # ce qui évite de faire une boucle pour indiquer que tous les nombres pairs ne sont pas premiers.

---

Je sais, ma deuxième version fait vraiment chipotage, mais il me semble que l'on parle d'optimisation, par ici.

N.B. j'appelle mon tableau sieve, qui est la traduction anglaise de crible (hop, une recherche "crible eratosthene" vous donnera toutes les infos ! ;)

Citation:

---

Envoyé par yoshik

En utilisation "normale", tu te contentes :
1. d'écrire : return premiers
2. de récupérer premiers et laisser z : premiers = eratosthene(n, [])

---

Même pas !

Code:

---

1 2 3

premiers = [] eratosthene(n, premiers)

---

Ceci devrait suffire : premiers est une liste, donc mutable. Comme append ne renvoie pas de valeur (elle modifie la liste sur place) et que Python ne fait que des passages par référence, tu ne devrais pas avoir besoin de retourner quoi que ce soit !
Ceci est purement théorique, je n'ai pas testé ton code.

SAlut,

Merci ! Intéressant ! Ton histoire de mutable, va falloir que je regarde ça de plus près : c'est la deuxième référence qu'on m'y fait en une semaine...Pour l'instant, c'est flou !
Bon, effectivement tu as raison, à condition comme tu l'indiques eratosthene(n,premiers) et non pas comme je je l'ai fait :
eratosthene(n,[]) qui me renvoie une liste vide, ce qui me fait penser que ce dernier procédé est plus gourmand en mémoire, parce que si j'ai bien compris, il n'y a pas une liste nommée premiers quand j'appelle
premiers=eratosthene(n,[]) mais 2 :
une dans le corps du programme et une autre locale dans le def...
Si c'est bien exact, j'ai utilisé jusqu'à maintenant une procédure "impropre" dans sa conception.

Mes soupçons sont-ils fondés ou pas ? Ô amateurs éclairés et chevronnés que je vois passer régulièrement, voulez-vous infirmer ou confirmer.

D'autre part, si ma liste de nombres premiers a besoin dêtre abondée au coup par coup (sans avoir besoin de la reconstruire à chaque fois du début) puis-je remplacer return par yield ?
Il faudrait que j'essaie...

@+

PS
Nan ! Marche pas !
Soit il ne renvoie rien : affichage vide, soit j'ai droit à :
<generator object eratosthene at 0x011B8C38>

Ah m.... alors !!

A supprimer : erreur ! Merci !
Pas de bouton "Supprimer" sur ce forum ?

Voici une petite amélioration en termes de rapidité :

Code:

---

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

#!/usr/bin/env python #coding=utf-8   from time import clock   def eratosthene_1(n): premiers = [] nombres = [] for i in xrange(2,n+1): nombres.append(True) # affecte True à tous les nombres de 2 à n for i in xrange(2,n+1): if nombres[i-2]: # décalage de 2, entre l'indice et le nombre, donc son état # Si le nombre i, d'indice i-2, est à TRUE premiers.append(i) # C'est un premier for j in xrange(2*i,n+1,i): # On boucle donc sur tous ses multiples jusqu'à la imite n fixée nombres[j-2] = False # Et on les passe à False return premiers   def eratosthene_2(n): """     Here we just work woth odd natural numbers.         numbers[i]   0  1  2     N            3  5  7...         We have i = N//2 - 1     """ premiers = [2]   if str(n)[-1] in ['0', '2', '4', '6', '8']: i_max = n/2 - 1 else: i_max = n/2   nombres = ['True']*i_max   for i in xrange(i_max): if nombres[i]: # Cf. doc string ci-dessus. premiers.append(2*i + 3) # Si n = 3, on élimine n + 2n = 9 , n + 4n = 15 ,... etc # On va donc de 2n en 2n. # # En terme d'indice, cela devient : # n = 2*i+3 <==> i = (n-3)//2 # 3n = 2*j+3 , 3n = 6*i+9 <==> 2*j+3 = 6*i+9 # <==> 2*j = 6*i+6 # <==> j = 3*i+3 --> PAS = 2*i+3 # 5n = 2*k+3 , 5n = 10*i+15 <==> 2*k+3 = 10*i+15 # <==> 2*k = 10*i+12 # <==> k = 5*i+6 --> PAS = 2*i+3 pas = 2*i+3 # L'intérêt est que le pas devient de plus en plus en grand # en même temps que les nouveaux nombres premiers découverts. # Du coup, on fait moins de testes inutiles. for j in xrange(i,i_max,pas): nombres[j] = False return premiers       n = 1000000   timeStart = clock() premiers_1 = eratosthene_1(n) timeEnd = clock()   print '=== METHODE 1' print '\t'*5 + ' Temps : ' + str(timeEnd - timeStart) print '\t'*5 + ' Dernier premier trouve : ' + str(premiers_1[-1])   timeStart = clock() premiers_2 = eratosthene_2(n) timeEnd = clock()   print '=== METHODE 2' print '\t'*5 + ' Temps : ' + str(timeEnd - timeStart) print '\t'*5 + ' Dernier premier trouve : ' + str(premiers_2[-1])   print '=== COMPARAISON DES METHODES' print '\t'*5 + ' premiers_1 = premiers_2 : ' + str(premiers_1 == premiers_2)

---

J'ai obtenu :

Code:

---

1 2 3 4 5 6 7 8

=== METHODE 1 Temps : 1.06 Dernier premier trouve : 999983 === METHODE 2 Temps : 0.38 Dernier premier trouve : 999983 === COMPARAISON DES METHODES premiers_1 = premiers_2 : True

---

Citation:

---

Envoyé par ju_bicycle

Hello a tous
Alors voila. Aprés avoir eu besoins de 11h30 de temps d'execution pour résoudre la question 12, j'ai (enfin) décidé de m'attaquer a un algo propre et efficace de décomposition en nombre premier.
Il semblerai que l'algo de rho-pollard soit pas mal...

---

Regardez cette page. Il faudrait voir si cela est rapide à programmer.

Citation:

---

Envoyé par yoshik

eratosthene(n,[])

---

Ben, moi, perso, je veux bien que tu tapes ça, mais comment tu récupères le résultat ? :mrgreen:

Citation:

---

Envoyé par yoshik

si j'ai bien compris, il n'y a pas une liste nommée premiers quand j'appelle
premiers=eratosthene(n,[]) mais 2 :
une dans le corps du programme et une autre locale dans le def...

---

En fait, non. Tu avais 2 références à cette liste, ce qui du coup n'est pas gourmand en mémoire.
Il faut bien comprendre que les variables en Python sont juste des références à des objets.
Après, je ne sais pas si le return fait une copie de l'objet (ce qui ne m'étonnerait pas) mais, même s'il le fait, le garbage collector devrait s'activer lors de la sortie de la fonction et nettoyer la liste "interne" à la fonction (attention, je suppute).

Citation:

---

Envoyé par yoshik

Si c'est bien exact, j'ai utilisé jusqu'à maintenant une procédure "impropre" dans sa conception.

---

Boaf.
1. On est tous passés par là ;
2. si tu n'as pas de contrainte de mémoire, je ne vois pas où est le problème ;
3. si ton programme produit le bon résultat, le principal (et le moins fun, donc le + ardu) est fait.

L'optimisation reste du "superflu", quoique toujours la partie la + intéressante et la + stimulante.

Sinon, histoire de pinailler un peu, il n'y a pas de procédure en Python, juste des fonctions.

Pour ta génération au coup par coup, je crois deviner que tu as réussi... et que tu as compris que tu avais réussi ! :D

@rambc:
Pour avoir une idée + précise du temps d'exécution de tes fonctions, utilise le package timeit au lieu de relever l'heure "à la pogne".
Il fait tourner les tests plusieurs fois, et donc obtient une moyenne de temps d'exécution, ce qui est + valide qu'un one-shot, qui peut toujours être perturbé par ce que fait ton OS (genre, "ah ben tiens, il serait pas temps de relever les mails ?")

Bonsoir,

@rambc : tu divises le temps par 3 : belle perf, merci !

@nardo47
J'ai employé "procédure" dans son acceptation du français pas de Python...

Citation:

---

Pour ta génération au coup par coup, je crois deviner que tu as réussi... et que tu as compris que tu avais réussi !

---

Bin, non justement, ça devrait marcher, et je n'arrive pas à récupérer ma liste..
J'ai essayé :
yield premiers
en lieu et place de : return premiers

puis eratosthène(n,premiers)
print premiers

S'affiche alors: [] et je suis bien avancé...

Et si j'essaie à la place :
premiers=eratosthene(n, premiers)
j'obtiens : <generator object eratosthene at 0x011B8C60>
là, par contre, j'entrevois pourquoi ça cloche...

@+

Citation:

---

Envoyé par yoshik

J'ai employé "procédure" dans son acceptation du français pas de Python...

---

:P

Citation:

---

Envoyé par yoshik

yield premiers

---

Ah ! Alors:
yield renvoie une valeur et "se souvient" de l'état dans laquelle est la fonction lors de ce renvoi.
Ce qui fait que l'appel suivant à la fonction reprend à partir de ce point.

Et donc, on n'utilise pas yield pour retourner le résultat final, mais une partie du résultat.
Dans le cas d'une liste, on "yielde" chaque élément de la liste final au fur et à mesure de leur calcul.
Il faut donc que tu places ton yield au niveau du premiers.append que tu fais.

Du coup, cet appel de fonction se fait dans une boucle for :

Code:

---

1 2 3

for x in eratosthene_yield(n): print x

---

Et là, tu va devenir accroc !

Citation:

---

Envoyé par nardo47

Pour avoir une idée + précise du temps d'exécution de tes fonctions, utilise le package timeit au lieu de relever l'heure "à la pogne".
Il fait tourner les tests plusieurs fois, et donc obtient une moyenne de temps d'exécution, ce qui est + valide qu'un one-shot, qui peut toujours être perturbé par ce que fait ton OS (genre, "ah ben tiens, il serait pas temps de relever les mails ?")

---

Merci pour cette info. Par contre je ne pense qu'optimiser un code soit superflu, j'essaye toujours de faire en sorte de limiter les dégâts.

Salut a tous
Merci a Yoshi et rambc et aux autres pour le crible...Ca marche pas mal. Avec tout ca je suis tombé sous les 2 secondes, avec un machine médiocre et sans psyco...
A comprarer avec les 11h30 de ma premiere version :mouarf:
Next!

Juste pour info : un algo détaillé basé sur le crible est proposé dans Linux Mag de Novembre.

Hello a tous: Quelqu'un c'est penché sur le prob 15? Celui ou il faut compter les chemins possible dans le carré? J'ai toujours était trop nul pour ce genre de probleme, je ne visualise pas du tout les trucs.
Attention je ne demande surtout pas du code, mais plutot la logique derriere...Si quelqu'un a une idée...

Il faut juste savoir que l'on peut se déplacer soit vers la gauche ou la droite (soit -1, +1 en x), soit vers le bas ou le haut (soit -1, +1 en y). Dans le cas où les déplacements se font sans retour, ie toujours vers la droite et/ou vers le bas, il y a une formule mathématique. J'imagine qu'ici il est interdit de repasser par un point déjà visité pour éviter les boucles infinies. Effectivement, je viens de lire le problème en entier. Dans ce cas, les mathématiques ont une réponse mais là je ne dirais rien...

Si c'est pour dire "j'ai la solution mais je ne dirait rien nananere..." je vois pas l'interet de ton post

Il faut aussi lire le début de son post, il donne une indication, et il me semble que le but du défi, c'est de le réaliser seul, non ?

Citation:

---

Envoyé par ju_bicycle

Attention je ne demande surtout pas du code, mais plutot la logique derrière...Si quelqu'un a une idée...

---

Si je te donne la formule, il n'y a rien à faire car elle est toute simple. De plus, je pense que l'on peut calculer ce nombre de combinaisons sans passer par la formule.

Le sens de mon post n'est pas dans l'esprit de ta remarque. Sur ce, je ne répondrais plus à tes messages si tu le prends sur ce ton.

Effectivement la formule ne m'interessait pas. Pour ma précédente réponse, reconnait que:

Citation:

---

Dans ce cas, les mathématiques ont une réponse mais là je ne dirais rien...

---

Fait un peu du "nananere". Rien de bien méchant, c'est une remarque c'est tout

Ceci dit l'indication du +1/-1 m'a donné le coup de pouce necessaire. Donc je t'en remercie. Mais en fait c'est meme un peu plus simple puisqu' apparemment
d'aprés l'exemple fournit on ne peut pas revenir en arriere.Donc uniquement des +1 (en x ou en y)...

Citation:

---

Envoyé par ju_bicycle

Fait un peu du "nananere".

---

J'ai juste passé l'âge de ce genre de niaiserie. Voici un fichier commenté sur le problème 15. Il fonctionne avec Python 3.

Code:

---

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

#!/usr/bin/env python # # WARNNG : use Python 3 # # This code solves brutally the following problem (cf. http://projecteuler.net/index.php?section=problems&id=15) : # Starting in the top left corner of a 2*2 grid, there are 6 routes (without backtracking) to the bottom right corner. # How many routes are there through a 20*20 grid? # # Nous devons modéliser un chemin comme le suivant pour une grile 3*3 # (on change la dimension par rapport à celle du problème car on s'intéresse # aux intersections de la grille et non à son nombre de carreaux) : # # S | . | . # * | * | . # . | * | E # # Nous avons à chaque étape deux alternatives, où on note (x;y) les coorodnnées dans la grille : # 1) Soit on se déplace horizontalement d'une case : x += 1. # 2) Soit on se déplace verticalement d'une case : y += 1. # # Nous avons deux contraintes : # 1) Quand x = 4 (pour une grille 4*4), on ne peut plus faire que y += 1 jusqu'à obtenir y = 4. # 2) Quand y = 4 (pour une grille 4*4), on ne peut plus faire que x += 1 jusqu'à obtenir x = 4. # # Voici une modélisation possible du chemin représenté ci-dessus en exemple : # 0-1-0-1 # Ce codage ce lit comme suit : au départ on ne bouge pas horizontalement, # donc on monte de un, puis ensuite on bouge horizontalment de un # donc on ne bouge pas verticalement.. etc. # # Tous les chemins possibles sont modélisés comme suit : # # 0-0-1-1 # 0-1-0-1 # 0-1-1-0 # 1-0-0-1 # 1-0-1-0 # 1-1-0-0 # # On constate donc que l'on doit avoir à chaque fois deux 0 et deux 1. # Ceci donne la voix pour la solution mathématique mais c'est pour après. # # Passons maintenant au programme brutal dans le cas connu.   nbreChemins = 0 tailleGrille = 3   for rangPremierZero in range(tailleGrille): for rangSecondZero in range(rangPremierZero+1, tailleGrille+1): nbreChemins += 1   print('') print('Pour une grille de taille {0}, il existe {1} chemins possibles.'.format(tailleGrille, nbreChemins))   # Comment généraliser cela. Et bien comme suit...   # Voici une grille 5*5 (toujours avec notre convention), et une autre 6*6 : # # S | * | * | * | * S | * | * | * | * | * # . | . | . | . | * . | . | . | . | . | * # . | . | . | . | * . | . | . | . | . | * # . | . | . | . | * . | . | . | . | . | * # . | . | . | . | E . | . | . | . | . | * # . | . | . | . | . | E # # Notre modélisation est de longeur 8 pour la grille 5*5, et 12 pour la grille 6*6. # Il suffit de considérer le chemin particulier indiqué. # # Ceci nous amène à la formule suivante : pour une grille N*N, notre modélistaion sera de longueur 2(N-1). # On constate aussi que le nombre de zéros doit être égal à (N-1) # # Voilà ou cela nous mène.   tailleGrille = 3   nbreDeZeros = tailleGrille -1 # Remarque : nbreMaxDeplacements = 2*nbreDeZeros   # Il faut remplacer les boucles imbriquées suivantes : # # for rangPremierZero in range(nbreDeZeros): # for rangSecondZero in range(rangPremierZero, nbreDeZeros+1): # for rangTroisiemeZero in range(rangTroisiemeZero, nbreDeZeros+2): # ... etc   def monCompteur(nbreDeZeros, indiceDuZeroActuel, debutBoucle): nbreChemins = 0 iMax = nbreDeZeros + indiceDuZeroActuel + 1   if indiceDuZeroActuel == nbreDeZeros -1: for i in range(debutBoucle, iMax): nbreChemins += 1 else: for i in range(debutBoucle, iMax): nbreChemins += monCompteur(nbreDeZeros, indiceDuZeroActuel + 1, i+1)   return nbreChemins   nbreChemins = monCompteur(nbreDeZeros, 0, 0)     print('') print('Pour une grille de taille {0}, il existe {1} chemins possibles.'.format(tailleGrille, nbreChemins))   # Pour finir, voici la solution mathématique : # # Considérons une grille 6*6 pour fixer les idées : # # S | * | * | * | * | * # . | . | . | . | . | * # . | . | . | . | . | * # . | . | . | . | . | * # . | . | . | . | . | * # . | . | . | . | . | E   # Les chemins sont modélisés comme suit : # # 0-0-0-0-0-1-1-1-1-1 # 0-0-0-0-1-0-1-1-1-1 # 0-0-0-1-0-0-1-1-1-1 # ... etc # # Choisir un chemin c'est choisir quatre emplacements pour les zéros parmi les huit possibles. # Les mathématiques nous donnent que ce nombre est est égal au nombre de combinaisons de 4 parmi 8 : # 8! / 4!^2 # Dans le cas général, pour une grille N*N avec notre convention, on a (2N-2)! / (N-1)!^2 chemins possibles. # # Testons les deux approches.   def combin(k,n): """Calcul de C(k;n) = n! / k!(n-k)! en utilisant         C(k;n) = C(k-1;n-1) + C(k;n-1)""" if k==0 or k==n: return 1   return (combin(k-1, n-1) + combin(k, n-1))   tests = [3, 6, 21]   for tailleGrille in tests: print('-'*30) print('tailleGrille = ' + str(tailleGrille))   nbreDeZeros = tailleGrille -1 nbreCheminsViaMath = combin(nbreDeZeros, 2*nbreDeZeros) print ('---' + str(nbreCheminsViaMath)) nbreChemins = monCompteur(nbreDeZeros, 0, 0) print('...')   if nbreChemins != nbreCheminsViaMath: print ('\tECHEC') else: print ('\tOK ! On obtient {0} chemins possibles;'.format(nbreChemins))

---

Il faut pas mal de temps pour la cas du problème 15 même via les combinaisons.