IEEE Challenge 2008 (04)

I found a copy of this year’s IEEE Extreme Programming Challenge. I’m a bit too late to enter the competition but thought it might be fun to have a go at a couple of the challenges. Here is my attempt at Challenge #4: Road Construction.

The full official challenge brief is in this document here.

You can skip ahead to my solution here.

Simply put, the object of this challenge is to write some code that calculates the arrangement of a specified number of rectangles of land along a road that has the greatest area. Hopefully this sample diagram from the full challenge brief makes this task clearer.

RoadConstruction Example

The diagram shows the optimum solution when the required number of rectangles is three. Note that all rectangles must be used and houses may not appear in rectangles. The rectangles must include the road.

The problem is actually a pretty straightforward search problem. All that is required is to try every possible ordering of rectangles along the road and to note the maximum area covered. Of course this is easier said than done and there are various subtlties that come out in the details. It is possible to narrow down the search space quite a lot with a few simple observations.

For example, since the puzzle asks for the maximum area we can assume that whenever we attempt to plot a rectangle we’re going to plot the maximum width possible. This means we now only need to try out rectangles of different heights and assume that the maximum width rectangle is the one that is required. In the example we can see rectangles of heights 12, 5 and 1.

The next helpful observation is that we don’t really need to track the positions of the houses. Instead we just need to note the maximum allowed widths to the left and right of the road for each row. As we read in the houses we update this record. After that the house locations are no longer required to solve the problem.

The tricky part of the problem is writing the code to try out all possible combinations of rectangle heights that fit onto the road. I spent some time investigating the C++ next_permutation() STL library function. (There’s a neat discussion of the algorithm here). I had hoped to use this function so that I could avoid the potential issues associated with writing a recursive function to solve the problem. Unfortunately the problem isn’t really about permutations and to convert it into a form where the next_permutation() function would be useful would require extremely long run times.

In the end, the recursive algorithm is pretty simple to write and doesn’t appear to have especially large memory overhead. With a bit of thought and pre-planning we end up with a reasonably neat and tidy program which does the job it was designed to do.

Final solution source code is here.