Problem Definition

There are two containers with capacities x and y. A well containing an inexhaustible supply of water is available.

A desired amount, z of water must be obtained in large container by

completely filling up container and/or emptying one container into another or onto the ground. Possible moves are:

- filling the smaller jug from the water supply

- filling the larger jug from the water supply

- pouring out the contents of the smaller jug (onto the ground)

- pouring out the contents of the larger jug (onto the ground)

- pouring the contents of the smaller jug into the larger jug, until the larger jug is full, or the smaller jug is empty

- pouring the contents of the larger jug into the smaller jug, until the smaller jug is full, or the larger jug is empty

This is two-jugs version, three-jugs version is also popular.

Idea

This problem has a naturally graph-like representation. State state can be easily implemented to CN. If we try to draw state space, elements will be like below;

  • format of state : state (smallJug, largeJug).
  • initial state : (0, 0).
  • final state : (_, z). Any possible state that final jug value is z. (z is desired value for the problem)

Every possible should be will be primitive, thus state can be change through these primitives.



Solution Idea

This problem has a naturally graph-like representation. State state can be easily implemented to CN. If we try to draw state space, elements will be like below;

  • format of state : state (smallJug, largeJug).
  • initial state : (0, 0).
  • final state : (_, z). Any possible state that final jug value is z. (z is desired value for the problem)

Every possible move should be primitive, thus state can be change through these primitives.



Global Variables

"State" is a record that contains small jug value, large jug value, move name in current state and cumulative cost up to current state.

"Item" is a record that has current state and a pointer to previous state. These "Item" s are pushed and popped to a stack in search process.

"ptr_item" is a pointer to "Item".

"path" is array of State. At the end of the search process full path copied to "path" from stack, then "path" is printed.

"cost" represents cost of the current state.

"smallJug" represents small jug value of the current state.

"largeJug" represents large jug value of the current state.

"stack_count" represents total elements in the stack.

"small_jug_cap" represents capacity of the small jug. It is defined by user at beginning of the program.

"large_jug_cap" represents capacity of the large jug. It is defined by user at beginning of the program.

"final_value" represents desired value in large jug at the end of the search process.

"current" is pointer to current item in the stack. It is used in search process.

"top" is pointer to top item of the stack.

type State = RECORD smallJug : integer; largeJug : integer; cost : integer; move : string; end; ptr_item = ^Item; Item = RECORD st : State; prev : ptr_item; end; var Path : array of State; cost, smallJug, largeJug, stack_count, small_jug_cap, large_jug_cap, final_value: integer; move : string; current, top : ptr_item; function SpiderSolutions : integer; { for CNP execution ! }


Subnets




Subnet: MainNetwork
Parameters:
Variables:
----------------------------------



Primitives


print

"print" primitive copies stack content to "Path" array from end to beginning. Then it prints the "Path" content.


procedure print; var temp : ptr_item; i: integer; begin if FORW then begin temp := top; SetLength(Path, stack_count); for i := (stack_count-1) downto 0 do begin Path[i] := temp^.st; temp := temp^.prev; end; writeln(); for i := 0 to (stack_count-1) do begin write('smallJug = ', Path[i].smallJug); write(' largeJug = ', Path[i].largeJug); write(' cost = ', Path[i].cost); writeln(' move = ', Path[i].move); end; write('smallJug = ', smallJug); write(' largeJug = ', largeJug); write(' cost = ', cost); writeln(' move = ', move); writeln(); writeln('Press Enter to see another solution'); writeln(); readln; end; end;

initialize

"initialize" primitive asks user for small jug capacity, large jug capacity, desired value of large jug and assigns them. It also assigns

initial values of other variables.


procedure initialize; begin if FORW then begin writeln('Water Jug Problem - Iterative Solution'); writeln('=========================================='); write('Enter small jug capacity = '); readln(small_jug_cap); write('Enter large jug capacity = '); readln(large_jug_cap); write('Enter final large jug value = '); readln(final_value); stack_count := 0; smallJug := 0; largeJug := 0; cost := 0; move := '---'; end; end;

