## Brush Strokes

### May 31, 2019

The obvious solution has two loops, one running along the floors bottom to top and one running along each floor left to right; it takes time O(*n*²). A better solution makes a single scan from left to right, counting the number of floors that start at each building:

(define (f x) (do ((x x (cdr x)) (p 0 (car x)) (s 0 (+ s (max (- (car x) p) 0)))) ((null? x) s)))

I did some code golfing, using a `do`

instead of named `let`

and making all the variable names single characters: *x* for the input array, *s* for the running sum, and *p* for the previous building height. I’m not sure I could golf that any farther.

The program runs in time O(*n*). Here are some examples:

> (f '(1 4 3 2 3 1)) 5 > (f '(4 1 2 1 2 2)) 6

You can run the program at https://ideone.com/faRcFT.

Advertisements

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: