- August 14, 2020
Macquarie University Dept of Computing COMP3000 Programming Languages 2020 Assignment 1 – Snake Due: see submission page Worth: 10% of unit assessment Marks breakdown: Code: 50% (of which tests are worth 10%) Report: 50% (of which test description is worth 10%) Submit a notice of disruption via ask.mq.edu.au if you are unable to submit on time for medical or other legitimate reasons. Late penalty without proper justification: 20% of the full marks for the assessment per day or part thereof late. Overview The assignment code bundle provides a Scala skeleton program for solving the “snake” puzzle. The snake is a sequence of 27 wooden cubes strung along a piece of string that runs through them. The aim of the puzzle is to arrange the snake so that it forms a 3x3x3 cube. Other than the two end cubes, each other cube either has the string: passing through two opposite faces; or passing through two adjacent faces A cube that has the string passing through two adjacent faces can be rotated into any of four positions (90 degrees apart) that will determine which direction the next segment heads in. Technical description We will refer to cube positions using an X-Y-Z coordinate system that will also correspond to indexing a 3D array. The cube in the bottom corner closest to us is at position (0, 0, 0) and the farthest corner on the top layer is at (2, 2, 2). We will refer to directions using (as defined in the Scala program): XPos – moving along the X-axis in the positive direction XNeg – moving along the X-axis in the negative direction YPos – moving along the Y-axis in the positive direction YNeg – moving along the Y-axis in the negative direction ZPos – moving along the Z-axis in the positive direction ZNeg – moving along the Z-axis in the negative direction A snake will be specified by the length of its segments, not including the last cube of the previous segment. In this way, the sum of the segment lengths will always be 27 (= 3 x 3 x 3). In the picture at right, we can see that the first segment has 3 cubes. The next looks like it might have 2 cubes but we have to exclude the last cube of the first segment; so the second segment has just one cube. Etc. A solution to the puzzle will specify: the position of the first cube (in the 3D coordinate space) a list of directions For example, if we wanted to describe the start of the snake in the picture at right, then we can see that the start position is (0, 0, 0). The first few directions are: YPos (going from (0, 0, 0) to (0, 2, 0)) ZPos (going from (0, 2, 0) to (0, 2, 2)) XPos (going from (0, 2, 2) to (2, 2, 2)) ZNeg (going from (2, 2, 2) to (2, 2, 0)) (then it wanders out of the 3x3x3 cube) Note that the snake isn’t required to start from (0, 0, 0). Your task will be to find all solutions for a given snake. To prevent symmetrical solutions, we have the following restrictions: the start position (x, y, z) must have y < 2 and z = 0 the first direction must be XPos (so the picture above has an invalid first direction) the second direction must be YPos What you have to do The skeleton code bundle contains: Main.scala (in src/main/scala); no changes required to this (although you may what to do some informal testing from the main function Snake.scala (in src/main/scala); flesh out the skeleton functions here SnakeTests.scala (in src/test/scala); add your test cases here (in this file, not a separate file) The Scala program The skeleton code bundle includes the functions and data structures you will need to solve the puzzle (in Snake.scala). The directions are defined with the names as above. A snake is specified as a list of integers. The one corresponding to the picture above with segment numbers is: val snake = List(3, 1, 1, 2, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 2, 2) The state of the cube is represented by the CubeState class: sealed abstract class CubeState case class StartState(segments: List[Int], start: (Int,Int,Int)) extends CubeState case class OtherState(segments: List[Int], occupied:Set[(Int,Int,Int)], end: (Int,Int,Int), dir: Direction, numMoves: Int) extends CubeState The StartState is used before anything has been put into the 3x3x3 cube. It contains: the list of segment lengths in the snake the start position in the cube for the snake Note that an X-Y-Z position can be directly represented in Scala as a 3-tuple (x, y, z) which has type (Int,Int,Int). The OtherState is used for any cube state after the first move (i.e. positioning of the first snake segment). It contains: the segments of the snake (all of them, not just the ones still to be used) what parts of the cube are occupied the end position of the last move so far the direction of that last move the number of moves so far (i.e. how many snake segments have been placed) Each “move” corresponds to the placing of each snake segment in the cube. (Segments are placed in the cube in the order they appear in the snake.) The occupation of the cube could have been represented by a three-dimensional array of Boolean values (true = occupied, false = unoccupied). Instead we have a set of positions (3-tuples). If a position is in the set then that position in the cube is occupied; otherwise not occupied. The top-level function for finding all the solutions is: def solveSnake(segments: List[Int]): List[((Int,Int,Int), List[Direction])] It takes a snake segment list and returns a list of solutions. A single solution has the form: ((Int,Int,Int), List[Direction]) It is a 2-tuple where the first part is the start position of the snake and the second part is the list of directions for the segments. This function will try all possible first moves (subject to the symmetry restrictions) and it will pursue the valid ones. The function tryMove is used to determine whether a specific move (a direction) can be applied to the current state of the cube: def tryMove(state: CubeState, move: Direction): Option[CubeState] As can be seen, the function either returns the next cube state, indicating the move was valid, or it fails. The solveSnake function relies on the function getSolutions to recursively look for solutions: def getSolutions(state: CubeState): Option[List[List[Direction]]] This function will see what directions are possible for the current state and try them (tryMove) and recurse . It returns either returns failure or a list of solutions from the current state. There are some useful helper functions … def getPossibleDirections(state: CubeState): List[Direction] This produces a list of possible directions that can be used in the current state. Note that this function must: rely on only the state’s direction and numMoves fields order the directions in the order they are listed in the definition of class Direction (to allow for predictable marking) def prependDir(dir: Direction, solutions: List[List[Direction]]): List[List[Di rection]] This takes a list of lists of directions and puts the specified direction at the font of each of the lists. def prependStart(xyz: (Int,Int,Int), solutions: List[List[Direction]]): List[((Int,Int,Int), List[Direction] )] This takes a list of lists of directions and turns each of the lists into a 2-tuple where: the first part is the specified position (xyz) the second part is the original list def getIncrement(dir: Direction):(Int,Int,Int) This function takes a direction and produces a 3-tuple that says how to increment x, y and z when moving in that direction. Functional programming While the aim of the programming is to solve the puzzle, you will also be assessed on how well your program is written in the style of functional programming. For example: use val instead of var for variable declarations avoid iterative loops (for/while); use map, filter, reduce, … if you have to use a FOR loop, consider using: for(…) yield … use match instead of multiple IFs Running the program The skeleton for this assignment is designed to be run from within sbt. In the command prompt for sbt, there are three relevant commands: test – runs the test suite (tests are in src/test/scala/SnakeTests.scala run – executes the main function in src/main/scala/Main.scala compile – compiles any changed source files; there is no need to separately compile because the run and test command always do any required compilation Testing Testing accounts for 20% of the assignment’s marks, 10% for the test cases you write and 10% for your report of the testing (mainly focusing on why you have added your test cases). Your test cases should be added at the end of src/test/scala/SnakeTests.scala after the FIXME comment. You will see that there are functions for inputting and displaying the cube: see show and toSet. These rely on visualising the cube as three layers (z=0, z=1, z=2): and using 1=occupied and 0=not occupied. What you must hand in and how 1. A zip file containing all of the code for your project and a type-written report. Submit every source and build file that is needed to build your program from source, including files in the skeleton that you have not changed. Do not add any new files or include multiple versions of your files. Do not include any libraries or generated files (run the sbt "clean" command before you zip your project). We will compile all of the files that you submit using sbt, so you should avoid any other build mechanisms. 2. Your submission should include all of the tests that you have used to make sure that your program is working correctly. Note that just testing one or two simple cases is not enough for many marks. You should test as comprehensively as you can. 3. Your report should describe how you have achieved the goals of the assignment. Do not neglect the report since it is worth 50% of the marks for the assignment. Your report should contain the following sections: A title page or heading that gives the assignment details, your name and student number. A brief introduction that summarises the aim of the assignment and the structure of the rest of the report. A description of the design and implementation work that you have done to achieve the goals of the assignment. Listing some code fragments may be useful to illustrate your description, but don't give a long listing. Leaving out obvious stuff is OK, as long as what you have done is clear. A good rule of thumb is to include enough detail to allow a fellow student to understand it if they are at the stage you were at when you started work on the assignment. A description of the testing that you carried out. You should demonstrate that you have used a properly representative set of test cases to be confident that you have covered all the bases. Include details of the tests that you used and the rationale behind why they were chosen. Do not just print the tests out without explanation. Submit your code and report electronically as a single zip file called ass1.zip using the appropriate submission link on the COMP3000 iLearn website by the due date and time. Your report should be in PDF format and should sit in the top directory of project (where build.sbt sits). DO NOT SUBMIT YOUR ASSIGNMENT OR DOCUMENTATION IN ANY OTHER FORMAT THAN ZIP and PDF, RESPECTIVELY. Use of any other format slows down the marking and may result in a mark deduction. Marking The assignment will be assessed according to the assessment standards for the unit learning outcomes. Marks will be allocated equally to the code and to the report. Your code will be assessed for correctness and quality with respect to the assignment description. Marking of the report will assess the clarity and accuracy of your description and the adequacy of your testing. 20% of the marks for the assignment will be allocated to testing.