Project Euler ist eine Serie von spannenden Programmier-Problemen, die oft einen mathematisch Hintergrund haben. Die Probleme sind oft so gestellt, das man raffinierte Algorithmen entwickeln muss, um in einer vernünftigen Laufzeit zum Ziel zu kommen. Heute lösen wir Problem 15: Lattice paths, bei dem man mit einfachen kombinatorischen Mitteln an die Lösung kommt.
Die Frage lautet wie folgt:
„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?“
Die Problemstellung lässt sich auch anders formulieren: Gesucht ist die Mächtigkeit der Teilmenge aller Wege
$$W = {w_1, …, w_{2^n}}, \, w_k = p_1 \cdots p_{2\cdot n}, \, p_k \in \{ R, D \}.$$
Es handelt sich hier um ein einfaches kombinatorisches Problem, bei dem wir das Urnenmodell heranziehen (ohne Zurücklegen und ohne Beachtung der Reihenfolge). Wir sind nun genau an denjenigen Wegen interessiert, für die gilt, dass \(R\) und \(D\) genau gleich oft vorkommen. Demnach ergibt sich für alle möglichen Kombinationen:
$$\binom{2\cdot n}{n} = \frac{(2\cdot n)!}{n!\cdot n!}$$
Für \(n=20\) ergibt sich damit:
$$ \frac{(40)!}{20!\cdot 20!} = 137846528820.$$
Wir können das Problem auf nicht-quadratische Grids erweitern. Nachfolgende Lösung realisiert in PHP mit Hilfe von bcmath mit einer Laufzeit von \( O(n) \) eine Berechnung mit dem Eingabeformat "Anzahl der Testfälle, \(n_1\) \(m_1\), ...":
47bb78215ee0531a787bb5034652eaf4
Alle Probleme des Euler Projects lassen sich auf der empfehlenswerten Seite HackerRank übrigens auch online lösen.