首页 > > 详细

代写CSCI 3136作业、代做C++编程语言作业、代写Programming课程作业、Java实验作业代做代写Python编程|帮做Java程序

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.
∗ 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:
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
a pure function of type decodeMaze :: ByteString -> Maybe Maze.
1 The computation of
a path should be achieved using a pure function of type findPath :: Maze -> Maybe Path.
After reading the input, your IO code should call these functions to decode the input and compute
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 understands
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.

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.
 

联系我们
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codehelp

联系我们 - QQ: 99515681 微信:codinghelp
© 2014 www.7daixie.com
程序代写网!