Assignment 3- C++ Pthreads program

Aim
The objective of this assignment is to
apply the concepts of threading by developing a simple C++ Pthreads program to
discover the surroundings and the shortest path in a 2D maze

Background
This assignment requires you to write a multi-threaded C/C++ “Pathfinder” program to
discover the surroundings of a jungle maze. Each [x, y] location in the maze
represents a ‘grid area’ of the jungle terrain. A particular gird area could be
                
“impassable”             (rep. by ‘#’ barrier) ,
                   
contains
danger       (rep. by ‘X’ danger area)

·                    
clear,                          (i.e. allows you to
travel)

An example of the jungle maze will be provided to you (see Appendix A,
‘mazedata.txt’).
Your objective is to explore as much of the jungle maze terrain as possible, and
mark the discovered area as barrier (‘#’), or danger (‘X’) accordingly.
When your program terminate, it should output a map of the explored jungle maze, as
well as 1 ‘safe’ path, to traverse from Start to End locations.

Task Requirements
A)  
At startup, your program should read in the 2D maze configuration (“mazedata.txt”)
which stores the information about the maze dimensions, barriers, start and end
locations. Please refer to Appendix A for an example.

B)  
For the purposes of testing your program, a sample of what information should be
output is shown in Appendix B.
C)  
Before you start developing your program, you should take some time to review the
output, and analyze the requirements of the Pathfinder program.
D)  
Your program should have at least 2 threads, each thread attempting to
explore surrounding locations to discover whether it contains a barrier (‘#’)
or danger (‘X’).

E)  
Impt
1 : your program should maintain a global Maze resource or variable, holding
information about all the barriers or danger areas uncovered by your exploring
threads!

F)  
Impt
2 : when a particular thread has encountered a barrier (‘#’) or danger (‘X’),
it should …
      
Record
the path (history of point locations) it has traversed, since the Start
Location, to reach the barrier / danger areas, and locations of barrier /
danger should be marked on your ‘global Maze resource’
        
The thread ‘loses its life’ (i.e. should be destroyed) if it has encountered a
danger area (‘X’) !!

G)  
Whenever
a thread is destroyed, your program should create another replacement thread,
to traverse the jungle maze beginning from the Start Location again. But this
time, it should access the ‘global Maze resource’ to learn and avoid the
barriers and danger areas discovered by its predecessor threads!
 
H)  
In this way, the ‘sacrifice’ of the destroyed threads are not in vain, as its
knowledge (of locations of the barriers / danger areas) have been recorded in
the ‘global Maze resource’ that can be accessed by future generations of
created threads to aid their survival in order to discover a path to End
Location!
I)    
As you probably guess by now, the access to the ‘global Maze resource’ should be
protected via usage of mutex locks. Whether a thread is:
  
Updating
its discovery of the path to barrier / danger areas  OR
     
Accessing
the ‘global Maze resource’ to learn about the discovered locations of the
barriers / danger areas

Only 1 thread can access it
at any one time!
 J)   
Once
the program is completed and tested to be working successfully, you are highly
encouraged to add on “new features” to the program that you feel are applicable
to the task of finding the shortest path thru a maze. Additional marks may be
awarded subject to the relevancy and correctness of the new functionalities.

K)  
Your
program should be written in C++, and using the library functions available in
header file ‘pthread.h’, to handle all aspects of thread creation, management
and synchronization.

L)   
To
encourage good program design, you should consider using different *.cpp class files
to encapsulate groups of related methods/functions.

Additional Resources



    • After all students have gone through this
      document, your tutor will hold a special session to discuss / elaborate on
      the requirements of this assignment.






  • In
    addition, your tutor will hold a Q & A sessions to clarify any issues/doubts
    you may have on the analysis and design of this multi-threaded program. To
    ensure a fruitful session, all students must come prepared with their list
    of questions, so that everybody’s time is efficiently utilized.


Deliverables
1)           
The
deliverables include the following:
a)   
The
actual working shell program (hard+soft copies), with comments on each file,
function or block of code
to help the tutor understand its purpose.
b)   
A
word document (hard+soft copies) that elaborates on:
     
