Ferry Loading Before bridges were common, ferries were used to transport cars ac
ID: 3603388 • Letter: F
Question
Ferry Loading
Before bridges were common, ferries were used to transport cars across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river's current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars exit from the other end of the ferry.
There is an l-meter-long ferry that crosses the river. A car may arrive at either river bank to be transported by the ferry to the opposite bank. The ferry travels continuously back and forth between the banks so long as it is carrying a car or there is at least one car waiting at either bank. Whenever the ferry arrives at one of the banks, it unloads its cargo and loads up cars that are waiting to cross as long as they fit on its deck. The cars are loaded in the order of their arrival and the ferry's deck accommodates only one lane of cars. The ferry is initially on the left bank where it had mechanical problems and it took quite some time to fix it. In the meantime, lines of cars formed on both banks that wait to cross the river.
The first line of input contains c, the number of test cases. Each test case begins with the number l, a space and then the number m. m lines follow describing the cars that arrive in this order to be transported. Each line gives the length of a car (in centimeters), and the bank at which the car awaits the ferry ("left" or "right").
For each test case, output one line giving the number of times the ferry has to cross the river in order to serve all waiting cars.
Sample input
4
20 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 right
1040 left
15 4
380 left
720 left
1340 left
1040 left
15 4
380 right
720 right
1340 right
1040 right
Output for sample input
3
3
5
6
This problem can be easily solved using your queue data structure (two of them). You must write your implementation file using a linked list instead of an array as we did in class. You can even make the list “doubly linked” which means that in addition to have a next pointer, every node also has a previous pointer so that you can traverse the list in either direction.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//#define MAX_SIZE 100
//structure to store the details of a car
typedef struct {
int car_length; //length of car in centimeters
char car_bank[10]; //river bank on which car is at
} Car;
//structure of a node of linked list
typedef struct {
Car* car;
struct Node *next;
} Node;
typedef struct {
Node *head;
Node *tail;
} Queue;
Queue *left_bank_cars = NULL;
Queue *right_bank_cars = NULL;
/*Node *left_bank_head = NULL; //head node of linked list
Node *left_bank_tail = NULL; //tail node of linked list
Node *right_bank_head = NULL; //head node of linked list
Node *right_bank_tail = NULL; //tail node of linked list*/
//check if Queue is empty
int is_empty(Queue *queue) {
return (queue->head == NULL ? 1 : 0);
}
//insert an item at the tail of the list.
//any new item is to be inserted in tail
//of list for it to behave like a queue.
void insert_item(Queue *queue, Car *car) {
Node* node = (Node*) malloc(sizeof(Node));
node->car = car;
node->next = NULL;
printf("empty:%d ", is_empty(queue));
if (!is_empty(queue)) {
queue->tail->next = node;
queue->tail = node;
printf("item inserted in tail. ");
} else {
queue->tail = node;
queue->head = node;
printf("item inserted as head node:%d ", queue->head->car->car_length);
}
}
//delete an item from head of list.
//an item is to be deleted from head of list
//for it to behave like a queue.
Car* delete_item(Queue *queue) {
if (is_empty(queue))
return NULL;
Car* deleted_item = queue->head->car;
//Node *to_delete=queue->head;
queue->head = queue->head->next;
//free(to_delete);
return deleted_item;
}
//Car* left_bank_cars[MAX_SIZE];
//Car* right_bank_cars[MAX_SIZE];
int main(void) {
int l; //length of ferry in meters
int m; //number of cars on any river ferry_bank
int n; //available capacity on ferry to accommodate cars
char ferry_bank[5]; //current bank of ferry
int c; //number of test cases
int i, j; //counter variables
int car_length; //length of car in centimeters
char car_bank[10]; //bank of a car
int num_left_bank_cars = 0, num_right_bank_cars = 0, num_cars_ferried = 0,
num_ferries = 0;
char line[20]; //line containing car details
char *token;
left_bank_cars = (Queue*) malloc(sizeof(Queue));
left_bank_cars->head = NULL;
left_bank_cars->tail = NULL;
right_bank_cars = (Queue*) malloc(sizeof(Queue));
right_bank_cars->head = NULL;
right_bank_cars->tail = NULL;
strcpy(ferry_bank, "left");
//read number of test cases to execute
fflush(stdin);
scanf("%d", &c);
fflush(stdin);
//loop to process each test case.
for (i = 1; i <= c; i++) {
//for current test case, read length of ferry and number of cars to be ferried.
fflush(stdin);
scanf("%d %d", &l, &m);
//loop to read car details
for (j = 1; j <= m; j++) {
fflush(stdin);
gets(line);
token = strtok(line, " ");
if (token != NULL)
car_length = atoi(token);
token = strtok(NULL, " ");
if (token != NULL)
strcpy(car_bank, token);
Car *car = (Car*) malloc(sizeof(Car));
car->car_length = car_length;
strncpy(car->car_bank, car_bank, strlen(car_bank));
if (strcmp(car_bank, "left") == 0) {
//left_bank_cars[num_left_bank_cars]=car;
insert_item(left_bank_cars, car);
//printf("left:%d ",left_bank_cars->head->car->car_length);
num_left_bank_cars++;
} else if (strcmp(car_bank, "right") == 0) {
//right_bank_cars[num_right_bank_cars]=car;
insert_item(right_bank_cars, car);
num_right_bank_cars++;
}
free(car);
}
//printf("left bank cars:%d ",num_left_bank_cars);
//printf("right bank cars:%d ",num_right_bank_cars);
//now ferry cars for current test case till a car is left on any bank
while (num_cars_ferried <= m) {
//printf("in while loop..%d,%d ",num_cars_ferried,m);
if (strcmp(ferry_bank, "left") == 0) {
//printf("On left bank... ");
n = l * 100; //available capacity on ferry in centimeters
while (num_left_bank_cars > 0) {
if (!is_empty(left_bank_cars)) {
if (left_bank_cars->head->car->car_length <= n) {
printf("Decking a car from left... ");
Car *car = delete_item(left_bank_cars);
if (car != NULL) {
n -= car->car_length;
num_left_bank_cars--;
num_cars_ferried++;
free(car);
}
}
} else
break;
}
num_ferries++;
strcpy(ferry_bank, "right");
//puts(ferry_bank);
} else if (strcmp(ferry_bank, "right") == 0) {
//printf("On right bank... ");
n = l * 100; //available capacity on ferry in centimeters
while (num_right_bank_cars > 0) {
if (!is_empty(right_bank_cars)) {
if (right_bank_cars->head->car->car_length <= n) {
Car *car = delete_item(right_bank_cars);
if (car != NULL) {
n -= car->car_length;
num_right_bank_cars--;
num_cars_ferried++;
free(car);
}
}
} else
break;
}
//if(num_cars_ferried==m)
//break;
num_ferries++;
strcpy(ferry_bank, "left");
}
printf("Number of cars ferried:%d ", num_cars_ferried);
printf("Number of ferries:%d ", num_ferries);
}
}
return EXIT_SUCCESS;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.