% Question 1

:- dynamic count/2.
freq(L) :- retractall(count(_,_)), freq_act(L).
freq_act([]).
freq_act([Code|L]) :-
  char_code(C,Code),
  freq_code(C,L).

freq_code(C,L) :-
  retract(count(C,OldN)),
  !,NewN is OldN + 1,
  assert(count(C,NewN)),
  freq_act(L).
freq_code(C,L) :-
  assert(count(C,1)),
  freq_act(L).


% Question 2

deref(X-Struct,Ref,CurrentStruct) :-
   var(X), Ref = X, CurrentStruct = Struct.
deref(X-_Struct,Ref,CurrentStruct) :-
   nonvar(X), deref(X,Ref,CurrentStruct).

% or use shallow cuts:
% deref(X-Struct,Ref,CurrentStruct) :-
%   var(X) -> Ref = X, CurrentStruct = Struct
%  ; deref(X,Ref,CurrentStruct).

append([],L,L).
append([E|L1],L2,[E|L3]) :- append(L1,L2,L3).

make(Elt,[(_Ref-[Elt])-Elt]).
combine(M1,M2,M) :-
  append(M1,M2,UnSortedM), sort(UnSortedM,M).
find(Elt,Mapping,Ref-Struct) :-
  member(SetRef-Elt,Mapping),
  deref(SetRef,Ref,Struct).
union(Set1,Set2) :-
  deref(Set1,Ref1,Struct1),  % may not need these, depending on contract
  deref(Set2,Ref2,Struct2),  % but good practice to do so
  Ref1 = Ref2,
  append(Struct1,Struct2,NewStruct),
  sort(NewStruct,UnionStruct),
  Ref1 = _NewRef-UnionStruct.

makec(Elt,[_Set-Elt]).
combinec(M1,M2,M) :-
  append(M1,M2,UnSortedM), sort(UnSortedM,M).
findc(Elt,Mapping,Set) :-
  member(Set-Elt,Mapping).
unionc(Set1,Set2) :-
  Set1 = Set2.  % sets are just uninstantiated vars

% Question 3

% (a)
generate(N,Circuit) :-
  length(Inputs,N),  % this is a list of input variables that we'll bind
                     % non-determinstically at circuits of depth 0
  iter_generate(Circuit,Inputs,0).

iter_generate(Circuit,Inputs,DepthBound) :-
  generate(0,Circuit,Inputs,DepthBound,DepthBound).
iter_generate(Circuit,Inputs,DepthBound) :-
  NewBound is DepthBound + 1,  % iterate through all possible depths
  iter_generate(Circuit,Inputs,NewBound).

% generate(+CurDepth,-Circuit,+Inputs,+DepthBound,-Depth)
% Generate Circuit of Depth beginning at CurDepth over input lines Inputs, but
%  do not exceed DepthBound.
generate(CurDepth,Input,Inputs,_,CurDepth) :-
  member(Input,Inputs).  % this backtracks through all of the inputs
generate(CurDepth,Circuit,Inputs,DepthBound,Depth) :-
  EmbeddedDepth is CurDepth + 1,
  EmbeddedDepth =< DepthBound,  % enforce the depth bound
  generate_complex(Circuit,EmbeddedDepth,Inputs,DepthBound,Depth).

generate_complex(and(C1,C2),EmbeddedDepth,Inputs,DepthBound,Depth) :-
  generate(EmbeddedDepth,C1,Inputs,DepthBound,D1),
  generate(EmbeddedDepth,C2,Inputs,DepthBound,D2),
  Depth is max(D1,D2).  % we only need this extra argument to ensure
                        % that iterative deepening with bound N does
                        % not produce solutions of depth N-1 or less.
generate_complex(or(C1,C2),EmbeddedDepth,Inputs,DepthBound,Depth) :-
  generate(EmbeddedDepth,C1,Inputs,DepthBound,D1),
  generate(EmbeddedDepth,C2,Inputs,DepthBound,D2),
  Depth is max(D1,D2).
generate_complex(not(C1),EmbeddedDepth,Inputs,DepthBound,Depth) :-
  generate(EmbeddedDepth,C1,Inputs,DepthBound,Depth).

% (b)

% bool(xor,2,[0,1,1,0]).
% bool(nand,2,[1,1,1,0]).

nth(1,[E|_],E).
nth(N,[_|L],E) :-
  N>1,
  NMinus1 is N - 1,
  nth(NMinus1,L,E).

test(Name,Arity,Circuit) :-
 term_variables(Circuit,Inputs),
 length(Inputs,Arity),
 bool(Name,Arity,Outputs),
 \+ fault(Inputs,Outputs,Circuit).

fault(Inputs,Outputs,Circuit) :-
 set_inputs(Inputs,N),
 N1 is N + 1,
 nth(N1,Outputs,O),
 \+ verify_circuit(Circuit,O).

set_inputs(Inputs,N) :- set_inputs(Inputs,0,N).
set_inputs([],N,N).
set_inputs([I|Inputs],Accum,N) :-
  (I = 0 ; I = 1),
  NewAccum is (2*Accum) + I,
  set_inputs(Inputs,NewAccum,N).

verify_circuit(and(C1,C2),O) :-
  verify_circuit(C1,O1),
  verify_circuit(C2,O2),
  O is O1 /\ O2.
verify_circuit(or(C1,C2),O) :-
  verify_circuit(C1,O1),
  verify_circuit(C2,O2),
  O is O1 \/ O2.
verify_circuit(not(C1),O) :-
  verify_circuit(C1,O1),
  O is 1 - O1.
verify_circuit(1,1).
verify_circuit(0,0).

% (c)

circuit(Name,Arity,Circuit) :-
  generate(Arity,Circuit),
  test(Name,Arity,Circuit).

% Question 4

% In an (N+1)-ary term, there are N adjacent argument pairs.  Associate
% each element of S with a distinct such pair.  Bind the first argument
% of every term representation to 0, and the last argument of every
% representation to 1.  For the term representation of subset P, for
% every element not in P, bind the paired arguments associated with that
% element together with a shared variable.  Example:

% S = {a,b,c}, P = {a,b}
% a: f(0,1,1,1)
% b: f(0,0,1,1)
% c: f(0,0,0,1)
% S: f(0,_,_,1)
% P: f(0,_,1,1)

% Unification of a pair of terms excludes the union of the complements
% of their corresponding subsets, and thus implements intersection.
% If all elements are excluded (empty set), then 0 must be unified
% with 1, which fails.