Assignment 2COMP9021, Session 2, 20181 General presentationYou will design and implement a program that will• analyse the various characteristics of a maze, represented by a particular coding of its basic con-stituents into numbers stored in a file whose contents is read, and• – either display those characteristics– or output some Latex code in a file, from which a pictorial representation of the maze can beproduced.The representation of the maze is based on a coding with the four digits 0, 1, 2 and 3 such that• 0 codes points that are connected to neither their right nor below neighbours• 1 codes points that are connected to their right neighbours but not to their below ones:• 2 codes points that are connected to their below neighbours but not to their right ones:• 3 codes points that are connected to both their right and below neighbours:A point that is connected to none of their left, right, above and below neighbours represents a pillar :Analysing the maze will allow you to also represent:• cul-de-sacs:• certain kinds of paths:2 Examples2.1 First exampleThe file named maze_1.txt has the following contents.11 0 2 2 1 2 3 03 2 2 1 2 0 2 23 0 1 1 3 1 0 02 0 3 0 0 1 2 03 2 2 0 1 2 3 21 0 0 1 1 0 0 0Here is a possible interaction:$ python3…>>> from maze import *>>> maze = Maze(‘maze_1.txt’)>>> maze.analyse()The maze has 12 gates.The maze has 8 sets of walls that are all connected.The maze has 2 inaccessible inner points.The maze has 4 accessible areas.The maze has 3 sets of accessible cul-de-sacs that are all connected.The maze has a unique entry-exit path with no intersection not to cul-de-sacs.>>> maze.display()The effect of executing maze.display() is to produce a file named maze_1.tex that can be given asargument to pdflatex to produce a file named maze_1.pdf that views as follows.22.2 Second exampleThe file named maze_2.txt has the following contents.022302120222222223111032301322130302312322232330001000100000Here is a possible interaction:$ python3…>>> from maze import *>>> maze = Maze(‘maze_2.txt’)>>> maze.analyse()The maze has 20 gates.The maze has 4 sets of walls that are all connected.The maze has 4 inaccessible inner points.The maze has 13 accessible areas.The maze has 11 sets of accessible cul-de-sacs that are all connected.The maze has 5 entry-exit paths with no intersections not to cul-de-sacs.>>> maze.display()The effect of executing maze.display() is to produce a file named maze_2.tex that can be given asargument to pdflatex to produce a file named maze_2.pdf that views as follows.32.3 Third exampleThe file named labyrinth.txt has the following contents.3111111113221122131202330230221122031021312231011120202212302301123022303130203122121212222031103222211031100211111101110Here is a possible interaction:$ python3…>>> from maze import *>>> maze = Maze(‘labyrinth.txt’)>>> maze.analyse()The maze has 2 gates.The maze has 2 sets of walls that are all connected.The maze has no inaccessible inner point.The maze has a unique accessible area.The maze has 8 sets of accessible cul-de-sacs that are all connected.The maze has a unique entry-exit path with no intersection not to cul-de-sacs.>>> maze.display()The effect of executing maze.display() is to produce a file named labyrinth.tex that can be given asargument to pdflatex to produce a file named labyrinth.pdf that views as follows.43 Detailed description3.1 InputThe input is expected to consist of ydim lines of xdim members of {0, 1, 2, 3}, where xdim and ydim are atleast equal to 2 and at most equal to 31 and 41, respectively, with possibly lines consisting of spaces onlythat will be ignored and with possibly spaces anywhere on the lines with digits. If n is the xth digit ofthe yth line with digits, with 0 ≤ x < xdim and 0 ≤ y < ydim , then• n is to be associated with a point situated x× 0.5 cm to the right and y × 0.5 cm below an origin,• n is to be connected to the point 0.5 cm to its right just in case n = 1 or n = 3, and• n is to be connected to the point 0.5 cm below itself just in case n = 2 or n = 3.The last digit on every line with digits cannot be equal to 1 or 3, and the digits on the last line withdigits cannot be equal to 2 or 3, which ensures that the input encodes a maze, that is, a grid of width(xdim − 1)× 0.5 cm and of height (ydim − 1)× 0.5 cm (hence of maximum width 15 cm and of maximumheight 20 cm), with possibly gaps on the sides and inside. A point not connected to any of its neighboursis thought of as a pillar; a point connected to at least one of its neighbours is thought of as part of a wall.We talk about inner point to refer to a point that lies (x+0.5)×0.5 cm to the right of and (y+0.5)×0.5cm below the origin with 0 ≤ x < xdim − 1 and 0 ≤ y < ydim − 1.3.2 OutputConsider executing from the Python prompt the statement from maze import * followed by the state-ment maze = Maze(some_filename). In case some_filename does not exist in the working directory,then Python will raise a FileNotFoundError exception, that does not need to be caught. Assume thatsome_filename does exist (in the working directory). If the input is incorrect in that it does not containonly digits in {0, 1, 2, 3} besides spaces, or in that it contains either too few or too many nonblank lines,or in that some nonblank lines contain too many or too few digits, or in that two of its nonblank linesdo not contain the same number of digits, then the effect of executing maze = Maze(some_filename)should be to generate a MazeError exception that readsTraceback (most recent call last):...maze.MazeError: Incorrect input.If the previous conditions hold but the further conditions spelled out above for the input to qualify asa maze (that is, the condition on the last digit on every line with digits and the condition on the digitson the last line) do not hold, then the effect of executing maze = Maze(some_filename) should be togenerate a MazeError exception that readsTraceback (most recent call last):5...maze.MazeError: Input does not represent a maze.If the input is correct and represents a maze, then executing maze = Maze(some_filename) should havethe effect of outputting a first line that reads one ofThe maze has no gate.The maze has a single gate.The maze has N gates.with N an appropriate integer at least equal to 2, a second line that reads one ofThe maze has no wall.The maze has walls that are all connected.The maze has N sets of walls that are all connected.with N an appropriate integer at least equal to 2, a third line that reads one ofThe maze has no inaccessible inner point.The maze has a unique inaccessible inner point.The maze has N inaccessible inner points.with N an appropriate integer at least equal to 2, a fourth line that reads one ofThe maze has no accessible area.The maze has a unique accessible area.The maze has N accessible areas.with N an appropriate integer at least equal to 2, a fifth line that reads one ofThe maze has no accessible cul-de-sac.The maze has accessible cul-de-sacs that are all connected.The maze has N sets of accessible cul-de-sacs that are all connected.with N an appropriate integer at least equal to 2, and a sixth line that reads one ofThe maze has no entry-exit path with no intersection not to cul-de-sacs.The maze has a unique entry-exit path with no intersection not to cul-de-sacs.The maze has N entry-exit paths with no intersections not to cul-de-sacs.with N an appropriate integer at least equal to 2.6• A gate is any pair of consecutive points on one of the four sides of the maze that are not connected.• An inaccessible inner point is an inner point that cannot be reached from any gate.• An accessible area is a maximal set of inner points that can all be accessed from the same gate (sothe number of accessible inner points is at most equal to the number of gates).• A set of accessible cul-de-sacs that are all connected is a maximal set S of connected inner pointsthat can all be accessed from the same gate g and such that for all points p in S, if p has beenaccessed from g for the first time, then either p is in a dead end or moving on without ever gettingback leads into a de ad end.• An entry-exit path with no intersections not to cul-de-sacs is a maximal set S of connected innerpoints that go from a gate to another (necessarily different) gate and such that for all points p inS, there is only one way to move on from p without getting back and without entering a cul-de-sac.Pay attention to the expected format, including spaces.If the input is correct and represents a maze, then executing maze = Maze(some_filename) followed bymaze.display() should have the effect of producing a file named some_filename.tex that can be givenas argument to pdflatex to generate a file named some_filename.pdf. The provided examples willshow you what some_filename.tex should contain.• Walls are drawn in blue. There is a command for every longest segment that is part of a wall.Horizontal segments are drawn starting with the topmost leftmost segment and finishing withthe bottommost rightmost segment. Then vertical segments are drawn starting with the topmostleftmost segment and finishing with the bottommost rightmost segment.• Pillars are drawn as green circles.• Inner points in accessible cul-de-sacs are drawn as red crosses.• The paths with no intersection not to cul-de-sacs are drawn as dashed yellow lines. There is acommand for every longest segment on such a path. Horizontal segments are drawn starting withthe topmost leftmost segment and finishing with the bottommost rightmost segment, with thosesegments that end at a gate sticking out by 0.25 cm. Then vertical segments are drawn startingwith the topmost leftmost segment and finishing with the bottommost rightmost segment, withthose segments that end at a gate sticking out by 0.25 cm.Pay attention to the expected format, including spaces and blank lines. Lines that start with % arecomments; there are 4 such lines, that have to be present even when there is no item to be displayed ofthe kind described by the comment. The output of your program redirected to a file will be comparedwith the expected output saved in a file (of a different name of course) using the diff command. Foryour program to pass the associated test, diff should silently exit, which requires that the contents ofboth files be absolutely identical, character for character, including spaces and blank lines. Check yourprogram on the provided examples using the associated .tex files, renaming them as they have the namesof the files expected to be generated by your program.74 Submission and assessment4.1 SubmissionYour program will be stored in a file which has to be named maze.py. Your code can be submittedmore than once on Ed; the last version and only the last version will be run, tested and marked. Yourassignment is due by October 28, 11:59pm.4.2 AssessmentThe automarking script will let each both assessed methods of your program run for 30 seconds. Stillyou should not take advantage of this and strive for a solution that gives an immediate output.Late assignments will be penalised: the mark for a late submission will be the minimum of the awardedmark and 10 minus the number of full and partial days that have elapsed from the due date.4.3 Reminder on plagiarism policyYou are permitted, indeed encouraged, to discuss ways to solve the assignment with other people. Suchdiscussions must be in terms of algorithms, not code. But you must implement the solution on yourown. Submissions are routinely scanned for similarities that occur when students copy and modify otherpeople’s work, or work very closely together on a single implementation. Severe penalties apply.8
