Courses/CS 460/Fall 2005/Homework/Cynthia York/Nov 19

From CSWiki

[edit] Jugs

• List the steps used to measure out a goal amount of water given any number of jugs, with any capacity and any valid initial contents. However, this does not work.

 
local
%   proc {Jugs JugsIn#Msg Goal Iteration ?JugsOut}
   proc {Jugs JugsIn#Msg Goal ?JugsOut}
      % Produces the list of jugs & their capacities at each step with
      % the final list containing the goal capacity
      LastLst
   in
      LastLst = {List.last [JugsIn]}
      if {List.some LastLst fun {$ Cap#Amt} Amt == Goal end}
      then
	 JugsOut = [JugsIn#Msg LastLst#'GOAL AMOUNT '#Goal#' HAS BEEN FOUND!']
      elseif {List.some LastLst fun {$ Cap#Amt} Cap == Goal end}
      then
	 JugsOut = [JugsIn#Msg LastLst#'GOAL AMOUNT '#Goal#' HAS BEEN FOUND!']
	 fail
      else
	 fail
%	 JugsOut = [JugsIn#Msg {ChooseJug LastLst Iterator Goal}]
      end
   end

%    proc {ChooseJug Lst Goal Iterator ?Sol}
%       {Browse 'ChooseJug Lst:'#Lst}
%       Sol = {List.mapInd Lst
% 	     fun {$ I C#A}
% 		[{ChooseOp Lst I Iterator Goal}]
% 	     end}
%    end

%    proc {ChooseOp Lst I Goal Iterator ?Sol}
%       {Browse 'ChooseOp Lst:'#Lst#', I:'#I}
%       Sol = {List.mapInd Lst
% 	     fun {$ I C#A}
% 		{Browse 'ChooseOp I:'#I#', C:'#C#', A:'#A}
% 		cond C=Goal then [{FillJug Lst I}]
% 		[] A=Goal then [Lst#'GOAL AMOUNT '#Goal#' HAS BEEN REACHED!']
% 		else
% 		   for Inx2 in Inx+1; Inx2 =< {Length List}; I+1
% 		   do [{PourJug Lst Inx Inx2 Iterator Goal}]
% 		   end
% 		end
% 	     end}
%    end

%    proc {FillJug Lst Ind ?Sol}
%       {Browse 'FillJug Lst:'#Lst#', Ind:'#Ind}
%       Sol = {List.mapInd Lst
% 	     fun{$ I C#A}
% 		if I=Ind
% 		then
% 		   if A=0
% 		   then
% 		      C#C
% 		   else
% 		      [{EmptyJug Lst I} {FillJug Lst I}]
% 		   end
% 		end
% 	     end}#'Filled Jug'#Ind
%    end

%    proc {EmptyJug Lst Ind ?Sol}
%       {Browse 'EmptyJug Lst:'#Lst#', Ind:'#Ind}
%       Sol = {List.mapInd Lst
% 	     fun{$ I C#A}
% 		if I=Ind
% 		then
% 		   C#0
% 		end
% 	     end}#'Emptied Jug'#Ind
%    end
   
%    proc {PourJug Lst Inx Inx2 Goal Iterator ?Sol}
%       Cap1 Amt1 Cap2 Amt2 in
%       Cap1#Amt1={Nth Lst Inx}
%       Cap2#Amt2={Nth Lst Inx2}
%       Sol = {List.mapInd Lst
% 	     fun{$ I C#A}
% 		if I=Inx
% 		then
% 		   {List.mapInd Lst
% 		    fun{$ I2 C2#A2}
% 		       if I=Inx2
% 		       then
% 			  C2#{Mod (A2*A-Iterator*A) A2}
% 		       end
% 		    end}
% 		end
% 	     end}#'Poured Jug'#Inx#'into Jug'#Inx2'
%    end

   proc {JugsID JugLst#Msg#Goal Iteration ?JugsMsg}
      JugsMsg = 'Iteration'#Iteration#{Jugs JugLst#Msg Goal}
   end

   fun {IterativeDeepening Func Data Max}
      % Declare Iteration to be an FD variable 
      % with range 0#134217726.
      Iteration % = {FD.decl}
   in
      % Distribute over Iteration: try a value of 0; if that fails,
      % try a value of 1; if that fails, try a value of 2, etc.
      Iteration :: [0#Max]
      {FD.distribute naive [Iteration]}
      
      % Pass Max & a value for Iteration to the Function to be
      % explored along with its Data.
      {Func Data Iteration}
   end
in
   {Browse {SearchAll fun {$} {IterativeDeepening JugsID [3#0 4#0 5#0]#'Initial amounts'#4 1} end}}
   {ExploreAll fun {$} {IterativeDeepening JugsID [5#4 3#0]#'Initial amounts'#4 1} end}
end