trapped_rainwater.cpp File Reference

Implementation of the Trapped Rainwater Problem More...

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

Include dependency graph for trapped_rainwater.cpp:

Go to the source code of this file.

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.

Functions
uint32_t	dynamic_programming::trappedRainwater (const std::vector< uint32_t > &heights)
	Function to calculate the trapped rainwater.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of the Trapped Rainwater Problem

This implementation calculates the amount of rainwater that can be trapped between walls represented by an array of heights.

Author

SOZEL

Definition in file trapped_rainwater.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 101 of file trapped_rainwater.cpp.

           {
    test();  // run self-test implementations
    return 0;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

Definition at line 62 of file trapped_rainwater.cpp.

                   {
    std::vector<uint32_t> test_basic = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
    assert(dynamic_programming::trappedRainwater(test_basic) == 6);
 
    std::vector<uint32_t> test_peak_under_water = {3, 0, 2, 0, 4};
    assert(dynamic_programming::trappedRainwater(test_peak_under_water) == 7);
 
    std::vector<uint32_t> test_bucket = {5, 1, 5};
    assert(dynamic_programming::trappedRainwater(test_bucket) == 4);
 
    std::vector<uint32_t> test_skewed_bucket = {4, 1, 5};
    assert(dynamic_programming::trappedRainwater(test_skewed_bucket) == 3);
 
    std::vector<uint32_t> test_empty = {};
    assert(dynamic_programming::trappedRainwater(test_empty) == 0);
 
    std::vector<uint32_t> test_flat = {0, 0, 0, 0, 0};
    assert(dynamic_programming::trappedRainwater(test_flat) == 0);
 
    std::vector<uint32_t> test_no_trapped_water = {1, 1, 2, 4, 0, 0, 0};
    assert(dynamic_programming::trappedRainwater(test_no_trapped_water) == 0);
 
    std::vector<uint32_t> test_single_elevation = {5};
    assert(dynamic_programming::trappedRainwater(test_single_elevation) == 0);
 
    std::vector<uint32_t> test_two_point_elevation = {5, 1};
    assert(dynamic_programming::trappedRainwater(test_two_point_elevation) ==
           0);
 
    std::vector<uint32_t> test_large_elevation_map_difference = {5, 1, 6, 1,
                                                                 7, 1, 8};
    assert(dynamic_programming::trappedRainwater(
               test_large_elevation_map_difference) == 15);
}