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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
10 Comments »

10 Responses to “Brush Strokes”

  1. Zack said
    May 31, 2019 at 9:50 AM

    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
    May 31, 2019 at 10:40 AM

    In Python using the scan method of @programmingpraxis.

    def scan(heights):
    hlp = [0] + heights
    return sum(max(0, h2 - h1) for h1, h2 in zip(hlp, hlp[1:]))
  3. chaw said
    May 31, 2019 at 12:09 PM

    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
    May 31, 2019 at 12:12 PM

    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
    June 1, 2019 at 12:27 AM

    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
    June 1, 2019 at 3:54 AM

    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 ++ [0] ++ reverse heights)

    $ ./brush
0
5
10
  7. karma77 said
    June 1, 2019 at 10:10 PM

    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
    June 6, 2019 at 3:28 PM

    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
    June 30, 2019 at 3:32 AM

    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
    June 30, 2019 at 3:34 AM

    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[0];
  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

Leave a comment