Project 1
CSCI 3136: Principles of Programming Languages
Due February 17, 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 Haskell program to solve the following problem: 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.
∗ Theupperbitis1ifandonlyifthecellisnotinthebottomrowandthereisawall 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 Haskell 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.)
• Apart from the code needed to parse command line arguments, read the input, and write the output, your solution should be implemented purely functionally. Specifically, you should define an appropriate type Maze representing a maze and an appropriate type Path representing a path through the maze. The conversion of the binary input file into a Maze should be achieved using apurefunctionoftypedecodeMaze :: ByteString -> Maybe Maze.1 Thecomputationof apathshouldbeachievedusingapurefunctionoftypefindPath :: Maze -> Maybe Path. After reading the input, your IO code should call these functions to decode the input and com- pute the path.
1Use Hoogle to find out about the ByteString type, which is the type you should use to represent binary data. The Data.ByteString module also offers I/O actions that can be used to read binary data from disk.
2
The functions have Maybe return types because the input may not be a valid maze file meeting the expectations above. Thus, it is possible that the decoding process fails. Even if it succeeds, the decoded maze may not have a path from the start to the end. In these cases, the functions should fail by returning Nothing.2
The type signatures of decodeMaze and findPath prevent them from using IO actions. They do not prevent them from using the ST monad in their implementations. Do not use the ST monad. If you think it is helpful, you are allowed to use the State monad, Maybe monad, and other monads that are nothing more than devices to structure purely functional code more conveniently. (My sample solution uses the list monad, which I mentioned in the lab notes but did not discuss in detail. You do not need the list monad, but it makes things just a tiny bit cleaner.)
• Your program should run in linear time in the size of the maze, that is, in the number of cells in the maze.
Tools to Help You
If you add /users/faculty/nzeh/.local/bin to your shell’s search path on bluenose, 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.
2There is a third failure possibility, namely that the maze contains cycles. Dealing with this possibility is much harder, so we ignore it here.
3
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: Can I provide these programs for you to install on your computer so you can use them on your computer instead of on bluenose? No. For example, writing the I/O code that reads and decodes the maze is part of your project and printMaze, verifyPath, and solveMaze all need to accomplish this task. This is why I grant you access to the executables on bluenose but I do not provide the source code.
4