Проект Эйлера № 15

Question

Прошлой ночью я пытался решить задачу № 15 от Project Euler :

Начиная с верхнего левого угла Сетка 2х2, есть 6 маршрутов (без возврат) внизу справа угол.

_{(источник: projecteuler.net )}

Сколько существует маршрутов через Сетка 20 × 20?

Я подумал, что это не должно быть так сложно, поэтому я написал базовую рекурсивную функцию:

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;
}

Я проверил, что он работает для меньших сеток, таких как 2 × 2 или 3 × 3, а затем настроил его для работы с сеткой 20 × 20. Представьте себе мое удивление, когда 5 часов спустя программа все еще успешно разбирала цифры, и только около 80% сделали это (основываясь на проверке ее текущей позиции / маршрута в сетке).

Очевидно, я поступаю неправильно. Как бы вы решили эту проблему? Я думаю, что это должно быть решено с использованием уравнения, а не метода, подобного моему, но, к сожалению, это не является моей сильной стороной.

Обновление

Теперь у меня есть рабочая версия. В основном он кэширует результаты, полученные до того, как блок n × m еще предстоит пройти. Вот код вместе с некоторыми комментариями:

// 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];
}

Вызов его 20 раз для сеток с размерами от 1 × 1 до 20 × 20 дает следующий вывод:

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

Я принимаю ответ Данбена, потому что он помог мне найти это решение наиболее. Но приветствует также Тим Гудман и Агос:)

Бонусное обновление :

Прочитав ответ Эрика Липперта, я еще раз посмотрел и несколько переписал его. Основная идея все та же, но часть кэширования была удалена и помещена в отдельную функцию, как в примере Эрика. В результате получается более элегантный код.

// 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();

Кстати, я не мог придумать лучшего способа использовать два аргумента в качестве ключа для словаря. Я немного погуглил, и, похоже, это общее решение. Ну хорошо.

Answer 1

Вы можете вдвое сократить время расчета, принимая во внимание, что при уменьшении его до квадрата сетка станет симметричной. Поэтому, когда у вас есть равное количество пространства в направлениях X и Y для прохождения оставшихся, вы можете использовать один и тот же расчет для увеличения хода x и увеличения хода y.

При этом я делал это на python и много кешировал результаты, чтобы избежать пересчета.

Answer 2

Мое решение было наивно, но довольно легко понять:

Количество маршрутов до данного пересечения в сетке является суммой количества маршрутов к двум его соседям.

Учитывая, что существует только один маршрут к каждой из точек на верхнем и левом краях, довольно легко перебрать оставшиеся точки и заполнить пробелы.

для x или y = 0: сетка [x, y] = 1
для x и y> = 1: сетка [x, y] = сетка [x-1, y] + сетка [x, y -1]

Таким образом, после итерации по всем квадратам окончательный ответ содержится в сетке [20,20].

Answer 3

Каждый указывает на динамическое программирование и результаты кэширования. У меня где-то есть скрипт на Ruby, в результате которого получился очень большой хэш, в котором хранились все данные. По правде говоря, как и большинство задач проекта Эйлера, это скрытый математический трюк, и есть способы получить результат с помощью простого вычисления.