CIS 554 Scala 3: Jigsaw Puzzle
Fall 2013, David Matuszek

# Purpose of this assignment

• To encourage you to explore some of the features of Scala

# General idea of the assignment

Solve a "jigsaw puzzle."

# Details

Each piece in a typical jigsaw puzzle has four edges (left, right, top, bottom) and can fit with other pieces in only one way. Since it's hard to represent curved edges in a program, we will use random numbers to represent edge shapes. Two edges will fit together if they have the same number. Hence, our completed jigsaw puzzle will look something like this:

 000 000 143 171
 000 143 777 091
 000 777 298 451
 000 298 000 380
 171 000 212 188
 091 212 317 167
 317 155 451 304
 380 304 000 441
 188 000 667 000
 167 667 850 000
 155 850 240 000
 441 240 000 000

All outside edges will be zero.

All non-edges will have a number between 1 and 999, inclusive. If two pieces have edges with the same number (for example, `143` and `143`), you are guaranteed that those two pieces belong together; no other edges in the puzzle will have this number.

Pieces are immutable; the orientation of pieces is irrelevant. If, for example, two pieces each have a side 166, then those pieces may be placed adjacent to each other, either side-by-side or one above the other. For example, pink piece in the above example, although rotated 90°, is placed correctly.

## Specific requirements

We need to be able to run our unit tests on your program. That means we need to specify a bare minimum of classes and methods. You should have:

• A `class PuzzlePiece(val sides: List[Int])`. The sides will be listed in clockwise order, starting with any side.
• A `class JigsawPuzzle(pieces: Set[PuzzlePiece])`.
• A method (in `JigsawPuzzle`)` solve: Arr``ay[Array[PuzzlePiece]]`.
• Note: Syntax for creating such an array is `val ary = Array.ofDim[PuzzlePiece](nRows, nColumns) `

To allow us to test your program, the input parameters and output results must have the types shown. This is not intended to constrain your implementation to work with these types internally.

# General idea of the assignment

Clarity and conciseness are highly correlated. In other words, short programs are usually (but not always) easier to understand than long programs. Your goal should almost always be to write the clearest, most easily understandable program that you can.

This time is different.

This time the goal is to write the shortest program you can to solve the given problem, even at the expense of clarity.

• The length of the program will be the number of tokens in it. Example of tokens are: variable names, function names, keywords (such as `while`), integers, floating point numbers, single punctuation marks (such as a bracket,` [`), multiple-character operators (such as `+=`).
• A string counts as one token, regardless of length.
• An operator counts as one token, regardless of the number of characters in it.
• Unit tests are not counted. Unit test all non-I/O methods.

When attempting this, I strongly recommend:

• Use Test-Driven Development.
• Make it correct before you make it shorter.
• Make it clear before you make it shorter.

## This assignment is a competition

The winner will score 150 points; runners-up may score as much as 120 points. Correct, on-time programs longer than 3.25 times the length of the shortest program will receive 75 points.

Pay attention to the grading scheme, because it's unusual.

Among the completely correct programs turned in by the due date,

• Let `min_length` be the length (as defined above) of the shortest completely correct program turned in by the due date
• Let `your_length` be the length of your program
• Let `N` be a factor chosen by us (`20`, unless we have reason to change it)

Then `your_score = max(75, 100 + 2 * N - N * (your_length / min_length))`.

For example, if the shortest program is 1000 tokens long, and your program is 1200 tokens long, then (with N = 20), your score would be
`     max(75, 100 + 40 - 20 * (1200/1000)) = max(75, 140 - 20 * 1.2) = 116`
and if your program is 3000 tokens long, then your score would be
`     max(75, 100 + 40 - 20*(3000/1000)) = max(75, 140 - 20 * 3) = 80`

Finally, the winner of the competition (shortest correct on-time program) will receive a bonus of 30 points. In the event of a tie, points will be distributed evenly.

Thus, grades for correct, on-time programs may range from 75 to 120 points. A completely correct program, with no deductions for style or lateness, will be worth 75 points, regardless of length.

Programs that are late or not completely correct will be graded on the basis of 75 points (not 100), with the usual kinds of deductions for failed tests and lateness.

I am providing a project Tokenizer.zip that you can use to count tokens in your program. This program may be updated as circumstances warrent.

Note: You are not allowed to use `scala.tools.nsc` (a Scala interpreter) or anything similar.

# Due date

Your program is due before 6am November 20. Zip up the entire project and submit via Canvas.