Bridge problem

Help!
1

Hello,

I have a solution for the bridge crossing problem (4 people crossing a bridge with a time of 1,2,5,10 with a torch and they need to take the torch back as long as they didnt all crossed the bridge).
here is my code :

time(b,1).
time(e,2).
time(a,5).
time(l,10).

traverser(Tmax,[],MembresResDG,Temps,Transitions).
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-
    select(Me1,MembresResGD,MembresResGD1),
    select(Me2,MembresResGD1,MembresResGD2),
    append([Me1],MembresResDG,MembresResDG1),
    append([Me2],MembresResDG1,MembresResDG2), 
    select(Me3,MembresResDG2,MembresResDG3),
    append([Me3],MembresResGD2,MembresResGD3),
    time(Me1,X),
    time(Me2,Y),
    time(Me3,Z),
    NewTemps is Temps + max(X,Y) + Z,
    NewTemps =< Tmax,
    append(["Rive gauche : ", MembresResGD3," Rive Droite : ", MembresResDG3," Temps : ",NewTemps],Transitions,NewTransitions),
 %   write(NewTransitions),
    traverser(Tmax, MembresResGD3, MembresResDG3, NewTemps,NewTransitions).

I don’t get why i cant get the solution.
Can anybody help ?

2

When I tried your program, (in file /tmp/pont.pl), I got these warnings:

Warning: /tmp/pont.pl:6:
Warning:    Singleton variables: [Tmax,MembresResDG,Temps,Transitions]

You might start by looking at those.

Also, what is the form of your query? I got this:

?- traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions).
MembresResGD = [] ;
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:   [11] _11792 is _11804+ ... + 1
ERROR:   [10] traverser(_11830,[b,b|_11850],_11834,_11836,_11838) at /tmp/pont.pl:17
ERROR:    [9] toplevel_call(user:user: ...) at /usr/lib/swi-prolog/boot/toplevel.pl:1117

PS: When posting, if you surround your code with triple back-quotes, it preserves the layout.

3

I fixed it for them.

4

Hello,
the call you have to do for the function traverser is traverser(17,[b,e,a,l],[],0,[]). The idea is that you start the problem with 4 guys on left of the bridge. You start to move 2 guys on the right and examine if you still have people on the left. If they are not 0, (and that s the point where i have a lack of knowledge in prolog i think), you move one guy from with to left and call the function.
I have reworked my code and here is the new version :

“”"
time(b,1).
time(e,2).
time(a,5).
time(l,10).

traverser(_Tmax,[],_MembresResDG,_Temps,_Transitions).
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-
select(Me1,MembresResGD,MembresResGD1),
select(Me2,MembresResGD1,MembresResGD2),
append([Me1],MembresResDG,MembresResDG1),
append([Me2],MembresResDG1,MembresResDG2),
time(Me1,X),
time(Me2,Y),
Temps2 is Temps + max(Y,X),
not(length(MembresResDG2,0)),
select(Me3,MembresResDG2,MembresResDG3),
append([Me3],MembresResGD2,MembresResGD3),
time(Me3,Z),
NewTemps is Temps2 + Z,
NewTemps =< Tmax,
append([“Rive gauche : “, MembresResGD3,” Rive Droite : “, MembresResDG3,” Temps : “,NewTemps],Transitions,NewTransitions),
write(NewTransitions),
traverser(Tmax, MembresResGD3, MembresResDG3, NewTemps,NewTransitions).””"

My last problem is that i cannot take that line not( length(MembresResDG2,0)), and put instead a test that enable me to write all the transitions that has been used for solving the problem. I dont know how to deal with such test in prolog4 but i know i m close to the solutions (by looking at all the transitions).
Can you help me ?

5

i tried the triple quote but i am not sure of what i did.
Can you tell me if its ok.

6

You used “”" when you need to use ```, e.g.

``` Prolog code goes here ```

See: Language highlighting

7

First, a minor thing: you can test for a zero-length (empty) list by MembresResDG2 = [_|_] – that is, it has at least one member. (Alternatively: MembresResDG2 \= []).

Also, your debug output would be easier to read if you used writeln/1.

I think you need to think in terms of “what conditions allow me to terminate”. The first clause seems to be the termination (when MembresResGD = []). The second clause allows either an empty or a non-empty list for MembresResGD; however, the two calls to select/3 require that MembresResGD has at least 2 elements. You can see this for yourself:

