How to resolve the algorithm Water collected between towers step by step in the Racket programming language

Published on 12 May 2024 09:40 PM
#Racket

How to resolve the algorithm Water collected between towers step by step in the Racket programming language

Table of Contents

Problem Statement

In a two-dimensional world, we begin with any bar-chart (or row of close-packed 'towers', each of unit width), and then it rains, completely filling all convex enclosures in the chart with water.

In the example above, a bar chart representing the values [5, 3, 7, 2, 6, 4, 5, 9, 1, 2] has filled, collecting 14 units of water. Write a function, in your language, from a given array of heights, to the number of water units that can be held in this way, by a corresponding bar chart. Calculate the number of water units that could be collected by bar charts representing each of the following seven series:

See, also:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Water collected between towers step by step in the Racket programming language

Source code in the racket programming language

#lang racket/base
(require racket/match)

(define (water-collected-between-towers towers)
  (define (build-tallest-left/rev-list t mx/l rv)
    (match t
      [(list) rv]
      [(cons a d)
       (define new-mx/l (max a mx/l))
       (build-tallest-left/rev-list d new-mx/l (cons mx/l rv))]))

  (define (collect-from-right t tallest/l mx/r rv)
    (match t
      [(list) rv]
      [(cons a d)
       (define new-mx/r (max a mx/r))
       (define new-rv (+ rv (max (- (min new-mx/r (car tallest/l)) a) 0)))
       (collect-from-right d (cdr tallest/l) new-mx/r new-rv)]))

  (define reversed-left-list (build-tallest-left/rev-list towers 0 null))  
  (collect-from-right (reverse towers) reversed-left-list 0 0))

(module+ test
  (require rackunit)
  (check-equal?
   (let ((towerss
          '[[1 5 3 7 2]
            [5 3 7 2 6 4 5 9 1 2]
            [2 6 3 5 2 8 1 4 2 2 5 3 5 7 4 1]
            [5 5 5 5]
            [5 6 7 8]
            [8 7 7 6]
            [6 7 10 7 6]]))
     (map water-collected-between-towers towerss))
   (list 2 14 35 0 0 0 0)))

You may also check:How to resolve the algorithm Arrays step by step in the Argile programming language
You may also check:How to resolve the algorithm String length step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm I before E except after C step by step in the Picat programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the XPL0 programming language
You may also check:How to resolve the algorithm Associative array/Merging step by step in the B4X programming language