Projet Euler #15

Question

La nuit dernière, j'ai essayé de résoudre défi #15 du Projet Euler :

En commençant dans le coin supérieur gauche d'une 2×2, il y a 6 routes (sans retour en arrière) retour en arrière) jusqu'au coin inférieur droit droite.

_{(source : <a href="http://projecteuler.net/project/images/p_015.gif" rel="nofollow noreferrer">projecteuler.net </a>)}

Combien de routes y a-t-il à travers une grille 20×20 ?

Je me suis dit que ça ne devait pas être si difficile, alors j'ai écrit une fonction récursive de base :

const int gridSize = 20;

// call with progress(0, 0)
static int progress(int x, int y)
{
    int i = 0;

    if (x < gridSize)
        i += progress(x + 1, y);
    if (y < gridSize)
        i += progress(x, y + 1);

    if (x == gridSize && y == gridSize)
        return 1;

    return i;
}

J'ai vérifié qu'il fonctionnait pour des grilles plus petites comme 2×2 ou 3×3, puis je l'ai configuré pour qu'il fonctionne sur une grille 20×20. Imaginez ma surprise lorsque, 5 heures plus tard, le programme était toujours en train de calculer les chiffres, et n'avait terminé qu'à 80 % (d'après l'examen de sa position/route actuelle dans la grille).

Il est clair que je m'y prends de la mauvaise façon. Comment résoudriez-vous ce problème ? Je pense qu'il devrait être résolu en utilisant une équation plutôt qu'une méthode comme la mienne, mais ce n'est malheureusement pas mon point fort.

Mise à jour :

J'ai maintenant une version qui fonctionne. En gros, elle met en cache les résultats obtenus auparavant lorsqu'il reste un bloc n×m à parcourir. Voici le code ainsi que quelques commentaires :

// the size of our grid
static int gridSize = 20;

// the amount of paths available for a "NxM" block, e.g. "2x2" => 4
static Dictionary<string, long> pathsByBlock = new Dictionary<string, long>();

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static long progress(long x, long y)
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // create a textual representation of the remaining
    // block, for use in the dictionary
    string block = (gridSize - x) + "x" + (gridSize - y);

    // if a same block has not been processed before
    if (!pathsByBlock.ContainsKey(block))
    {
        // calculate it in the right direction
        if (x < gridSize)
            i += progress(x + 1, y);
        // and in the down direction
        if (y < gridSize)
            i += progress(x, y + 1);

        // and cache the result!
        pathsByBlock[block] = i;
    }

    // self-explanatory :)
    return pathsByBlock[block];
}

En l'appelant 20 fois, pour des grilles de taille 1×1 à 20×20, on obtient le résultat suivant :

There are 2 paths in a 1 sized grid
0,0110006 seconds

There are 6 paths in a 2 sized grid
0,0030002 seconds

There are 20 paths in a 3 sized grid
0 seconds

There are 70 paths in a 4 sized grid
0 seconds

There are 252 paths in a 5 sized grid
0 seconds

There are 924 paths in a 6 sized grid
0 seconds

There are 3432 paths in a 7 sized grid
0 seconds

There are 12870 paths in a 8 sized grid
0,001 seconds

There are 48620 paths in a 9 sized grid
0,0010001 seconds

There are 184756 paths in a 10 sized grid
0,001 seconds

There are 705432 paths in a 11 sized grid
0 seconds

There are 2704156 paths in a 12 sized grid
0 seconds

There are 10400600 paths in a 13 sized grid
0,001 seconds

There are 40116600 paths in a 14 sized grid
0 seconds

There are 155117520 paths in a 15 sized grid
0 seconds

There are 601080390 paths in a 16 sized grid
0,0010001 seconds

There are 2333606220 paths in a 17 sized grid
0,001 seconds

There are 9075135300 paths in a 18 sized grid
0,001 seconds

There are 35345263800 paths in a 19 sized grid
0,001 seconds

There are 137846528820 paths in a 20 sized grid
0,0010001 seconds

0,0390022 seconds in total

J'accepte la réponse de danben, car c'est lui qui m'a le plus aidé à trouver cette solution. Mais upvotes aussi à Tim Goodman et Agos :)