(Interpreted)
requirements of the program
      
Diagram
/ Illustrations of program design

·        
Summary
of implementation of each module in your program

·        
Reflections
on program development (e.g. assumptions made, difficulties faced, what could
have been done better, possible enhancements in future, what have you learnt,
etc)
c)   
A
program demo/evaluation during lab session. You must be prepared to perform
certain tasks / answer any questions posed by the tutor.
2)           
IMPT:
Please follow closely, to the submission
instructions in Appendix C, which contains details
about what to submit, file naming conventions, when to submit, where to submit,
etc.
3)           
The evaluation will be held during lab session where
you are supposed to submit your assignment. Some time will be allocated for you
to present / demonstrate your program during the session.
Grading
Student’s
deliverable will be graded according to the following criteria:
(i)           
Program
fulfills all the basic requirements stipulated by the assignment

The
requirements includes some/all of the following:
ability to handle maze of different sizes
No. of danger areas uncovered
     
No. of barriers uncovered
      
No. of threads utilized
Validity of the single solution path (a series of
Point locations leading from Start to End locations

(ii)         
Successful
demonstration of a working program, clarity of presentation and satisfactory
answers provided during Q & A session.

(iii)        
Additional
efforts in enhancing the program with features over and above task
requirements, impressive, “killer” presentation and demonstration, etc.

(iv)        
After
the submission of deliverables, students will be required undergo an evaluation
process (to determine fulfillment of task requirements.) Further instructions
will be given by the Tutor during the subsequent respective labs. Please pay
attention as failure to adhere to instructions 
may result in deduction of marks.

Tutor’s
note:

In
the real working world, satisfactory completion of your tasks is no longer
enough. The ability to add value, communicate and/or demonstrate
your ideas with clarity is just as important as correct functioning of your
program. The grading criteria is set to imitate such requirements on a ‘smaller
scale’.


APPENDIX A

(Sample contents for Maze
‘mazedata.txt’)

Length : 20

Breadth : 10

 

// ------------------------------

// ----- Start of Maze Data -----

// ------------------------------

// 'S' denotes Starting position 

// 'E' denotes Ending position

// '#' denotes Barrier

// 'X' denotes Danger Area

 

####################

#S #  #            #

#  # ##  ##  ###
###

#     #   #  
#  E #

## #  # X
#  X 
## #

#   X ###
#####    #

# #   #   # 
#   ###

# ### ### ## # #####

#  #               #

####################

 

 

 

 

 

 

 

 





 

APPENDIX B

 

(Output solution
stored in a generated text, based on the maze configuration in Appendix A)

 

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  #

 
1  #  S    
#        #                                      #

 
2  #        #    
#  #        # 
#        #  # 
#     #  #  #

 
3  #                 #           #           #        E    
#

 
4  #  #    
#        #     X    
#        X        # 
#     #

 
5  #           X    
#  #  #    
#  #  # 
#  #              #

 
6  #     #          
#           #        #           # 
#  #

 
7  #     #  #  #    
#  #  #    
#  #     #    
#  #  # 
#  #

 
8  #        #                                              
#

 
9  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  #

 

 

_length  : 20

_breadth : 10

 

_startLocation : [ 1, 1 ]

_endLocation   : [ 17, 3 ]

 

No. of paths discovered : 0

 

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0                                                           


 
1     S                                                     


 
2                                                            

 
3                                                    
E     

 
4                                                           


 
5                                                           


 
6                                                            

 
7                                                           


 
8                                                           


 
9                                                           


 

 

_length  : 20

_breadth : 10

 

_startLocation : [ 1, 1 ]

_endLocation   : [ 17, 3 ]

 

No. of paths discovered : 0

 

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  #

 
1  #  S    
#        #                                      #

 
2  #        #    
#  #        # 
#        #  # 
#     #  #  #

 
3  #                 #           #           #        E    
#

 
4  #  #    
#        #     X    
#        X        # 
#     #

 
5  #           X    
#  #  #    
#  #  # 
#  #              #

 
6  #     #          
#           #        #           # 
#  #

 
7  #     # 
#  #     # 
#  #     # 
#     #     # 
#  #  #  #

 
8  #        #                                              
#

 
9  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  #

 

Thread 'POOH' has been created !!

Total no. of steps : 1

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                     


 
1     S                                                      

 
2                                                           


 
3                                                    
E     

 
4                                                           


 
5                                                            

 
6                                                           


 
7                                                           


 
8                                                           


 
9                                                            

 

Total no. of steps : 1

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                     


 
1  #  S                                                     


 
2                                                            

 
3                                                    
E     

 
4                                                           


 
5                                                           


 
6                                                            

 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 2

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                     


 
1  #  S                                                     


 
2  #  1                                                  
   

 
3                                                    
E     

 
4                                                           


 
5                                                           


 
6                                                        
   

 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 3

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                     


 
1  #  S                                                     


 
2  #  1                                                     


 
3     2                                               E     

 
4     #                                                     


 
5                                                           


 
6                                                           


 
7                                                            

 
8                                                           


 
9                                                           


 

Total no. of steps : 3

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                      

 
1  #  S                                                     


 
2  #  1                                                     


 
3  #  2                                              
E     

 
4     #                                                      

 
5                                                           


 
6                                                           


 
7                                                           


 
8                                                            

 
9                                                           


 

Total no. of steps : 5

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #                                                      

 
1  #  S                                                     


 
2  #  1 
4  #                                               


 
3  #  2 
3                                            E     

 
4     #                                                      

 
5                                                           


 
6                                                           


 
7                                                           


 
8                                                            

 
9                                                           


 

Total no. of steps : 6

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S 
5                                                   

 
2  #  1 
4  #                                               


 
3  #  2 
3                                            E     

 
4     #                                                     


 
5                                                            

 
6                                                           


 
7                                                           


 
8                                                           


 
9                                                            

 

Total no. of steps : 6

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S 
5  #                                               


 
2  #  1 
4  #                                               


 
3  #  2 
3                                            E     

 
4     #                                                     


 
5                                                           


 
6                                                           


 
7                                                           


 
8                                                           


 
9                                                           


 

Thread 'POOH' hits a DEAD END
near [2, 1] !!

 

Thread 'TIGGER' has been created
!!

Thread 'ROO' has been created !!

 

===========================================================

 Elapsed Time : 0

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 1

Barriers Discovered    : 8

Danger Area Discovered : 0

 

 

Total no. of steps : 5

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4                                                  


 
5                                                           


 
6                                                           


 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 5

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                                

 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5                                   
                        

 
6                                                           


 
7                                                           


 
8                                                           


 
9                                   
                        

 

Total no. of steps : 6

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1     #                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5        5                                                  


 
6        #                                                   

 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 7

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                     
          

 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5     6  5                                                  


 
6        #                                                   

 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 7

 

     0 
1  2  3 
4  5  6  7  8  9 10
11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                  


 
6        #                                                  


 
7                                                            

 
8                                                           


 
9                                                           


 

Total no. of steps : 8

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7                                                           


 
8                                                           


 
9                                                           


 

Total no. of steps : 8

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                                

 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7                                                           


 
8                                      
                     

 
9                                                           


 

Total no. of steps : 9

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                                

 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                   

 
6  #  7 
#                                                  


 
7  #  8                                                     


 
8                                                           


 
9                                                            

 

Total no. of steps : 9

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                        
       

 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                   

 
6  #  7 
#                                                  


 
7  #  8 
#                                                  


 
8                                                           


 
9                                                    
       

 

Total no. of steps : 10

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                                

 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                  


 
6  #  7 
#                                                   

 
7  #  8 
#                                                  


 
8     9                                                     


 
9     #                                                     


 

Total no. of steps : 10

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                           
E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7  #  8 
#                                                  


 
8  #  9                                                     


 
9     #                                                     


 

Total no. of steps : 11

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7  #  8 
#                                                   

 
8  #  9 10                                                  


 
9     #                                                     


 

Total no. of steps : 11

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4  #                                                

 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7  #  8 
#                                                  


 
8  #  9 10   
                                               

 
9     #  #                                                  


 

Total no. of steps : 11

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                      
         

 
5  #  6 
5                                                  


 
6  #  7 
#                                                  


 
7  #  8 
#                                                  


 
8  #  9 10 
#                                      
         

 
9     #  #                                                  


 

Thread 'TIGGER' hits a DEAD END
near [2, 1] !!

 

 

===========================================================

 Elapsed Time : 1

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 2

Barriers Discovered    : 22

Danger Area Discovered : 0

 

 

Thread 'TIGGER' hits a DEAD END
near [2, 8] !!

 

 

===========================================================

 Elapsed Time : 2

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 3

Barriers Discovered    : 22

Danger Area Discovered : 0

 

 

Thread 'ROO' hits a DEAD END near
[2, 1] !!

 

 

===========================================================

 Elapsed Time : 3

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 4

Barriers Discovered    : 22

Danger Area Discovered : 0

 

 

Total no. of steps : 7

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                       
    E     

 
4     #  4 
#                                               


 
5  #     5 
6                                               


 
6  #     #                                                  


 
7  #     #                                                   

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 8

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                                

 
5  #     5 
6                                               


 
6  #     # 
7                                               


 
7  #     # 
#                                               


 
8  #        #                                                

 
9     #  #                                                  


 

Total no. of steps : 8

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #     5 
6                                               


 
6  #     # 
7                                               


 
7  #     # 
#                                               


 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 9

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                                

 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #     5 
6                                                

 
6  #     # 
7  8                                            

 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                   

 

Total no. of steps : 9

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1     #
                                               

 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #     5 
6  X                                            

 
6  #     #  7
 8                                            

 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                  


 

Thread 'TIGGER' stepped into
DANGER at [4, 5] !!

 

 

===========================================================

 Elapsed Time : 4

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 4

Barriers Discovered    : 26

Danger Area Discovered : 1

 

Thread 'TIGGER' is dead! It's
sacrifice shall not be in vain!

 

Creating new thread 'GOLPHER'

 

Thread 'GOLPHER' has been created
!!

 

Thread 'POOH' hits a DEAD END
near [2, 8] !!

 

 

===========================================================

 Elapsed Time : 5

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 5

Barriers Discovered    : 26

Danger Area Discovered : 1

 

 

Total no. of steps : 10

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                               


 
5  #     5 
6  X                                            

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                             

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 11

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#                                                

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        # 
                                              

 
9     #  #                                                  


 

Total no. of steps : 12

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                   

 
1  #  S    
#                                               


 
2  #  1    
#                                               


 
3  #  2 
3                                            E     

 
4     #  4 
#    11  #                                       

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                                

 
9     #  #                                                  


 

Total no. of steps : 13

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                                

 
2  #  1    
#     #                                         

 
3  #  2 
3       12                                   E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                       

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                   

 

Total no. of steps : 13

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1    
#     #                                         

 
3  #  2 
3       12  #                                E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9  #                                      

 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 15

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1     #
14  #                                          

 
3  #  2 
3    13 12  #                                E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                       

 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 15

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #                                                  


 
1  #  S    
#                                               


 
2  #  1     #
14  #                                         

 
3  #  2 
3    13 12 
#                               
E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     #  #  #                                            

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 16

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#                                            

 
1  #  S     #
15                                            


 
2  #  1     #
14  #                                         

 
3  #  2 
3    13 12  #                                E     


 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                             

 
8  #        #                                               


 
9     #  #                                                  


 

Total no. of steps : 16

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#                                             

 
1  #  S     #
15                                            


 
2  #  1     #
14  #                                         

 
3  #  2 
3    13 12  #                                E     

 
4     #  4 
#    11  #                                       

 
5  #     5 
6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                                

 
9     #  #                                                  


 

Total no. of steps : 17

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#  #                                         

  1  # 
S     # 15 16                                         

 
2  #  1     #
14  #                                         

 
3  #  2 
3    13 12  #                                E     

 
4     #  4 
#    11  #                                      

  5  #    
5  6  X 10  #                                      

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                               


  9     # 
#                                                  


 

Total no. of steps : 17

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#  #                                         

 
1  #  S     #
15 16                                          

 
2  #  1     #
14  #                                         

 
3  #  2 
3    13 12  #                                E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                       

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                   

 

Total no. of steps : 17

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#  #                                         

 
1  #  S     #
15 16  #                                      

 
2  #  1     # 14 
#                                         

 
3  #  2 
3    13 12  #                                E     

 
4     #  4 
#    11  #                                      

 
5  #     5 
6  X 10  #                                      

 
6  #     #  7 
8  9  #                                      

 
7  #     # 
#  #                                            

 
8  #        #                                           
Thread 'ROO' hits a DEAD END near [2, 8] !!

 

   

 
9     #  #                                                   

 

 

===========================================================

 Elapsed Time : 6

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 6

Barriers Discovered    : 38

Danger Area Discovered : 1

 

 

Thread 'ROO' hits a DEAD END near
[5, 1] !!

 

 

===========================================================

 Elapsed Time : 7

 Latest Update ...

===========================================================

 

Dead End Paths Found   : 7

Barriers Discovered    : 38

Danger Area Discovered : 1

 

 

Total no. of steps : 15

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

 
0     #  #    
#  #                                         

 
1  #  S    
#        #                                       

 
2  #  1    
#     #                                         

 
3  #  2 
3    13 12  #                                E     

 
4     #  4  # 14
11  #                                      

 
5  #     5 
6  X 10  #                                       

 
6  #     # 
7  8  9 
#                                      


 
7  #     # 
#  #                                            

 
8  #        #                                               


 
9     #  #                                                   

 

 

Note :





    • There are many pages of other intermediate
      output that is not feasible to show in this Appendix.






 





    • We are now skipping straight to the ending
      portion of the output.






 





    • Below output show the LAST FEW STEPS of the
      thread exploration leading to the discovery of a single, solution path
      from Start Location ‘S’ to End Location ‘E’ !!






 

 

 

Total no. of
steps : 51

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

  0    
#  #     # 
#     #  # 
#  #  # 
#  #  # 
#  #        

  1  # 
S     #        #   
23 24 25 26 33 34 35 36 37        


  2 
#  1     #    
#  #    22 
#  # 27 32  # 
#  # 38  # 
#  

  3 
#  2  3          
#    21 20  # 28 31    
# 40 39 50 49  #

  4    
#  4  #       
#       19  # 29 30      
41  #  # 48  #

  5  #    
5  6  X    
#  #  # 18 
#  #  #     #
42 45 46 47  #

  6 
#     #  7 
8  9  #      
17  #        #   
43 44  #  #  

  7 
#     #  #  #
10  # 
#  # 16  # 
#     #     # 
#  #  #  

  8 
#        #    11 12 13 14 15                             #

  9     # 
#     #  # 
#  #  # 
#  #  # 
#  #  # 
#  #  # 
#  

 

Thread 'ROO' just
found a solution! Well done!!

 

 

 

 

 

 

Finished Finding
a SAFE PATH !!

Printing
submitted maze solution ...

 

Printing solution
for Tan Ah Beng, id : 1001001

--------------------------------------------------------------------------------------------

 

Total no. of
steps : 50

 

     0 
1  2  3 
4  5  6 
7  8  9 10 11 12 13 14 15 16 17 18 19

  0    
#  #     # 
#     #  # 
#  #  # 
#  #  # 
#  #        

  1 
#  S     #       
#    23 24 25 26 33 34 35 36
37        

  2 
#  1     #    
#  #    22 
#  # 27 32  # 
#  # 38  # 
#  

  3 
#  2  3          
#    21 20  # 28 31    
# 40 39  E 49  #

  4    
#  4  #       
#       19  # 29 30      
41  #  # 48  #

  5 
#     5  6 
X     #  #  # 18  # 
#  #     # 42 45 46 47  #

  6 
#     #  7 
8  9  #      
17  #        #   
43 44  #  #  

  7 
#     #  #  #
10  # 
#  # 16  # 
#     #     # 
#  #  #  

  8 
#        #    11 12 13 14 15                             #

  9    
#  #     # 
#  #  #  #  # 
#  #  # 
#  #  # 
#  #  #  

 

Total no. of
Threads submitting info : 3

 

Duplicated Paths
(to Barriers)    submitted  : 155

Duplicated Paths
(to Danger Area) submitted  : 0

Total no. of
Barrier     ('#') discovered    : 90 out of 105 !!

Total no. of Danger
Area ('X') discovered    : 1 out of 3 !!

 

Printing Thread
Statistics !!

--------------------------------------------------------------------------------------------

 

Stats for Thread
ID : 3070360432

 

Found Solution
Path                        : No ...

 

UNIQUE     Path to barriers discovered     : 26

DUPLICATED Path
to barriers submitted      : 0

 

UNIQUE     Path to danger areas discovered : 1

DUPLICATED Path
to danger areas submitted  : 0

 

**********************************************************************

 

Stats for Thread
ID : 3061967728

 

Found Solution
Path                        : YES !!

 

UNIQUE     Path to barriers discovered     : 103

DUPLICATED Path
to barriers submitted      : 0

 

UNIQUE     Path to danger areas discovered : 0

DUPLICATED Path to
danger areas submitted  : 0

 

**********************************************************************

 

Stats for Thread
ID : 3078753136

 

Found Solution
Path                        : No ...

 

UNIQUE     Path to barriers discovered     : 22

DUPLICATED Path
to barriers submitted      : 0

 

UNIQUE     Path to danger areas discovered : 0

DUPLICATED Path
to danger areas submitted  : 0

 

**********************************************************************

 

 





 

APPENDIX C

 

Submission
Instructions  (V. IMPT!!)

 

 

1)   
Deliverables

 

