Programming Praxis

Today’s problem must be someone’s homework from an algorithms course; it makes a fine opportunity for some code golfing:

An array of positive integers represents the heights of a series of buildings; for instance, the array [1, 4, 3, 2, 3, 1] represents the six buildings that, placed in a row, look like this:

     XXX
     XXX  XXX       XXX
     XXX  XXX  XXX  XXX
XXX  XXX  XXX  XXX  XXX  XXX

A painter drawing a picture of the buildings paints the buildings by making a single horizontal brush stroke from left to right as far as possible, working from bottom to top. The first stroke covers the first floor of all six buildings. The second stroke covers the second floor of four buildings. The third stroke covers the third floor of two buildings, and the fourth stroke covers the third floor of one building. Finally, the fifth stroke covers the fourth floor of one building. The painter requires five brush strokes to cover all six buildings.

Your task is to write a program that takes an input array representing building heights and calculates the number of horizontal brush strokes required to cover all floors on all buildings. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2