Today's Little Program solves the following problem:

Consider a two-dimensional board, tall and narrow. Into the board are nailed a number of horizontal obstacles. Place a water faucet at the top of the board and turn it on. The water will dribble down, and when it hits an obstacle, some of the water will go left and some will go right. The goal is to find the shortest path to the ground from a given starting position, counting both horizontal and vertical distance traveled.

In the above diagram, the water falls three units of distance until it encounters Obstacle 1, at which some goes to the left and some goes to the right. The water that goes to the left travels three units of distance before it reaches the end of the obstacle, then falls three units and encounters Obstacle 2. Upon reaching Obstable 2, the water can again choose to flow either left or right. The water that flows to the left falls to the ground; the water that flows to the right falls and encounters a third obstacle. From the third obstacle, the water can flow left or right, and either way it goes, it falls to the ground. On the other hand, the water that chose to flow to the right when it encountered Obstable 1 iwould fall past Obstacle 2 (which is not in a position to intercept the water) and land directly on Obstacle 3.

In the above scenario, there are five paths to the ground.

- From Obstacle 1, flow left, then from Obstacle 2, flow left again. Total distance traveled: 17 units.
- From Obstacle 1, flow left, then from Obstacle 2, flow right, then from Obstacle 3, flow left. Total distance traveled: 18 units.
- From Obstacle 1, flow left, then from Obstacle 2, flow right, then from Obstacle 3, flow right. Total distance traveled: 20 units.
- From Obstacle 1, flow right, then from Obstacle 3, flow left. Total distance traveled: 16 units.
- From Obstacle 1, flow right, then from Obstacle 3, flow right. Total distance traveled: 14 units.

In this case, the shortest path to the ground is the last path.

There are many ways to attack this problem. The brute force solution would be to enumerate all the possible paths to the ground, then pick the shortest one.

A more clever solution would use a path-finding algorithm like A*, where the altitude above the ground is the heuristic.

In both cases, you can add an optimization where once you discover two paths to the same point, you throw out the longer one. This may short-circuit future computations.

But I'm going to use an incremental solution, since it has the advantage of incorporating the optimization as a convenient side-effect. Instead of studying individual drops of water, I'm going to study all of them at once. At each step in the algorithm, the data structures represent a horizontal cross-section of the above diagram, representing all possible droplet positions at a fixed altitude.

In addition to collapsing redundant paths automatically, this algorithm has the nice property that it can be done as an on-line algorithm: You don't need to provide all the obstacles in advance, as long as the obstacles are provided in order of decreasing altitude.

Instead of presenting the raw code and discussing it later (as is my wont), I'll explain the code as we go via code comments. We'll see how well that works.

I originally wrote the program in C# because I thought I would need one of the fancy collection classes provided by the BCL, but it turns out that I didn't need anything fancier than a hash table. After I wrote the original C# version, I translated it to JavaScript, which is what I present here.

The inputs which correspond to the diagram above are

- Initial X position = 6, Initial Y position = 12
- Obstacle: Left = 3, Right = 7, height = 9
- Obstacle: Left = 1, Right = 5, height = 6
- Obstacle: Left = 4, Right = 8, height = 3

And here's the program.