a)    All submissions should be
in softcopy, unless otherwise instructed

 

b)    For the actual files to be
submitted, you typically need to include the following:

 

-       word document report (e.g. *.doc), save as MS Word 97-2003
format

 

-       the source file(s), (e.g. *.sh, *.c, *.h,
*.o, or *.cpp files)

 

-       the executable file,
compile into an executable file with *.exe

     
(e.g. Assn3.exe).  Note: this only applies to non-shell script assignments!

 

 

2)   
How to package

 

            Compress all your assignment files into a single zip file.
Please use the following naming             format
:

 

                           <FT/PT_Assn3_<Stud. No._<Name.zip

       

 

 

 

Example
:
 FT_Assn3_1234567_JohnDoeAnderson. zip

 

 

-          
<FT/PT Use “FT” for Full-Time student, “PT
if you are Part-Time
student

 

-          
Assn3 if you are submitting assignment 3, Assn1
if submitting assignment 1 etc.

 

-          
<Stud. No. refers to your UOW student
number (e.g. 1234567)

 

-          
<Name refers to your UOW
registered name (e.g. JohnDoeAnderson)

 

 

 

 





 

3)   
Where to submit

 

            Please email your single zip file to your tutor at :

 

            [email protected]            for FULL
TIME students













 




            (To be announced)                      for