fillSmall

"fillSmall" primitive fills small jug, assigns cost and move for current state.


procedure fillSmall; var cost_local : integer; begin if FORW then begin push; cost_local := small_jug_cap - smallJug; cost := cost + cost_local; smallJug := small_jug_cap; move := 'fs'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end; end;

fillLarge

"fillLarge" primitive fills large jug, assigns cost and move for current state.


procedure fillLarge; var cost_local : integer; begin if FORW then begin push; cost_local := large_jug_cap - largeJug; cost := cost + cost_local; largeJug := large_jug_cap; move := 'fl'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end end;

emptysmall

"emptySmall" primitive pours water in small jug to ground, assigns cost and move for current state.


procedure emptysmall; var cost_local : integer; begin if FORW then begin push; cost_local := smallJug; cost := cost + cost_local; smallJug := 0; move := 'es'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end end;

emptyLarge

"emptyLarge" primitive pours water in large jug to ground, assigns cost and move for current state.


procedure emptyLarge; var cost_local : integer; begin if FORW then begin push; cost_local := largeJug; cost := cost + cost_local; largeJug := 0; move := 'el'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end end;

pourLargeToSmall

"pourLargeToSmall" primitive pours water in large jug to small jug until large jug empty or small jug is full


procedure pourLargeToSmall; var cost_local : integer; begin if FORW then begin push; if(largeJug <= (small_jug_cap - smallJug)) then {No OverFlow} begin cost_local := largeJug; smallJug := largeJug + smallJug; largeJug := 0; end else {OverFlow} begin cost_local := small_jug_cap - smallJug; largeJug := largeJug - (small_jug_cap - smallJug); smallJug := small_jug_cap; end; cost := cost + cost_local; move := 'pls'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end end;

pourSmallToLarge

"pourSmallToLarge" primitive pours water in small jug to large jug until small jug empty or large jug is full


procedure pourSmallToLarge; var cost_local : integer; begin if FORW then begin push; if(smallJug <= (large_jug_cap - largeJug)) then {No OverFlow} begin cost_local := smallJug; largeJug := largeJug + smallJug; smallJug := 0; end else {OverFlow} begin cost_local := large_jug_cap - largeJug; smallJug := smallJug - (large_jug_cap - largeJug); largeJug := large_jug_cap; end; cost := cost + cost_local; move := 'psl'; FAILURE := onStack or isFound; end else begin smallJug := top^.st.smallJug; largeJug := top^.st.largeJug; cost := top^.st.cost; move := top^.st.move; pop; end end;

isFinal

"isFinal" primitive if checks current state is final state.


procedure isFinal; begin if FORW then begin if (largeJug <> final_value) then begin FAILURE := true; end end end;


OtherFunctions


onStack : boolean

"onStack" function returns true if reached state is in the stack.


function onStack : boolean; var temp : ptr_item; begin temp := top; while (temp <> nil) do begin if (temp^.st.smallJug = smallJug) and (temp^.st.largeJug = largeJug) then begin exit(true); end else begin temp := temp^.prev; end; end; exit(false); end;

isFound : boolean

"isFound" function returns true if reached state is desired state.


function isFound : boolean; begin if (top^.st.largeJug = final_value) then begin exit(true); end; exit(false); end;

push

"push" procedure push an "Item" to stack.


procedure push; begin new(current); current^.st.smallJug := smallJug; current^.st.largeJug := largeJug; current^.st.cost := cost; current^.st.move := move; current^.prev := top; top := current; inc(stack_count); end;

pop

"pop" procedure pop an "Item" from stack.


procedure pop; begin current := top^.prev; dispose(top); top := current; dec(stack_count); end;

SpiderSolutions : integer

"SpiderSolutions" function for CNP execution.


function SpiderSolutions : integer; { for CNP execution ! } begin SpiderSolutions :=-123 end;