% ES 95 Midterm Exam Solutions

% Solution to Problem 1


member(E,[E|_]).
member(E,[_|T]):-member(E,T).

pickFoods(Avail,Cal,Poss):-
     pickFoods1(Avail,Cal,[],0,Poss).

% pickFoods1(Avail,Cal,NotChosen,CalSoFar,Chosen) does the actual work.
% Avail is the list of available foods. pickFoods1 will examine one
%  of these and do a recursive call on the rest.
% Cal is the energy limit for the meal. It does not change with recursion.
% NotChosen is a list of foods which were considered but not chosen for
%  the meal.
% CalSoFar is the energy in the foods chosen so far. These foods
%  are held in the instances "above".
% Chosen is the list of foods chosen by pickFoods1.



% Add a food (Food) to the Chosen list.
%
pickFoods1([Food|More],Cal,NotChosen,SoFar,[Food|ChosenBelow]):-
        food(Food,FC),
	Next is SoFar+FC,
	Next =< Cal,
	pickFoods1(More,Cal,NotChosen,Next,ChosenBelow).

% Do not add food to Chosen list. Instead it is added to the NotChosen
% list.
%
pickFoods1([FoodOmitted|More],Cal,NotChosen,SoFar,ChosenBelow):-
     pickFoods1(More,Cal,[FoodOmitted|NotChosen],SoFar,ChosenBelow).

% No more foods in Avail list. If any of the NotChosen foods could
% be added to the list then fail. Otherwise succeed. (Failure would
% result in backtracking which in turn would result in the food
% being added to the list.)
%
pickFoods1([],Cal,NotChosen,SoFar,[]):-
     Rem is Cal-SoFar,
     not((food(F,C),member(F,NotChosen),C=<Rem)).

food(apple,70). food(candyCorn,200).  food(coke,160). food(broccoli,50).
food(lowFatTwinkie,90).


% Solution to Problem 2.

% Three predicates are used here. matchList initializes mL1.
% mL1 scans BigList, calling mL2 at each character position.
% mL2(A,B) Does the actual comparison. It suceeds only every element
%  in B matches the corresponding element in A.
 
matchList(BigList,LittleList,Locs):-
	mL1(BigList,1,LittleList,Locs).

mL1([H|T],Pos,LL,Locs):-
	( mL2([H|T],LL),Locs=[Pos|Locs2]
	  ;
	  Locs=Locs2
	),
	PM is Pos + 1,
	mL1(T,PM,LL,Locs2).
mL1([],_,_,[]).

mL2([H|T],[H|T2]):-mL2(T,T2).
mL2(_,[]).


% Data for Problem 3.

h(a).
h(b).
g(X,_,X).
g(X,X,_).
g(_,X,X).
j(X,X):-!.
j(_,_).
a(q).
a(r).
b(r).
b(q).
c(s).

% Solution to Problem 3.

%  C-Prolog version 1.5
%  | ?- ['es95mid.pro'].
%  es95mid.pro consulted 2152 bytes 0.0166667 sec.
%  
%  yes
%  | ?-  h(X),write(X),fail.
%  ab
%  no
%  | ?-  h(X),h(Y),write(got(X,Y)),fail.
%  got(a,a)got(a,b)got(b,a)got(b,b)
%  no
%  | ?-  a(X),b(Y),c(Z),g(X,Y,Z).
%  
%  X = q
%  Y = q
%  Z = s 
%  
%  yes
%  | ?-  j(X,Y),a(X),b(Y),c(Z),j(Y,Z).
%  
%  X = q
%  Y = q
%  Z = s 
%  
%  yes
%  | ?- 

% Problem 3b:
%  Pro:
%   E.S. might determine if box's contents are fragile. (Weak box,
%   clinking sounds, etc.) This could not be done by a conventional
%   program.
%  There might be many factors to consider when positioning a box in a
%   truck, for example crushability, weight, stability, etc. These
%   might be difficult to express using a conventional program.
% 
%  Con:
%   Arranging boxes by size, weight, and fragility to fit in a truck
%    without damage could be done using conventional programming techniques.
%   Movers do a good job arranging boxes, so domain experts are readily
%    available and can do a good job.
%