Implementing Trapping Rain Water , Twitter’s Interview Question using UIImageGraphics in Swift

In this my first article , I will tell you how to implement the Trapping Rain Water question which have asked in an interview by Google , Twitter and asked by many companies , with using Swift , UIImageGraphics .

What is the question ?

Photo is taken from http://javabypatel.blogspot.com.tr/2016/10/trapping-rain-water-between-towers.html

Firstly , I want to explain the question . There will be given n non-negative integers to represent height of towers and each tower width is just 1 unit . We assume that the rained and here is the question :

How many unit water fills between the all towers ?

How to Solve ?

First , I will tell you how to solve it and then I will explain how to implemented it Swift and Core Image.

We always assume the bar heights is available in a structure (in an array) available . For example tower heights are [ 3 , 0 , 0 , 2 , 0 , 4 ] .

For each tower we must figure out if there is a tower higher than it in the left side of it and if there is a tower higher than it in the right side of it . If one of the tower is not exist , we assume that the place where the tower was , will not take any water .

If there are exist 2 tower we can take highest one of left side and highest one of right side then we must take the minimum of both of them . The unit where tower placed , totally will take that minimum number units of water .

If we subtract the tower height from this minimum number , we will be find out how much water there will be for every tower unit.

First index as first tower and last index as last tower of Scene will take no water because there are no tower where left of First tower and same way there are no tower where right of Last Tower.

Swift Implementation

The UIViewController has an UIButton for generate and an UIImageView for represent the image which is processed . Here is the struct for store all tower heights and I will show you that I have divided and represented UIImage as 8x8 parts . So there will be 8 tower and maximum 8 height unit for each tower for this question.

struct WallHeights {

var wallHeights : [Int] = [0,0,0,0,0,0,0,0];

}

Now , the time for generate tower height randomly .

var testWall : WallHeights = WallHeights();

for iterator in 0..<8{

testWall.wallHeights[iterator] = Int(arc4random_uniform(256)) % 8;

}

Then , I have started to using UIGraphics functions to start to process image and implemented many functions to find out that can it be filled with water , handle image to generate scenarios and filling water between towers .

Here is the random scenarios :

Generating Random Scenarios for this Problem

The last part of this problem , implement the water fill functions to image . Here is the final state of this problem :

Filled water into towers

If the article were helpful and you can star this project on Github.

eliakorkmaz/Trapping-Rain-Water-with-Swift_Trapping-Rain-Water-with-Swift - Trapping Rain Water question implemented with Swift and UIImageGraphics_github.com

If you want to ask question , please comment or message me directly on Twitter . I will share articles about programming , algorithms and mostly Swift so you can follow me and like the article.