Ce que l'advent of code m'a appris en Python #1

axel584 — Mon, 04 Dec 2023 17:13:41 +0000

L'advent of code est une compétition composée d'énigme à résoudre dans le langage que l'on souhaite.

J'ai vraiment commencé à me pencher sur les énigmes que depuis l'année dernière en essayant autant que possible de faire les énigmes chaque jour en utilisant le langage Python que j'apprécie particulièrement.

Et chaque jour, je découvrais des subtilités du langage et j'ai décidé de compiler ce que j'ai appris dans des billets.

Expression régulière : recherche gauche

Pour le premier jour, je voulais faire une recherche dans une chaîne de caractère, mais en récupérant la dernière occurrence dans une ligne (on appelle ça parfois faire une recherche gauche.)

Pour cela, on utilise le negative lookahead qui permet d'obtenir la dernière occurence.

(Test)(?!Test)

Bon, au final, j'ai utilisé une autre technique pour trouver ce dont j'avais besoin, mais j'étais content de découvrir cette fonctionnalité des regexp.

Test Unitaire

Bien que j'utilise les TU au quotidien dans mon boulot, l'année dernière, je n'avais pas pris l'habitude d'écrire les tests avant d'écrire mon code et comme les énigmes d'Advent of Code sont toujours fourni avec un jeu de données de test et leur résultat, il est très facile d'écrire un test pour s'assurer que le code est bon (au moins sur le jeu de test) pour l’exécuter ensuite sur notre entrée principal de l'énigme.

A bientôt pour les découvertes des autres jours.

Projet Euler #1 : Multiples de 3 ou 5

axel584 — Tue, 30 Aug 2022 14:10:32 +0000

Le Project Euler est un site web proposant une série de problèmes mathématiques conçus pour être résolus à l'aide de programmes informatiques. Il tient son nom du mathématicien suisse Leonhard Euler qui a vécu au XVIIIème siècle.

Il comprend actuellement plus de 700 problèmes de difficultés variables, chacun pouvant être résolu en principe en moins d'une minute par un algorithme efficace sur un ordinateur de puissance modeste.

Ce challenge permet de découvrir des curiosités mathématiques, mais aussi d'améliorer ses compétences en programmation. Je me suis amusé à en résoudre quelques uns et je voulais vous partager mes découvertes.

La première énigme a pour énoncé :

Si nous énumérons tous les nombres naturels inférieurs à 10 qui sont des multiples de 3 ou 5, nous obtenons 3, 5, 6 et 9. La somme de ces multiples est 23.
Trouver la somme de tous les multiples de 3 ou 5 en dessous de 1000.

Une solution très facile

`somme = 0
for i in range(1000) :
if i%3==0 or i%5==0 :
somme = somme + i

print(somme) `

Pour décrire certains points pour les non-pythoniens, on pourrait parler de la fonction "range" qui permet d'itérer sur un nombre donné (ici de 0 à 9999). Le nombre passé en paramètre est "exclu" de l'itération. Cette fonction peut aussi être appelée avec 2 paramètres range(a,b) et dans ce cas, on va itérer de la valeur a (inclue) à la valeur b (exclue). Et dans le cas de 3 paramètres, on aura le "pas" comme 3ème paramètre. Ainsi :

>>> for i in range(10,2,-1): ... print(i) ... 10 9 8 7 6 5 4 3

Pour résumer :

range(stop) prend un argument.
range(start, stop) prend deux arguments.
range(start, stop, step) prend trois arguments.

Et le deuxième point qui peut être intéressant est le % qui permet de calculer le "modulo", c'est à dire le reste de la division entière. Ainsi, 9 % 3 = 0 et si le reste de la division est zéro, c'est que le nombre est divisible par 3 et donc que c'est un multiple de 3.

Une solution plus complexe

Une suite arithmétique est une suite de nombres où l'on ajoute toujours la même valeur pour avoir le nombre suivant (exemple : 3, 6, 9, 12... on a ajouté 3 à chaque fois). La somme d'une suite arithmétique est donné par la formule : Sn = nombre de termes × (premier terme + dernier terme)/2

Mon prof de math au collège m'expliquait qu'il faut voir ça comme un escalier où chaque marche fait la même hauteur. Si on veut connaître la surface de l'escalier, il suffit de couper l'escalier en deux et d'en retourner la moitié pour l'emboiter sur l'autre. La plus grande marche coïncide avec la plus petite, la deuxième plus grande marche avec la deuxième plus petite etc.
Un dessin vaut mieux qu'un long discours :

Pour calculer la somme des nombres inférieur à 1000 divisibles par 3, il faudra faire la somme des 333 premiers nombres, on y ajoutera la somme des 200 premiers nombres de la suite arithmétique de raison 5 (c'est comme cela qu'on appelle l'incrément), mais il faudra aussi supprimer les multiples de 15 qui ont été compté 2 fois.

Comme vous pouvez le voir, une énigme peut se résoudre de différentes façons. Ici, la deuxième façon sera beaucoup plus rapide à exécuter que la première.