Programming Fundamentals

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.

The output from your program should look exactly like this:

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

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest reverse_array

Download pool_max_volume.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/23T1/activities/pool_max_volume/pool_max_volume.c .

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 being 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.

Below are some example inputs/outputs. Alternatively, generate arrays above and test with those as the maximum pool can be seen easily in the interactive.

 ./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

Hints, Notes and Assumptions

• You can assume that no more than 200 inputs will be provided
• Hint: 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.

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest pool_max_volume

Download pool_max_volume_challenge.c here, or copy it to your CSE account using the following command:

cp -n /web/cs1511/23T1/activities/pool_max_volume_challenge/pool_max_volume_challenge.c .

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 (...) {
        ...
    }
}

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest pool_max_volume_challenge

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

Output Format

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).

An Extra Challenge (☠)

As backstory, this challenge was written in a single night, after I nerd-sniped myself.

I'm pretty sure the solution I have to this question is correct, but I invite anyone who is really interested in this problem to submit a proof of their code being correct. If doing so interests you, you may find the courses COMP3121, COMP4161, COMP2111 and COMP6721 interesting.

Submit your proof via the cs1511.challenge@cse.unsw.edu.au email (be sure to include your zID).

When you think your program is working, you can use autotest to run some simple automated tests:

1511 autotest going_electric