Mise à jour du bonus :

Après avoir lu la réponse d'Eric Lippert, j'y ai jeté un nouveau coup d'œil et l'ai quelque peu réécrite. L'idée de base est toujours la même, mais la partie "cache" a été supprimée et placée dans une fonction distincte, comme dans l'exemple d'Eric. Le résultat est un code beaucoup plus élégant.

// the size of our grid
const int gridSize = 20;

// magic.
static Func<A1, A2, R> Memoize<A1, A2, R>(this Func<A1, A2, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<string, R>();
    return (A1 a1, A2 a2) =>
    {
        R r;
        string key = a1 + "x" + a2;
        if (!dictionary.TryGetValue(key, out r))
        {
            // not in cache yet
            r = f(a1, a2);
            dictionary.Add(key, r);
        }
        return r;
    };
}

// calculate the surface of the block to the finish line
static long calcsurface(long x, long y)
{
    return (gridSize - x) * (gridSize - y);
}

// call using progress (0, 0)
static Func<long, long, long> progress = ((Func<long, long, long>)((long x, long y) =>
{
    // first calculate the surface of the block remaining
    long surface = calcsurface(x, y);
    long i = 0;

    // zero surface means only 1 path remains
    // (we either go only right, or only down)
    if (surface == 0)
        return 1;

    // calculate it in the right direction
    if (x < gridSize)
        i += progress(x + 1, y);
    // and in the down direction
    if (y < gridSize)
        i += progress(x, y + 1);

    // self-explanatory :)
    return i;
})).Memoize();

Au fait, je n'ai pas trouvé de meilleure façon d'utiliser les deux arguments comme clé pour le dictionnaire. J'ai fait quelques recherches sur Internet, et il semble que ce soit une solution courante. Mais bon.

Answer 1

Solution rapide sans programmation (basé sur la combinatoire)

Je suppose que "pas de retour en arrière" signifie que nous augmentons toujours soit x soit y.

Si c'est le cas, nous savons qu'au total nous aurons 40 étapes à franchir pour atteindre l'arrivée -- 20 augmentations de x, 20 augmentations de y.

La seule question est de savoir lesquels des 40 sont les 20 augmentations de x. Le problème se résume à : combien de façons différentes pouvez-vous choisir 20 éléments parmi un ensemble de 40 éléments. (Les éléments sont : étape 1, étape 2, etc. et nous choisissons, disons, ceux qui sont des augmentations de x).

Il existe une formule pour cela : c'est le coefficient binomial avec 40 en haut et 20 en bas. La formule est la suivante 40!/((20!)(40-20)!) en d'autres termes 40!/(20!)^2 . Ici ! représente la factorielle. (par exemple, 5! = 5*4*3*2*1 )

En annulant un des 20 ! et une partie des 40 !, cela devient : (40*39*38*37*36*35*34*33*32*31*30*29*28*27*26*25*24*23*22*21)/(20*19*18*17*16*15*14*13*12*11*10*9*8*7*6*5*4*3*2*1) . Le problème est donc réduit à une simple arithmétique. La réponse est 137,846,528,820 .

À titre de comparaison, notez que (4*3)/(2*1) donne la réponse à partir de leur exemple, 6 .

Answer 2

Cela peut être fait beaucoup plus rapidement si vous utilisez programmation dynamique (stockage des résultats des sous-problèmes plutôt que de les recalculer). La programmation dynamique peut être appliquée à des problèmes qui présentent une sous-structure optimale - ce qui signifie qu'une solution optimale peut être construite à partir de solutions optimales à des sous-problèmes (crédit Wikipedia ).

Je préfère ne pas dévoiler la réponse, mais considérez comment le nombre de chemins vers le coin inférieur droit peut être lié au nombre de chemins vers les carrés adjacents.

De plus, si vous deviez faire ce travail à la main, comment le feriez-vous ?

Answer 3

Comme d'autres l'ont noté, il existe une solution mathématique discrète à ce problème particulier. Mais supposons que vous vouliez le résoudre de manière récursive. Votre problème de performance est que vous résolvez les mêmes problèmes encore et encore.

