Solve a "jigsaw puzzle."
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:














All outside edges will be zero.
All nonedges will have a random positive integer between 1
and Int.MaxValue
, inclusive. The four edges of a piece will
be given in clockwise order, starting from any side; thus, a piece may be
in any of four orientations. If two pieces have edges with the same
nonzero number, you are guaranteed that those two pieces belong together;
no other edges in the puzzle will have this number.
Pieces are immutable; when solving the puzzle, 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 sidebyside or one above the other. For example, pink piece in the above example, although rotated 90°, is placed correctly. However, when the completed puzzle is printed, the pieces should be printed so that matching sides are adjacent. The above puzzle should be printed as follows:
+++++  000  000  000  000  000 143143 777777 298298 000  171  091  451  380 
+++++
 171  091  451  380  000 212212 317317 304304 000  188  167  155  441 
+++++
 188  167  155  441  000 667667 850850 240240 000  000  000  000  000 +++++
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:
class PuzzlePiece(val sides: List[Int])
.
The sides will be listed in clockwise order, starting with any side.
Thus they may be in any of four (not eight!) orientations.class JigsawPuzzle(firstPiece: PuzzlePiece, pieces:
Set[PuzzlePiece])
. The firstPiece
(which is also included in pieces
) will go in location (0)(0)
of the array; JigsawPuzzle
) def solve:
Arr
ay[Array[PuzzlePiece]]
.val ary =
Array.ofDim[PuzzlePiece](nRows, nColumns)
JigsawPuzzle
) def
printSolution(solution: Arr
ay[Array[PuzzlePiece]]):
Unit
.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.
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.
while
), integers, floating point numbers, single
punctuation marks (such as a bracket, [
),
multiplecharacter operators (such as +=
).
When attempting this, I strongly recommend:
The winner will score 150 points; runnersup may score as much as 120 points. Correct, ontime 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,
min_length
be the length (as defined above) of the
shortest completely correct program turned in by the due
dateyour_length
be the length of your programThen your_score
= max(75, 140  20 * (your_length / min_length))
.For example, if the shortest program is 1000 tokens long, and your
program is 1200 tokens long, then your score would be
max(75, 140  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, 140  20 * (3000/1000)) =
max(75, 140  20 * 3) = 80
Finally, the winner of the competition (shortest correct ontime program) will receive a bonus of 30 points. In the event of a tie, points will be distributed evenly.
Thus, grades for correct, ontime 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 has two known bugs, neither of which should affect the token counts in this assignment:
\"
quote characters are not
counted correctly.Note: You are not allowed to use scala.tools.nsc
(a Scala interpreter) or anything similar.