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

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

A Haskell version.

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