Solution of Google Lake Volume Puzzle
Below we have output and code for the
Google lake volume puzzle.<p><pre><code>     &gt;glv_puzzle 4 9 7 5 9 7 4 8 3 4 2 6 5 8 12 0 0 0 3 6 5 8 9 0 2 5 3
     GLV_puzzle:  Started ...
     GLV_puzzle:  Number of walls = 27
     GLV_puzzle:  Max wall height = 12
     GLV_puzzle:  Max wall height at 15
     GLV_puzzle.  Calculating left results.
     GLV_puzzle.  Calculating right results.
     GLV_puzzle:  Lake volume = 89

     PRINT_LAKE:  We display the lake with walls &#x27;X&#x27; and water &#x27;.&#x27;

                   X
                   X
                   X
      X..X.........X.......X
      X..X..X.....XX......XX
      XX.XX.X.....XX......XX
      XX.XX.X...X.XX....X.XX
      XXXXX.X...XXXX....XXXX..X
     XXXXXXXX.X.XXXX....XXXX..X
     XXXXXXXXXX.XXXX...XXXXX..XX
     XXXXXXXXXXXXXXX...XXXXX.XXX
     XXXXXXXXXXXXXXX...XXXXX.XXX

     GLV_puzzle:  Returning.


     &#x2F;* GLV_PUZZLE.REX -- Google lake volume puzzle.                       *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   Here we have code for a solution to                              *&#x2F;
     &#x2F;*   the Google lake volume puzzle.                                   *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   The code is in Open Object Rexx and                              *&#x2F;
     &#x2F;*   easy to read.                                                    *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   The lake is one foot wide and, for                               *&#x2F;
     &#x2F;*   some positive integer n, n feet long.                            *&#x2F;
     &#x2F;*   Each foot of length has a vertical                               *&#x2F;
     &#x2F;*   wall with square cross section of one                            *&#x2F;
     &#x2F;*   square foot.                                                     *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   The heights of the walls, in feet, &gt;=                            *&#x2F;
     &#x2F;*   0, are inputs to the program.                                    *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   Water is poured into the lake to fill                            *&#x2F;
     &#x2F;*   it.  The water is stored between                                 *&#x2F;
     &#x2F;*   walls.                                                           *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   The puzzle is to find the volume, in                             *&#x2F;
     &#x2F;*   cubic feet, of the water in the lake.                            *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   For i = 1, 2, ..., n, the wall at i                              *&#x2F;
     &#x2F;*   has height a.i.                                                  *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   For our solution, first we find k so                             *&#x2F;
     &#x2F;*   that a.k &gt;= a.i for all i.  Second we                            *&#x2F;
     &#x2F;*   go to the left end and work toward                               *&#x2F;
     &#x2F;*   the wall at k finding lake volumes.                              *&#x2F;
     &#x2F;*   Then go the the right end and work                               *&#x2F;
     &#x2F;*   toward wall at k finding the rest of                             *&#x2F;
     &#x2F;*   the lake volumes.                                                *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   It&#x27;s an O(n) solution.                                           *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;*   The wall heights are arguments on the                            *&#x2F;
     &#x2F;*   command line.                                                    *&#x2F;
     &#x2F;*                                                                    *&#x2F;
     &#x2F;* Created at 10:20:52 on Monday, December 10th, 2018.                *&#x2F;

     &#x2F;*   Get the name of this program:                                    *&#x2F;

          exec_name = &#x27;GLV_puzzle&#x27;
          return_code = 0
          sq = &quot;&#x27;&quot;

          Say exec_name&#x27;:  Started ...&#x27;

          Parse Arg all

          n = 0

          Do Forever
            Parse Var all token all
            If token = &#x27;&#x27; Then Leave
            n = n + 1
            If Datatype( token,&#x27;N&#x27; ) \= 1 Then
              Do
                Say exec_name&#x27;:  Input&#x27; n &#x27;has bad data.&#x27;
                Signal out
              End
            a.n = token
          End

          If n = 0 Then Signal out

          max_height = -1
          Do i = 1 To n
           If a.i &gt; max_height Then
             Do
               max_height = a.i
               k = i
             End
          End

          Say exec_name&#x27;:  Number of walls =&#x27; n
          Say exec_name&#x27;:  Max wall height =&#x27; max_height
          Say exec_name&#x27;:  Max wall height at&#x27; k

          Do i = 1 To n
            Do j = 1 To max_height
              lake.i.j = &#x27; &#x27;
            End
          End

          Say exec_name&#x27;.  Calculating left results.&#x27;

          volume = 0

          result_code = left_calculate()

          Say exec_name&#x27;.  Calculating right results.&#x27;

          result_code = right_calculate()

          Say exec_name&#x27;:  Lake volume =&#x27; volume

          result_code = print_lake()

     out:
       Say exec_name&#x27;:  Returning.&#x27;
       Return return_code

     &#x2F;* ================================================================== *&#x2F;

     left_calculate:
          Procedure Expose n a. k volume lake.

          return_code = 0

          height = a.1

          Do i = 1 To k
            Do j = 1 To a.i
              lake.i.j = &#x27;X&#x27;
            End
            Do j = a.i + 1 To height
              lake.i.j = &#x27;.&#x27;
            End

            If a.i &lt;= height Then volume = volume + (height - a.i)
            Else height = a.i

          End

     left_calculate_out:
          Return return_code

     &#x2F;* ================================================================== *&#x2F;

     right_calculate:
          Procedure Expose n a. k volume lake.

          return_code = 0

          height = a.n

          Do i = n To k By -1
            Do j = 1 To a.i
              lake.i.j = &#x27;X&#x27;
            End
            Do j = a.i + 1 To height
              lake.i.j = &#x27;.&#x27;
            End

            If a.i &lt;= height Then volume = volume + (height - a.i)
            Else height = a.i

          End

     right_calculate_out:
          Return return_code

     &#x2F;* ================================================================== *&#x2F;

     print_lake:
          Procedure Expose n lake. max_height

          return_code = 0

          Say &#x27; &#x27;

          Say &#x27;PRINT_LAKE:  We display the lake with walls &#x27;&#x27;X&#x27;&#x27; and water &#x27;&#x27;.&#x27;&#x27; &#x27;

          Say &#x27; &#x27;

          line = &#x27;&#x27;
          Do j = max_height To 1 By -1
            line = &#x27;&#x27;
            Do i = 1 To n
              line = line || lake.i.j
            End
            Say line
          End

          Say &#x27; &#x27;

     print_lake_out:
          Return return_code</code></pre>