KIT107 Programming Assignment 3 Solved

KIT107 Programming Assignment 3
Context
The assignment is to construct a program that given some representation of a maze will find the path through to the end without you lifting a pencil or getting mud on your shoes!

 

An example of a maze is the following:

 

 

 

The challenge is to find a path from the square marked Start to the square marked Stop! by moving forwards, turning left, and turning right (with all directions relative to the current direction of travel) without going through “walls” which are indicated as black squares.

 

The application of this game to computing is the design of a program that allows a starting square to be given and then for the user to be graphically shown a solution derived by the computer.  The computer will select moves by creating a game tree.  A game tree consists of all the possible states of the game and in this assignment the computer determines any possible solution as the best one.  Each node of the game tree has children that indicate the states of the game that follow from the state of the parent for each possible move, i.e. each node in the tree possesses three branches which represent the maximum possible moves from the parent node.

 

This assignment uses many data structures (trees, linked-lists, stacks, and queues) to solve the puzzle.  The game will be text only.

 

A sample run of the game is shown below for depth-first:

 

  

 

And breadth-first:

 

  

Task
A Visual Studio project file is available for download from MyLO.  The project contains many header (.h) and source (.c) files.  All required files are present.   

 

Your task is to complete the functions within the program files which have been declared but for which the function bodies are missing and to update the header comments for the source files that you change.

Program Style
Your program should follow the following coding conventions:

•       const variable identifiers should be used as much as possible, should be written all in upper case and should be declared before all other variables;

•       Variable identifiers should start with a lower case letter, be meaningful, and variables should only be declared at the top of a function;

•       Every if and if-else statement should have a block of code (i.e. collections of lines surrounded by { and }) for both the if part and the else part (if used);

•       Every loop should have a block of code;

•       The keyword continue should not be used;

•       The keyword break should only be used as part of a switch statement;           Opening and closing braces of a block should be aligned;

•       All code within a block should be aligned and indented 1 tab stop (or 4 spaces) from the braces marking this block;      Commenting:

o   There should be a block of header comment which includes at least

§  file name

§  student names

§  student identity numbers

§  a statement of the purpose of the program

§  date o  Each variable declaration should be commented

o   There should be a comment identifying groups of statements that do various parts of the task

o   Comments should describe the strategy of the code and should not simply translate the C into English

Style marks will be awarded proportionally, i.e. if you attempt only half the coding you can expect only half the style marks.

Marking scheme 
Task/Topic 
Maximum mark 
Program operates as specified 
 
square_state.c correctly completed 
2 
game_state.c correctly completed 
10 
t_node.c correctly completed 
5 
game_tree.c correctly completed 
21 
stack.c correctly completed 
5 
queue.c correctly completed 
5 
Program Style 
 
Does not unnecessarily repeat tests or have other redundant/confusing code 
6 
Uses correctly the C naming conventions 
6 
Alignment of code and use of white space makes code readable 
6 
Always uses blocks in branch and loop constructs 
6 
Meaningful identifiers 
6 
Variables declared at the top of functions 
6 
Each variable declaration is commented 
6 
Comments within the code indicate the purpose of sections of code (but DO NOT just duplicate what the code says) 
6 
What and how to submit
Only one submission is required for the pair but both paper and electronic submission is required for each pair.

What to submit
Paper submission
•       A signed cover page (blanks can be collected from the ICT office or from the ICT web site). Your assignment will not be marked unless this is present;

•       A print-out of the six ‘.c’ source code files you changed; and

•       A statement from each person indicating what proportion of the work was theirs.  If the work was done equally, then each person should claim 50% of the effort.  

It is expected that this will be the case and this will be assumed if no statement

is submitted.  If, however, one person has done very little, then this should be stated.  A reason why this is the case should be given.  For example, if one student does 80% of the work because their partner did not turn up to meetings, complete work by the agreed time, etc. then this should be stated.  If one student does 30% of the work because the other student simply went off and did it all by themselves and without consultation then this should be stated.

Electronic submission
 You should submit the entire Visual Studio project folder compressed as a ZIP file.

How to submit 
Paper submission     Print the programs which you have modified in landscape orientation.

    Firmly staple together all of the required documents (with the signed cover page on top) and place them in the appropriate submissions box near the ICT Help Desk. Your assignment will not be marked unless this is present.

Electronic submission
•       Log in to MyLO and navigate to the Assignments tool under the Assessments icon in the top tool bar.

•       Select Assignment 2 from the list of available drop-boxes.

•       Click on Add a File and follow the instructions to attach your ZIPped project folder and then click Add.  Then click Submit.

•       If you want to resubmit, rename your ZIPped project folder as ‘version 2’ and repeat the submission process.

 

Remember that only one paper and electronic submission is required per pair. Plagiarism and Cheating: 

Practical assignments are used by the School of Engineering and ICT for students to both reinforce and demonstrate their understanding of material which has been presented in class. They have a role both for assessment and for learning.  It is a requirement that work you hand in for assessment is substantially your own.

Working with others
One effective way to grasp principles and concepts is to discuss the issues with your peers and/or friends. You are encouraged to do this. We also encourage you to discuss aspects of practical assignments with others. However, once you have clarified the principles, your pair must express them in writing or electronically entirely by yourselves. In other words you must develop the algorithm to solve the problem and write the program which implements this algorithm with your partner and no one else (other than staff).

Cheating
•       Cheating occurs if you claim work as your own when it is substantially the work of someone else.

•       Cheating is an offence under the Ordinance of Student Discipline within the University.  Furthermore, the ICT profession has ethical standards in which cheating has no place.

•       Cheating involves two or more parties.

o   If you allow written work, computer listings, or electronic version of your code to be borrowed or copied by another student you are an equal partner in the act of cheating.

o   You should be careful to ensure that your work is not left in a situation where it may be stolen by others.

•       Where there is a reasonable cause to believe that a case of cheating has occurred, this will be brought to the attention of the unit lecturer. If the lecturer considers that there is evidence of cheating, then no marks will be given to any of the students involved. The case will be referred to the Head of School for consideration of further action.

Julian Dermoudy, May 8th 2017.