联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> C/C++编程C/C++编程

日期:2020-04-02 10:22

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:

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 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.

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


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp