<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/the-twitter-waterflow-problem/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://www.mango-solutions.com/blog/the-twitter-waterflow-problem"> Blog</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p> <img sizes="100vw" src="https://i0.wp.com/www.mango-solutions.com/blog/images/2/f/4/2/4/2f424ca9ed9690b9487b8140215675416fd3d91d-image-1.png?w=456&ssl=1" data-recalc-dims="1"></p>
<h4>Nathan Eastwood, Data Scientist</h4>
<p>I was recently introduced to the <a rel="nofollow" href="http://chrisdone.com/posts/twitter-problem-loeb" target="_blank">Twitter Waterflow Problem</a> and I decided it was interesting enough to try and complete the challenge in R. </p>
<p>Consider the following picture:</p>
<p><img alt="" sizes="100vw" src="https://i1.wp.com/www.mango-solutions.com/blog/user/pages/01.blog/130.the-twitter-waterflow-problem/image%201.png?w=456&ssl=1" data-recalc-dims="1"></p>
<p>This plot shows a series of walls and empty valleys. We can represent this picture by an array of integers, where the value at each index is the height of the wall. So in this case, the array of integers can be defined as:</p>
<pre><code>wall &lt;- c(2, 5, 1, 2, 3, 4, 7, 7, 6)</code></pre>
<p>Now imagine it rains. How much water is going to be accumulated in puddles between walls? No puddles are formed at edges of the wall and water is considered to simply run off the edge. We count volume in square blocks of 1×1. Thus, we are left with a puddle between column 2 and column 7 and the volume is 10.</p>
<h4>The Approach</h4>
<p>The approach I took was one of many ways you could solve this problem. I chose to treat each column (wall) as an index and then for each index I implement a loop:</p>
<ul>
<li>Find the height of the current index</li>
<li>Find the maximum height of the walls to the left of the current index</li>
<li>Find the maximum height of the walls to the right of the index</li>
</ul>
<p>I then work out what the smallest maximum height is between the maximum heights to the left and right of the current index. If this smallest height minus the current index height is greater than zero, then I know how many blocks will fill with water for the current index. Of course, if the smallest maximum height to the left or right is less than the current height, then I get the run off. Converting this to code looks like this:</p>
<pre><code>len &lt;- length(wall)
# pre-allocate memory to make the loop more efficient
water &lt;- rep(0, len)
for (i in seq_along(wall)) {
  currentHeight &lt;- wall[i]
  maxLeftHeight &lt;- if (i > 1) {
    max(wall[1:(i - 1)])
  } else {
    0
  }
  maxRightHeight &lt;- if (i == len) {
    0
  } else {
    max(wall[(i + 1):len])
  }
  smallestMaxHeight &lt;- min(maxLeftHeight, maxRightHeight)
  water[i] &lt;- if (smallestMaxHeight - currentHeight > 0) {
    smallestMaxHeight - currentHeight
  } else {
    0
  }
}
water
[1] 0 0 4 3 2 1 0 0 0</code></pre>
<p>This returns a vector of the number of blocks of water at each index.</p>
<h4>The R6 Class</h4>
<p>For this problem I chose to use the <a rel="nofollow" href="https://github.com/r-lib/R6" target="_blank"><code>R6</code></a> class system because it is very self contained. The <code>R6</code> class system is different from the functional <code>S3</code> and <code>S4</code> class systems found in base R in that it is an encapsulated class system. Some key differences between the two are:<br>
<strong>Functional:</strong></p>
<ul>
<li>Objects contain data</li>
<li>Class methods are separate from objects</li>
<li>Objects are immutable – they cannot be changed after they have been created</li>
</ul>
<p><strong>Encapsulated:</strong></p>
<ul>
<li>Objects contain methods and data</li>
<li>Objects are mutable</li>
</ul>
<p>Winston Chang details these differences very well in his <a rel="nofollow" href="https://channel9.msdn.com/Events/useR-international-R-User-conferences/useR-International-R-User-2017-Conference/The-R6-Class-System" target="_blank">userR!2017 talk</a>.</p>
<p>I wanted the user to be able to acquire two key pieces of information: the total blocks of water and the filled plot. I therefore created three <code>public</code> methods inside an <code>R6</code> class and placed the class in a simple package which can be found <a rel="nofollow" href="https://github.com/nathaneastwood/waterflow" target="_blank">here</a>. <code>public</code> methods are a list of functions (and/or non-functions) which are essentially methods (or data) of the class that are intended to be used by the user of the class.</p>
<p>When writing a new <code>R6</code> class, we often want to perform some initial functionality when we instantiate an object of this class. This is true in our case as when we instantiate a new object of class <code>waterflow</code>, we want it to calculate the heights of the water straight away. We therefore call our earlier function <code>initialize</code> and place it inside the <code>public</code> list.</p>
<pre><code>initialize = function(wall = NULL) {
  if (is.null(wall)) {
    stop(&quot;Please provide some wall heights&quot;)
  }
  if (!is.numeric(wall)) {
    stop(&quot;Please provide a numeric vector&quot;)
  }
  len &lt;- length(wall)
  water &lt;- rep(0, len)
  for (i in seq_along(wall)) {
    currentHeight &lt;- wall[i]
    maxLeftHeight &lt;- if (i > 1) {
      max(wall[1:(i - 1)])
    } else {
      0
    }
    maxRightHeight &lt;- if (i == len) {
      0
    } else {
      max(wall[(i + 1):len])
    }
    smallestMaxHeight &lt;- min(maxLeftHeight, maxRightHeight)
    water[i] &lt;- if (smallestMaxHeight - currentHeight > 0) {
      smallestMaxHeight - currentHeight
    } else {
      0
    }
  }
  private$heights &lt;- private$tidyWater(water, wall)
}</code></pre>
<p><strong>Note:</strong> we have one key difference here, we are assigning the results to members of the <code>private</code> list within our object. Once we have calculated our <code>water</code> heights, we use them along with our <code>wall</code> heights in the function <code>private$tidyWater()</code> and assign the resulting <code>data.frame</code> to <code>private$heights</code>. The <code>private</code> argument is a list which contains methods (and/or data) which are internal to the class and are not intended to be used by the user. We do similar things when writing packages – we explicitly export the functionality we want other people to use and don’t export functionality that is only used within the package itself.</p>
<p>So to use the class, first we instantiate the class with some data in a call to <code>$new()</code> which in turn runs the above <code>initialize</code> function.</p>
<pre><code>library(waterflow)
wall &lt;- c(2, 5, 1, 2, 3, 4, 7, 7, 6)
p &lt;- waterflow$new(wall)</code></pre>
<p>So now we have an object called <code>p</code> which is of class <code>waterflow</code> (and <code>R6</code>). <code>p</code> contains the data, as well as the (<code>public</code>) methods we can perform on that data.</p>
<p>Typically when we return <code>p</code>, <code>R6</code> objects have a default <code>print</code> method that lists all members of the object but here there is a custom <code>$print()</code> function that returns <code>heights</code>.</p>
<pre><code>p
   pos  type val
1    1 water   0
2    2 water   0
3    3 water   4
4    4 water   3
5    5 water   2
6    6 water   1
7    7 water   0
8    8 water   0
9    9 water   0
10   1  wall   2
11   2  wall   5
12   3  wall   1
13   4  wall   2
14   5  wall   3
15   6  wall   4
16   7  wall   7
17   8  wall   7
18   9  wall   6</code></pre>
<p>We can still return the members of the object by looking at the structure of <code>p</code>.</p>
<pre><code>str(p)
Classes 'waterflow', 'R6' </code></pre>