Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66

E C E 2071 C o m pu t e r O r g a n i sa t i on & P r og r a mm i ng

L a b V I a nd A ss i gn m e n t 2 : S o l v i ng M a z es w i t h t h e L ee A l go r i t h m

1 O b j ec t i ves

In this lab activity and assignment, we will learn how the fundamental data structures such as linked lists, queues and stacks can be used for solving some engineering problems.

2 I n t r odu c t i on

One application of computers is the study of algorithms. In this laboratory experiment and the associated assignment, an algorithm, the Lee Algorithm [ 1 , 3 ] for ﬁnd ing a path between two locations (called the source and target cells) in a maze is investigated. The Lee Algorithm guarantees to ﬁnd the shortest path – if it exists – between two points in a maze. It is an extremely eﬀective tool and is universally used, such as computer aided design of printed circuit board layouts.

Details of the Lee Algorithm are provided in Appendix A .

3 P r og r a mm i ng A ss i gn m e n t

Write a C program (called ece2071 asg2.c) that will implement the Lee Algorithm. Your program should

1. Accept, as a command line argument, the name of an ASCII text ﬁ le that describes the maze. Each row of the maze is stored as a single line consisting of ‘#’ or ‘ . ’ characters. In addition, somewhere in the ﬁ le one ‘S’ and one ‘T ’ representing the start and target

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

# . . . # . . . . . . #

. . # . # . # # # # . #

# # # . # . . . . # . #

# . T . . # # # . # . .

# # # # . # . # . # . #

# . . # . # . # . # . #

# # . # . # . # . # . #

# . . . . . S . . # . #

# # # # # # . # # # . #

# . . . . . . # . . . #

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

Figure 1: A maze of 12 by 12 cells. The source cell coordinates are (9,7) and the target cell is at (5,3).

points of the path to be discovered by the algorithm (See Figure 1 , which is the same maze we used in our maze solver laboratory experiment).

2. Print, upon completion:

❼ if it ﬁnds a path from the source to target, it should print a trace of the path as

a sequence of matrix coordinates separated by space characters. For example, if we run the program of the maze shown in Figure 1 , it should print the following sequence:

5,3 5,4 5,5 6,5 7,5 8,5 9,5 9,6 9,7

❼ if no path is found, it should print the following message

No path found.

You are not allowed to use global or static arrays. Starting from the source, cells to be visited should be placed in a queue (of which elements are dynamically allocated) and solution path (if ever exists) should be placed in a dynamically allocated stack as explained in Chapters 12.5 and 12.6 of [2].

Note that your program needs to discover the dimensions of the maze by itself (but you can safely assume that we will be dealing with square mazes).

Rename your program as ece2071 asg2.c, and submit as a single .c ﬁle containing only ASCII text characters (no other formats will be accepted). Do not submit any other ﬁles. Please read carefully the submission rules and marking procedure provided in Appendix B .

A T h e L ee A l go r i t h m

Consider the maze conﬁguration shown in Figure 1 . So, as before, we represent the maze as a grid of dots ( .) and hashes (#). The hashes represent the walls of the maze and the dots represent cells in the possible paths through the maze. Moves can only be made to the left, right, up or down from the current location, 1 cell at a time, and diagonal moves are not allowed. Naturally, if a cell contains a #, it cannot be moved into. The cells labelled with the characters ‘S’ and ‘T ’ are the source and target cells respectively.

# # # # # # # # # # # # # . . . # . . . . . . # . . # . # . # # # # . # # # # . # . . . . # . # # . T . . # # # . # . . # # # # . # . # . # . # # . . # . # . # . # . # # # . # . # 1 # . # . # # . . . . 1 S 1 . # . # # # # # # # 1 # # # . # # . . . . . . # . . . # # # # # # # # # # # # #

(a)

# # # # # # # # # # # # # . . . # . . . . . . # . . # . # . # # # # . # # # # 8 # . . 8 7 # . # # . T 7 6 # # # 6 # . . # # # # 5 # 3 # 5 # . # # 7 6 # 4 # 2 # 4 # . # # # 5 # 3 # 1 # 3 # . # # 5 4 3 2 1 S 1 2 # . # # # # # # # 1 # # # . # # 7 6 5 4 3 2 # . . . # # # # # # # # # # # # #

(b)

# # # # # # # # # # # # # . . . # . . . . . . # . . # . # . # # # # . # # # # . # . . . . # . # # . T 7 6 # # # . # . . # # # # 5 # . # . # . # # . . # 4 # . # . # . # # # . # 3 # . # . # . # # . . . 2 1 S . . # . # # # # # # # 1 # # # . # # . . . . . . # . . . # # # # # # # # # # # # #

(c)

Figure 2: Diagrams that sketch the operation of the Lee algorithm while ﬁ nding the shortest possible path between a source and a target cell: (a) First wavefront generated by the Lee Algorithm. (b) Waveform propagation from the source cell to the target cell. (c) A path connecting the source and target cells.

To ﬁnd a path starting from ‘S’ to ‘T ’, empty cells adjacent to the source are ﬁrst labelled 1, indicating the cost of reaching these cells from the source. This is shown in Figure 2 (a).

Next, a cost of 2 is placed in each empty cell adjacent to cells labelled 1, and so on. Thus, a diamond shaped expanding wavefront of increasing numbers propagates until the target cell is reached or there are no remaining empty cells adjacent to any of the labelled cells. Figure 2 (b) illustrates the complete waveform propagation.

If the target cell has been reached, the algorithm backtracks from the target, moving at each step to any cell with a lower cost. Figure 2 (c) shows the algorithm with a backtrack path. Note that, quite often there will be alternative choices for the backtrack path.

B S ub m i ss i on R u l es a nd M a r k i ng P r o ce du r e

Please read carefully the following submission rules and marking procedure. They will be strictly applied:

1. This is a single person activity. Group submissions will not be accepted. Do not share your code with anybody, and do not use someone else’s code. Please read carefully Monash University’s information pages about academic integrity, plagiarism and collu- sion1 .

2. We will compile your program on a Windows 10 command window by using the following command:

gcc -std=c17 -pedantic -Werror ece2071_asg2.c -o ece2071_asg2 -lm If no executable ﬁle is generated, we will send you the error output, and invite you to re-submit. But, if you decide to re-submit, we will consider the submission as late, and

consequently you will l o se a t l eas t 50 % o f t h e a ll o ca t e d m a r k .

Therefore, before submitting, make sure that your program compiles with the above command in a Windows 10 machine command window of one of our department’s laboratory computers.

3. Do not use any non-standard libraries. Our system will not have them, and your program will inevitably fail if you use any non-standard libraries.

4. Similarly, do not include any non-standard header (“.h”) ﬁles.

5. We will run the generated executable ﬁle with the following command: ece2071_asg2 <mazefilename>

where “ mazefilename” will be one of our test maze ﬁles. They will be of increasing dimensions (there will be at least one huge maze). Note that our Windows 10 machine has 16 GB of memory, so be careful about the memory usage limits of your program.

If your program produces the expected output in a reasonable time for each maze ﬁle (the hard-limit is 10 minutes, if your program gets stuck in an inﬁnite loop, the system will terminate it after 10 minutes) you will get at least 60% of the allocated mark.

We will then rank all the successful programs from shortest run time to the longest. Fastest 25% of the programs will get the full remaining 40%, second fastest group of 25% will get an extra 30%, third fastest group of 25% will receive 20% and ﬁnal 25% will get an extra 10%.

6. If your program crashes when we run, we will examine the program and its output, and assign a mark between 20% and 60%. If no useful output is generated, we will examine the source code and assign a mark between 0% and 20%.