Solutions for Session 9

Merge sort

• gt(X,Y):- X > Y.
  
  merge([],L,L).
  merge(L,[],L).
  merge([H1|T1],[H2|T2],[H1|Res]):-
          gt(H2,H1), !,
          merge(T1,[H2|T2],Res).
  merge([H1|T1],[H2|T2],[H2|Res]):-
          merge([H1|T1],T2,Res).
  

• split([],[],[]).
  split([A],[A],[]).
  split([A,B|T],[A|S1],[B|S2]):-
          split(T,S1,S2).
  

• mergesort([],[]).
  mergesort([X],[X]).
  mergesort([X,Y|T],S):-
          split([X,Y|T],L1,L2),
          mergesort(L1,S1),
          mergesort(L2,S2),
          merge(S1,S2,S).
  

• merge_unique([],L,L).
  merge_unique(L,[],L).
  merge_unique([H|T1],[H|T2],[H|Res]):-
          !, merge_unique(T1,T2,Res).
  merge_unique([H1|T1],[H2|T2],[H1|Res]):-
          gt(H2,H1), !,
          merge_unique(T1,[H2|T2],Res).
  merge_unique([H1|T1],[H2|T2],[H2|Res]):-
          merge_unique([H1|T1],T2,Res).
  
  mergesort_unique([],[]).
  mergesort_unique([X],[X]).
  mergesort_unique([X,Y|T],S):-
          split([X,Y|T],L1,L2),
          mergesort_unique(L1,S1),
          mergesort_unique(L2,S2),
          merge_unique(S1,S2,S).
  

• To sort these moves you do not need to change anything in the split/3, merge/3 or mergesort/2 predicates. The only thing that needs to change is the gt/2 predicate:

  gt(move(_,A,_),move(_,B,_)):- B>A.
  gt(move(_,N,A),move(_,N,B)):- A>B.
  

Searching

• For 4 given cubes (with given figures), we can find the number of correct stacks by using the findall-predicate on generate_and_test/2. Finding cubes such that there are exactly 2 correct stacks, is then done by a generate-and-test approach: generate 4 cubes and test them (check if the number of correct stacks is 2), if necessary backtrack and find other cubes.

  find_4_cubes:-
       % generate 4 cubes:
       generate_cube(C1),
       generate_cube(C2),
       generate_cube(C3),
       generate_cube(C4),
       % test the cubes:
       findall(Sol,generate_and_test([C1,C2,C3,C4],Sol),SolutionList),
       length(SolutionList,2),
       write([C1,C2,C3,C4]).
  
  generate_cube(cube(T,Bo,F,L,Ba,R):-
       % each side can be circle, triangle, rectangle or star
       member(T,[c,t,r,s]),
       member(Bo,[c,t,r,s]),
       member(F,[c,t,r,s]),
       member(L,[c,t,r,s]),
       member(Ba,[c,t,r,s]),
       member(R,[c,t,r,s]).
  

  Note that this strategy might be very slow in practice since we are using generate-and-test nested inside another generate-and-test (i.e. the generation of stacks from session5 is nested inside generating labelings).


• We use the following representation for a state: t(M,C,B) where M (resp B) stands for the number of missionaries (resp cannibals) on the start-shore and B stands for the shore where the boat is (-1 for start-shore, 1 for end-shore).

  solve:- search(t(3,3,-1),[t(3,3,-1)],Trace), write(Trace).
  
  search(State,Trace,Trace):-
          solution(State).
  
  search(State,AccTrace,Trace):-
          try_action(State,NewState),
          validate_state(NewState),
          no_loop(NewState,AccTrace),
          search(NewState,[NewState|AccTrace],Trace).
  
  % desired end state is t(0,0,1).
  solution(t(0,0,1)).
  
  
  try_action(t(M,C,-1),t(NewM,NewC,1)):- 
  	% boat goes from start-shore to end-shore
          cross_start_to_end(M,C,2,NewM,NewC); %either 2 people cross ...
  	cross_start_to_end(M,C,1,NewM,NewC). % ... or only 1.
  
  try_action(t(M,C,1),t(NewM,NewC,-1)):- 
  	% boat goes from end-shore to start-shore
          cross_end_to_start(M,C,2,NewM,NewC); %either 2 people cross ...
  	cross_end_to_start(M,C,1,NewM,NewC). % ... or only 1.
  
  
  cross_start_to_end(M,C,0,M,C):- !.
  
  cross_start_to_end(M,C,N,NewM,NewC):-
  	M2 is M-1,  % let a missionary cross
  	M2>=0,
  	N1 is N-1,
  	cross_start_to_end(M2,C,N1,NewM,NewC).
  
  cross_start_to_end(M,C,N,NewM,NewC):-
  	C2 is C-1,  % let a cannibal cross
  	C2>=0,
  	N1 is N-1,
  	cross_start_to_end(M,C2,N1,NewM,NewC).
  
  cross_end_to_start(M,C,0,M,C):- !.
  
  cross_end_to_start(M,C,N,NewM,NewC):-
  	M2 is M+1,  % let a missionary cross
  	M2=<3,
  	N1 is N-1,
  	cross_end_to_start(M2,C,N1,NewM,NewC).
  
  cross_end_to_start(M,C,N,NewM,NewC):-
  	C2 is C+1,  % let a cannibal cross
  	C2=<3,
  	N1 is N-1,
  	cross_end_to_start(M,C2,N1,NewM,NewC).
  
  validate_state(t(M,C,_)):-
          OtherM is 3 - M,
          OtherC is 3 - C,
          nobody_eaten(M,C),  % start-shore
          nobody_eaten(OtherM,OtherC). % end-shore
  
  nobody_eaten(0,_). % no missionaries
  nobody_eaten(M,C):-
          C =< M. % not more cannibals than missionaries.
  
  
  no_loop(_,[]).
  no_loop(State,[OtherState|Tail]):-
          not(State=OtherState),
          no_loop(State,Tail).
  

  The query ?- solve. gives the following result:
  [t(0, 0, 1), t(1, 1, -1), t(0, 1, 1), t(0, 3, -1), t(0, 2, 1), t(2, 2, -1), t(1, 1, 1), t(3, 1, -1), t(3, 0, 1), t(3, 2, -1), t(2, 2, 1), t(3, 3, -1)]
  Note that the Trace is in reverse chronological order since we used an accumulator.