Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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:

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

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
101 {
102 test(); // run self-test implementations
103 return 0;
104}
static void test()
Self-test implementations.
Definition trapped_rainwater.cpp:62
Here is the call graph for this function:

◆ test()

static void test ( )
static

Self-test implementations.

Returns
void
62 {
63 std::vector<uint32_t> test_basic = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
64 assert(dynamic_programming::trappedRainwater(test_basic) == 6);
65
66 std::vector<uint32_t> test_peak_under_water = {3, 0, 2, 0, 4};
67 assert(dynamic_programming::trappedRainwater(test_peak_under_water) == 7);
68
69 std::vector<uint32_t> test_bucket = {5, 1, 5};
70 assert(dynamic_programming::trappedRainwater(test_bucket) == 4);
71
72 std::vector<uint32_t> test_skewed_bucket = {4, 1, 5};
73 assert(dynamic_programming::trappedRainwater(test_skewed_bucket) == 3);
74
75 std::vector<uint32_t> test_empty = {};
76 assert(dynamic_programming::trappedRainwater(test_empty) == 0);
77
78 std::vector<uint32_t> test_flat = {0, 0, 0, 0, 0};
79 assert(dynamic_programming::trappedRainwater(test_flat) == 0);
80
81 std::vector<uint32_t> test_no_trapped_water = {1, 1, 2, 4, 0, 0, 0};
82 assert(dynamic_programming::trappedRainwater(test_no_trapped_water) == 0);
83
84 std::vector<uint32_t> test_single_elevation = {5};
85 assert(dynamic_programming::trappedRainwater(test_single_elevation) == 0);
86
87 std::vector<uint32_t> test_two_point_elevation = {5, 1};
88 assert(dynamic_programming::trappedRainwater(test_two_point_elevation) ==
89 0);
90
91 std::vector<uint32_t> test_large_elevation_map_difference = {5, 1, 6, 1,
92 7, 1, 8};
94 test_large_elevation_map_difference) == 15);
95}
uint32_t trappedRainwater(const std::vector< uint32_t > &heights)
Function to calculate the trapped rainwater.
Definition trapped_rainwater.cpp:27
Here is the call graph for this function: