The follow is done in Scheme Pretty big language

HW5Scheme2

The Problem - The Jugs

In the movie "Die Hard 3", Bruce Willis and Samuel L. Jackson were confronted with the following puzzle. They were given a 3-gallon jug and a 5-gallon jug and were asked to fill the 5-gallon jug with exactly 4 gallons. This problem generalizes that puzzle. You are given two jugs, A and B, and an infinite supply of water. There are three types of actions that you can take: (1) you can fill a jug, (2) you can empty a jug, and (3) you can pour from one jug to the other. Pouring from one jug to the other stops when either the first jug is empty or the second jug is full, whichever comes first. For example, if A has 5 gallons and B has 6 gallons and a capacity of 8, then pouring from A to B leaves B full and 3 gallons in A.

Functions in supporting roles 

Define six procedures that perform the basic operations of the two jugs, as described below:

• Fill-A – fill Jug A,

ex., (Fill-A ‘(0 2 5 3)) à (5 2 5 3)

• Fill-B
• Empty-A

Ex., (Empty-A ‘(3 2 5 3)) à (0 2 5 3)

• Empty-B
• A-to-B – pour everything from A to B until either A is empty or B is full, whichever comes first

Ex.,

(A-to-B '(5 2 5 3)) à (4 3 5 3) ;; A is not necessarily empty after this action

(A-to-B '(2 0 5 3)) à (0 2 5 3) ;; B is not necessarily full

• B-to-A

Be sure to name your function exactly as specified.

Breadth-first Search

Write scheme functions that uses breadth-first search to solve the jugs problem. The breadth-first search examples discussed in class (ex., FWGC), could be a good starting point. Note that the main procedure will be named Jugs which takes 3 arguments: Size-A, Size-B, Goal, where Size-A and Size-B are the capacities of the jugs A and B, respectively, and Goal is the desired amount of water in A. After a solution is found, Jugs will return a list of states representing the solution sequence. Specifically, each state has the form (Water-in-A Water-in-B Size-A Size-B). It returns '() if a solution can not be found. For example,

(Jugs 5 3 4) à ( (0 0 5 3) (5 0 5 3) (2 3 5 3) (2 0 5 3) (0 2 5 3) (5 2 5 3) (4 3 5 3) )

You could earn 20 bonus points if you create a printJugs function that prints the actual sequence of moves of the solution from the state list. For example,

(printJugs (Jugs 5 3 4))) ->

6 steps:

Fill-A

A-to-B

Empty-B

A-to-B

Fill-A

A-to-B