function Obstacle(left, right, y) { this.left = left; this.right = right; this.y = y; } // A single step in a path, representing the cost to reach that point. function Step(x, y, cost) { this.x = x; this.y = y; this.cost = cost; } // Add a step to an existing step Step.prototype.to = function to(x, y) { var dx = Math.abs(this.x - x); var dy = Math.abs(this.y - y); return new Step(x, y, this.cost + dx + dy); } // Record a droplet position function addDroplet(l, step) { // If no previous droplet at this position or the new droplet // has a cheaper path, then remember this droplet. var existingStep = l[step.x]; if (!existingStep || step.cost < existingStep.cost) { l[step.x] = step; } } // Take an existing collection of locations and updates them to account // for a new obstacle. Obstacles must be added in decreasing altitude. // (Consecutive duplicate altitudes allowed.) function fallTo(oldLocations, obstacle) { var newLocations = {}; for (var x in oldLocations) { var step = oldLocations[x]; // fall to the obstacle's altitude step = step.to(step.x, obstacle.y); // If the falling object does not hit the obstacle, // then there is no horizontal displacement. if (step.x <= obstacle.left || step.x >= obstacle.right) { addDroplet(newLocations, step); } else { // The falling object hit the obstacle. // Split into two droplets, one that goes left // and one that goes right. addDroplet(newLocations, step.to(obstacle.left, obstacle.y)); addDroplet(newLocations, step.to(obstacle.right, obstacle.y)); } } return newLocations; } function printStep(step) { console.log("Cost = " + step.cost + ": " + step.x + "," + step.y); } // Debugging function function printLocations(l) { for (var x in l) printStep(l[x]); } function shortestPath(x, y, obstacles) { var l = {}; l[x] = new Step(x, y, 0); printLocations(l); obstacles.forEach(function (obstacle) { l = fallTo(l, obstacle); console.log(["after", obstacle.left, obstacle.right, obstacle.y].join(" ")); printLocations(l); console.log("==="); }); // Find the cheapest step. var best; for (x in l) { if (!best || l[x].cost < best.cost) best = l[x]; } // Fall to the floor and print the result. printStep(best.to(best.x, 0)); } shortestPath(6,12,[new Obstacle(3,7,9), new Obstacle(1,5,6), new Obstacle(4,8,3)]);

This program finds the cost of the cheapest path to the floor, but it merely tells you the cost and not how the cost was determined. To include the winning path, we need to record the history of how the cost was determined. This is a standard technique in dynamic programming: In addition to remembering the best solution so far, you also remember how that solution was arrived at by remembering the previous step in the solution. You can then walk backward through all the previous steps to recover the full path.

// A single step in a path, representing the cost to reach that point // and the previous step in the path. function Step(x, y, cost, previous) { this.x = x; this.y = y; this.cost = cost; this.previous = previous; } // Add a step to an existing step Step.prototype.to = function to(x, y) { var dx = Math.abs(this.x - x); var dy = Math.abs(this.y - y); // These next two test are not strictly necessary. They are for style points. if (dx == 0 && dy == 0) { // no movement return this; } else if (dx == 0 && this.previous && this.previous.x == x) { // collapse consecutive vertical movements into one return new Step(x, y, this.cost + dx + dy, this.previous); } else { return new Step(x, y, this.cost + dx + dy, this); } } function printStep(firstStep) { // Walk the path backwards, then reverse it so we can print // the results forward. var path = []; for (var step = firstStep; step; step = step.previous) { path.push("(" + step.x + "," + step.y + ")"); } path.reverse(); console.log("Cost = " + firstStep.cost + ": " + path.join(" ")); }

Notice that we didn't change any of the program logic. All we did was improve our record-keeping so that the final result prints the full path from the starting point to the ending point.

I started off wondering how the subset enumeration algorithm would be a good solution to this problem. :-)

GPU implementation of the solution

psantoki.com/…/ParticleCollision2_sm.jpg

"The brute force solution would be to enumerate all the possible paths to the ground, then pick the shortest one. "

I like the brute-force solution (or backtracking in this case), because is easy to implement and understand and the future belongs to quantum computing. A quantum computer would, using the superposition of qubits, generate all the solutions at the same time and then we pick the shortest one. KISS.

I have to say, this is the first time I've heard "being ready for quantum computers" as a justification for choosing a brute force algorithm.

Thanks. Nice job.

In my work, we need to consider things other than the shortest path. Ground loops, Eddy currents and other things can be problems as well.

@Danny: I'm not sure there's a quantum algorithm for "choosing the smallest result". I'm not saying there isn't, but be aware that this isn't just something you can assume.

Interesting.

Isn't it true (in this case) that the height does not matter at all for the shortest path distance? All droplets travel vertically as much as each other droplet. It only matters whether you go left or right over obstacles. Maybe this could provide with additional gains to speed in some cases.

@Drak: yup.

In addition to not needing to store the y coordinate of the particle, you also don't need to store the x coordinate, since that's its (string) index in the map. (Sadly switching to an array won't give you an integer enumeration.)