PART TIME students

 

            In your email subject line,
type in the following information :

 

                        <FT/PT <assignment info
<student
number
and <name.











































 

 




            Example:

 

            To                   :           tutor's
email
(see above)

 

            Subject          :           FT Assn3
1234567
JohnDoeAnderson

 

 

            Note 1 :          The
timestamp shown on tutor’s email Inbox will be used to determine if the                              assignment
is late or not.

 

            Note 2 :          After email submission, your
mailbox’s  sent folder 
would have a                                         copy
(record) of your sent email, please do not delete
that copy !!  It could                                     be used to
prove your timely submission, in case the Tutor did not receive                                                 your
email!

 

 

4)   
When to submit

 

a)   
Ignore the instructions in b) and c), ONLY IF
your tutor/lecturer has already explicitly
informed
you of the submission date-time for the assignment, during
your lessons.
Otherwise, you are to follow the submission
instructions below strictly!

 

b)   
Please
refer to the following table on the different submission events and deadlines

 




Assignment


Email
Submisson to reach Tutor’s Inbox by :



Assignment
Evaluation (Tasks)



Email
Evaluation files by :





1


Night before Lab - 2(PT), 3(FT)


Lab 2(PT), 3(FT)


End of Lab 2(PT), 3(FT)




2


Night before Lab - 3(PT), 4(FT)


