Programming Fundamentals

Information

  • This page contains extra challenge exercises for week 04.
  • These exercises are not compulsory, nor do they provide any marks in the course.
  • These exercises are intended for students that want more challenge in the course.
  • You cannot submit any of these exercises, however autotests are available for them (Command included at bottom of each exercise).

Exercise
(●◌◌)
:
Reverse an array

Write a C program, reverse_array.c, which reads integers line by line, and when it reaches the end of input, prints those integers in reverse order, line by line.

You will never be given more than 100 integers to print out.

Examples

dcc reverse_array.c -o reverse_array
./reverse_array
Enter numbers forwards:
10
50
20
40 

Reversed:
40
20
50
10
./reverse_array
Enter numbers forwards:
-5
-4
-3
-2
-1 

Reversed:
-1
-2
-3
-4
-5
Sample solution for reverse_array.c 
// 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;
}

Exercise
(●●◌)
:
Max Pool Volume

Download pool_max_volume.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity pool_max_volume

Your task is to add code to these functions in pool_max_volume.c: 

// 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]) {
    // TODO: Complete this function
    return 42;
}

The Problem

For the last week, it has been raining continously. You have noticed that with this rain, water has been trapped in uneven parts of the land. You, being the curious person that you are, wish to find which pool of trapped water contains the most volume.

The Program

For this exercise, you have been given some starter code to scan in n numbers into an array. You are to write the function seen at the top of this question

The input provided to the program is the height of each consecutive piece of land that you have measured

Water is said to be trapped if it has two pieces of land to both sides of it (does not need to be directly next to either piece) such that both pieces of land are taller, or the same height as this water

An interactive example has been provided below to show where water is trapped

Number of Elements:
(Max 100)

You can generate arrays above and test with those as the maximum pool can be seen easily in the interactive

Examples

 dcc pool_max_volume.c -o pool_max_volume
 ./pool_max_volume
Please enter heights: 7 2 7 6 4 6 8 2 4 5

Maximum volume of pools: 5
 ./pool_max_volume
Please enter heights: 6 2 5 0 5 0 2 8 3 5 7 13 17 17 14 17 14 17 11 14

Maximum volume of pools: 22
 ./pool_max_volume
Please enter heights: 3 9 1 2 0 6 5 3 5 8

Maximum volume of pools: 34
 ./pool_max_volume
Please enter heights: 8 7 6 5 4 3 2 1

Maximum volume of pools: 0

Assumptions/Restrictions/Clarifications

  • You can assume that no more than 200 inputs will be provided
  • If you picked any height in the array, could you move forward in the array and find the the furthest height that could hold water with the selected height? Could you repeat this for every height?
  • It can be assumed that any land that appears before and after the inputs (E.g. not in the array) have a negative infinite height. This means that pools cannot be formed such that they would continue out of the array
Sample solution for pool_max_volume.c 
// 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;
}

Exercise
(●●●)
:
Max Pool Volume Without Nested Looping

Download pool_max_volume_challenge.c here

Or, copy these file(s) to your CSE account using the following command:

1511 fetch-activity pool_max_volume_challenge

Your task is to add code to these functions in pool_max_volume_challenge.c: 

// 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]) {
    // TODO: Complete this function WITHOUT using any nested loops
    return 42;
}

For this exercise, you will be completing the exact same question as the previous one. The difference however, is that you cannot use nested loops anymore. This means that you cannot put a loop inside of a loop

For example, the below is illegal in this exercise!

while (...) {
    ...
    // You cannot put a loop inside another loop!
    while (...) {
        ...
    }
}

Sample solution for pool_max_volume_challenge.c 
// 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);
}

Exercise
(●●●)
:
Help route an electric car along a long road

You are in charge of planning a route for an electric car across a long road.

Your electric car takes exactly one unit of charge to travel one kilometer. It has infinite battery capacity, but starts off empty

Conveniently, every kilometer along this road, there is a charging station, where you can stop to charge your car. These charging stations may have a limited of supply of charge you can use to charge your car. A charging station may have no charge available

Your job is to determine if it is possible to drive your car to the last charging station on the road, and if so, what the minimum number of stops is to get your car there

Input Format

You should write a C program, going_electric.c

This program will be provided a series of numbers. Each number represents the charge available from a given charging station. The first number given is the charge of the first station (where your car begins its journey). The second number given is the charge at the second station, and so on

Output Format

Your program should print a single integer, the minimum number of charging stops required to cross the road. This should include the initial charging stop

If it is not possible to drive all the way along the road, you should print the integer 0.

Examples

dcc going_electric.c -o going_electric
./going_electric
2 0 0

1

In the above example, the car had to charge at the first station. It then had 2 units of charge, which let it reach the final station. Note that even though that final charging station had no charge to give, the car successfully reached it (just), so this journey is possible.

./going_electric
2 0 0 3 0

0

In the above example, the car could not make it to the last charging station -- the two units of charge at the first station aren't enough to drive to the next charging station with more charge.

./going_electric
1 1 1 1 0

4

In the above example, the car charges at each of the four stations it can. In this way, it just makes it to the final charging station.

./going_electric
3 3 2 1 0

2

In the above example, the car must charge twice, but there are three possible ways it could do so -- it must charge at the first station, but then it could charge at any of the others (excluding the last).

Assumptions/Restrictions/Clarifications

  • The road will have no more than 10000 charging stations
  • The road is longer than 1 kilometer (that is, it has at least two charging stations)
  • A charging station always has a non-negative amount of charge (that is, either a charging station has a positive amount of charge, or no charge at all)
Sample solution for going_electric.c 
// Solution to Going Electric
// Tom Kunc (t.kunc@unsw.edu.au) - 2020-06-20

#include <stdio.h>
#include <stdbool.h>

#define MAX_STATIONS 10000

int contains_nonzero(int size, int array[size]) {
    int i = 0;
    while (i < size) {
        if (array[i] > 0) {
            return true;
        }
        i++;
    }
    return false;
}

int find_max_index(int size, int array[size]) {
    int max_index = 0;

    int i = 0;
    while (i < size) {
        if (array[i] > array[max_index]) {
            max_index = i;
        }
        i++;
    }

    return max_index;

}

int main(void) {
    int stations[MAX_STATIONS] = {0};
    int num_stations = 0;
    while (scanf("%d", &stations[num_stations++]) == 1);

    int num_stops = 0;
    int fuel = 1;

    while (contains_nonzero(fuel, stations) && fuel < num_stations - 1) {
        int max_index = find_max_index(fuel, stations);
        fuel += stations[max_index];
        stations[max_index] = 0;
        num_stops++;
    }

    if (fuel >= num_stations - 1) {
        printf("%d\n", num_stops);
    } else {
        printf("%d\n", 0);
    }
    return 0;
}