4. [20 points] Escape from the Vault
Tokyo, Rio, Berlin and Denver have just looted the Museum of Modern Arts and need to cross the Kosciusko Bridge in order to reach a deserted runway where Professor Plock¡¯s aeroplane is waiting for them. However, the bridge is fragile and can hold at most two of them at the same time. Moreover, to cross the bridge a flashlight is needed to avoid traps and broken parts. The problem is that there is only one flashlight with one battery that lasts for only 60 minutes. Each of them need different times to cross the bridge (in either direction):
10 minutes
20 minutes
Copyright By PowCoder代写 加微信 powcoder
25 minutes
Since there can be only two people on the bridge at the same time, they cannot cross the bridge all at once. Since they need the flashlight to cross the bridge, whenever two have crossed the bridge, somebody has to go back and bring the flashlight to the people on the other side that still have to cross the bridge. The problem now is: In which order can the above four cross the bridge in time (that is, in 60 minutes) to be saved from getting caught? Being the mastermind of the heist, you need to find the answer to the above conundrum. You could have solved the problem in your head, had you not been day drinking. The only possible way for you now is to try all possible combinations. Curiously, the alcohol seems to have no effect on your ability to write logically correct software. So, you decide to write some Prolog rules to answer this.
Writing a Prolog program for solving the riddle is in principle a rather straightforward task (using backtracking) once one has figured out how to formulate the solution. The most difficult part is to find an appropriate term representation for the states of the search problem, i.e., the position of people on either side of the bridge and the position of the flashlight. We are going to develop one such idea here. Let us assume that initially, everyone is on the left side of the bridge and want to cross over to the right side. We represent intermediate states of a bridge crossing by facts of the form st(P,L) where L is a list giving the people that are currently on the left side of the bridge and where P is a flag that indicates the position (left or right side) of the flashlight. We denote movement from left to right as the rule r(L1) where L1 is a list of people who move from left to right. Similarly, we define l(L2) to denote movement from right to left.
1. Writearuletime(P,T)whereTisthetimetakenbypersonPtocrossthebridge(ineitherdirection).
2. Write a fact team(T) where T is a list of all four people who need to cross the bridge.
3. Write a rule cost(L,C) where C is the maximum time required for all the people in list L to cross the bridge (in either direction), assuming that they all can cross the bridge simultaneously.
4. Write two rules move(st(l,L1), st(r,L2), r(M), C) and move(st(r,L1), st(l,L2), l(M), C), where:
move(st(l,L1), st(r,L2), r(M), C): This movement is generated if the flashlight is on the left side of the bridge. C is the time required to move people contained in the list M from left to right, where st(l,L1) is the old state and st(r,L2) is the new state. In this case, the time is determined by the predicate cost/2. The list M of people to move to the right is computed by the predicate split/3, which computes lists of length 2, which are sorted to avoid redundancy caused by representing groups of people as lists. Implementation of split/3 is provided to you:
split(L,[X,Y],M) :-
member(X,L),
member(Y,L),
compare(<,X,Y), subtract(L,[X,Y],M). Here, M is the list after removing X and Y from the list L. move(st(r,L1), st(l,L2), l(M), C): This movement is generated if the flashlight is on the right side of the bridge. C is the time required to move people contained in the list M from right to left on the bridge, where st(r,L1) is the old state and st(l,L2) is the new state. In this move, it makes sense to send back only one person. Therefore, the definition of move for this case uses the predefined member/2 1 predicate and computes the time by simply looking into the rule time/2. 5. Finally, the trans/4 predicate generates all possible bridge crossings together with the required time, i.e., write a rule trans(I,F,M,C) where C is the amount of time needed to reach the final state F from initial state I and M is the ordered list of movements(refer to the example below for a clear understanding). The cross/2 predicate formulates the search problem by giving the initial and final configuration of the search space. The definition of cross/2 is as follows: cross(M,D) :- trans(st(l,T),st(r,[]),M,D0), The solution to the original problem is then given by: solution(M) :- cross(M,60). There are two possible answers to the above problem. So, upon executing solution/1 the final output should be: ?- solution(M). M = [r([rio, tokyo]), l(tokyo), r([berlin, denver]), l(rio), r([rio, tokyo])] ; M = [r([rio, tokyo]), l(rio), r([berlin, denver]), l(tokyo), r([rio, tokyo])] . Note: The order of the above solutions does not matter. 1https://www.swi-prolog.org/pldoc/man?predicate=member/2 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com