round - root c# math
Proyecto Euler#15 (13)
Anoche intenté resolver el desafío # 15 del Proyecto Euler :
Comenzando en la esquina superior izquierda de una cuadrícula 2 × 2, hay 6 rutas (sin retroceso) a la esquina inferior derecha.
texto alternativo http://projecteuler.net/project/images/p_015.gif
¿Cuántas rutas hay a través de una cuadrícula de 20 × 20?
Pensé que esto no debería ser tan difícil, así que escribí una función recursiva básica:
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;
}
Verifiqué que funcionaba para redes más pequeñas, como 2 × 2 o 3 × 3, y luego lo configuré para una cuadrícula de 20 × 20. Imagínense mi sorpresa cuando, 5 horas después, el programa todavía estaba felizmente machacando los números, y solo un 80% hecho (basado en el examen de su posición / ruta actual en la cuadrícula).
Claramente estoy haciendo esto de la manera incorrecta. Como resolverías este problema? Estoy pensando que debería resolverse usando una ecuación en lugar de un método como el mío, pero desafortunadamente no es un lado fuerte mío.
Actualización :
Ahora tengo una versión funcional. Básicamente almacena en caché los resultados obtenidos antes cuando un bloque de × m todavía no se ha atravesado. Aquí está el código junto con algunos comentarios:
// 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];
}
Llamarlo 20 veces, para cuadrículas con tamaño 1 × 1 a 20 × 20 produce el siguiente resultado:
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
Estoy aceptando la respuesta de Danben porque me ayudó a encontrar esta solución al máximo. Pero también vota a Tim Goodman y Agos :)
Actualización de bonificación :
Después de leer la respuesta de Eric Lippert, volví a mirar y reescribí un poco. La idea básica sigue siendo la misma, pero la parte de almacenamiento en caché se ha eliminado y puesto en una función separada, como en el ejemplo de Eric. El resultado es un código de aspecto mucho más elegante.
// 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();
Por cierto, no puedo pensar en una mejor manera de usar los dos argumentos como una clave para el diccionario. Busqué en Google un poco, y parece que esta es una solución común. Oh bien.
Aunque la programación dinámica parece una forma atractiva de abordar el problema (y lo convierte en un desafío de codificación interesante), un poco de pensamiento creativo sobre las estructuras de datos se presta para dar una respuesta inmediata.
[El resto de esto es esencialmente una explicación de por qué la respuesta de Tim Goodman es la mejor, por algún valor de "mejor"]
Si tenemos una grilla nXm, podemos representar cada ruta válida de esquina a esquina como una cadena de bits n + m, usando 0 o 1 para representar "abajo". Un poco más de pensamiento da a la mano que el número exacto de rutas es el número de formas de tomar N elementos de los elementos N + M y esto, convenientemente, pasa a ser el estándar simple combinatorio M sobre N.
Entonces, para cualquier rectángulo N + M, el número de rutas posibles desde la esquina superior izquierda a la esquina inferior derecha es (n + m) (n + m-1) ... (m + 1) / (n * (n-1) * ... 1).
El programa más rápido es el que no tiene que almacenar mucho, utiliza mucho en el almacenamiento y (idealmente) tiene una respuesta cerrada.
Como otros han notado, hay una solución matemática discreta para este problema en particular. Pero supongamos que quieres resolverlo recursivamente. Su problema de rendimiento es que está resolviendo los mismos problemas una y otra vez.
Déjame mostrarte un pequeño truco de programación de orden superior que dará grandes dividendos. Tomemos un problema recursivo más fácil:
long Fib(n)
{
if (n < 2) return 1;
return Fib(n-1) + Fib(n-2);
}
Usted pide esto para calcular Fib (5). Eso calcula Fib (4) y Fib (3). Computing Fib (4) calcula Fib (3) y Fib (2). Computing Fib (3) calcula Fib (2) y Fib (1). Computing Fib (2) calcula Fib (1) y Fib (0). Ahora volvemos y calculamos Fib (2) nuevamente . Luego volvemos y calculamos Fib (3) nuevamente . Enormes cantidades de recalculación.
Supongamos que almacenamos en caché los resultados del cálculo. Luego, la segunda vez que se solicitó el cálculo, simplemente devolveríamos el resultado almacenado en caché. Ahora viene el truco de orden superior. Quiero representar este concepto de "almacenar en caché los resultados de una función" como una función que adopta una función y me devuelve una función que tiene esta propiedad agradable. Lo escribiré como un método de extensión en funciones:
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;
};
}
Ahora hacemos una reescritura menor en Fib:
Func<long, long> Fib = null;
Fib = (long n) =>
{
if (n < 2) return 1;
return Fib(n-1) + Fib(n-2);
};
OK, tenemos nuestra función no memorable. Ahora, magia
Fib = Fib.Memoize();
Y boom, cuando llamamos a Fib (5), ahora hacemos una búsqueda en el diccionario. 5 no está en el diccionario, entonces llamamos a la función original. Eso llama a Fib (4), que realiza otra búsqueda en el diccionario y falla. Eso llama a Fib (3), y así sucesivamente. Cuando volvemos a llamar a Fib (2) y Fib (3) la segunda vez, los resultados ya están en el diccionario, por lo que no los recalculamos.
Escribir una versión de dos argumentos:
static Func<A1, A2, R> Memoize(this Func<A1, A2, R>) { ... }
no es demasiado difícil y se deja como un ejercicio. Si haces eso, entonces puedes simplemente tomar tu hermosa lógica recursiva original, hacer una simple reescritura en un lambda, y decir:
progress = progress.Memoize();
y de repente su rendimiento aumentará, sin pérdida de legibilidad del algoritmo original.
Creo que algunas matemáticas de secundaria serían útiles aquí, este enlace explica la fórmula de combinación requerida:
http://mathworld.wolfram.com/Combination.html
Ahora, usando esto para encontrar el número de caminos a través de una cuadrícula, la fórmula se convierte en 2n, elija n. Como advertencia, deberá usar un tipo de datos que pueda contener un número bastante grande
De hecho, estás calculando números catalanes para los que está disponible una fórmula cerrada que usa la serie de Taylor.
Entonces, un programa que compute la solución podría calcular coeficientes binomiales, que son difíciles de obtener si no tiene una clase BigInt ...
El problema es mucho más simple de lo que muchas personas creen. La ruta debe ser una secuencia con 20 ''derechos'' y 20 ''downs''. El número de secuencias diferentes es la cantidad de formas en que puede elegir 20 posiciones para (por ejemplo) ''derechos'' fuera de los posibles 40.
Esto se puede hacer mucho más rápido si usa la programación dinámica (almacenando los resultados de subproblemas en lugar de volver a calcularlos). La programación dinámica se puede aplicar a problemas que exhiben una subestructura óptima; esto significa que se puede construir una solución óptima a partir de soluciones óptimas a subproblemas (crédito de Wikipedia ).
Preferiría no dar la respuesta, pero considere cómo el número de caminos a la esquina inferior derecha puede estar relacionado con el número de caminos a los cuadrados adyacentes.
Además, si tuvieras que resolver esto a mano, ¿cómo lo harías?
Las soluciones se reflejan a lo largo de una diagonal desde el NW hasta el SE de su cuadrícula. Entonces, solo deberías calcular soluciones para la mitad superior derecha de la grilla, y luego reflejarlas para obtener la otra mitad ...
Mi solución fue niaive pero bastante fácil de entender:
El número de rutas a una intersección dada en una cuadrícula es la suma del número de rutas a sus dos vecinos.
Dado que solo hay una ruta para cada uno de los puntos en los bordes superior e izquierdo, es bastante fácil iterar sobre los puntos restantes y rellenar los espacios en blanco.
para x o y = 0: cuadrícula [x, y] = 1
para x y y> = 1: grid [x, y] = grid [x-1, y] + grid [x, y-1]
Entonces, después de iterar sobre todos los cuadrados, la respuesta final está contenida en la cuadrícula [20,20].
Por cierto, puedes aumentar aún más tu rendimiento al darte cuenta de que un 2x3 tendrá la misma cantidad de rutas a través de él que un 3x2. Su función de memorización parece representar solo una cadena que es exactamente columnas x filas. Sin embargo, puede incluir en su memorización para poner las rutas totales para la clave de 2x3 y 3x2.
Entonces, cuando memorice 4x2, etc., automáticamente completará 2x4 con la misma cantidad de rutas. Esto reducirá tu tiempo de manera que ya has calculado todos los caminos a través de esa área de superficie una vez antes, entonces ¿por qué hacerlo de nuevo?
Puede reducir a la mitad el tiempo de cálculo teniendo en cuenta que, una vez que lo reduce a un cuadrado, la cuadrícula será simétrica. Por lo tanto, siempre que tenga la misma cantidad de espacio en la dirección X e Y para recorrer el resto, puede usar el mismo cálculo para el aumento de x viajes y el aumento de viajes.
Una vez dicho esto, hice esto en Python e hice un montón de almacenamiento en memoria caché de los resultados para evitar volver a calcular.
Si bien la programación dinámica es ciertamente una forma correcta de resolver este tipo de problemas, esta instancia en particular muestra una regularidad que puede ser explotada.
Puede ver el problema como organizar una serie de "derecha" s y "abajo" s, teniendo cuidado de no contar varias veces arreglos idénticos.
Por ejemplo, las soluciones del problema de tamaño 2 (informadas en las imágenes de la pregunta) se pueden ver de esta manera:
→→↓↓
→↓→↓
→↓↓→
↓→→↓
↓→↓→
↓↓→→
Entonces, para cualquier grilla de lado n, puede encontrar la solución por medio de combinatorics :
from math import factorial
n = 20
print factorial(2*n)/(factorial(n)*factorial(n))
2n! es el número de arreglos de los 20 → + 20 ↓, mientras que los dos n! tenga en cuenta las formas idénticas en que se pueden organizar los → y ↓.
Todo el mundo indica programación dinámica y resultados de almacenamiento en caché. Tengo, en alguna parte, un script de Ruby que terminó con un hash muy grande donde se almacenaron todos los datos. En verdad, como la mayoría de los problemas del proyecto Euler, este es un ''truco'' matemático oculto, y hay formas de obtener el resultado con un simple cálculo.
Solución Rápida de No Programación (basada en combinatoria)
Considero que "sin retroceso" significa que siempre aumentamos x o aumentamos y.
Si es así, sabemos que en total tendremos 40 pasos para llegar al final: 20 aumentos en x, 20 aumentos en y.
La única pregunta es cuál de los 40 son los 20 aumentos en x. El problema es: cuántas formas diferentes puede elegir 20 elementos de un conjunto de 40 elementos. (Los elementos son: paso 1, paso 2, etc. y elegimos, por ejemplo, los que aumentan en x).
Hay una fórmula para esto: es el coeficiente binomial con 40 en la parte superior y 20 en la parte inferior. La fórmula es 40!/((20!)(40-20)!) , En otras palabras 40!/(20!)^2 . Aquí ! representa factorial (por ej., 5! = 5*4*3*2*1 )
Cancelando uno de los 20! y parte de los 40 !, esto se convierte en: (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) . El problema se reduce a simple aritmático. La respuesta es 137,846,528,820 .
Para comparar, tenga en cuenta que (4*3)/(2*1) da la respuesta de su ejemplo, 6 .