Beginner Prolog issue

1
votes

We have a box that contains red & yellow balls. A man comes daily and gets 2 balls from the box, if he couldn't get 2 balls the game finishes. There is a heap of red balls next to the box. If the 2 balls which the man has withdrawn from the box were similar, he puts red ball into the box, while if they were different, he puts yellow ball in the box. We suppose that the box is represented like this

initialCan([y, r, y, r, y, r, y, r, y, r]).

y represents yellow ball, r represents red ball. The man withdraws the 2 balls from the beginning of the list, then he puts back 1 ball also to the beginning of the list. So what is the procedure in Prolog which gives the color of the last ball in the box whatever was the box containing at the beginning?

2
prolog
In Prolog, a list can be represented as [H|T] where H is the first element and T is the rest of the list (T itself is a list). So if you queried, initialCan([H|T]), in your example, H would be instantiated as y (H = y would be true). Have you been through any Prolog tutorials or are you taking a class? - lurker
I am taking a class , and I read a few tutorials I understood the main concepts and how it works, but I didn't found a reference to a tutorial which teaches solving simple issues similar to this. I either found tutorial which teach complex issues, or tutorials which teach main concepts only. I need something in middle - Abo Homam
You don't want to think in terms of procedures but unification and predicates. Lists are a common structure in Prolog. A good tutorial should be giving a lot of examples using lists. When you enter, initialCan(L), this unifies L and [y, r, y, r, y, r, y, r, y, r] (so that L is instantiated with the list). You can then unify L with the form [H|T] and say, L = [H|T]. When these expressions are unified, then Prolog makes this = true by instantiating H with the value of the first element in L and T with the list representing the rest of L. - lurker
mmmm, ok Thanks dear. I will try to adapt your instructions - Abo Homam

2 Answers

1
votes

You might abstract your problem as a search in the space of possible states.

search(FinalState, FinalState):-
    is_final(FinalState).

search(CurrentState, FinalState):-
    transition(CurrentState, NextState),
    search(NextState, FinalState).

solution(FinalState):-
    initial_state(State0),
    search(State0, FinalState).

So you jump from state to state until you reach the final one which becomes your solution. You need to do some things:

  1. design a representation for a state (for example, a state might be a list like [r,y,r,...])

  2. write a predicate initial_state(S0) which is satisfied if S0 is the initial state of the game

  3. write a predicate transition(S1, S2) which is true if you can get from S1 to S2

  4. write a predicate is_final(S) which is true if S is a final state

0
votes

It is even easier to design the state as just box(Yellow_count, Red_count) and not bother with any particular list (after all, the balls are all identical, like electrons). Here is my try. I'm probably writing someone's homework here, but this is actually interesting.

Also consider checking out "Why correctness must be a mathematical concern" by Edsger W. Dijkstra, wherein this problem is described.

% last_ball(box(Yellow_initial_count, Red_initial_count), Last_ball_color, Time_at_end)


% ---------- TRIVIAL CASES ---------

% if there is only 1 yellow ball, the color is 'yellow' and we needed zero steps to reach this state

last_ball(box(1,0), yellow, 0).

% if there is only 1 red ball, the color is 'red' and we needed zero steps to reach this state

last_ball(box(0,1), red,    0).

% ---------- CASES DEFINING INDUCTION OVER Yellow+Red BALLS -----------

% take two yellow: check that this is possible for the given box, 
% then find out what the last color is from the reduced counts, then define the number of steps to be higher by 1

last_ball(box(YI, RI), LBC, TAE) :- YI>=2, YIp is (YI-2), RIp is (RI+1), last_ball(box(YIp,RIp),LBC,TAEp), TAE is (TAEp+1).

% take two red: check that this is possible for the given box, 
% then find out what the last color is from the reduced counts, then define the number of steps to be higher by 1

last_ball(box(YI, RI), LBC, TAE) :- RI>=2, YIp is YI, RIp is (RI-2+1), last_ball(box(YIp,RIp),LBC,TAEp), TAE is (TAEp+1).

% take a red and a yellow: check that this is possible for the given box, 
% then find out what the last color is from the reduced counts, then define the number of steps to be higher by 1

last_ball(box(YI, RI), LBC, TAE) :- RI>=1, YI>=1, YIp is (YI-1+1), RIp is (RI-1), last_ball(box(YIp,RIp),LBC,TAEp), TAE is (TAEp+1).

% Now ask for example:
% ?- last_ball(box(2,1), C, T).

% ===================================
% This problem is of course Edsger W. Dijkstra's "balls in the urn" problem, and 
% there is a very easy way to deduce the color without exhautsive check of the move tree, as Prolog does in the above.
% See: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD07xx/EWD720.html

last_ball_ewd(box(YI, _), red)    :- 0 is (YI mod 2).
last_ball_ewd(box(YI, _), yellow) :- 1 is (YI mod 2).

% We can test this by trying to find a counterexample of the result of last_ball_ewsd for the other color via '\+'

othercolor(red,yellow).
othercolor(yellow,red).

verify(box(YI, RI)) :- last_ball_ewd(box(YI, RI), LBC), othercolor(LBC,LBCO), \+last_ball(box(YI, RI), LBCO, _).

% Now ask for example:
% ?- verify(box(2, 1))