Lab 3(PT), 4(FT)


End of Lab 3(PT), 4(FT)




3


Night before Lab - 4(PT), 5(FT)


Lab 4(PT), 5(FT)


End of Lab 4(PT), 5(FT)




 
























 




Note: (PT) = Part Time Students, (FT)
= Full Time Students !

 





 

c)   
For example, for Full Time (FT) students submitting Assignment 3, if Lab 5
falls on 29 / 01 / 2014, then

 

-      
Email
your zip file to Tutor by 28 / 01 / 2014,
2359 hrs        (nite b4 Lab 5)

 

-      
Setup
your program for evaluation on 29 / 01 / 2014          (Lab 5)

 

-      
Finish
evaluation tasks, email files on 29 / 01
/ 2014         (end of Lab 5)

 

 

5)   
Please help by paying attention to the following …

 

 

          ! VERY IMPORTANT !

 

            PLEASE FOLLOW THE GUIDELINES IN ALL
ASSIGNMENT APPENDICES !!

 

            PLEASE FOLLOW THE SUBMISSION
INSTRUCTIONS FROM 1 TO 4 !!

 

            IF YOU ARE NOT SURE,

 

                        PLEASE CHECK WITH YOUR
TUTOR DURING LABS / LECTURES !

 

                        OR ...

 

                        PLEASE EMAIL YOUR
