Project 2
CSCI 3136: Principles of Programming Languages
Due April 6, 2020
Assignments are due on the due date by 23:59 AST. Since this is a programming assignment, this cover page does not need to be submitted. Plagiarism in assignment answers will not be tolerated. By submitting their answers to this assignment, the authors named above declare that its content is their original work and that they did not use any sources for its preparation other than the class notes, the textbook, and ones explicitly acknowledged in the answers. Any suspected act of plagiarism will be reported to the Faculty’s Academic Integrity Officer and possibly to the Senate Discipline Committee. The penalty for academic dishonesty may range from failing the course to expulsion from the university, in accordance with Dalhousie University’s regulations regarding academic integrity.
Problem Description
In this project, you will write a simple Prolog program to solve the same problem as in the Haskell project: You are given a maze of h × w cells and you are to find a path from the top-left cell to the bottom-right cell. The input specifies whether there’s a wall between adjacent cells. The path must not cross any walls and must not visit any cell more than once. The following is an example:
In general, the maze is not necessarily square. However, the maze is connected and contains no cycles. In particular, there always exists a path from the start cell to the end cell and there is exactly one such path that does not visit any cell more than once. Thus, depth-first search or breadth-first search is an appropriate search strategy to find the path. Since there are no cycles in the maze, any path you follow has no way to double back on itself if you don’t immediately go back to the cell you just came from. This simplifies the search process significantly because you do not need to keep track of the complete list of cells you have already visited.
The input to your program is given as a binary file in the following format:
• The first four bytes store the height of the maze as a little-endian integer, that is, the bytes of this 4-byte integer are stored in the order from least significant byte to most significant byte.
• The next four bytes store the width of the maze as a little-endian integer.
• The remaining bytes represent the walls between cells:
– The outside walls of the maze are always present and thus are not represented as part of the input.
– Any inside wall of the maze is between two cells of the maze and thus has a cell to its left (for a vertical wall) or a cell above it (for a horizontal wall). Thus, we store two bits for every cell:
The lower bit is 1 if and only if the cell is not in the rightmost column and there is a wall to its right.
The upper bit is 1 if and only if the cell is not in the bottom row and there is a wall below it.
We number the bytes encoding the cells in order, starting from 0, and use these byte numbers to number the bits. For each byte, let its least significant bit be bit 0 and its most significant bit be bit 7. Then the jth bit in the ith byte has number 8i + j.
1
If the maze has height h and width w, then the two bits representing the cell in row r and column c are the bits with numbers 2(rw + c) and 2(rw + c) + 1. Row and column numbers also count from 0.
As an example, the file encoding the maze above has the content
05 00 00 00 05 00 00 00 30 1C 4B C9 86 00 00,
where the byte values are written in hexadecimal format here.
Your program should read and decode this binary input, compute a path through the maze, and
output the path it computes to a file. The output should list the visited cells in order with one cell per line. Each cell should be represented by two integers. The first one is the row of the cell, counting from top to bottom, starting with zero; the second one is the column of the cell, counting from left to right, starting with zero. The output for the maze above thus looks like this:
00 01 11 21 31 32 42 43 44
Note that the output file should be a plain text file, not a binary file.
Your Task
• Write a Prolog program to be run from the command line. It takes two arguments: the name of the maze file to be read and the name of the file to write the solution to. Your program should find a path through the maze given in the input file as specified in the problem description and write the result to the file given as the output file.
• You may assume that the input file to be read is small enough to be read into memory in its entirety. (If that’s not the case, you have much bigger problems because the program-internal representation of the maze is likely much bigger than the compact representation in the input file.)
• Your program should run in linear time in the size of the maze, that is, in the number of cells in the maze.
Some Notes
Do not let yourself be fooled by the fact that the input is binary. If you open the file to be read as a binary file as discussed in one of the labs, you can then use phrase_from_stream to parse the binary input using a definite clause grammar. This should make reading the input relatively easy. Similarly, for printing the output, write, writeln and nl should be enough.
2
Given that the maze does not contain any cycles, the same logic used by the Haskell function to find the path works also for the Prolog predicate to find the path. The basic idea is that you can define a path inductively: If you’re already at the exit cell, the path from the current cell to the exit simply consists of the current cell. Otherwise, it must start with the current cell and the remainder must be a path to the exit starting at one of the current cell’s neighbours that is not separated from the current cell by a wall.
Tools to Help You
These are the same support programs that you used for the Haskell lab to generate mazes, print them to your screen, and verify the correctness of the output produced by your program.
If you add /users/faculty/nzeh/.local/bin to your shell’s search path on bluenose or timberlea, you gain access to four programs:
genMaze: This program can be used to generate random mazes to test your code on. Start with small mazes until you are sure that your code works correctly. Once your code is correct, test its efficiency on 1, 000 × 1, 000 mazes. Your code should take only a few seconds on such inputs. (My code runs in a little of 2s.) If it takes longer, it is likely not a linear-time solution. (The generator takes O(n lg n) time and takes close to a minute to generate a 1, 000 × 1, 000 maze on bluenose, so be patentient with your data generation once you’re ready to test your code on such large mazes.)
printMaze: This program may be helpful for you to visualize the input. Given a maze file, it prints it to stdout in human-readable format. Note that you should not use this program on large mazes for obvious reasons. If you pass an optional path file (presumably produced by your solver), it will show the path in the visualization of the maze.
Also note that for this output to look reasonable, you need to ensure that your terminal under- stands UTF-8 (and that you are using a fairly complete UTF-8 font). For any reasonably modern Linux system or for a Mac, this should be the case. I suspect things should also work fine if you use PuTTY to connect to bluenose from a Windows box, but I was not able to test this because I do not own a Windows computer.
verifyPath: Given a maze file and a text file representing a path through the maze, this program tests whether the given path is indeed a valid path through the maze. If not, it will indicate the errors it finds.
solveMaze: This is a sample implementation of the program you are expected to write, only the command line arguments are slightly different.
Which brings me to the question of how you can find out about how to run these four programs. All four programs accept a -h or –help option. If you run, for example, genMaze –help, you see the list of command line arguments that genMaze accepts. This should be all you need to run these programs.
Final note: Now that the Haskell project’s due date is past, you are free to download the source code of these helper programs and compile it for your laptop using stack if you prefer to work on your laptop. To do so, find the maze.tar.gz file in the Assignment Solutions module on Brightspace. Note, however, that your code must work on bluenose or timberlea.
3