3 ms·

Solution of Google Lake Volume Puzzle

• graycat 8y ago
  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