ENQUIRIES TO YOUR TUTOR !

 

 

    MARKS WILL BE DEDUCTED IF YOU FAIL TO FOLLOW INSTRUCTIONS
!!

 

 

            Example :

 

·     
Your
report document or zip file does not follow naming convention

·     
Your
email address does not include your name (i.e. cannot be used to identify
sender)

·     
You
have no email subject

 

·     
Wrong
naming or misleading information
given

(e.g. putting “Assn2” in email
subject, when you are submitting “Assn1”)

(e.g. naming “Assn1” in your zip file,
but inside contains Assn2 files )

 

·     
Your
submission cannot be downloaded and unzipped

·     
Your
report cannot be opened by Microsoft Word / Access

·     
Your
program cannot be re-compiled and/or executable file cannot run

 

 





 

6)   
Re-submission administration

 

            If for some reason, student needs to
re-submit their files, please adhere to the following             instructions carefully:

 

           

<Step
1

           

            Zip up for re-submission files
according to the following format :

 

   <FT/PT_Assn3_Resubmit_v1_<Stud. No. _<Name.zip

 

    Example :  FT _ Assn3_Resubmit_v1_1234567_JohnDoeAnderson. zip

 

-          
<FT/PT Use “FT” for Full-Time student, “PT
if you are Part-Time
student

 

-          
Assn3 if you are submitting assignment 3, Assn1
if submitting assignment 1 etc.

 

-          
Resubmit_v1 if this is your 1st  re-submission

 

-          
Resubmit_v2 if this is your 2nd re-submission

 

-          
<Stud. No. refers to your UOW student
number (e.g. 1234567)

 

-          
<Name refers to your UOW
registered name (e.g. JohnDoeAnderson)

 

-          
V. IMPT - To prevent Tutor’s Inbox from blowing up
in his face, each student is only allowed to re-submit twice, for each
assignment only!

 

   

<Step
2

 

            Please email your single zip file to your tutor's email
(refer to section 3) - Where to submit)

 

            In your email subject line,
type in the following information :

 

            <FT/PT
<assignment info 
<re-submission ver. <student number and <name














































 

 




            Example:

 

            To                   :
          tutor's email (refer to
section 3) - Where to submit)

 

            Subject          :           FT Assn3
Resubmit_v1 1234567 JohnDoeAnderson
Powered by