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 = [0] + 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 ++ [0] ++ 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[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 Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: