Voici un résumé de l'énoncé du problème 19 "Counting Sundays" du Project Euler (traduction complète en français ici) :

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000) ?

Compréhension du problème

Reformulons le problème : il nous faut trouver le nombre de dimanches qui tombent le premier du mois dans tout le XXè siècle.

Pour résoudre ce problème, 2 méthodes existent (sûrement plus). La première est relativement simple et est réalisable sur Python, ce qui n'est pas le cas pour tous les langages : cette méthode consiste à lister toutes les dates qui correspondent à un premier du mois (01/01/1901, 01/02/1901, 01/03/1901...) et à demander à Python, en important au préalable la bibliothèque datetime, le jour de la semaine qui correspondait à cette date, permettant de compter facilement le nombre de dimanches.

La seconde méthode est plus compliquée, mais par contre est implémentable sur n'importe quel langage. Cette méthode consiste, non plus à trouver le jour de la semaine en fonction de la date, mais à trouver la date en fonction du jour de la semaine, c'est à dire que si nous savons que le 07/01/1900 est un dimanche (information donnée dans l'énoncé du problème), nous pouvons en déduire que le 14/01/1900, puis le 21/01/1900 et 28/01/1900 sont aussi des dimanches. En d'autres termes, si nous connaissons une date correspondant à un dimanche, ainsi que les différentes informations (fournies dans l'énoncé) au sujet des dates, alors nous pouvons trouver toutes les dates correspondant à un dimanche ou un autre jour de la semaine.

Dans notre cas, il nous faut donc, en partant du dimanche 07/01/1900, lister les dates de tous les dimanches postérieurs et regarder ceux qui tombent, durant le XXème siècle, un 1er du mois.

Le programme

Voici donc les programmes Python correspondant aux 2 méthodes et utilisables pour résoudre ce problème :

• 1er programme correspondant à la 1ère méthode :

  import datetime
  resultat = 0
  for i in range(1901, 2001):
      for j in range(1, 13):
          #la fonction date prend en paramètre le mois, l'année et le jour et
          #retourne le numéro du jour de la semaine, le 6 étant le dimanche
          if datetime.date(i, j, 1).weekday() == 6:
              resultat += 1
  print(resultat)

• 2ème programme correspondant à la 2nd méthode :

  #Cette fonction prend en paramètre une date (sous forme de liste)
  #et retourne la date suivante ayant le même jour de la semaine
  def get_next_sunday(date):
      #On initialise le nombre de jour de chacun des mois de l'année
      month_len = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
      #Teste si l'année est bissextile. Si c'est le cas, on passe le
      #nombre de jour du mois de février à 29
      if date[2]%4 == 0 and (date[2]%100 != 0 or date[2]%400 == 0):
          month_len[1] = 29
      #On augmente le nombre de jour de 7
      date[0] += 7
      #On regarde si le nouveau nombre de jour est supérieur au maximum de
      #nombre de jour du mois. Si c'est le cas, on augmente de 1 le nombre
      #de mois et baisse le nombre de jour.
      if date[0] > month_len[date[1]-1]:
          date[0] = date[0] - month_len[date[1]-1]
          date[1] += 1
          #On regarde si le nombre de mois est supérieur à 12. Si c'est le cas,
          #on augmente de 1 le nombre de mois et remet à 0 le nombre de mois.
          if date[1] > 12:
              date[1] = date[1]%12
              date[2] += 1
      return date
  resultat = 0
  #On initialise la date du 1er dimanche au 07/01/1900
  date = [7, 1, 1900]
  #On trouve la date correspondant au 1er dimanche de 1901
  while date[2] != 1901:
      date = get_next_sunday(date)
  #A partir de cette nouvelle date, on liste les dates de tous
  #les dimanches du XXe siècle et regarde si elles correspondent
  #à un premier du mois.
  while date[2] != 2001:
      if date[0] == 1:
          resultat += 1
      date = get_next_sunday(date)
  print(resultat)

Il est clair que le 1er programme est bien plus simple et court que le second. Cela est dû au fait que Python possède nativement une fonction retournant le numéro du jour de la semaine en fonction d'une date, ce qui n'est pas le cas de tous les langages de programmation.

Le résultat

La réponse à ce problème est 171.