Project Euler: solution au problème 28, en Python

Ça faisait longtemps que je n'avais pas gratifié mon blog d'un des si particulièrement passionnants problèmes de Project Euler. Il était grand temps d'y remédier, donc voici une solution au problème 28.

L'idée est de remplir une grille carrée de nombres, de dimension impaire, qui est remplie des entiers successifs en spirale partant du centre et allant vers la droite et le bas. Aga? En gros, ayant ce genre de chose:

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

La somme des éléments de deux diagonales de ce carré de dimension 5 vaut 101. Que vaut la somme pour un carré de dimension 1001?

Je vous avais présenté mon pote Récursion?

#! / usr/bin/python

# 2009/06/26 - euler028.py
# Solution au Probleme 28 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=28
# Jean Karim Bockstael - jkb@jkbockstael.be

def sum_of_diagonals(dimension):
    if (dimension == 1):
        return 1
    else:
        corner_tr = dimension ** 2
        corner_tl = corner_tr - dimension + 1
        corner_bl = corner_tl - dimension + 1
        corner_br = corner_bl - dimension + 1
        corner_sum = corner_tr + corner_tl + corner_bl + corner_br
        return corner_sum + sum_of_diagonals(dimension - 2)

print sum_of_diagonals(1001)

...la suite par ici...

Codechef: Petit déjeuner de l'autre côté du miroir

The Codechef, le concours de programmation organisé par Directi, propose depuis peu deux problèmes par jour via Twitter. Ce matin, le problème est de compter le nombre d'entiers inférieurs à 1000 qui, quand on les ajoute à leur image miroir, forment un entier qui n'est composé que de chiffres impairs.

Exemple simple:

...
20 + 02 = 22 NON
21 + 12 = 33 OUI
22 + 22 = 44 NON
...


Et comme d'habitude, j'ai sorti l'ami Python, celui qui nous veut du bien.

#! /usr/bin/python
# Codechef Twitter Daily 2009/06/24
# How many numbers below 1000 which when added with their respective mirror images result in a number with entirely odd digits?
# 2009/06/24 - Jean Karim Bockstael - jkb@jkbockstael.be


def reverse_number(num):
    return int(str(num)[::-1])

def is_all_odds(num):
    for digit in str(num):
        if (int(digit) % 2 == 0):
            return False
    return True

def count_mirrors(max):
    n_mirrors = 0
    for num in range(1, max):
        if is_all_odds(num + reverse_number(num)):
           n_mirrors += 1
    return n_mirrors

print count_mirrors(1000)

...la suite par ici...

Tiens j'avais oublié ça...

Il est un fait établi qu'il m'arrive souvent de perdre de vue quelque chose tant mes occupations et projets sont nombreux et variés. Il est également un fait établi qu'il m'arrive dans ma distraction d'effectuer du nettoyage par le vide et de le regretter après, bien que ça ne porte pas à conséquences (sinon il y aurait une copie de sauvegarde, c'est évident).

Ainsi, dans mon tout premier post sur le présent blog, je donnais un petit teaser d'un projet personnel qui approchait de la fin et que je m'apprêtais à vous dévoiler. J'avais juste montré ceci:

Et, comme un distrait que je suis, non content d'avoir oublié de donner suite à cette promesse je me suis permis d'éradiquer par un bon vieux rm des familles le répertoire où je conservais les photos des différentes étapes de la réalisation dudit projet, qui s'étalait sur quelques mois de temps libre trop sporadique.

Bon tant pis, vous n'aurez droit qu'au produit fini alors:

...la suite par ici...