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.
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: