> Hi, I see you have a lot of solutions to puzzles her, but i still miss > one, maybe you are familiar with it. It is the crossing the river > problem. 4 people need to cross the river with only one flashlight and > the bridge can only hold 2 persons at a time, it takes person 1: 10 > minutes ,person2: 5, person3: 2 and person4: 1 minute and they need to > cross the bridge in 17 minutes. so i hope you can solve this in prolog! > i'm looking forward to the publishing online Here is a program to do this. I wrote it when I was learning ECLiPSe, so the implementation could be a lot better, e.g. you have to fix the number of actions (i.e. bridge crossings) in advance. Still, it does find the optimal solution to Mr Zhu's puzzle. The query to start the search is: cross_bridge([john, paul, george, ringo]). (when I read the problem statement, the bridge-crossers were the fab four). josh Developer, Parc Technologies Limited josh.singer@parc-technologies.com http://www.parc-technologies.com This e-mail message is for the sole use of the intended recipient(s) -its contents are the property of Parc Technologies Limited (or its licensors) and are confidential. Please do not copy, review, use (except for the intended purposes), disclose or distribute the e-mail or its contents (or allow anyone else to do so) without our prior permission. Parc Technologies Limited does not guarantee that this e-mail has not been intercepted and amended nor that it is virus-free. You should carry out your own virus checks before opening any attachment. Any opinions expressed in this e-mail message are those of the author and not necessarily Parc Technologies Limited. -- :- lib(fd_global). :- lib(fd). :- lib(lists). % The time that each band member takes to cross the bridge. time(john, 1). time(paul, 2). time(george, 5). time(ringo, 10). % The maximum number of action periods in each band member's plan max_actions(7). % given a list of band members find the optimal plan for crossing the % bridge and print it out. cross_bridge(BandMembers):- % create the variables + their domains create_plans_and_locations(BandMembers, BandPL), max_actions(MaxActions), % ActionTimes is a list of integers: each element % is the duration of the corresponding action period length(ActionTimes, MaxActions), MaxTime is MaxActions + 1, % TorchLocation is a list: element i is the location of the torch % at the beginning of action period i length(TorchLocations, MaxTime), TorchLocations :: [here, there], % post the constraints post_constraints(BandPL, ActionTimes, TorchLocations, Time), % allocate values to all plan variables, minimising the time taken get_plans(BandPL, Plan), flatten(Plan, AllActions), minimize(labeling(AllActions), Time), write_pretty_plan(Time, BandPL, TorchLocations). % given a list of band members, return a list of elements of the form % m(MemberName, Plans, Locations) where % Plans is a list of MaxActions action variables and % Locations is a list of MaxActions+1 location variables create_plans_and_locations([], []):-!. create_plans_and_locations([M1|Rest], [m(M1, Plans, Locations)|RestPlans]):- max_actions(MaxActions), length(Plans, MaxActions), Plans :: [no_op, cross_here2there, cross_there2here], MaxTime is MaxActions + 1, length(Locations, MaxTime), Locations :: [here, there], create_plans_and_locations(Rest, RestPlans). % post the various constraints post_constraints(BandPL, ActionTimes, TorchLocations, Time):- % Time equals the sum of the ActionTimes time_constraints(ActionTimes, Time), % The action time at each step is the maximum action time % of any band member at each step. This predicate sets up a % list of action times for each band member, relates these to % the action performed, and then sets the corresponding % action time to be the maximum length of any action performed % at that time. determine_action_times(ActionTimes, BandPL), % all band members must start here and finish there start_here_finish_there(BandPL), % you can only cross to there when you are here and vice versa. % if you cross to there, you end up there, if you cross to here, % you end up here. % you can only cross the ravine on the bridge (there is no other % way of changing your location crossing_conditions(BandPL), % only two members can cross at once two_members_at_once(BandPL), % Anyone who crosses must have a torch, and they carry it across. must_have_torch(BandPL, TorchLocations), % The torch must be carried by someone crossing % (it cannot leap across of its own accord). torch_must_be_carried(BandPL, TorchLocations). time_constraints(ActionTimes, Time):- sumlist(ActionTimes, Time). determine_action_times(ActionTimes, BandPL):- % create a list of lists of action times, 1 list per band member, % and constrain the band member action time according to the action create_and_constrain_band_action_times(BandPL, BandActionTimes), % set the action time to be the maximum band member action time % at each point constrain_action_time(ActionTimes, BandActionTimes). create_and_constrain_band_action_times([],[]):-!. create_and_constrain_band_action_times([m(BandMember, Actions, _)|RestBandPL], [ActionTimes|RestActionTimes]):- time(BandMember, CrossingTime), % create ActionTimes as a list of length MaxActions max_actions(MaxActions), length(ActionTimes, MaxActions), % constrain the values in ActionTimes to be dependent on the Actions % taken in Actions band_member_action_time(CrossingTime, Actions, ActionTimes), create_and_constrain_band_action_times(RestBandPL, RestActionTimes). band_member_action_time(_, [], []):-!. band_member_action_time(CrossingTime, [Action1|RestAction], [ActionTime1|RestActionTime]):- % if the action is no_op then the time taken is 0 (Action1 #= no_op) #=> (ActionTime1 #= 0), % if the action is cross, the time taken is CrossingTime (Action1 #= cross_here2there) #=> (ActionTime1 #= CrossingTime), (Action1 #= cross_there2here) #=> (ActionTime1 #= CrossingTime), band_member_action_time(CrossingTime, RestAction, RestActionTime). % Constrain the amount of time taken in each period to be the maximum time % taken by any band member in that period. constrain_action_time([], _):-!. constrain_action_time([ActionTime1|RestActionTimes], BandActionTimes):- % get all the amounts of time taken by band members in the current % period get_heads(BandActionTimes, Heads, NewBandActionTimes), % the amount of time taken is the maximum of these. maxlist(Heads, ActionTime1), constrain_action_time(RestActionTimes, NewBandActionTimes). % constrain the first and last elements of the Locations lists to be here and % there respectively. start_here_finish_there([]):-!. start_here_finish_there([m(_, _, Locations)|RestPL]):- Locations = [FirstLoc|_], FirstLoc #= here, reverse(Locations, [LastLoc|_]), LastLoc #= there, start_here_finish_there(RestPL). % capture the concept of crossing for each band member. crossing_conditions([]):-!. crossing_conditions([m(_, Plans, Locations)| RestPL]):- band_member_crossing_conditions(Plans, Locations), crossing_conditions(RestPL). % capture the concept of crossing for each action. band_member_crossing_conditions([], _):-!. band_member_crossing_conditions([Action1|RestAction], [Loc1, Loc2|RestLoc]):- % the bandmember is crossing from here2there iff he starts % here and ends there. (Action1 #= cross_here2there) #<=> (Loc1 #= here #/\ Loc2 #= there), % the bandmember is crossing from there2here iff he starts % there and ends here. (Action1 #= cross_there2here) #<=> (Loc1 #= there #/\ Loc2 #= here), band_member_crossing_conditions(RestAction, [Loc2 | RestLoc]). % no more than two members may cross at once. two_members_at_once(BandPL):- get_plans(BandPL, BandP), two_members_at_once_aux(BandP). two_members_at_once_aux([[]|_]):-!. two_members_at_once_aux(BandP):- % heads is all band members actions at the current period. get_heads(BandP, Heads, NewBandP), % C1 is the number crossing from here to there. occurrences(cross_here2there, Heads, C1), % C2 is the number crossing from there to here. occurrences(cross_there2here, Heads, C2), % no more than 2 C1 + C2 #<= 2, two_members_at_once_aux(NewBandP). % anyone crossing must have the torch with them % impose this constraint for each band member individually. must_have_torch([], _):-!. must_have_torch([m(_, MPlans, _)|RestPL], TorchLocations):- band_member_must_have_torch(MPlans, TorchLocations), must_have_torch(RestPL, TorchLocations). band_member_must_have_torch([], _):-!. band_member_must_have_torch([Action1|RestActions], [T1, T2 | RestTorchLocations]):- % if action is crossing, torch must cross in same direction at same % time (Action1 #= cross_here2there) #=> (T1 #= here #/\ T2 #= there), (Action1 #= cross_there2here) #=> (T1 #= there #/\ T2 #= here), band_member_must_have_torch(RestActions, [T2 | RestTorchLocations]). torch_must_be_carried(BandPL, TorchLocations):- get_plans(BandPL, BandP), torch_must_be_carried_aux(BandP, TorchLocations). % Apply for each action period torch_must_be_carried_aux(_, [_]):-!. torch_must_be_carried_aux(BandP, [TL1, TL2 | RestTL]):- % heads is the set of actions executed this period get_heads(BandP, Heads, NewBandP), % N1 and N2 are the number of band members crossing in % each direction occurrences(cross_here2there, Heads, N1), occurrences(cross_there2here, Heads, N2), % if the torch moves there, at least one band member must be % crossing in that direction (to carry it) (TL1 #= here #/\ TL2 #= there) #=> (N1 #>= 1), % similarly for the other direction (TL1 #= there #/\ TL2 #= here) #=> (N2 #>= 1), torch_must_be_carried_aux(NewBandP, [TL2 | RestTL]). % Extract a list of action lists from a list of m/3 terms get_plans([],[]):-!. get_plans([m(_, P, _)| RestPL], [P | RestP]):- get_plans(RestPL, RestP). % given a list of list, return a list of heads and a list of decapitated lists. get_heads([], [], []):-!. get_heads([[I1Head|I1Rest]|InputRest], [I1Head|RestHeads], [I1Rest|RestRests]):- get_heads(InputRest, RestHeads, RestRests). write_pretty_plan(Time, Plan, TorchLocations):- write("Solution which took time "), write(Time), writeln(":"), write_pretty_plan_aux(Plan, _, TorchLocations, 0). write_pretty_plan_aux(_,_,[], _):-!. write_pretty_plan_aux(PlanIn,PlanOut,[TL1|RestTL], Time):- write("The torch is "), writeln(TL1), write("Time taken: "), writeln(Time), write_pretty_actions(PlanIn, PlanMid, 0, ActionTime), NewTime is Time + ActionTime, write_pretty_plan_aux(PlanMid, PlanOut, RestTL, NewTime). write_pretty_actions([], [], A, A):-!. write_pretty_actions([m(Name, [], _)|RestBandIn], [m(Name, [], _)|RestBandOut], A, B):- !, write_pretty_actions(RestBandIn, RestBandOut, A, B). write_pretty_actions([m(Name, [no_op|ActRest], _)|RestBandIn], [m(Name, ActRest, _)|RestBandOut], A, B):- !, write_pretty_actions(RestBandIn, RestBandOut, A, B). write_pretty_actions([m(Name, [cross_here2there|ActRest], _)|RestBandIn], [m(Name, ActRest, _)|RestBandOut], A, NewA):- !, time(Name, NA), max(A, NA, MidA), write(Name), writeln(" crosses over to the other side"), write_pretty_actions(RestBandIn, RestBandOut, MidA, NewA). write_pretty_actions([m(Name, [cross_there2here|ActRest], _)|RestBandIn], [m(Name, ActRest, _)|RestBandOut], A, NewA):- time(Name, NA), max(A, NA, MidA), write(Name), writeln(" crosses back over to this side"), write_pretty_actions(RestBandIn, RestBandOut, MidA, NewA).Received on Fri Jan 04 14:52:43 2002
This archive was generated by hypermail 2.1.8 : Wed 16 Nov 2005 06:07:12 PM GMT GMT