Courses/CS 460/Fall 2005/Homework/Kelly Breed/Nov 19

From CSWiki

My main homework page

Contents 1 HW 8 1.1 The Jugs Puzzle

[edit] HW 8

[edit] The Jugs Puzzle

This program works but iterative deepening is not figured out.

local
   fun {Fill S}
      A in
      A#_ = S
      A#A
   end

   fun {Empty S}
      A in
      A#_ = S
      A#0
   end
   
   proc {Pour Src DstLst Nsrc Ndst Rol}
      C1 C2 V1 V2 in
      C1#V1 = Src
      C2#V2 = {ListItems DstLst}
      Rol = {List.subtract DstLst C2#V2}
      if V1>(C2-V2) then Nsrc=C1#V1-(C2-V2)
	 Ndst=C2#C2
      else Nsrc=C1#0
	 Ndst=C2#V2+V1 end
   end
   
   proc {Ops E Rol ?L}
      A B R in
      choice L = {Fill E}|Rol
      [] L = {Empty E}|Rol
      [] {Pour E Rol A B R}
	 L = A|B|R
      %L = {List.sort A|B|R fun {$ A#B C#D} A < B end}
      end
   end
   
   fun {ListItems L}
      H T in
      choice
	 L= H|_ H
      [] L= _|T {ListItems T}
      end
   end
   
   proc {MatchTarget T L O}
      C={NewCell 0} in
      {ForAll L proc{$ X}
		   A in
		   X=_#A
		   if A == T then C:=@C+1 end
		end
      }
       if @C>0 then O=true 
       else O=false end
   end
   
   proc {Jugs In Target ?Out}
      % Cannot figure out the iterative deepening.  '5' below is a manually plugged
      % in number of iterations.
      {Jugs3 [In] 5 Target Out}
   end
   
   proc {Jugs3 In I Target ?R}
      H N E in
      case In of
	 H|_ then E={ListItems H}
	 N={List.sort {Ops E {List.subtract H E}} fun {$ A#B C#D} A < C end}
	 else skip
      end

      if {Member N In} then fail
      else if {MatchTarget Target N} then R = {List.reverse N|In}
	   else if I>0 then {Jugs3 N|In I-1 Target R}
		   else if I==0 andthen {MatchTarget Target N}==false then fail
		end end end end
   end
R   
in
   R =  {SearchAll fun {$} {Jugs [3#0 5#0]  4} end}
   %{Browse {Length R}}
   {Browse R}
end

My user page.