#OK to post homework
#Jason Saied, March 31, 2019, Assignment 16

Help:=proc(): print(`GuessWho(x,N), ProfileMod(n,k), ABTmod(N,k), BT(n), OT(n)`): end:

#####Problem 1

#If there are 2^k numbers in an ordered list, it should actually take k questions to figure out which one your opponent is thinking of.
#Also, it's N=2^k-1 that gives us a list with 2^k numbers, 
#so really we want N=2^k-1 to return k. This code will do that!
GuessWho:=proc(x,N) local co, L, U, U0:
	
	#the case where N=0 is degenerate: no questions needed
	if N=0 then 
		return 0:
	fi:
	
	L:=0:
	U:=trunc(N/2):
	co:=0:
	
	while L<U do
	
		co:=co+1:
		
		if L<=x and x<=U then
			U:=L+trunc((U-L)/2):
		else
			U0:=U:
			U:=U+ceil((U-L)/2):
			L:=U0+1:
		fi:
	
	od:
	
	#in the nondegenerate case, we need one more question once L=U
	return co+1:

end:

###Problem 2

#[[Name,[DescriptiveFeature1, ..., DescriptiveFeature],targetFeature] , ...]

#ProfileMod(n,k): inputs a positive integer n and k outputs
#a list of positive integers of length k whose i-th item is "what is n modulo the ith prime" for i from 1 to k
#For example
#ProfileMod(10,3) should output [0, 1, 0]
#ProfileMod(10,6) should output [0,1,0,3, 10, 10]
ProfileMod:=proc(n,k) local i:
	[seq(modp(n,ithprime(i)),i=1..k)]:
end:

#ABTmod(N,k)
#Inputs a positive integer N and pos. integer k outputs an ABT
#for the data generated from them using the k descriptive features
#"what is N modulo the ith prime" for i from 1 to k
ABTmod:=proc(N,k) local n:
	[seq([n,ProfileMod(n,k), isprime(n)],n=1..N)]:
end:


###Problem 3

#input a positive integer n
#returns the set of all binary trees with exactly n leaves 
BT:=proc(n) local S,a,b,i:

	option remember:

	if n<=0 then
		return {}:
	fi:

	if n=1 then 
		return {[]}:
	fi:
	
	S:={}:
	
	#to get a tree on n leaves, you can join any two trees whose numbers of leaves sum to n 
	for i from 1 to n-1 do 
	
		for a in BT(i) do
		
			for b in BT(n-i) do
			
				S:=S union {[a,b]}:
			
			od:
		
		od:
	
		
	
	od:
	
	return S:

end:

#No experimentation needed for this one. Let B(n)=nops(BT(n)). From how we constructed BT(n), we see that B(n) satisfies the recursion B(1)=0, B(n)=add(B(i)*B(n-i), i=1..n). 
#This is a shifted version of the recursion for the Catalan numbers C(n). We have C(n)=B(n+1) for n>=0. 


###Problem 4

#Note that the problem statement as written is false. The number of vertices of [T1, ..., Tk] is actually 1 plus the numbers of vertices of each Ti. The definition in the statement doesn't make sense, since [[[...]]] would be said to have 1 vertex. 
OT:=proc(n) local S,a,T1, T2:

	option remember:

	if n<=0 then
		return {}:
	fi:
	
	if n=1 then 
		return {[]}:
	fi:
	
	S:={}:
	
	#let a be the number of vertices in the tree we are adding on 
	for a from 1 to n-1 do 
	
		#take a tree with n-a vertices
		#take another tree with a vertices 
		#put them together into one tree (putting the a one as a subtree under the n-a one's root node)
		
		for T1 in OT(n-a) do
		
			for T2 in OT(a) do
			
				S:=S union {[op(T1), T2]}:
			
			od:
		
		od:
		
	
	od:
	
	return S:

end:

#Interestingly, we again have the recursion for the Catalan numbers. If T(n):=nops(OT(n)), we have T(1)=1, and for n>1 we have T(n)=add(T(a)*T(n-a), a=1..n-1). 
#So with the notation from Problem 3, C(n)=B(n+1)=T(n+1). Then we have closed form T(n+1)=B(n+1)=C(n)=binomial(2n,n)/(n+1)