Beginner Prolog issue

Question

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?

Answer 1

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))

Answer 2

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