Summary
This is a simple coding coding challenge that should be short enough to be done in a one hour lab session. You are free to use any language in implementing the challenge, although the primariy use of this instance is as a progamming task in the course F20SC/F21SC "Industrial Programming". The specification and sample input/output will be posted here on the day of the challenge.
The specification for the Coding Challenge is here
The Gitlab repo with template code for the Coding Challenge is here
To sign up for the challenge (optional) follow this link
The specification below is taken literally from http://rosettacode.org/wiki/Water_collected_between_towers , published under GNU Free Documentation License 1.2
Spec: 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.
9 ██ 9 ██ 8 ██ 8 ██ 7 ██ ██ 7 ██≈≈≈≈≈≈≈≈██ 6 ██ ██ ██ 6 ██≈≈██≈≈≈≈██ 5 ██ ██ ██ ████ 5 ██≈≈██≈≈██≈≈████ 4 ██ ██ ████████ 4 ██≈≈██≈≈████████ 3 ██████ ████████ 3 ██████≈≈████████ 2 ████████████████ ██ 2 ████████████████≈≈██ 1 ████████████████████ 1 ████████████████████
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.
Task: 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.
Sample inputs:
Test your implementation by using bar charts representing each of the following seven series:
[[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]]
This is a fairly simple programming exercise. Since it is on Rosetta Code, you will be able to compare your final solution, with the one given there. I encourage you to do so, BUT don't look up any of the solutions before or while you are coding to get the best learning experience. There is also a good video by Guy Steele (a very prominent prgramming languages researcher) linked on the Rosetta code page, "Four Solutions to a Trivial Problem" , with an explanation how to develop an efficient version for this program. See also this definition of the word "trivial" in the New Hacker's Dictionary.
The spec gives a list of sample inputs to test. Follow this link here for the solutions, produced by the C# sample implementation.
Submission of solutions for the coding challenge is either via Vision (for those doing course F20SC), or via email to me (in this case, send a .zip file with the complete code, and include a README file that describes how to build the solution and how to run it).
If you want a larger input (lenghth 200, max 20), try this one
{ 14,15,16,0,18,4,14,5,0,12,20,7,5,8,12,3,16,4,16,20, 8,15,16,7,14,11,19,2,9,5,3,19,0,8,7,8,0,9,9,0, 12,3,11,4,6,14,1,4,12,17,18,17,17,10,6,20,11,15,5, 13,1,11,5,6,17,3,13,1,2,1,19,6,11,19,16,12,11,11, 2,2,18,4,13,14,5,5,20,2,2,18,0,11,6,7,12,11,14, 14,13,16,0,13,6,4,15,6,12,3,19,15,6,19,4,14,18,18,5, 17,16,5,3,20,3,2,8,1,10,4,11,12,13,5,4,15,18,17,12,10, 16,0,15,0,13,11,5,15,7,9,1,0,4,1,19,19,11,16,3, 12,18,0,10,4,6,7,9,12,8,12,1,11,1,13,4,14,10,12,5, 13,3,19,8,0,0,4,0,17,5,6,7,18,1,15,18,18,5,17,6,7,4,0 }
and expect 1939 as a result.
As an extra task, display the towers and the water held as shown in the above picture.
Copyright
Except where stated otherwise, all teaching material, including lecture notes, tutorials and lab exercises, are Copyright (C) Heriot-Watt University, and respective authors. Please respect our rights over this material and contact us if you want to use it in another context.