RE: Fw: Logic Puzzle

From: josh singer <>
Date: Fri 04 Jan 2002 12:34:53 PM GMT
Message-ID: <0B9686DD2E83D411B67200508B9A9DA255F7AA@LON-SRV2>
> 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).


Developer, Parc Technologies Limited

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


% given a list of band members find the optimal plan for crossing the 
% bridge and print it out.

	% create the variables + their domains
	create_plans_and_locations(BandMembers, BandPL),
	% 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]):-
	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
	% 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
	% only two members can cross at once
	% 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([m(BandMember, Actions,
	time(BandMember, CrossingTime),
	% create ActionTimes as a list of length 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], 
	% 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([], _):-!.

	% 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
% there respectively.


start_here_finish_there([m(_, _, Locations)|RestPL]):-
	Locations = [FirstLoc|_],
	FirstLoc #= here,
	reverse(Locations, [LastLoc|_]),
	LastLoc #= there,

% capture the concept of crossing for each band member.


crossing_conditions([m(_, Plans, Locations)| RestPL]):-
	band_member_crossing_conditions(Plans, Locations), 

% capture the concept of crossing for each action.

band_member_crossing_conditions([], _):-!.

	                           [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.

	get_plans(BandPL, 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, 

% 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([], _):-!. 

	[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([m(_, P, _)| RestPL], [P | RestP]):-
	get_plans(RestPL, RestP).

% given a list of list, return a list of heads and a list of decapitated

get_heads([], [], []):-!.

get_heads([[I1Head|I1Rest]|InputRest], [I1Head|RestHeads], 
	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 "),
	write("Time taken: "),
	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),
	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),
	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