Project Euler es una serie de apasionantes problemas de programación, a menudo con una base matemática. Estos problemas suelen estar diseñados para requerir el desarrollo de algoritmos sofisticados que permitan alcanzar el objetivo en un plazo razonable. Hoy resolveremos el Problema 15: Caminos reticulares , que puede resolverse mediante métodos combinatorios sencillos.
La pregunta es la siguiente:
„Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner. How many such routes are there through a 20×20 grid?“
El problema también se puede formular de manera diferente: lo que se necesita es el poder del subconjunto de todos los caminos
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Este es un problema combinatorio simple en el que usamos el modelo de urna (sin reemplazar y sin considerar el orden). Ahora estamos interesados precisamente en aquellos caminos para los que se sostiene que \(R\) y \(D\) exactamente con la misma frecuencia. Esto da como resultado todas las combinaciones posibles:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Para \(n=20\) obtenemos:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Podemos extender el problema a las cuadrículas no cuadradas. La siguiente solución implementa un cálculo en PHP con la ayuda de bcmath con un tiempo de ejecución de \( O(n) \) con el formato de entrada "Número de casos de prueba, \(n_1\) \(m_1\) , ...":
47bb78215ee0531a787bb5034652eaf4
Por cierto, todos los problemas del Proyecto Euler también se pueden resolver en línea en el sitio recomendado de HackerRank .