4

I am trying to implement a prolog progarm that implement depth first search and breadth first search the solves the following problem

Rowena has three unmarked glasses of different sizes: 3 ounces, 5 ounces, and 8 ounces. The largest glass is full. What can Rowena do to get 4 ounces of liquid into each of the larger two glasses?

I will have (Large,Medium,Small)

So the initial state is (8,0,0) and the goal state is (4,4,0).

Now I know that I have 6 available moves in the state space.

(1,2) Pour Large into medium or small (3,4) Pour Medium into large or small (5,6) Pour small into medium or large

Now I just need help with the first rule and the rest I will figure out. So I can only pour out the large into the medium if the large > 0 and medium is not full, and the new large becomes the old large minus the amount that was poured into the medium and the new medium becomes the old medium plus the amount that was poured into it, and the small of course never changes.

Here is what I attempted.

%move rule #1: Pour Large into Medium (L--> M) 
%move(oldstate,newstate)

move([L, M, S], [NewLarge,NewMedium,S]) :-
L > 0, %We can't move large into medium if Large has nothing
M < 5, %We can't pour into the medium if medium is full
Diff = 5 - M, 
NewLarge is L - Diff, %calculate the new Large
NewMedium is M + (L - NewLarge). %calculate the new Medium

Is this a correct implementation of the first avaliable move (Large into medium). Did I get the correct logic there ?

false
  • 10,264
  • 13
  • 101
  • 209
Pro
  • 173
  • 4
  • 15

1 Answers1

2

I think the logic should be instead

move([L, M, S], [NewLarge, NewMedium, S]) :-
  Diff is min(5 - M, L),
  Diff > 0,
  NewLarge is L - Diff, %calculate the new Large
  NewMedium is M + Diff. %calculate the new Medium
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • that makes a lot of sense, But what If want to move from Medium to large, Do we calculate the Diff is max(8- L, M) ?? – Pro Nov 08 '15 at 21:25
  • It's obvious, but maybe what you're missing is a check that a state has already been tried, to avoid looping forever. Your change state recursive predicate should have a Visited accumulator, and after generating a move, verify it (using \+memberchk(NewState,Visited)) – CapelliC Nov 08 '15 at 21:29
  • No I guess it has to still be the min(8- L,M) and then if Diff > 0 then the new Large becomes L + Diff and the new Medium becomes M - Diff right @Capellic ?? – Pro Nov 08 '15 at 21:31