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 = [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: