程序代写代做代考 algorithm # Macquarie University, Department of Computing #

# Macquarie University, Department of Computing #

## COMP332 Programming Languages 2019 ##

## Assignment 1 ##

Due: 11am Wednesday 4 September (week 6)
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](https://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 ###

You should consult the [README file](README.md) of this project

### What you have to do ###

You can clone the skeleton SBT project for this assignment from its [BitBucket](https://bitbucket.org) repository at [https://bitbucket.org/dominicverity/comp332-frogs-and-toads](https://bitbucket.org/dominicverity/comp332-frogs-and-toads). This skeleton contains:

1. [Main.scala](src/main/scala/Main.scala) the driver module containing the `main()` entry point of the application. Also provides a utility function `runAnumation()` which takes a sequence of animation frames, given as an object of type `Seq[doodle.image.Image]`, and displays them as the frames of an animation in a window.

2. [FrogsAndToads.scala](src/main/scala/FrogsAndToads.scala) this is a skeleton module in which you should put your code to solve the frogs and toads game. It currently just contains stub code for an `AnimationState` class and a `solve()` function.

3. [FrogsAndToadsTests.scala](src/test/scala/FrogsAndToadsTests.scala) this is a skeleton module in which you should put your automated tests of the functions you’ve provided in the [FrogsAndToads.scala](src/main/scala/FrogsAndToads.scala) module.

Search for the `FIXME` comments to find places where you should put your solution code. Your task in this assignment is to:

* Complete the implementation of the `PuzzleState` class and its associated companion object. In particular you should:
* Add code to the `solve()` function to generate and return a solution to the frogs and toads puzzle, expressed as a sequence of `PuzzleState` objects.
* Add code to the `animate()` function to turn a solution generated by `solve()` into a sequence of images which can be displayed as an animation by the `runAnimation()` function.
* Add whatever auxiliary functions / methods are necessary for your solution.
* Add automated tests of the methods of the `PuzzleState` class, of your `solve()` method, and of your auxiliary functions to the `FrogsAndToadsTests` class in the tests module.

You should consult the comments in our code for more information about what these methods are expected to do and how they might be implemented.

In your solution you must:

1. Only use immutable values. So, for example, you should declare all of your variables as `val`s rather than `var`s.
2. You should demonstrate that you know how to use case classes and pattern matching, in particular your code should make use of the `match` expression.
3. Your `solve()` function should implement a **recursive** algorithm.

### Plot points from Dom’s solution ###

Here are a few things I did in my solution. You are welcome to follow these tips in your solution or to come up with a completely new architecture for your solution.

1. I added methods called `jumpFromLeft()`, `jumpFromRight()`, `slideFromLeft()` and `slideFromRight()` to the `PuzzleState` class, each of which returns an object of type `Option[PuzzleState]`. Each one of these checks to see if the given move can be legally executed when the game is in the `PuzzleState` it is called on. If that move is legal then the method returns a `Some` value wrapping the `PuzzleState` object obtained by executing that legal move, otherwise it returns `None`.
2. My `solve()` method only creates new `PuzzleState` objects by calling these methods on existing `PuzzleState` objects, in that way I know that it can only generate sequences of `PuzzleState` objects that do obey the rules of the puzzle.
3. I added a `toImage()` method to the `PuzzleState` class and to each of the `Cell` classes, in which I put the code to turn objects of those kinds into corresponding `Image`s. Maybe this requires all of those classes to implement some kind of `IntoImage` trait that declares the `toImage()` method.
4. While I was at it I also overrode the `toString` methods of these classes, so that I could easily print string representations of `PuzzleState` objects. This was particularly useful when I was debugging and testing my code.
5. My code used a bunch of methods from the `Option` and `Seq` classes, including `map()`, `flatMap()`, `getOrElse()`, `orElse()`, `zip()`, and `forall()`. You might want to checkout what these do and use them in your own code.

### A note about the Doodle library ###

In this assignment we are using the most recent version (9.4) of the [doodle SVG library](https://github.com/creativescala/doodle), rather than the older version (8.3) described in the [Creative Scala](https://www.creativescala.org/) book. We are doing this in order to be able to display our solutions as animations.

The parts of this library that involve the construction of `Image` objects are largely identical to the version of the library described in the book. The only difference I have noticed is that methods named things like `lineWidth()` and `lineColor()` have been renamed `strokeWidth()` and `strokeColor()`.

### Running and testing your code ###

The skeleton for this assignment is designed to be run from within the Scala [simple build tool (SBT)](https://www.scala-sbt.org/). To do this from the console run the command `sbt` from the root directory of the assignment project. After a few messages you should end up at the following prompt:

assignment1 0.1 2.12.8>

You can use the following _tasks_ to compile, run and test the code:

* `run` compiles and runs the application.
* `compile` compiles any modules that have been updated since the last compile operation.
* `test` compiles any updated modules and executes the automated tests. The are simply Scala modules which can be found in the [tests directory](src/test/scala).
* `console` compiles any updated modules and allows you to execute Scala code at a console.

The file [FrogsAndToadsTests.scala](src/test/scala/BTreeTests.scala) illustrates the basic infrastructure for writing automated tests using the [ScalaTest](http://www.scalatest.org/) framework. At the moment it contains a few very simple tests of the `PuzzleState` class, that you can use as templates for your own tests.

### Asking questions ###

We’ve tried to give you lots of pointers on how to complete this assignment, but we are sure there are plenty of things we have missed. So you are strongly encouraged to ask lots questions about this assignment on the COMP332 forum. So start the assignment early and when you get stuck post a question – all of these will be answered in detail. You can, of course, ask questions about this assignment in your tutorial class, your tutor will be happy to help you.

We will not, however, answer forum questions about this assignment after 6pm on Monday the 2nd of September 2019. So please don’t leave your questions to the last moment.

### What you must hand in and how ###

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.

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.

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 COMP332 iLearn website by the due date and time. Your report should be in PDF format.

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.



[Dominic Verity](http://orcid.org/0000-0002-4137-6982)
[Copyright (c) 2019 by Dominic Verity. Macquarie University. All rights reserved.](http://mozilla.org/MPL/2.0/)
Last modified: 11 August 2019