CODEWITHSUNDEEP
prolog
Sean-McCreary
Sean-McCreary

Reputation: 13

How can I prevent prolog from backtracking and deleting my list?

I am working on a homework question and I think that I have gotten very close but I can't quite figure out how to get my program to return the list instead of recursively deleting it on the return.

The code is meant to check through the given met facts and try to determine if the goal person is sick because of a related sickness that happened in the office. Each person is infectious for 7 days once they are in contact with a sick person and we want to return a list that contains the possible infection pathway to the final person from the given start person.

mymember in the code has the same functionality as member

My code is

mymember(X, [X|_]).
mymember(X, [_|Z]) :- 
mymember(X,Z).

met(john,28,mary).
met(john,3,mary).
met(peter,21,john).
met(mary,23,mark).
met(anne,19,peter).
met(anne,29,john).
met(anne,24,mary).
met(mark,17,paul).

%%% Question 7
contact(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),ZS) :-
    contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),[],ZS).

contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,InfectionPath) :-
    StartPerson == GoalPerson,
    StartTime >= Goaltime.
contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,InfectionPath) :-
    (met(StartPerson,MetTime,MidPerson);met(MidPerson,MetTime,StartPerson)),
    StartTime >= MetTime,
    StartTime - MetTime < 7,
    \+ (mymember(met(StartPerson,MetTime,MidPerson),MetHistory);mymember(met(MidPerson,MetTime,StartPerson),MetHistory)),
    contact4(infect(MidPerson,MetTime),infect(GoalPerson,Goaltime),[(met(StartPerson,MetTime,MidPerson)),(met(MidPerson,MetTime,StartPerson))|MetHistory],[infect(MidPerson,MetTime)|InfectionPath]).

The code that I have above correctly follows the path and I have confirmed it is correct with trace. The issue is, at the end of the trace when it reaches the goal person, it is deleting all of the entries before it returns. This can be seen clearly in the last 5 Exit calls that are made by the program. I have provided the trace below using the call.

contact(infect(john,31),infect(paul,11),ZS).

