Courses/CS 460/Fall 2005/Homework/Brian Smith/Nov 19

From CSWiki

[edit] Jug Puzzle Solver

This program solves jug puzzles with any number of jugs. The jugs can have any capacity and any initial level of water between 0 and capacity. The program verifies that all jugs have a valid level and that at least one jug can contain the goal level. The jugs are represented by records mostly for clarity in the code.

The result is a list of sequences of states. Each sequence begins with the initial state and ends with a state in which a jug contains the goal level. Transitions between states represent one of three actions: fill a jug, empty a jug, or pour water from one jug to another.

Each action requires that I modify one or two jugs from a state, but I don't want to change the order of jugs. I used the miraculous Append/3 in two procedures that split the state into 3 or 5 pieces. They work non-deterministically to try all variations of pieces, provided that the pieces that represent jugs to modify have length 1. Another great reason to use Append/3 is that it works in reverse--I use the same statement to reassemble the pieces in the correct order to create the new state.

The program uses a basic form of loop avoidance by not allowing repeated states. Since it doesn't use iterative deepening the first result doesn't necessarily have the smallest number of steps to the goal state. I sorted the results based on length.

[edit] Solutions

In the classic example of 5 and 3 gallon jugs my shortest answer matches the solution on the Homework page:

[[[jug(cap:5 level:0) jug(cap:3 level:0)]
  [jug(cap:5 level:5) jug(cap:3 level:0)]
  [jug(cap:5 level:2) jug(cap:3 level:3)]
  [jug(cap:5 level:2) jug(cap:3 level:0)]
  [jug(cap:5 level:0) jug(cap:3 level:2)]
  [jug(cap:5 level:5) jug(cap:3 level:2)]
  [jug(cap:5 level:4) jug(cap:3 level:3)]]
 ...

In variations with more than two jugs searching takes longer, so I used SearchOne instead of SearchAll.

[edit] Code

local
   proc {Jugs States Goal ?OutStates}
      S  % the current state
      N  % the new state
   in
      % Get the most recent state
      S = {List.last States}

      choice
         % 1. Fill a jug and make new state
	 Pre J Post Jn in
	 {Threepend S Pre J Post}
	 Jn = [{MakeJug J.1.cap J.1.cap}]
	 {Threepend N Pre Jn Post}
	 
      [] % 2. Empty a jug and make new state
	 Pre J Post Jn in
	 {Threepend S Pre J Post}
	 Jn = [{MakeJug J.1.cap 0}]
	 {Threepend N Pre Jn Post}
	 
      [] % 3. Pour from one jug to another and make new state
	 Pre J1 In J2 Post
	 Source Dest Forward
	 W1 W2 Sourcen Destn
      in
	 {Fivepend S Pre J1 In J2 Post}

	 % choose direction of pouring
	 choice
	    Source = J1.1 Dest = J2.1 Forward = true
	 []
	    Source = J2.1 Dest = J1.1 Forward = false
	 end

	 % determine amount to pour
	 W1 = (Dest.cap - Dest.level)
	 W1 > 0 = true
	 if W1 > Source.level then
	    W2 = Source.level
	 else
	    W2 = W1
	 end
	 
	 % create new jugs for new state
	 Sourcen = [{MakeJug Source.cap Source.level-W2}]
	 Destn = [{MakeJug Dest.cap Dest.level+W2}]

	 if Forward == true then
	    {Fivepend N Pre Sourcen In Destn Post}
	 else
	    {Fivepend N Pre Destn In Sourcen Post}
	 end
      end

      % Fail if N is already in States (prevents looping)
      {Member N States} = false

      % Stop if a jug has the final level
      if {Some N fun {$ J} J.level == Goal end} then
	 OutStates = {Append States [N]}
      else
	 OutStates = {Jugs {Append States [N]} Goal}
      end
   end

   proc {Append Xs Ys Zs}
      choice
	 Xs = nil Ys = Zs
      [] X Xr in
	 Xs = X | Xr
	 Zs = X | {Append Xr Ys}
      end
   end

   proc {Threepend L Pre J Post}
      JPost in
      {Append Pre JPost L}
      {Append J Post JPost}
      {Length J} == 1 = true
   end

   proc {Fivepend L Pre J1 In J2 Post}
      J1Post Part2 in
      {Append Pre J1Post L}
      {Append J1 Part2 J1Post}
      {Threepend Part2 In J2 Post}
      {Length J1} == 1 = true
      {Length J2} == 1 = true
   end

   proc {MakeJug Capacity Level ?R}
      R = {MakeRecord jug [cap level]}
      R.cap = Capacity
      R.level = Level
      R.level =< R.cap = true
   end

   fun {Juggle}
      Js = [{MakeJug 5 0} {MakeJug 3 0}]
      Goal = 4
   in
      {Some Js fun {$ J} Goal =< J.cap end} = true
      {Jugs [Js] Goal}
   end

   Results SResults
in
   Results = {SearchAll Juggle}
   SResults = {Sort Results fun {$ X Y} {Length X} < {Length Y} end}
   {Browse SResults}
%   {Browse {SearchOne Juggle}}
%   {ExploreOne Juggle}
end