Purposes of this assignment

• To encourage you to explore some of the features of Scala
• To provide a bit of fun, for those of you that enjoy competition

General idea of the assignment

Write a program to read in and solve path-finding puzzles. A puzzle consists of an NxN array of integers, like this:

7	4	4	6	6	3	2	2	6	8
3	3	6	5	4	3	7	2	8	3
4	1	6	6	2	4	4	4	7	4
4	5	3	4	3	5	4	4	8	5
5	1	4	6	6	5	0	7	1	4
2	6	9	4	9	7	7	9	1	4
3	5	4	0	6	4	5	5	5	6
6	6	2	3	4	7	1	2	3	3
3	5	4	3	6	5	4	5	2	6
3	9	3	5	1	1	5	4	6	0

The problem is as follows: Starting in the upper left-hand corner (location (0)(0)), find a sequence of moves that takes you to the bottom right-hand corner (for an NxN array, this would be location (N-1)(N-1)). From each location in the array you may move left, right, up, or down; the number in the location tells you exactly how far to move.

For example, location (0)(0) contains a 7, so from there you must move exactly 7 squares, either to the right or down. You cannot move up or left, because that would take you outside the array.

To help you see the solution, the squares along the solution path have been colored orange. From 7 you move right to 2, down to 4, down to 5, up to 5, etc. The complete solution is
     ((0, 0), (0, 7), (2, 7), (6, 7), (1, 7), (1, 5), (1, 2),
      (7, 2), (7, 4), (7, 8), (4, 8), (5, 8), (5, 9), (9, 9))
That is,
     R D D U L L D R R U D R D

(Also, in the example, there are several squares from which you cannot move at all! Can you find them?)

Details

You may assume:

• The puzzle is square (not just rectangular).
• The number at (0)(0) is nonzero.
• There are no negative numbers in the puzzle.
• There is at least one solution.

You may not assume:

• There is any particular number in the goal location. (If you can get there, it's irrelevant what number it contains.)
• There are no zeros in the array. (There might be, and if you go there you are stuck.)
• There is a legal move from every location in the array. (The above array might contain a 20, for example.)
• There is only one solution. (In the case of multiple solutions, we will accept any correct solution.)
• There are no cycles.

You may not change the numbers in the array.

Notes

Use a JFileChooser to read in the puzzle. There is a chooseFile method in NewGrader.zip that you can use as a model.

The input file will consist of n lines, where each line represents a single row. Each line will contain n nonnegative integers, separated by single blanks, with no leading or trailing blanks.

Write your program to solve one puzzle and quit. Don't ask the user whether s/he wishes to solve additional puzzles.

You are not required to use a Scala Array; feel free to use a List or any other data structure that you prefer.

The solution should be printed out in one of the two formats shown above (your choice).

Hints

There are two basic ways to solve a problem of this type:

• Use backtracking. When you reach a location from which you cannot move, or which you have been to before, backtrack and try another direction.
• Use nondeterminism. At each choice point, go all possible ways, and keep track of all the paths that result. Stop exploring any path from which you cannot move, or which takes you to a previous location along this path.

Scoring 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.
• Comments are not counted. Please comment your program properly!
• Unit tests are not counted. If you provide any tests (this is not required), put them in a separate file, so that it is easy to avoid counting them.
• Tokens will be counted by the NewGrader.zip program (also linked to above).

When attempting this, I strongly recommend:

• Make it correct before you make it shorter.
• Make it clear before you make it shorter.
  

Grading

This assignment is a competition!

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.

Then your_score = 90 + (30 * min_length / your_length).

For example, if the shortest program is 1000 tokens long, and your program is 1200 tokens long, then your score would be
     90 + (30 * 1000/1200) = 90 + (30000/1200) = 90 + 25 = 115

and if your program is 3000 tokens long, then your score would be
     90 + (30 * 1000/3000) = 90 + (30000/3000) = 90 + 10 = 100

These numbers have been chosen so that you will receive less than 100 points only if your program is more than three times longer than the shortest program. Even if your program is six times longer, you will still get 95 points for it.

Winners

First place (shortest correct on-time program): will receive a bonus of 30 points. resulting in a total score of 150 points.

Second place will get a bonus of 20 points, in addition to the score calculated as above.

Third place will get a bonus of 10 points, in addition to the score calculated as above.

Other programs

As usual, you may request late days for this assignment. However, programs turned in after the due date will not be eligible for the competition, even if they do not receive a late penalty. Also, because it is the end of the semester, you may request a maximum of 2 late days.

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

Note: You are not allowed to use scala.tools.nsc (a Scala interpreter for programs represented as strings) or anything similar.

Due Date

Zip your Scala project and submit it via Canvas by 6am Wednesday, December 9. The latest you can submit to Canvas will be 6am Friday, December 11.