/* crossing4.pl code with dump_vrml v0.02 2/10/99 2pm -cut (!) added to find_count for v0.01 -changes to move_from Load added to parmameter list -changes to select_passengers 3 vrml_dump_state lines added */ /* to run this program copy the file cprolog from the class account. Then give the command cprolog Inside the prolog interpreter give the line ['crossing.pl']. Be sure to include the . it is the terminator character for PROLOG To run the program give the command trip. When you make changes to the file be very careful about upper and lower case characters. The language is case sensitive. In addition, if the first character is a capital, it is a variable, else it is a literal. */ /* starting from a copy of crossing3.pl 2/9/99 added code to dump VRML visializations. Change to existing code in the select_passengers routine */ /* do the full crossing problem */ trip :- init(List), crossings(List,ListNew). /* trip2 is a debugging tool, it is used to see if starting in the stopping position the program will stop*/ trip2:- init([Side1,Side2]), crossings([Side2,Side1],ListNew). /* do the sequence of crosssings */ crossings(List,List) :- done(List). crossings(List,ListNew) :- write(about_to_try_crossings),write(List),nl, write(before_do_crossing),write(List),nl, do_crossing(List,ListNew1), write(after_do_crossing),write(ListNew1),nl, crossings(ListNew1,ListNew),write(after_crossings),write(ListNew),nl. /* do a single crossing */ do_crossing(List,ListNew) :- write(about_to_try_do_crossing),nl, select_passengers(List,ListNew), write(about_to_try_stop_repeats),write(ListNew),nl, stop_repeats(ListNew). write(after_stop_repeats_newstoplist),nl, write(end_of_do_crossing),write(ListNew),nl. /* starting values, all on side1, none on side2 */ :- dynamic looked_at/1. init([[boat,father,son1,son2],[]]):- retractall(looked_at(X)),asserta(looked_at( junk)). looked_at(junk). retractall(X) :- retract(X). retractall(_). /* succeed if boat and all passengers at side2 */ done([[],Side2]) :- write(trying_done),write(Side2),nl, set_equal([boat,father,son1,son2],Side2). /* pick subset of passengers from boat side and give result on moving boat and boat load */ select_passengers([Side1,Side2],[Side1New,Side2New]) :- write(select_passengers1),write(Side1),write(Side2),nl, member(boat,Side1),move_from(Side1,Side2,Load,Side1New,Side2New), write([Side1,Load,Side2,Side1New,Side2New]),/*debug*/ vrml_step_state(StateNum1),vrml_dump_state(Side1,StateNum1,1,blue), vrml_step_state(StateNum2),vrml_dump_state([boat|Load],StateNum2,2,red), vrml_step_state(StateNum3),vrml_dump_state(Side2New,StateNum3,3,blue). select_passengers([Side1,Side2],[Side1New,Side2New]) :- write(select_passengers2),write(Side1),write(Side2),nl, member(boat,Side2),move_from(Side2,Side1,Load,Side2New,Side1New), vrml_step_state(StateNum1),vrml_dump_state(Side2,StateNum1,3,blue), vrml_step_state(StateNum2),vrml_dump_state([boat|Load],StateNum2,2,red), vrml_step_state(StateNum3),vrml_dump_state(Side1New,StateNum3,1,blue). /* select passengers and do the move */ move_from(SideA,SideB,Load,SideANew,SideBNew) :- write(move_from),write(SideA),write(SideB),nl, member_out(boat,SideA,SideA2), select_subset(Load,SideA2),setminus(Load,SideA2,SideANew), check_load(Load), write(using_load_of),write(Load),nl, setplus(Load,SideB,SideB2), setplus([boat],SideB2,SideBNew), write(end_of_move_from),write(SideBNew),nl. stop_repeats([Side1,Side2]) :- number_of(f,Side2,FatherCount), number_of(b,Side2,BoatCount), number_of(s,Side2,SonCount), !,add_new([BoatCount,FatherCount,SonCount]). add_new(Side) :- looked_at(Side),!,fail. add_new(Side) :- asserta(looked_at(Side)). /* succeed if boat not overloaded*/ check_load(Load) :- subset([father,son1],Load),!,fail. check_load(Load) :- subset([father,son2],Load),!,fail. check_load([]) :- !,fail. check_load(Load). /* member(Item,List): succeed if Item is in List */ member(Item,[Item|_]). member(Item,[_|RestList]) :- member(Item,RestList). /* subset(L1,LFull): succeed if L1 is a subset of LFull, the items in L1 can be in any order */ subset([],List). subset([A|RestA],B) :- member_out(A,B,B1), subset(RestA,B1). /* member_out(Item,ListOld,ListNew): remove Item from ListOld giving ListNew */ member_out(Item,[Item|BNew],BNew). member_out(Item,[B|BRest],[B|BRestNew]) :- member_out(Item,BRest,BRestNew). /* set_member(Set,List_of_Sets): succeed if Set is a set found in the list of sets List_of_Sets */ set_member(Set,[Set|SetList]). set_member(Set,[MSet|SetList]) :- set_equal(Set,MSet). set_member(Set,[MSet|SetList]) :- set_member(Set,SetList). setminus(Set,[],[]). setminus(Set,Set,[]). setminus([],Set,Set). setminus([A|RestA],Set,NewSet) :- nonvar(Set),member_out(A,Set,Set2),setminus(RestA,Set2,NewSet). setminus([A|RestA],Set,NewSet) :- nonvar(NewSet),member_out(A,NewSet,Set2),setminus(RestA,Set,Set2). setplus([],A,A). setplus(A,[],A). setplus([A|RA],[B|RB],[A,B|Combine]) :- setplus(RA,RB,Combine). /* set_equal(Set1,Set2): succeed if the two sets are equal. N.B. can not just check for equal because of differnt orders to the lists */ set_equal([],[]). set_equal([A|RestA],MSet) :- member_out(A,MSet,MSetNew),set_equal(RestA,MSetNew). select_subset([],[]). /* use instead of subset so not permutations */ select_subset(AR,[B|BR]) :- select_subset(AR,BR). select_subset([B|AR],[B|BR]) :- select_subset(AR,BR). set_equal(A,B) :- subset(A,B),subset(B,A). /* number_of(Letter,List,Num):go through List and count the number of elements with a first letter of Letter and return the count in Num */ number_of(_,[],0). number_of(Letter,[B|BRest],Num) :- name(Letter,[L|_]),name(B,[L|_]),!, number_of(Letter,BRest,Num2),Num is Num2 + 1. number_of(Letter,[B|BRest],Num) :- number_of(Letter,BRest,Num). /*---------------------------------*/ /* start of dump_vrml support code */ /*---------------------------------*/ :- dynamic vrml/3. :- dynamic vrml_state_num/1. find_count(State,Pool,Add,Count) :- vrml(State,Pool,Count),!, CountP1 is Count + Add + 1, retract(vrml(State,Pool,Count)), asserta(vrml(State,Pool,CountP1)). find_count(State,Pool,Add,0) :- NewLoc is Add + 1, asserta(vrml(State,Pool,NewLoc)). vrml_step_state(StateNum) :- vrml_state_num(StateNum), retract(vrml_state_num(StateNum)), NewState is StateNum + 1, asserta(vrml_state_num(NewState)). vrml_state_num(0). vrml_dump_state2(XX,StateNum,Pool,Color) :- nl,write([vrml_dump_state,XX,StateNum,Pool,Color]),nl, vrml_dump_state(XX,StateNum,Pool,Color). vrml_dump_state([],StateNum,Pool,Color). vrml_dump_state([Item|List],StateNum,Pool,Color) :- dump_vrml(Item,StateNum,Pool,Color), vrml_dump_state(List,StateNum,Pool,Color). dump_vrml(Name,State,Pool,Color) :- vrml_db(Name,Image,SizeX,SizeY,SizeZ), find_count(State,Pool,SizeX,Count), write(vR),write(mL), /* marker seperated to stop trapping */ /* the command listing */ /* write(object(box,Name,State,Pool,Count,SizeX,SizeY,SizeZ,Color)), */ Lineloc is Count + 20 * Pool, NegState is -(2*State ), write(object(box,Name,Lineloc,NegState,0,SizeX,SizeY,SizeZ,Color)), write(v),write(rML). vrml_db(s1,son1,1,2,0.25). vrml_db(son1,son1,1,2,0.25). vrml_db(s2,son2,1,2,0.25). vrml_db(son2,son2,1,2,0.25). vrml_db(f,father,1,3,0.25). vrml_db(father,father,1,3,0.25). vrml_db(b,boat,4,1,1). vrml_db(boat,boat,4,1,1). vrml(-1,-1,-1). testdump :- dump_vrml(s1,1,1,red),dump_vrml(s2,1,1,blue), dump_vrml(b,1,2,blue), dump_vrml(f,2,2,green). dump_demo :- dump_vrml(s1,1,1,red), dump_vrml(s2,1,1,red), dump_vrml(f,1,1,red), dump_vrml(b,1,1,red), dump_vrml(s1,2,2,blue), dump_vrml(s2,2,2,blue), dump_vrml(b,2,2,blue), dump_vrml(s1,3,3,green), dump_vrml(s2,3,3,green), dump_vrml(b,3,3,green), dump_vrml(s1,4,2,blue), dump_vrml(b,4,2,blue), dump_vrml(s1,5,1,red), dump_vrml(f,5,1,red), dump_vrml(b,5,1,red), dump_vrml(f,6,2,blue), dump_vrml(b,6,2,blue), dump_vrml(s2,7,3,green), dump_vrml(f,7,3,green), dump_vrml(b,7,3,green), dump_vrml(s2,8,2,blue), dump_vrml(b,8,2,blue), dump_vrml(s1,8,1,red), dump_vrml(s2,8,1,red), dump_vrml(b,8,1,red), dump_vrml(s1,9,2,blue), dump_vrml(s2,9,2,blue), dump_vrml(b,9,2,blue), dump_vrml(s1,10,3,green), dump_vrml(s2,10,3,green), dump_vrml(f,10,3,green), dump_vrml(b,10,3,green).