Walls and Water

2013-11-16

The problem originally stated here, but finding the full result, rather than just the sum. Also, zeroes count as holes.

There exists an O(n) solution.

Some tests:

(module+ test
  (require rackunit)
  (check-equal? (walls-and-water '(2 5 1 2 3 4 7 7 6))
    '(0 0 4 3 2 1 0 0 0))
  (check-equal? (walls-and-water (reverse '(2 5 1 2 3 4 7 7 6)))
    (reverse '(0 0 4 3 2 1 0 0 0)))
  (check-equal? (walls-and-water '(2 5 1 3 1 2 1 7 7 6))
    '(0 0 4 2 4 3 4 0 0 0))
  (check-equal? (walls-and-water '(2 6 1 2 3 4 4 5 4))
    '(0 0 4 3 2 1 1 0 0))
  (check-equal? (walls-and-water '(2 5 3 1 6 3 2 7 6 1))
    '(0 0 2 4 0 3 4 0 0 0))
  (check-equal? (walls-and-water '(5 0 1 0 5))      ; zeros count as holes
    '(0 0 0 0 0))
  (check-equal? (walls-and-water '(5 0 4 1 4 0 5))
    '(0 0 0 3 0 0 0)))