How to resolve the algorithm Water collected between towers step by step in the C programming language

Published on 7 June 2024 03:52 AM
#C

How to resolve the algorithm Water collected between towers step by step in the C programming language

Table of Contents

Problem Statement

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.

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. 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. Calculate the number of water units that could be collected by bar charts representing each of the following seven series:

See, also:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Water collected between towers step by step in the C programming language

The C program calculates the maximum amount of water that can be trapped between two vertical lines formed by elements of a given array. The problem resembles a histogram.

The program works by iterating over the elements of the array and identifying the first and second highest elements. It then calculates the amount of water trapped between these elements and the next highest element. This process is repeated until there are no more elements to consider.

The program uses the following function to calculate the amount of water trapped between two elements:

int getWater(int* arr,int start,int end,int cutoff){
   int i, sum = 0;
   
   for(i=start;i<=end;i++)
   	sum += ((arr[cutoff] > arr[i])?(arr[cutoff] - arr[i]):0);
   
   return sum;
}

The getWater() function takes in the array, the starting and ending indices of the elements to consider, and the index of the highest element. The function then iterates over the elements between the starting and ending indices and calculates the amount of water trapped between the highest element and each element. The amount of water trapped is calculated by subtracting the height of the current element from the height of the highest element.

The program uses the following function to calculate the total amount of water trapped in the array:

int netWater(int* arr,int size){
   int i, j, ref1, ref2, marker, markerSet = 0,sum = 0;
   
   if(size<3)
   	return 0;

   for(i=0;i<size-1;i++){
   	start:if(i!=size-2 && arr[i]>arr[i+1]){
   			ref1 = i;
   			
   			for(j=ref1+1;j<size;j++){
   				if(arr[j]>=arr[ref1]){
   					ref2 = j;
   					
   					sum += getWater(arr,ref1+1,ref2-1,ref1);

   					i = ref2;
   					
   					goto start;
   				}
   				
   				else if(j!=size-1 && arr[j] < arr[j+1] && (markerSet==0||(arr[j+1]>=arr[marker]))){
   					marker = j+1;
   					markerSet = 1;
   				}
   			}
   			
   			if(markerSet==1){
   				sum += getWater(arr,ref1+1,marker-1,marker);

   				i = marker;
   				
   				markerSet = 0;
   				
   				goto start;
   			}
   		}
   	}
   
   return sum;
}

The netWater() function takes in the array and its size as input. The function then iterates over the elements of the array and identifies the first and second highest elements. It then calculates the amount of water trapped between these elements and the next highest element using the getWater() function. This process is repeated until there are no more elements to consider.

The program demonstrates the use of these functions to calculate the maximum amount of water that can be trapped between two vertical lines formed by elements of a given array.

Source code in the c programming language

#include<stdlib.h>
#include<stdio.h>

int getWater(int* arr,int start,int end,int cutoff){
	int i, sum = 0;
	
	for(i=start;i<=end;i++)
		sum += ((arr[cutoff] > arr[i])?(arr[cutoff] - arr[i]):0);
	
	return sum;
}

int netWater(int* arr,int size){
	int i, j, ref1, ref2, marker, markerSet = 0,sum = 0;
	
	if(size<3)
		return 0;

	for(i=0;i<size-1;i++){
		start:if(i!=size-2 && arr[i]>arr[i+1]){
				ref1 = i;
				
				for(j=ref1+1;j<size;j++){
					if(arr[j]>=arr[ref1]){
						ref2 = j;
						
						sum += getWater(arr,ref1+1,ref2-1,ref1);

						i = ref2;
						
						goto start;
					}
					
					else if(j!=size-1 && arr[j] < arr[j+1] && (markerSet==0||(arr[j+1]>=arr[marker]))){
						marker = j+1;
						markerSet = 1;
					}
				}
				
				if(markerSet==1){
					sum += getWater(arr,ref1+1,marker-1,marker);

					i = marker;
					
					markerSet = 0;
					
					goto start;
				}
			}
		}
	
	return sum;
}

int main(int argC,char* argV[])
{
	int *arr,i;
	
	if(argC==1)
		printf("Usage : %s <followed by space separated series of integers>");
	else{
		arr = (int*)malloc((argC-1)*sizeof(int));
		
		for(i=1;i<argC;i++)
			arr[i-1] = atoi(argV[i]);

		printf("Water collected : %d",netWater(arr,argC-1));
	}
	
	return 0;
}


  

You may also check:How to resolve the algorithm Arithmetic/Complex step by step in the D programming language
You may also check:How to resolve the algorithm Checkpoint synchronization step by step in the BBC BASIC programming language
You may also check:How to resolve the algorithm Statistics/Normal distribution step by step in the R programming language
You may also check:How to resolve the algorithm Naming conventions step by step in the Factor programming language
You may also check:How to resolve the algorithm Time a function step by step in the C# programming language