Fall 2015, David Matuszek

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

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),
```

That is,

(7, 2), (7, 4), (7, 8), (4, 8), (5, 8),
(5, 9), (9, 9))

` 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?)

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.

`Puzzle`

as the name of the object containing your main
method. Use additional classes, objects, and methods as you see fit.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).

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.

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,**[**

).**+=** - 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.

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.

**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.

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.

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.
**