Sunday, April 3, 2016

Water in valley one dimensional


Problem:
Given a one dimensional array of integers representing the height of cliffs of a valley, find the total amount of water that can be filled in the valley.

Diagram:


Java Program:

package com.sourabh.test;

import java.util.ArrayList;
import java.util.List;

public class ValleyWater {
 class Valley
 {
  private int start;
  private int end;
  private int water;

  public Valley() {
   super();
  }
  public Valley(int start, int end) {
   super();
   this.start = start;
   this.end = end;
  }
  public int getStart() {
   return start;
  }
  public void setStart(int start) {
   this.start = start;
  }
  public int getEnd() {
   return end;
  }
  public void setEnd(int end) {
   this.end = end;
  }
  public int getWater() {
   return water;
  }
  public void setWater(int water) {
   this.water = water;
  }
 }
 
 public List<Valley> getValleys(int... A) {
  List<Integer> maxima = new ArrayList<>();
  List<Integer> minima = new ArrayList<>();
  List<Valley> valleysList = new ArrayList<>();
  int index = 0;
  for(int i=0;i<A.length - 1;i++) {
   if(A[i+1] > A[i]) {
    minima.add(i);
    index = i;
    break;
   }
   if(A[i+1] < A[i]) {
    maxima.add(i);
    index = i;
    break;
   }
  }
  for(int i=index+1;i+1<A.length;i++) {
   if(A[i+1] < A[i] && A[i] >= A[i-1]) {
    maxima.add(i);
   }
   if(A[i+1] > A[i] && A[i] <= A[i-1]) {
    minima.add(i);
   }
  }
  for(int i = 0; i < maxima.size() - 1; i++) {
   valleysList.add(new Valley(maxima.get(i), maxima.get(i+1)));
  }
  return valleysList;
 }
 
 public int addWater(List<Valley> valleysList, int... A) {
  int totalWater = 0;
  for(Valley valley : valleysList) {
   int min = A[valley.getStart()] < A[valley.getEnd()] ? A[valley.getStart()] : A[valley.getEnd()];
   int water = 0;
   for(int i=valley.getStart(); i<=valley.getEnd(); i++) {
    if(A[i] < min) {
     water += min - A[i];
    }
   }
   valley.setWater(water);
   totalWater += water;
  }
  for(Valley valley : valleysList) {
   System.out.println(valley.getWater());
  }
  return totalWater;
 }
 
 public int getWater(int... A) {
  return addWater(getValleys(A), A);
 }
}
Unit Tests:
package com.sourabh.test;

import static org.junit.Assert.*;

import java.util.List;
import com.sourabh.test.ValleyWater.Valley;
import org.junit.Assert;

import org.junit.Test;

public class ValleyWaterTests {

 ValleyWater instance = new ValleyWater();
 
 @Test
 public void getValleysTest() {
  int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
  List<Valley> valleysList = instance.getValleys(A);
  Assert.assertEquals(3, valleysList.size());
  Assert.assertEquals(2,valleysList.get(0).getStart());
  Assert.assertEquals(4,valleysList.get(0).getEnd());
  Assert.assertEquals(4,valleysList.get(1).getStart());
  Assert.assertEquals(7,valleysList.get(1).getEnd());
  Assert.assertEquals(7,valleysList.get(2).getStart());
  Assert.assertEquals(12,valleysList.get(2).getEnd());
 }
 
 @Test
 public void getWaterTest() {
  int[] A = {1,2,3,1,2,1,4,6,5,4,2,3,4,1};
  int totalWater = instance.getWater(A);
  Assert.assertEquals(5, totalWater);
 }
}

1 comment: