An answer to this question on Stack Overflow.

Question

I've got two kinds of object, Ball and Platform. Balls have an (x,y) coordinate and the platforms have (x_begin, x_end, y). There can be at most 80 Platforms.

I was asked to find the shortest path for any given Ball to the ground (y=0). Note that the output of this should only be the minimum distance.

Given the constraints I thought it would be best to use brute force: calculate all the possible distances to the ground, and then return the minimum.

What I thought I'd do, is write a recursive function: first calculate the vertical distance to the nearest platform, and then branch into right and left, and back again. The breaking condition would be when all paths reach the ground.

void calculateDistances(Ball b, vector<Platform> ps, vector<float>* distances)
	{
		//The idea is to have, for every branch
		// distances[i] = vertical distance
		// distances[i+1] = distance to right
		// distances[i+2] = distance to left
		Platform* p = NULL;
		float d_y = verticalDistanceToNearestPlatform(ps, p); // "p" now holds the platform the ball is on
		if (d_y == 0) 
			return; //already on floor
		distances->push_back(d_y);
		d_x_right = distanceToRightEdgeOfPlatform(p);
		distances->push_back(d_x_right);
		d_x_left = distanceToLeftEdgeOfPlatform(p);
		distances->push_back(d_x_left);
	}

The problem here is obvious... how on Earth do I make this recursive?

Many thanks!

PS: this problem is meant to be solved in approximately two and a half hours.

Answer

You could convert this problem into a graph problem and then use any number of graph-searching algorithms to solve it.

To do so, loop through all the platforms and create nodes for each of their edges and for any points directly beneath the edge of another platform. Connect all the nodes that share a common platform together. Make the vertical connections as well.

Perform the same operation for the ground, but don't add additional nodes for the edges and don't connect the ground nodes

Now, you can use Dijkstra's algorithm (a reconstructive variant) to search your graph for the shortest path between the top and each point on the bottom. Choose the result with the lowest value and you're done. Dijkstra's algorithm runs in O(N^2), where N is a node, for a naive implementation and O(E+N log N) where E is an edge for a smart implementation.

You could also use A*, which may be easier to implement in a pinch.

Searching to see what platform a ball falling off the edge will hit is easy. Treat the ground as a platform. Sort the platforms by height. For each platform walk linearly through all the platforms beneath it, starting with the closest one. See if the x value of the higher platform falls in the range defined by the edges of the lower platform. This takes O(P^2). (P is number of platforms.)

This may not answer your question directly (i.e. this is not brute force), but I think it's a better direction to point you in. Plus, if you try to brute force all the directions the ball can go it ends up being something like O(2^P), which is an unpleasantly high time complexity.