Description
Problem Defintion
N ants numbered 1, 2, 3, . . . , N are trying to cross a road that contains several holes with different depths.
To pass through a hole with depth M < N1
, the M leading ants have to go into the hole so that the remaining
ants can safely cross the hole. Then, the last ant who crossed the hole (i.e., Nth ant in the line) pulls the
ant which is on top (i.e., Mth ant in the line) from the hole. Afterwards, the rescued ant (i.e., Mth ant)
pulls the ant on the top (i.e., (M − 1)th ant) from the hole, and so on until no ants are left in the hole.
Then they continue their trip to the next hole2
, and apply the same procedure there. For example, look at
the scenario below where N = 5 ants are crossing two holes with depths M = 2 and M = 1.
1 2 3 4 5
1
2
3 4 5
3 4 5 2 1
Initially 5 ants numbered as 1
to 5 try to cross a hole
2 leading ants go into the hole
1
2
3 4 5
Remainig 3 ants cross the hole
1
3 4 5 2
The Ant 5 who crossed the hole lastly
pulled up Ant 2 (the ant at the top) from the hole
Rescued Ant 2 pulled up Ant 1 (the ant at the top)
from the hole. No ants left in the hole.
Then, they continue their trip to the next hole
2 1
3
4 5
1 leading ant goes into the hole
4 5 2 1 Ant 1 pulled up Ant 3 (the ant at the top) from
the hole. They safely cross from all holes. The
output sequence is 4, 5, 2, 1, 3
3
5
2 1
Input File
N=5
M=2, 1
(see below description)
Figure 1: N = 5 ants are crossing two holes with depths M = 2 and M = 1
1The depth of the holes cannot be larger than the total number of ants N
2The distance between two holes can not be smaller than the number of ants in the ant sequence.
Page 1 of 3
BLG 223E Data Structures Homework #4
Implementation
1. Use the below data structure Ants. Implement queueAnt and stackAnt data structures. You are going
to implement queue and stack data structures respectively. Queue and Stack implementations will be
done with singly linked list implementations.
You are not allowed to include any Standard Template Library (STL) container.
struct Ants {
queueAnt ants ;
queueAnt holeDepths ;
stackAnt hole ;
void ReadFile ( char *);
void ShowContents ( bool );
void CrossRoad ();
};
2. Implement void ReadFile(char *):
Read number of ants and the depths of holes dynamically from the input file whose name is passed as
a command line parameter. The first line indicates the number of ants while the second line indicates
the depths of holes on the way separated by space character. You can use C++ classes to perform output
and input of characters to/from files.
3. Implement void ShowContents(bool):
Prints out the contents of the queues according to bool argument. If true, prints out the contents of
queueAnt ants; otherwise prints out the contents of queueAnt holeDepths.
4. Implement: void CrossRoad():
This function makes all ants cross the road that contains several holes whose depths are obtained from
the second line of the input file.
Main Program, Compilation and Screen Output
• You are going to use the below main program to test your implementations. Your source code file must
be a single file and has the name hw4.cpp.
int main (int argc , char ** argv ){
Ants a ;
a . ReadFile ( argv [1]); // store the number of ants and depths of holes
cout << "The initial Ant sequence is: ";
a . ShowContents (1); // list ant sequence ( initially : 1 , 2 , ... , N)
cout << "The depth of holes are : ";
a . ShowContents (0); // list depth of holes
a . CrossRoad ();
cout << "The final Ant sequence is: ";
a . ShowContents (1);
return 0;
}
• Your program should compile and run on Linux environment using g++ (version 4.8.5 or later).
You can test your program on ITUs Linux Server using SSH protocol. To compile the code, use the
following command:
g++ -Wall -Werror hw4.cpp -o hw4
Page 2 of 3
BLG 223E Data Structures Homework #4
• Your input data filename will be supplied from the command line. Don’t name it in your
program statically. Your program must take input filename as command line argument. Then run
your executable (named as hw4) using the following command:
./hw4 input file name
where input file name is name of any test file we will use to evaluate your homeworks. IF YOUR
PROGRAMS DON’T TAKE FILE NAME FROM THE COMMAND LINE, THEY
WILL NOT BE EVALUATED AND BE GRADED AS 0.
• Main program are going to print out the following message for the given scenario above:
The initial Ant sequence is : 1 2 3 4 5
The depth of holes are : 2 1
The final Ant sequence is : 4 5 2 1 3
Your program will be checked using Calico(https://bitbucket.org/uyar/calico) automatic
checker. Therefore, make sure you print the messages exactly as given in the homework
definition You get zero marks if the automatic checker fails.
Submission Rules
•
If a question is not clear, you can ask your question under the thread that is specially started for
homework 4 (Questions about HW4) on the message board for BLG 223E on NINOVA. Please
check before writing your question whether your question is asked by someone else.
Do not share any code or text that can be submitted as a part of an assignment (discussing ideas
is okay).
.
• Make sure you write your name and number in all of the files of your project, in the following format:
/* @Author
Student Name:
Student ID :
Date:
• Only electronic submissions through Ninova will be accepted no later than December, 13 at 11:59pm.
• You may discuss the problems at an abstract level with your classmates, but you should not share
or copy code from your classmates or from the Internet. You should submit your own, individual
homework.
• Academic dishonesty, including cheating, plagiarism, and direct copying, is unacceptable.
• Use comments wherever necessary in your code to explain what you did.
• Note that YOUR CODES WILL BE CHECKED WITH THE PLAGIARISM TOOLS!
Page 3 of 3 End of homework.
