island rainfall problem – C array/pointer algo (working v1)

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <algorithm>
#include <assert.h>
using namespace std;
int const island[] = { 54, 50, 54, 54, 52, 55, 51, 59, 50, 56, 52, 50 };
///////////////   Pos # 0   1   2   3   4   5   6   7   8   9  10  11
int const size = sizeof(island) / sizeof(int);
int accu = 0;
template<class ForwardIterator>
ForwardIterator max_element_last(ForwardIterator first, ForwardIterator last) {
    ForwardIterator ret = first;
    if (first == last)
        return last;//empty range
    while (++first != last)
        if (*ret <= *first)
            ret = first;
    return ret;
}
void print1(int const* const a, char const * const label) {
    printf("%s=%d/%d ", label, *a, a - island);
}
void printAll(int const* const L, int const* const l, int const* const h,
        int const* const H) {
    if (l < h) {
        print1(L, "wallL");
        print1(l, "ptr");
        printf("  ");
        print1(h, "ptr");
        print1(H, "wallH");
    } else {
        print1(H, "wallH");
        print1(h, "ptr");
        printf("  ");
        print1(l, "ptr");
        print1(L, "wallL");
    }
    printf("%d=accumulated\n", accu);
}
void onePassAlgo(){
    int*wallLo, *wallHi;
    int*l, *h; //moving pointers
    wallLo = l = const_cast<int*> (island);
    wallHi = h = const_cast<int*> (island) + size - 1;
    if (*l > *h) {
        std::swap(l, h);
        std::swap(wallLo, wallHi);
    }
    printAll(wallLo,l,h,wallHi);
    printf("All pointers initialized\n");
    while (l != h) {
        if (*l > *wallHi) {
            wallLo = wallHi;
            wallHi = l;
            std::swap(l, h);
            //printf("new wallHi:");
        } else if (*l >= *wallLo) {
            wallLo = l;
            //printf("new wallLo:");
        } else {
            accu += *wallLo - *l;
            printf("adding %d liter of water at Pos#%d (T=%d)\n", *wallLo - *l,
                    l - island, accu);
        }
        printAll(wallLo,l,h,wallHi);
        //now move the scanner
        if (l < h)
            ++l;
        else
            --l;
    }
}
void twoPassAlgo() {
    int const* const peak = max_element_last(island, island + size);
    printf("highest peak (last if multiple) is %d, at Pos %d\n", *peak, peak
            - island);
    //(island, island + size, ostream_iterator<int> (cout, " "));
 
    //forward scan towards peak
    int* pos = const_cast<int*> (island); //left edge of island
    int* wall = pos;
    for (++pos; pos < peak; ++pos) { if (*wall > *pos) {
            accu += *wall - *pos; // accumulate water
            printf("adding %d liter of water at Pos#%d (T=%d)\n", *wall - *pos,
                    pos - island, accu);
            continue;
        }
        //ALL new walls must match or exceed previous wall.
        printf("found new wall of %d^ at Pos#%d\n", *pos, pos - island);
        wall = pos;
    }
    cout << "^^^ end of fwd scan ; beginning backward scan vvv\n";
    //backward scan
    pos = const_cast<int*> (island) + size - 1;
    wall = pos;
    for (--pos; pos > peak; --pos) {
        if (*wall > *pos) {
            accu += *wall - *pos; // accumulate water
            printf("adding %d liter of water at Pos#%d (T=%d)\n", *wall - *pos,
                    pos - island, accu);
            continue;
        }
        //Note all new walls must match or exceed previous wall.
        printf("found new wall of %d^ at Pos#%d\n", *pos, pos - island);
        wall = pos;
    }
}
int main(int argc, char *argv[]) {
    onePassAlgo();
}
/*
 Requirement -- an island is completely covered with columns of bricks. If
 between Column
 A(height 9) and Column B(10) all columns are lower, then we get a basin to
 collect rainfall. Watermark level will be 9.  We can calculate the
 amount of water. If I give you all the columns, give me total rainfall collected.
 Code showcasing
 - stl algo over raw array
 - array/pointer manipulation
 - array initialization
 - array size detection
 - std::max_element modified
 - std::swap
 */
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s