?- L0 = [1], select(A, L0, L1), select(B, L1, L2).
false.

?- L0 = [1,2], select(A, L0, L1), select(B, L1, L2).
L0 = [1, 2],
A = 1,
L1 = [2],
B = 2,
L2 = [] ;  % backtrack for another solution
L0 = [1, 2],
A = 2,
L1 = [1],
B = 1,
L2 = [].
8

The fact of having at least in the worst case 2 elements for the two select is garanteed by the test. My problem is that i have no if then else. I reworked my code and got an error i still not understand. My problem is that i dont have any knowledge in prolog syntax. From the algorithmical point of view i have a clear idea of what i want to do, but I have no idea how (and if i can) to do it in Prolog. I dont understand clearly the previous post as i dont understand the behaviour of prolog. Backtracking should be commanded by conditions. If it fails, the program just stop and jump to another possible solution, at least its how i see its behaviour.
I have worked once again :

time(e,2).
time(a,5).
time(l,10).

ecrire([]).
ecrire([H|T]) :- write(H), nl, ecrire(T).

traverser(_Tmax,[],_MembresResDG,_Temps,Transitions).
    
traverser(Tmax,MembresResGD,MembresResDG,Temps,Transitions):-
    select(Me1,MembresResGD,MembresResGD1),
    select(Me2,MembresResGD1,MembresResGD2),
    append([Me1],MembresResDG,MembresResDG1),
    append([Me2],MembresResDG1,MembresResDG2), 
    time(Me1,X),
    time(Me2,Y),
    Temps2 is Temps + max(Y,X),
    append(["Rive gauche : ", MembresResGD2," Rive Droite : ", MembresResDG2," Temps : ",Temps2],Transitions,Transitions2),
    Temps2 =< Tmax,
    (   not(length(MembresResGD2,0))-> select(Me3,MembresResDG2,MembresResDG3),
    append([Me3],MembresResGD2,MembresResGD3),
    time(Me3,Z),
    NewTemps is Temps2 + Z,
    NewTemps =< Tmax,
    write(Transitions2),
    append(["Rive gauche : " MembresResGD3" Rive Droite : " MembresResDG3 " Temps : " NewTemps],Transitions2,NewTransitions),
    append(MembresResGD3, [], MembreResGFinal),
    append(MembreResDG3,[], MembresResDFinal),
    TempsFinal is NewTemps + 0,
    append(NewTransitions, [],TransitionsFinales);
    append(MembresResGD2, [], MembreResGFinal),
    append(MembreResDG2,[], MembresResDFinal),
    TempsFinal is Temps2 + 0,
    append(Transitions2, [],TransitionsFinales)),    
    traverser(Tmax, MembresResGFinal, MembresResDFinal, TempsFinal,TransitionsFinales).```
9

Perhaps it would help if you fully stated the problem (in French, if you wish – some of us can read French and Google Translate will help the others). E.g.: is it allowed for a single person to cross? Are there constraints on who can cross together? Etc.

Then write down in detail (in English or French) how you would find a single solution (not necessarily the best solution, just a solution). Very often, that solution can be translated directly into Prolog – one of the advantages of working in a high-level language.

As for backtracking: it’s best to think of it as simply finding something with constraints. So, for example, select(Me1,MembresResGD,MembresResGD1) simply says "pick an element (called Me1) from MembresResGd, leaving the residue in MembresResGD1. If a subsequent test (“goal”) determines that Me1 isn’t suitable, backtracking will select a different element for Me1 and all the subsequent tests (goals) will be tried again. If there is no suitable element, then everything fails. (This is not quite accurate, but I hope it gives you the idea)

That is, the following will select an item that’s divisible by 2:

?- select(X, [1,2,3,4], Residue), 0 is X mod 2.
X = 2,
Residue = [1, 3, 4] ;
X = 4,
Residue = [1, 2, 3].

Suggestion: some of your variable names are very similar. I would suggest, e.g., changing MembresResGD to MembresDroite and MembresResDG to MembresGauche, etc. to avoid typos. (Also, Membres doesn’t add information, so just Droite and Gauche should be enough.)

PS: why is there a goal TempsFinal is Temps2 + 0?

Edit: Added an “interpretation” of how select/3 backtracks.