CIS 554 Scala 3: Path-Finding Puzzle
Fall 2015, David Matuszek

Purposes of this assignment

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:

You may not assume:

You may not change the numbers in the array.

Use Puzzle as the name of the object containing your main method. Use additional classes, objects, and methods as you see fit.

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:

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.

When attempting this, I strongly recommend:

Grading

This assignment is a competition!

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

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.