[trace]  ?- contact(infect(john,31),infect(paul,11),ZS).
   Call: (10) ex3:contact(infect(john, 31), infect(paul, 11), _28656) ? creep
   Call: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) john==paul ? creep
   Fail: (12) john==paul ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:met(john, _32982, _32984) ? creep
   Exit: (12) ex3:met(john, 28, mary) ? creep
   Call: (12) 31>=28 ? creep
   Exit: (12) 31>=28 ? creep
   Call: (12) 31-28<7 ? creep
   Exit: (12) 31-28<7 ? creep
   Call: (12) ex3:mymember(met(john, 28, mary), []) ? creep
   Fail: (12) ex3:mymember(met(john, 28, mary), []) ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:mymember(met(mary, 28, john), []) ? creep
   Fail: (12) ex3:mymember(met(mary, 28, john), []) ? creep
   Redo: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _28656) ? creep
   Call: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) mary==paul ? creep
   Fail: (13) mary==paul ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:met(mary, _45284, _45286) ? creep
   Exit: (13) ex3:met(mary, 23, mark) ? creep
   Call: (13) 28>=23 ? creep
   Exit: (13) 28>=23 ? creep
   Call: (13) 28-23<7 ? creep
   Exit: (13) 28-23<7 ? creep
   Call: (13) ex3:mymember(met(mary, 23, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (14) ex3:mymember(met(mary, 23, mark), [met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mary, 23, mark), []) ? creep
   Fail: (15) ex3:mymember(met(mary, 23, mark), []) ? creep
   Fail: (14) ex3:mymember(met(mary, 23, mark), [met(mary, 28, john)]) ? creep
   Fail: (13) ex3:mymember(met(mary, 23, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:mymember(met(mark, 23, mary), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (14) ex3:mymember(met(mark, 23, mary), [met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mark, 23, mary), []) ? creep
   Fail: (15) ex3:mymember(met(mark, 23, mary), []) ? creep
   Fail: (14) ex3:mymember(met(mark, 23, mary), [met(mary, 28, john)]) ? creep
   Fail: (13) ex3:mymember(met(mark, 23, mary), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_28656]) ? creep
   Call: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_28656]) ? creep
   Call: (14) mark==paul ? creep
   Fail: (14) mark==paul ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_28656]) ? creep
   Call: (14) ex3:met(mark, _63714, _63716) ? creep
   Exit: (14) ex3:met(mark, 17, paul) ? creep
   Call: (14) 23>=17 ? creep
   Exit: (14) 23>=17 ? creep
   Call: (14) 23-17<7 ? creep
   Exit: (14) 23-17<7 ? creep
   Call: (14) ex3:mymember(met(mark, 17, paul), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(mark, 17, paul), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (16) ex3:mymember(met(mark, 17, paul), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (17) ex3:mymember(met(mark, 17, paul), [met(mary, 28, john)]) ? creep
   Call: (18) ex3:mymember(met(mark, 17, paul), []) ? creep
   Fail: (18) ex3:mymember(met(mark, 17, paul), []) ? creep
   Fail: (17) ex3:mymember(met(mark, 17, paul), [met(mary, 28, john)]) ? creep
   Fail: (16) ex3:mymember(met(mark, 17, paul), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (15) ex3:mymember(met(mark, 17, paul), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (14) ex3:mymember(met(mark, 17, paul), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (14) ex3:mymember(met(paul, 17, mark), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (15) ex3:mymember(met(paul, 17, mark), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (16) ex3:mymember(met(paul, 17, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Call: (17) ex3:mymember(met(paul, 17, mark), [met(mary, 28, john)]) ? creep
   Call: (18) ex3:mymember(met(paul, 17, mark), []) ? creep
   Fail: (18) ex3:mymember(met(paul, 17, mark), []) ? creep
   Fail: (17) ex3:mymember(met(paul, 17, mark), [met(mary, 28, john)]) ? creep
   Fail: (16) ex3:mymember(met(paul, 17, mark), [met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (15) ex3:mymember(met(paul, 17, mark), [met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Fail: (14) ex3:mymember(met(paul, 17, mark), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)]) ? creep
   Redo: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (14) ex3:contact4(infect(paul, 17), infect(paul, 11), [met(mark, 17, paul), met(paul, 17, mark), met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(paul, 17), infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Call: (15) paul==paul ? creep
   Exit: (15) paul==paul ? creep
   Call: (15) 17>=11 ? creep
   Exit: (15) 17>=11 ? creep
   Exit: (14) ex3:contact4(infect(paul, 17), infect(paul, 11), [met(mark, 17, paul), met(paul, 17, mark), met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(paul, 17), infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Exit: (13) ex3:contact4(infect(mark, 23), infect(paul, 11), [met(mary, 23, mark), met(mark, 23, mary), met(john, 28, mary), met(mary, 28, john)], [infect(mark, 23), infect(mary, 28)|_18]) ? creep
   Exit: (12) ex3:contact4(infect(mary, 28), infect(paul, 11), [met(john, 28, mary), met(mary, 28, john)], [infect(mary, 28)|_18]) ? creep
   Exit: (11) ex3:contact4(infect(john, 31), infect(paul, 11), [], _18) ? creep
   Exit: (10) ex3:contact(infect(john, 31), infect(paul, 11), _18) ? creep
true .

[trace]  ?-

I have also checked out the related questions but could not find a solution. here and here

Upvotes: 0

Views: 70

Answers (1)

Isabelle Newbie
Isabelle Newbie

Reputation: 9378

Thanks for the updates, I can now run your program.

What you are trying to do is to compute an infection path from a Start to a Goal person. You are doing this correctly by looking for a connection from a Start to a Mid person, and then from Mid to Goal. The detail you're missing is that the Start to Goal path is longer than the Mid to Goal path.

Therefore your code cannot be of this shape:

path(Start, Goal, Path) :-
    step(Start, Mid),
    path(Mid, Goal, [Step | Path]).

This would say that the Mid to Goal path is one element longer than the Start to Goal path! That's the wrong way round.

What you need instead is something of this shape:

path(Start, Goal, [Step | Path]) :-
    step(Start, Mid),
    path(Mid, Goal, Path).

This says: There is some Path from Mid to Goal. The path from Start to Goal is the same Path extended with one Step.

So you want something like this:

contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),_MetHistory,InfectionPath) :-
    StartPerson == GoalPerson,
    StartTime >= Goaltime,
    InfectionPath = [].
contact4(infect(StartPerson,StartTime),infect(GoalPerson,Goaltime),MetHistory,[infect(MidPerson,MetTime)|InfectionPath]) :-
    (met(StartPerson,MetTime,MidPerson);met(MidPerson,MetTime,StartPerson)),
    StartTime >= MetTime,
    StartTime - MetTime < 7,
    \+ (mymember(met(StartPerson,MetTime,MidPerson),MetHistory);mymember(met(MidPerson,MetTime,StartPerson),MetHistory)),
    contact4(infect(MidPerson,MetTime),infect(GoalPerson,Goaltime),[(met(StartPerson,MetTime,MidPerson)),(met(MidPerson,MetTime,StartPerson))|MetHistory],InfectionPath).

(BTW, your code is very hard to read if you don't use any spaces. It's a good idea to add a space after each , and around each ; and | and other operators.)

This behaves like this:

?- contact(infect(john,31),infect(paul,11),ZS).
ZS = [infect(mary, 28), infect(mark, 23), infect(paul, 17)] ;
ZS = [infect(anne, 29), infect(mary, 24), infect(mark, 23), infect(paul, 17)] ;
false.

Upvotes: 2

Related Questions