valgrindto perform simple checks on the program
pangolins.cthat plays the game of Pangolins (described below). As well as this lab script, you are provided with:
makefile into your
/opt/info/courses/COMP26120/problems/ex6 (use this path).
When you are using pointers, there is every chance that at some point your
program will crash with the message:
If you can't work out what happened, try using a debugger (e.g.
man gdb or
e.g. to use
The top pane will use a big red arrow to point to just before the line of code where the program crashed. The bottom pane will give more detailed information e.g. about function parameters and the line number.
The top pane will use a big grey arrow to point to just before the line of code where the previous function was called. Again, the bottom pane will give more detailed information.
Repeat this step if you need to.
Here's an example game. Your input is prefixed by '>', and the computer's output is in bold text.
Does it have a tail? > No Is it flat, round and edible? > Yes Is it a pizza? > No Oh. Well you win then :-( What were you thinking of? > a biscuit Please give me a question about a biscuit, so I can tell the difference between a biscuit and a pizza > Can you dip it in your tea? What is the answer for a biscuit? > Yes ThanksThe game is straightforward. The computer starts knowing only about a single 'object' (i.e. a thing, nothing to do with object oriented programming). Whatever object you're thinking of, the computer will offer its first and only possible answer as its guess. If this guess turns out to be wrong, the computer will ask you for three pieces of information:
A longer example game of Pangolins, with several rounds
How does the Pangolins game work?
Step 1A: Define your data structure e.g. using a struct. You might also use a union and an enum. (Hints about data structures.)
Write a diagnostic function called
that will print out the status of a single node of the tree.
(This should help you with debugging.)
Look at the decision tree
at the end of round 5 of the example game.
If we called the function
nodePrint on the
"does it like to chase mice" question, we might expect output something like
Object: [NOTHING] Question: Does it like to chase mice? Yes: A cat No: a pangolinAlternatively, calling the same function on the "a pizza" node would give output something like:
Object: a pizza Question: [NOTHING]Notice in this second example we have not printed out the 'Yes' and 'No' alternatives to the question since there isn't a question.
Now, you should 'hard-code' a small tree of questions and answers
into your program: you'll need this both to test your
function and later to get the game off to a good start. We suggest you
play the game on a piece of paper, and build up a small tree (say 6 or 7
nodes) of questions and objects. Now create a data structure to represent
this, and add it to your program. No need to use dynamically memory at this
stage - you can just create the data structures using statically declared
Now, write a new function -
treePrint - which prints
out the whole game tree you have just hard-coded. Parts of
treePrint will, of course, be similar to
nodePrint, but it will use recursion to print out
all the nodes of the tree in a systematic way.
You can get rid of
nodePrint when you are happy that
treePrint is working correctly.
(Hints about printing a tree.)
fgetsto get input from the user and then building new parts of the tree in response to what the user says.
When you hard-coded the data structures in part 1, they were conveniently allocated on the stack for you, strings and all. Since the compiler could tell from looking at your program how long your questions were, how many questions you had, how long the object names were, and so on, it could allocate appropriate amounts of stack for the job. However, when the game is being played 'live', there is no possible way of predicting these sizes, so you will have to use dynamic allocation techniques to store the strings that are typed in by the user, as well as the structs that form the tree itself.
The game should allow for arbitrarily long questions and object names, and
in principle the tree can be extended indefinitely. This means that it is
simply not possible to use static arrays to store the tree or its contents;
you'll have to dynamically allocate memory using
One exception to this open-endedness, is that in order to read a string of
characters from the user, it must be stored somewhere; there is no
'standard' function in C that will allow you to read in a string of
unbounded length since you have to pass a buffer to the functions into which
the string will be copied (so you have to know how long your maximum
string/buffer size is in advance.) Unless you want to go to the effort of
writing an extensible input-getting function, this means you have to choose
a sensible length of buffer to statically allocate. Use one of the standard
'input' functions from the C library (we'd recommend
making sure to tell the function what the maximum number of characters to
accept is, and finally copy the string from your fixed size static buffer
into a snug-fitting dynamically allocated buffer within your game tree. It's
not a perfect solution, but it will do fine for us here.
(Hints about performing input.)
A neat way of packaging this slightly unsatisfactory state of affairs up
would be to write a function that asks for a user input of a defined maximum
size, and then returns a
malloc-ed string exactly fitting
the string that the user actually entered.
Once you have a function (or functions) to deal with user input like this, coding the logic of the game so that appropriate questions are asked, appropriate guesses made and the tree dynamically created is relatively straightforward. (Hints about the basic logic of the game.)
To get full marks for this part, you should make your game robust to the types of input that a user might give. For example: if the user gives 'pangolin' rather than 'a pangolin' as a reply, does you program produce text that reads correctly the next time round? (i.e. does it assume that the user has given the correct article ('an', 'a', 'the' etc.) before the object name?) What happens if the user forgets to put a question mark at the end of their question? Can they type 'y' as well as 'yes'? Could they even type 'absolutely' or 'correct'? You won't be able to mitigate against all possible types of nonsense input, but given that the user is not trying to test an artificial intelligence program but might make a few genuine mistakes, can your program cope gracefully with these?
This would be a good place to get to by the end of the first lab session.
Of course, at the moment, every time you finish your program, it will forget about everything it has learned. Hardly what you'd want. Your task now is to write functions to load and save the question tree to a file.
Step 3A: Save your game tree to a text file. (Hints about saving and loading the tree.)
Step 3B: Read a saved game tree and recreate it in memory. Play the game to verify that the tree is correct.
To simplify testing, you should probably use program parameters to set the filenames, and only initialise and/or save the tree if filenames are given.
When you program is ready to finish, make sure you have explicitly
free-ed all the memory that has been
by you. You might want to do this recursively.
valgrind to convince yourself that there is nothing going
awry and that all the tiniest bits of memory have been
free-ed correctly (you will need to demonstrate
valgrind giving your program a clean bill of health to get your
marks for this task).
submit will look for:
This lab gets tougher as it goes along, and the marking scheme is kept quite tight and to-the-point. Once more there are a few marks allocated for 'subjective' issues like style, tidiness and clarity of code, and a few marks for really quite difficult bits towards the end. The majority of the marks are awarded on a 'does it work' basis.
The marks are awarded as follows:
1 mark : Part 1A - a sensible data structure 1 mark : Part 1C - nodePrint function 3 marks: Part 1D - treePrint function 3 marks: Part 2 - a basic working game of pangolins 3 marks: Part 2 - dealing sensibly with user input 3 marks: Part 3A - saving your game to a text file 3 marks: Part 3B - loading your game back from the file 3 marks: Part 4 - using
valgrindto show that all your data structures are tidied up nicely before your program exits Total 20