Reference no: EM132360785

Programming Languages Assignment -  Solving the Frogs and Toads problem in Scala

Introduction - This project provides (a minimal skeleton for) a Scala application to solve the [frogs and toads puzzle] and to generate an animation of the solution found. This puzzle was originally discussed in the book ["Winning Ways for your Mathematical Plays"] by E.R. Berlekamp, J.H. Conway, R.K. Guy.

Solving this problem - The purpose of this project is to construct and animate a solution to the frogs and toads puzzle for given numbers of frogs and toads. It is the case that this puzzle can always be solved for any starting numbers of frogs and toads.

Note: There is a subtle difference between writing an application to find a solution to a puzzle, if one exists, and constructing a mathematical proof that there must always exist a solution to that puzzle. These are certainly related activities but luckily for us, as programmers, the former is usually a little easier than the latter. We don't need to prove that the frogs and toads puzzle always has a solution, we just need to search for a solution to a specific instance of the puzzle.

Dom's solution to this problem works as follows:

A 'PuzzleState' object describes the positions of the frogs and toads (and the empty cell) at a specific point in time. The 'PuzzleState' object with all the frogs on the left and all the toads on the right is called the *initial state*. The 'PuzzleState' object with all the toads on the left and all the frogs on the right is called the *terminal state.

Define a recursive function with prototype.

We strongly encourage most people to implement a solution based upon the algorithm outlined in their submission for assignment. But if you are really confident, or you would just like to think more about how you might prove that this puzzle always has a solution, then you might want to ponder the following points.

Take a look at the animated images above and observe that they reveal a clear strategy for jumping frogs and toads past each other. Notice in particular that:

• As the solution unfolds the empty cell shuttles backwards and forwards, moving as far as possible in one direction before it doubles back in the other direction.
• Most of the moves are jumps, which propagate the empty cell from one side to the other.
• The only place that a slide occurs is once at the end of each shuttle, as a preparation for the shuttle back in the other direction.

Does this suggest a different strategy for constructing a solution to the frogs and toads problem to you? Can you implement that strategy in Scala?

One advantage of the algorithm we discussed above is that it is relatively easy to see that if there *is* a solution to the puzzle then that algorithm will find it. Why is that the case?

Can you show that an algorithm based on the shuttling observations above will also construct a solution if there is one? Can you use it to show that a solution always exists?

Attachment:- Programming Languages Assignment Files.rar