Laissez-moi vous montrer une petite astuce de programmation d'ordre supérieur qui vous rapportera beaucoup. Prenons un problème récursif plus simple :

long Fib(n) 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
}

Vous lui demandez de calculer Fib(5). Cela calcule Fib(4) et Fib(3). En calculant Fib(4), on calcule Fib(3) et Fib(2). En calculant Fib(3), on calcule Fib(2) et Fib(1). En calculant Fib(2), on calcule Fib(1) et Fib(0). Maintenant, nous revenons en arrière et calculons Fib(2). à nouveau . Puis nous revenons en arrière et calculons Fib(3) à nouveau . Des quantités énormes de recalcul.

Supposons que nous mettions en cache les résultats du calcul. Puis, la deuxième fois que le calcul est demandé, nous renvoyons simplement le résultat mis en cache. Maintenant vient l'astuce d'ordre supérieur. Je veux représenter ce concept de "mise en cache des résultats d'une fonction" comme une fonction qui prend une fonction et me renvoie une fonction qui a cette belle propriété. Je vais l'écrire comme une méthode d'extension sur les fonctions :

static Func<A, R> Memoize(this Func<A, R> f)
{
    // Return a function which is f with caching.
    var dictionary = new Dictionary<A, R>();
    return (A a)=>
    {
        R r;
        if(!dictionary.TryGetValue(a, out r))
        { // cache miss
            r = f(a);
            dictionary.Add(a, r);
        }
        return r;
    };
}

Maintenant, nous faisons quelques réécritures mineures sur Fib :

Func<long, long> Fib = null;
Fib = (long n) => 
{
    if (n < 2) return 1;
    return Fib(n-1) + Fib(n-2);
};

OK, nous avons notre fonction non mémorisée. Maintenant, la magie :

Fib = Fib.Memoize();

Et boum, quand on appelle Fib(5), on fait maintenant une recherche dans le dictionnaire. 5 n'est pas dans le dictionnaire, donc nous appelons la fonction originale. Cela appelle Fib(4), qui fait une autre recherche dans le dictionnaire et rate son coup. Cette fonction appelle Fib(3), et ainsi de suite. Lorsque nous appelons à nouveau Fib(2) et Fib(3), la fonction deuxième les résultats sont déjà dans le dictionnaire, donc nous ne les recalculons pas.

Écriture d'une version à deux arguments :

static Func<A1, A2, R> Memoize(this Func<A1, A2, R>) { ... }

n'est pas trop difficile et est laissé comme un exercice. Si vous faites cela, alors vous pouvez simplement prendre votre belle logique récursive originale, faire une simple réécriture dans un lambda, et dire :

progress = progress.Memoize();

et soudainement vos performances augmenteront, sans perte de lisibilité de l'algorithme original.

Answer 4

Bien que la programmation dynamique soit certainement un moyen correct de résoudre ce type de problèmes, cette instance particulière présente une régularité qui peut être exploitée.

Vous pouvez considérer que le problème consiste à arranger un certain nombre de "droite" et de "bas", en veillant à ne pas compter plusieurs fois des arrangements identiques.
Par exemple, les solutions du problème de la taille 2 (rapportées dans les images de la question) peuvent être vues de cette façon :

Ainsi, pour toute grille de côté n, vous pouvez trouver la solution au moyen de combinatoire :

from math import factorial
n = 20
print factorial(2*n)/(factorial(n)*factorial(n))

2n ! est le nombre d'arrangements de 20 + 20, tandis que les deux n ! représentent les façons identiques dont les et peuvent être arrangés.

Answer 5

À propos, vous pouvez encore améliorer vos performances en réalisant qu'un 2x3 aura le même nombre de chemins à travers lui qu'un 3x2. Votre fonction memorize ne semble tenir compte que d'une chaîne de caractères qui est exactement colonnes x lignes. Cependant vous pouvez inclure dans votre memorize de mettre le total des chemins pour la clé de 2x3 ainsi que 3x2.

Ainsi, lorsque vous mémorisez 4x2 etc., il remplit automatiquement 2x4 avec le même nombre de chemins. Cela vous fera gagner beaucoup de temps, car vous avez déjà calculé une fois tous les chemins passant par cette surface, alors pourquoi le faire à nouveau ?