Programming Fundamentals

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

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

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

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

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

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

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)

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

1511 autotest going_electric