## Brush Strokes

### May 31, 2019

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 XXXA 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.

Cute problem, reminiscent of some number puzzles I used to play. Here is my take using Julia 1.0:

function PaintByArray(x::Array{Int64, 1})

n = length(x)

M = maximum(x)

X = BitArray(undef, M, n)

end

function CalcNoOfIslands(X::BitArray{2}, M, n)

z = Array{Int64}(undef, M)

end

function main(x::Array{Int64, 1})

X, M, n = PaintByArray(x)

return sum(CalcNoOfIslands(X, M, n))

end

Example:

julia> main([1, 4, 3, 2, 3, 1])

5

Have a nice weekend!

In Python using the scan method of @programmingpraxis.

Unless I misunderstand the algorithm, the “obvious solution” is not

O(n^2). By the usual conventions, with n being the input size, I

believe it is \Theta(n 2^n). Consider, for example, the change in its

running time for inputs (10 1), (100 1), (1000000 1), etc.

Here is a R7RS Scheme solution that maybe golfs at the

semantic/concept level using pair-fold.

Klong version

A Haskell version.

A JavaScript version in O(n * m) where n is the number of build and m is the max floor.

Please note that there is no need to calculate a “max” floor.

buildinds = [2,4,5,6,7,8]

stroke_on = False

stroke=0

for r in range(max(buildinds)) :

for c in range(len(buildinds)) :

if r+1<=buildinds[c] :

stroke_on = True

else :

if stroke_on==True :

stroke+=1

print(stroke)

Here’s a recursive solution in Python. If there is a zero-height building, it recursively counts the number of strokes on the set of buildings to the left and right of the zero-height building. Otherwise, it counts the number of strokes as the minimum height of all buildings plus a recursive call with all building heights subtracted by the minimum.

Output:

I prefer @programmingpraxis’s solution to my preceding solution, so I also implemented the same approach in C.

Example Usage: