Week 05 Extra Sample Solutions

// A program to print a list of integers in reverse
// Written by Tom Kunc (t.kunc@unsw.edu.au)
// Created in 2019-06-23

#include <stdio.h>

#define MAX_NUMBERS 100

int main(void) {
    
    int i = 0;
    int did_scan_something = 0;
    int scanned_value;
    int scanned_numbers[MAX_NUMBERS];

    printf("Enter numbers forwards:\n");

    while (scanf("%d", &scanned_value) == 1) {
        scanned_numbers[i] = scanned_value;
        did_scan_something = 1;
        i++;
    }
    
    printf("Reversed:\n");

    while (i > 0 && did_scan_something) {
        i--;
        printf("%d\n", scanned_numbers[i]);
    }

    return 0;
}

// Program that takes in an array of heights and outputs the maximum volume
// that can be held in one region of these heights.
//
// Written by Rory Golledge (z5308772), 05-03-2022

#include <stdio.h>

#define MAX_HEIGHT 200

int max_pool_volume(int length, int heights[length]);

int main(void) {
    int height;

    int heights[MAX_HEIGHT];
    int n_heights = 0;
    printf("Please enter heights: ");
    while (n_heights < MAX_HEIGHT && scanf("%d", &height) == 1) {
        heights[n_heights] = height;
        n_heights++;
    }

    printf(
        "Maximum volume of pools: %d\n",
        max_pool_volume(n_heights, heights)
    );

    return 0;
}

// Given two integers, `a` and `b`, return whichever is smaller.
int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}

// Given two integers, `a` and `b`, return whichever is larger.
int max(int a, int b) {
    if (a < b) {
        return b;
    }
    return a;
}

// Given an array `heights` of length `length`, returns the volume of the
// largest possible pool that can be formed between the heights.
int max_pool_volume(int length, int heights[length]) {
    int i = 0;
    int max_volume = 0;
    while (i < length) {
        int largest_volume_index = i + 1;
        int j = i + 1;
        while (j < length) {
            if (heights[j] >= heights[i]) {
                largest_volume_index = j;
                j = length;
            } else if (heights[j] >= heights[largest_volume_index]) {
                largest_volume_index = j;
            }
            j++;
        }

        // An index needs to be found for any water volume to exist
        if (largest_volume_index != -1) {
            int pool_volume = 0;
            int min_height = min(heights[i], heights[largest_volume_index]);
            j = i + 1;
            while (j < largest_volume_index) {
                pool_volume += min_height - heights[j];
                j++;
            }

            // Update max volume if it applies.
            max_volume = max(max_volume, pool_volume);
        }
        i++;
    }

    return max_volume;
}

// Program that takes in an array of heights and outputs the maximum volume
// that can be held in one region between these heights.
//
// Written by Rory Golledge (z5308772), 05-03-2022
//
// In a perfect world, searching from left to right and from right to left would
// be a single function. However, for the sake of readability, they have been
// separated to prevent more complicated statements.

#include <stdio.h>

#define MAX_HEIGHT 200

int max_pool_volume(int length, int heights[length]);

int main(void) {
    int height;

    int heights[MAX_HEIGHT];
    int n_heights = 0;
    printf("Please enter heights: ");
    while (n_heights < MAX_HEIGHT && scanf("%d", &height) == 1) {
        heights[n_heights] = height;
        n_heights++;
    }

    printf(
        "Maximum volume of pools: %d\n",
        max_pool_volume(n_heights, heights)
    );

    return 0;
}


// Given two integers, `a` and `b`, return whichever is larger.
int max(int a, int b) {
    if (a < b) {
        return b;
    }
    return a;
}

// Finds the max pool given an array of heights and its length. Search direction
// is left to right
int max_pool_right_search(int length, int heights[length]) {
    int left = 0;
    int right = 1;

    int max_volume = 0;
    int running_land_sum = 0;
    while (right < length) {
        if (heights[right] >= heights[left]) {
            // Water height is always just the `left` piece of land here.
            int water_height = heights[left];
            int x_distance = right - left - 1;

            // Get the maximum possible water volume (width * height) of region
            int rectangle_sum = water_height * x_distance;

            // The final water volume is simply the difference between the max
            // water and the land heights in this region
            int water_volume = rectangle_sum - running_land_sum;

            // Update max_volume if required
            max_volume = max(max_volume, water_volume);

            // Now a new region is to be considered, so running sum is reset
            running_land_sum = 0;

            left = right;
        } else {
            running_land_sum += heights[right];
        }
        right++;
    }

    return max_volume;
}

// Finds the max pool given an array of heights and its length. Search direction
// is right to left
int max_pool_left_search(int length, int heights[length]) {
    int right = length - 1;
    int left = length - 2;

    int max_volume = 0;
    int running_land_sum = 0;
    while (left >= 0) {
        if (heights[left] >= heights[right]) {
            // Water height is always just the `right` piece of land here.
            int water_height = heights[right];
            int x_distance = right - left - 1;

            // Get the maximum possible water volume (width * height) of region
            int rectangle_sum = water_height * x_distance;

            // The final water volume is simply the difference between the max
            // water and the land heights in this region
            int water_volume = rectangle_sum - running_land_sum;

            // Update max_volume if required
            max_volume = max(max_volume, water_volume);

            // Now a new region is to be considered, so running sum is reset
            running_land_sum = 0;

            right = left;
        } else {
            running_land_sum += heights[left];
        }
        left--;
    }

    return max_volume;
}

// Given an array `heights` of length `length`, returns the volume of the
// largest possible pool that can be formed between the heights.
int max_pool_volume(int length, int heights[length]) {
    if (length <= 2) {
        return 0;
    }

    int max_right = max_pool_right_search(length, heights);
    int max_left = max_pool_left_search(length, heights);
    return max(max_left, max_right);
}