OK, ok, that wasn't very fair. We need to use the computer to solve anything bigger than a few lily pads. There's lots of ways to do this, for example, we could simply try starting at each pad calculate all possible sums, and then eliminate the paths that aren't valid.

Let's use n to be the number of lily pads. The above method would take n factorial (n!) steps. That's a lot of steps. The technical term for this is brute force. For example, if we had 10 lily pads, that would be 3,628,800 steps. If we could do 10,000,000 steps per second (not unreasonable on a even a smart phone in 2023), that would take a third of a second.

But if we had 20 lily pads, that would be 2,432,902,008,176,640,000 steps. If we could do 10,000,000,000 steps per second, that would take 2.4 x 10⁸ seconds. That's 7 and a half years! And we haven't even filtered out the invalid paths.

Let's create a data structure called a Directed Acyclic Graph (DAG). A graph is a set of nodes and edges, basically what we have already been using. Directed means that all the edges have a, er, direction. In our case, the direction is from left to right. Acyclic means that there are no loops. In our case, that means that we can't go back to a lily pad we have already visited.

Instead of 2.4 quintillion possible connections, we only have 103. So we don't have to wait 7 years. Even better, there are very efficient algorithms for finding the shortest path in a DAG.

The shortest path means the path with edges with the lowest values. We want the path with the maximum sum. So we have to have change +infinity to -infinity. The code looks like this:

    function max_path(d, seq) {
    const n = seq.length;
    let max_sum = [...seq]; // Copy of seq array to avoid overwriting
    let best_path = Array.from({ length: n }, (_, i) => [i]); // Initialize an array for storing paths
    for (let node = n - 1; node >= 0; node--) {
        if (d[node].length > 0) {
        let max_val = Number.NEGATIVE_INFINITY;
        let max_node = -1;
        for (let next_node of d[node]) {
            if (max_sum[next_node] > max_val) {
                max_val = max_sum[next_node];
                max_node = next_node;
                }
            }
        max_sum[node] = max_val + seq[node];
        best_path[node] = [node].concat(best_path[max_node]);
        }
    }
    let max_sum_start = Math.max(...max_sum); // maximum sum among all starting nodes
    let start_node = max_sum.indexOf(max_sum_start); // starting node for the maximum sum
    let path = best_path[start_node]; // path corresponding to the maximum sum
    return [max_sum_start, path];
    }

If you are familiar with "dynamic programming" that's what this is. We keep track of the best path and sum as we go. We start from the right and work backwards. Using a technique called "memoization" we only have to compute the sum for each node once. This is plus the DAG (d) is how we get the speedup.

(You may have expected recursion, but we don't need recursion for dynamic programming.)

The Grasshopper 🦗 and the Lily Pads 🪷

Page 2