## 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  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

### 10 Responses to “Brush Strokes”

1. Zack said

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)

``````for i = 1:n
for j = 1:M
X[j,i] = (x[i] >= j)
end
end

return X, M, n
``````

end

function CalcNoOfIslands(X::BitArray{2}, M, n)
z = Array{Int64}(undef, M)

``````for i = 1:M
c = Int(X[i,1])
flag = !X[i,1]

for j = 2:n
if !X[i,j]; flag = true; end

if X[i,j] && flag
c += 1
flag = false
end
end

z[i] = c
end

return z
``````

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!

2. Paul said

In Python using the scan method of @programmingpraxis.

```def scan(heights):
hlp =  + heights
return sum(max(0, h2 - h1) for h1, h2 in zip(hlp, hlp[1:]))
```
3. chaw said

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.

4. chaw said

Here is a R7RS Scheme solution that maybe golfs at the
semantic/concept level using pair-fold.

``` (import (scheme base) (scheme write) (only (srfi 1) pair-fold)) (define (count-strokes bldg-heights) (if (null? bldg-heights) 0 (+ (car bldg-heights) (pair-fold (lambda (hts strokes) (if (null? (cdr hts)) strokes (+ strokes (max 0 (- (cadr hts) (car hts)))))) 0 bldg-heights)))) (display (map count-strokes '((1 4 3 2 3 1) (4 1 2 1 2 2) () (#e10e6)))) (newline) ```

``` (5 6 0 10000000) ```

5. Steve said

Klong version

```
Code:
:" Brush strokes"

:" For each number in list, print 1 if > s otherwise 0"
g::{[s l]; s::x; l::y; {~x<s}'l}

:" Change numbers into lists of 1 and 0"
h::{[max l]; l::x; max::*l@>l; {g(x; l)}'1+!max}

.comment("End-of-comment")
:"h([1 4 3 2 3 1])"
:"[[1 1 1 1 1 1] [0 1 1 1 1 0] [0 1 1 0 1 0] [0 1 0 0 0 0]]"
End-of-comment

:"Get rid of leading and trailing zeroes"
strip2::{:[0=*x; strip(1_x); x]}
strip::{|strip2(|strip2(x))}

:" Get rid of duplicate zeroes"
dz::{[c l2]; l2::[]; {[n]; n::x; :[n=1; {c::0; l2::l2,n}(); {:[c=0; {c::1; l2::l2,n}(); ""]}()]}'x; l2}

:" Path sum - For each record sum = #zeroes + 1"
ps::{1+#x?0}

:" Grand sum = sum of sums"
go::{+/ps'dz'strip'h(x)}

Run:
go([1 4 3 2 3 1])
5

```
6. Globules said

```-- The number of brush strokes required to paint a series of buildings whose
-- heights are given by hs.
strokes :: Integral a => [a] -> a
strokes hs = sum \$ filter (>0) \$ zipWith (-) hs (0:hs)

main :: IO ()
main = do
let heights = [1, 4, 3, 2, 3, 1] :: [Int]

print \$ strokes ([] :: [Int])
print \$ strokes heights
print \$ strokes (heights ++  ++ reverse heights)
```
```\$ ./brush
0
5
10
```
7. karma77 said

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.

```function countBrushes(arr) {
var n = arr.length, brushes = 0, completed = 0;
arr.push(0); // add a fake completed build
while (completed != n) {
var painting = false;
for (var i=0; i<n; i++) {
var value = --arr[i];
if (value >= 0) {
if (value === 0) completed++;
if (!painting) brushes++;
painting = true;
} else {
painting = false;
}
}
}
return brushes;
}

print(countBrushes([1, 4, 3, 2, 3, 1]));
```
8. Sachit Dubey said

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

``````        stroke_on=False

if stroke_on==True :
stroke+=1
stroke_on=False
``````

print(stroke)

9. Daniel said

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.

```def strokes(array):
if not array:
return 0
elif 0 in array:
idx = array.index(0)
return strokes(array[:idx]) + strokes(array[idx + 1:])
else:
min_ = min(array)
array = [x - min_ for x in array]
return min_ + strokes(array)

print(strokes([1, 4, 3, 2, 3, 1]))
```

Output:

```5
```
10. Daniel said

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

```#include <stdio.h>
#include <stdlib.h>

int strokes(int* array, int n) {
if (n == 0) return 0;
int output = array;
for (int i = 1; i < n; ++i) {
int diff = array[i] - array[i - 1];
if (diff > 0) {
output += diff;
}
}
return output;
}

int main(int argc, char* argv[]) {
int n = argc - 1;
int* array = malloc(sizeof(int) * n);
for (int i = 0; i < n; ++i) {
array[i] = atoi(argv[i + 1]);
}
printf("%d\n", strokes(array, n));
free(array);
return EXIT_SUCCESS;
}
```

Example Usage:

```\$ ./a.out 1 4 3 2 3 1
5
```