#The Knaves function has a single input n, the number of people used; 
#these people are naturally identified by elements of [n].
#Its output has two components, a set of statements and the solution.

#Each statement is of one of the following forms:
# - (a,b,i), i.e. person a says person b has status i
# - (a,b,i,'or',c,j), i.e. person a says person b has status i or
#       person c has status j
# - (a,b,i,'and',c,j), i.e. person a says person b has status i and
#       person c has status j
#Here, a, b, and c are in [n] and i and j are in {0,1}.  A person with
#status 0 is a knight (i.e. always tells the truth), while a person 
#with status 1 is a knave (always lies).  Note that this applies to 
#each individual statement separately - so a knight may say the `or`
#of two things, of which only one is true, but cannot say these 
#two things in independent statements.

#The solution is an element of {0,1}^n, where the ith entry is the 
#status of person i.  It should be the only possible solution to the 
#puzzle. 



bool:=proc(n) local body,i:
 if n=0 then
  RETURN({[]}):
 fi:
 body:={}:
 for i in bool(n-1) do
  body:=body union {[op(i),0],[op(i),1]}:
 od:
 body:
end:
Knaves:=proc(n) local pop,i,maybe,maysize,stump,ready,speaker,p1,p2,q1,q2,hello,newmaybe,newmaybe2,statement,antistatement,elt,well:
 pop:=[seq(i,i=1..n)]:
 maybe:=bool(n):
 maysize:=nops(maybe):
 stump:={}:
 while maysize>1 do
  ready:=false:
  while ready=false do
   speaker:=roll(pop):
   p1:=roll(pop):
   p2:=roll(pop):
   q1:=roll([0,1]):
   q2:=roll([0,1]):
   hello:=roll([1,2,2]):
   while p1=speaker do
    p1:=roll(pop):
   od:
   while p2 in {speaker,p1} do
    p2:=roll(pop):
   od:
   newmaybe:={}:
   if hello=1 then
    statement:=[speaker,p1,q1]:
    antistatement:=[speaker,p1,1-q1]:
    for elt in maybe do
     if elt[speaker]=0 and elt[p1]=q1 then
      newmaybe:=newmaybe union {elt}:
     elif elt[speaker]=1 and elt[p1]<>q1 then
      newmaybe:=newmaybe union {elt}:
     fi:
    od:
   else
    statement:=[speaker,p1,q1,`or`,p2,q2]:
    antistatement:=[speaker,p1,1-q1,`and`,p2,1-q2]:
    for elt in maybe do
     well:=evalb(elt[p1]=q1) or evalb(elt[p2]=q2):
     if elt[speaker]=0 and well then
      newmaybe:=newmaybe union {elt}:
     elif elt[speaker]=1 and not well then
      newmaybe:=newmaybe union {elt}:
     fi:
    od:
   fi:
   newmaybe2:=maybe minus newmaybe:
   if nops(newmaybe)>0 and nops(newmaybe2)>0 then
    ready:=true:
    if nops(newmaybe2)<nops(maybe)/3 then
     maybe:=newmaybe2:
    elif nops(newmaybe)<nops(maybe)/3 then
     maybe:=newmaybe:
    else
     maybe:=roll([newmaybe,newmaybe2]):
    fi:
    if maybe=newmaybe then
     stump:=stump union {statement}:
    else
     stump:=stump union {antistatement}:
    fi:
   fi:
  od:
  maysize:=nops(maybe):
 od:
 [stump,maybe]:
end:

roll:=proc(L):
	L[rand(1..nops(L))()]:
end: