# OK to post homework
# Aurora Hiveley, 2/24/25, Assignment 10

Help := proc(): print(`SimulateNAND(n,k,K), Monotone(n,k,p), SimulateMonotone(n,k,p,K), EvalSPM(P,n), EvalSPM1(n,P)`): end:

with(combinat):
with(linalg):



# SimulateNAND(n,k,K): estimates the average number of vectors of length n in a random NAND SLP with n input gates and k other gates, 
# by running it K times and computing the average of this sample

SimulateNAND := proc(n,k,K) local i:
add( nops(EvalSP(RSLP(n,k),n)), i=1..K )/K:
end:


# What did you get for
# SimulateNAND(10,5, 1000)
# SimulateNAND(10,10, 1000)
# SimulateNAND(10,20, 1000)
# SimulateNAND(10,50, 1000)



# Monotone(n,k,p): adapted from RSLP(n,k). Has no NOT, i.e. only using AND and OR, and a typical member is [i,j,AND] or [i,j,OR]
#  for each non-input gate, the probability of AND is p and the probability of OR is 1-p)
Monotone := proc(n,k,p) local P,i,i1,j1 :

P:=[seq(i,i=1..n)]:

for i from n+1 to k+n do
 i1:=rand(1..nops(P))():
 j1:=rand(1..nops(P))():
 
 if LD(p) then 
    P:=[op(P),[i1,j1,AND]]:
  else 
    P:=[op(P),[i1,j1,OR]]:
  fi:
od:

P:
end:

# loaded die: returns true with probabality p (where p is a rational number between 0 and 1)
LD:=proc(p):evalb(rand(1..denom(p))()<=numer(p)):end:



# SimulateMonotone(n,k,p,K): adapted from SimulateNAND(n,k,K), but uses AND/OR instead of NAND SLP 
SimulateMonotone := proc(n,k,p,K) local i:
add( nops(EvalSPM(Monotone(n,k,p),n)), i=1..K )/K:
end:


## example computations:
# kList := [5,10,20,50]:

# [seq( SimulateMonotone(10,k,1/2,1000), k in kList )]:
# output: [63904/125, 64272/125, 131233/250, 64196/125]

# [seq( SimulateMonotone(10,k,3/4,1000), k in kList )]:
# output: [46684/125, 8731/25, 36301/125, 32409/125]

# [seq( SimulateMonotone(10,k,1,1000), k in kList )]:
# output: [27498/125, 21088/125, 27951/250, 27129/500]




# needed helpers 

#EvalSP1M(P,IN): inputs a straight-line AND/OR program and an input true-false vector
#outputs the value of the last gate
EvalSP1M:=proc(P,IN) local n,P1,i,i1,j1:
P1:=IN:
n:=nops(IN):
for i from n+1 to nops(P) do
 i1:=P[i][1]:
 j1:=P[i][2]:

 if P[i][3] = AND then 
    P1:=[op(P1),AND(P1[i1],P1[j1])]:
  else 
    P1:=[op(P1),OR(P1[i1],P1[j1])]:
  fi:
od:

P1[-1]:
end:


#EvalSPM(P,n): inputs a AND/OR SLP and outouts the set of vectors of length n that yields true 
EvalSPM:=proc(P,n) local V,v,T:
V:=TF(n):
T:={}:
for v in V do
 if EvalSP1M(P,v) then
   T:=T union {v}:
 fi:
od:
T:
end:















### copied form C10.txt 
#C10.txt, Feb. 24, 2025
Help10:=proc(): print(`NAND(x,y),NOT(x), AND(x,y),  OR(x,y) , RSLP(n,k), TF(n), EvalSP1(P,IN) `):
print(`EvalSP(P,n)`):
end:
#NAND(x,y): not (x and y)
NAND:=proc(x,y): not (x and y): end:
NOT:=proc(x): NAND(x,x):end:

AND:=proc(x,y): NAND(NAND(x,y),NAND(x,y)):end:

#x OR y= NOT (NOT x AND NOT y)
OR:=proc(x,y)
NAND(NAND(x,x) , NAND(y,y)):
end:

#Def. Straight-Line NAND porgram has n input gates labeled [1, ...n], and
#k (say) non-input gates of the form [i,j] where 1<=i<=j<=k-1 are previous gates
#[1,2,3,[1,1],[3,4],[1,3],[4,4]]
#The compute such a program you evaluate each gate in turn, and the last gate is the
#value of the Boolean function

RSLP:=proc(n,k) local P,i,i1,j1:
P:=[seq(i,i=1..n)]:

for i from n+1 to k+n do
 i1:=rand(1..nops(P))():
 j1:=rand(1..nops(P))():
 P:=[op(P),[i1,j1]]:
od:
P:
end:

#TF(n): the set of all true-false vectors of length n
TF:=proc(n) local V,v:
option remember:
if n=0 then
  RETURN({[]}):
fi:
V:=TF(n-1):
{seq([op(v),false],v in V),seq([op(v),true],v in V)}:
end:

#EvalSP1(P,IN): inputs a straight-line NAND program and an input true-false vector
#outputs the value of the last gate
EvalSP1:=proc(P,IN) local n,P1,i,i1,j1:
P1:=IN:
n:=nops(IN):
for i from n+1 to nops(P) do
 i1:=P[i][1]:
 j1:=P[i][2]:
  P1:=[op(P1),NAND(P1[i1],P1[j1])]:
od:

P1[-1]:
end:

#EvalSP(P,n): inputs a NAND SLP and outouts the set of vectors of length n that yields true 
EvalSP:=proc(P,n) local V,v,T:
V:=TF(n):
T:={}:
for v in V do
 if EvalSP1(P,v) then
   T:=T union {v}:
 fi:
od:
T:
end: