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

Dans l'enchaînement, ou presque, une solution au problème 15. Le problème 15 est un peu effrayant puisqu'il a un énoncé du genre qui déroute à priori, à savoir "Il y a 6 chemins (sans retour en arrière) pour aller du coin supérieur gauche au coin inférieur droit dans une grille de 2x2; combien y a-t-il de chemins dans une grille de 20x20?".

Ouch.

Papier, crayon...

Sur une grille de dimension 1, il y a 2 chemins possibles. Sur une grille de dimension 2, il y a 6 chemins possibles. Sur une grille de dimension 3, il y a 20 chemins possibles. Sur une grille de dimension 4, il y a 70 chemins possibles (non je ne les ai pas énumérés sur papier ceux-là). ...

Ces valeurs ne sont forcément pas innocentes. Plus précisément, ce sont les valeurs centrales du triangle de Pascal, pour les lignes où "valeur centrale" a un sens.

Mon algorithme se base là-dessus.

#! /usr/bin/env python

# 2009/02/20 - euler015.py
# Solution au Probleme 15 de Project Euler
# http://projecteuler.net/index.php?section=problems&id=15
# Jean Karim Bockstael - jkb@jkbockstael.be

def pascaltrirow(row):
    if row == 1:
        return [1]
    else:
        upper = pascaltrirow(row - 1)
        current = [1]
        for i in range(1, len(upper)):
            current.append(upper[i] + upper[i - 1])
        current.append(1)
        return current

def pascaltricell(row, col):
    currow = pascaltrirow(row)
    return currow[col - 1]

def euler15(size):
    centralvalue = pascaltricell((size * 2) + 1, size + 1)
    return centralvalue

print euler15(20)

cc-by-nc | code (python) | project euler

<<< Project Euler : solution au problème 13, en Python (2009-02-20) | Project Euler : solution au problème 14, en Python (2009-02-20) >>>