Solution of Google Lake Volume Puzzle
Below we have output and code for the
Google lake volume puzzle.
>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 'X' and water '.'
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.
/* GLV_PUZZLE.REX -- Google lake volume puzzle. */
/* */
/* Here we have code for a solution to */
/* the Google lake volume puzzle. */
/* */
/* The code is in Open Object Rexx and */
/* easy to read. */
/* */
/* The lake is one foot wide and, for */
/* some positive integer n, n feet long. */
/* Each foot of length has a vertical */
/* wall with square cross section of one */
/* square foot. */
/* */
/* The heights of the walls, in feet, >= */
/* 0, are inputs to the program. */
/* */
/* Water is poured into the lake to fill */
/* it. The water is stored between */
/* walls. */
/* */
/* The puzzle is to find the volume, in */
/* cubic feet, of the water in the lake. */
/* */
/* For i = 1, 2, ..., n, the wall at i */
/* has height a.i. */
/* */
/* For our solution, first we find k so */
/* that a.k >= a.i for all i. Second we */
/* go to the left end and work toward */
/* the wall at k finding lake volumes. */
/* Then go the the right end and work */
/* toward wall at k finding the rest of */
/* the lake volumes. */
/* */
/* It's an O(n) solution. */
/* */
/* The wall heights are arguments on the */
/* command line. */
/* */
/* Created at 10:20:52 on Monday, December 10th, 2018. */
/* Get the name of this program: */
exec_name = 'GLV_puzzle'
return_code = 0
sq = "'"
Say exec_name': Started ...'
Parse Arg all
n = 0
Do Forever
Parse Var all token all
If token = '' Then Leave
n = n + 1
If Datatype( token,'N' ) \= 1 Then
Do
Say exec_name': Input' n 'has bad data.'
Signal out
End
a.n = token
End
If n = 0 Then Signal out
max_height = -1
Do i = 1 To n
If a.i > max_height Then
Do
max_height = a.i
k = i
End
End
Say exec_name': Number of walls =' n
Say exec_name': Max wall height =' max_height
Say exec_name': Max wall height at' k
Do i = 1 To n
Do j = 1 To max_height
lake.i.j = ' '
End
End
Say exec_name'. Calculating left results.'
volume = 0
result_code = left_calculate()
Say exec_name'. Calculating right results.'
result_code = right_calculate()
Say exec_name': Lake volume =' volume
result_code = print_lake()
out:
Say exec_name': Returning.'
Return return_code
/* ================================================================== */
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 = 'X'
End
Do j = a.i + 1 To height
lake.i.j = '.'
End
If a.i <= height Then volume = volume + (height - a.i)
Else height = a.i
End
left_calculate_out:
Return return_code
/* ================================================================== */
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 = 'X'
End
Do j = a.i + 1 To height
lake.i.j = '.'
End
If a.i <= height Then volume = volume + (height - a.i)
Else height = a.i
End
right_calculate_out:
Return return_code
/* ================================================================== */
print_lake:
Procedure Expose n lake. max_height
return_code = 0
Say ' '
Say 'PRINT_LAKE: We display the lake with walls ''X'' and water ''.'' '
Say ' '
line = ''
Do j = max_height To 1 By -1
line = ''
Do i = 1 To n
line = line || lake.i.j
End
Say line
End
Say ' '
print_lake_out:
Return return_code