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 XXXA 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.
Programming Praxis 
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)
end
function CalcNoOfIslands(X::BitArray{2}, M, n)
z = Array{Int64}(undef, M)
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!
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:]))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.
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)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]) 5A Haskell version.
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]));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
print(stroke)
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:
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: