#OK to post homework
#Victoria Chayes, 1/31/2021, Assignment 3

with(combinat): 
Help:=proc(): print(`NewUCG(n), BoxG(L), Tomorrow(Date), Yesterday(Date), UCG(n), NEXG(w), PREG(w), RBW(n), Box(L)`): end:

#############################################

#1 Carefully read the code for the recursive procedure NEXG(w) in C3.txt , (with its companion procedure PREG(w)) and write a procedure NewUCG(n) that has the same input and output as UCG(n), but instead starts with the vector [0$n] and keeps applying NEXG(w), always appending the new guy to the list. Check that UCG(n)=NewUCG(n) are the same for n from 1 to 14.

NewUGC:=proc(n) local S,i:
S:=[[0$n]]:
i:=1:
while NEXG(S[i])<>FAIL do
  S:=[op(S),NEXG(S[i])]:
  i:=i+1:
od:
S:
end:


# Testing indicated 
# {seq(evalb(NewUGC(i)=UCG(i)),i=1..14)}
#                             {true}
# Out of curiosity, because it did not run immediately, I checked 
# seq([time(NewUGC(i)),time(UCG(i))],i=1..14)
# [0., 0.], [0., 0.], [0., 0.], [0., 0.], [0.001, 0.], [0.004, 0.], [0.007, 0.], [0.014, 0.], [0.022, 0.], [0.056, 0.], [0.124, 0.], [0.295, 0.], [0.773, 0.], [2.554, 0.]
#
# So we see that UCG is far more efficient than NewUCG.



#2 Generalize UCG(n) to write a procedure BoxG(L) that inputs a list of positive integers and outputs a list whose members are the same as Box(L), but in such an order that when you go from one member to the next, it only changes in one place. What is BoxG([2,2,2])?

BoxG:=proc(L) local k,B1:
if not type(L,list) then  #start with input checking 
  print(L, `should be a list `):
  RETURN(FAIL):
fi:
k:=nops(L):
if k=0 then 
  RETURN([[]]):
fi:
if not ({seq(type(L[i],integer),i=1..nops(L))}={true} and min(op(L))>=0) then
  print(`bad input`):
  RETURN(FAIL):
fi:
B1:=BoxG(L[2..k]):
[seq(seq([i,op(B1[((-1)^i)*j])],j=1..nops(B1)),i=0..L[1])]:
end:

# We first want to test BoxG by comparing it to UCG: BoxG([1$n]) should produce the same output as UCG(n). This ends up being true:
#
# {seq(evalb(BoxG([1$i])=UCG(i)),i=1..14)}
#                             {true}
#
# So, confident in our program, we calculate the gray ternary numbers:
#
# BoxG([2,2,2])
#   [[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 1, 2], [0, 1, 1], 
#
#     [0, 1, 0], [0, 2, 0], [0, 2, 1], [0, 2, 2], [1, 2, 2], 
#
#     [1, 2, 1], [1, 2, 0], [1, 1, 0], [1, 1, 1], [1, 1, 2], 
#
#     [1, 0, 2], [1, 0, 1], [1, 0, 0], [2, 0, 0], [2, 0, 1], 
#
#     [2, 0, 2], [2, 1, 2], [2, 1, 1], [2, 1, 0], [2, 2, 0], 
#
#     [2, 2, 1], [2, 2, 2]]



#3 Write procedures Tomorrow(Date), Yesterday(Date) that inputs four-tuple Date=[DayOfTheMonth , Month , Year, DayOfTheWeek ] and outputs the dates of the next day, and previous day, respectively.

# The single error-checking that my Tomorrow and Yesterday do not do is checking whether or not the assigned day of the week in the input matches the actual calendar day of the week. Otherwise, these programs do check whether or not the input can be considered a valid day. 

Tomorrow:=proc(Date) local newday, M1:
if not (type(Date,list) and nops(Date)=4 and {seq(type(Date[i],integer),i=1..4)}={true}) then
  print(`bad input`):
  return(FAIL):
fi:
M1:={1,  3,  5,  7, 8, 10, 12}:   #months with 31 days
if Date[4]<1 or Date[4]>7 then    #checking the day of the week
  print(`please insert a valid day of the week`):
  return(FAIL):
elif Date[4]<7 then
  newday:=Date[4]+1:
else
   newday:=1:
fi:
if Date[2]<1 or Date[2]>12 then
  print(`please insert a valid month`):
  return(FAIL):
elif Date[2]=2 then   #The February Case!
  if Date[1]<1 or Date[1]>29 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=29 then
    if modp(Date[3],400)=0 then
      return([1,3,Date[3],newday]):
    elif modp(Date[3],4)=0 and modp(Date[3],100)<>0 then
      return([1,3,Date[3],newday]):
    else 
      print(`you have entered February 29th but it is not a leap year`):
      return(FAIL):
    fi:
  elif Date[1]=28 then
    if modp(Date[3],400)=0 then
      return([29,2,Date[3],newday]):
    elif modp(Date[3],4)=0 and modp(Date[3],100)<>0 then
      return([29,2,Date[3],newday]):
    else 
      return([1,3,Date[3],newday]):
    fi:
  else
     return([Date[1]+1, 2, Date[3], newday]):
  fi:
elif Date[2] in M1 then #The 31 Days Case!
  if Date[1]<1 or Date[1]>31 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=31 then
     if Date[2]=12 then
       return([1,1,Date[3]+1, newday]):
     else 
        return([1, Date[2]+1, Date[3], newday]):
     fi:
  else
     return([Date[1]+1, Date[2], Date[3], newday]):
  fi:
else 
  if Date[1]<1 or Date[1]>30 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=30 then
      return([1, Date[2]+1, Date[3], newday]):
  else
     return([Date[1]+1, Date[2], Date[3], newday]):
  fi:
fi:
end:

Yesterday:=proc(Date) local newday, M1:
if not (type(Date,list) and nops(Date)=4 and {seq(type(Date[i],integer),i=1..4)}={true}) then
  print(`bad input`):
  return(FAIL):
fi:
M1:={1,  3,  5,  7, 8, 10, 12}:   #months with 31 days
if Date[4]<1 or Date[4]>7 then    #checking the day of the week
  print(`please insert a valid day of the week`):
  return(FAIL):
elif Date[4]>1 then
  newday:=Date[4]-1:
else
   newday:=7:
fi:
if Date[2]<1 or Date[2]>12 then
  print(`please insert a valid month`):
  return(FAIL):
elif Date[2]=2 then   #The February Case!
  if Date[1]<1 or Date[1]>29 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=29 then
    if modp(Date[3],400)=0 then
      return([28,2,Date[3],newday]):
    elif modp(Date[3],4)=0 and modp(Date[3],100)<>0 then
      return([28,2,Date[3],newday]):
    else 
      print(`you have entered February 29th but it is not a leap year`):
      return(FAIL):
    fi:
  elif Date[1]=1 then
    return([31,1,Date[3],newday]):
  else
    return([Date[1]-1, 2, Date[3], newday]):
  fi:
elif Date[2] in M1 then #The 31 Days Case!
  if Date[1]<1 or Date[1]>31 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=1 then
     if Date[2]=1 then
        return([31,12,Date[3]-1, newday]):
     elif Date[2]=3 then
        if modp(Date[3],400)=0 then
          return([29,2,Date[3],newday]):
        elif modp(Date[3],4)=0 and modp(Date[3],100)<>0 then
          return([29,2,Date[3],newday]):
        else 
          return([28,2,Date[3],newday]):
        fi:
     elif Date[2]=8 then
        return([31,7,Date[3], newday]):
     else
        return([30,Date[2]-1,Date[3], newday]):
     fi:
  else
     return([Date[1]-1, Date[2], Date[3], newday]):
  fi:
else
  if Date[1]<1 or Date[1]>30 then
    print(`please insert a valid day of the month`):
    return(FAIL):
  elif Date[1]=1 then
    return([31,Date[2]-1,Date[3],newday]): #all 30-day months are preceded by 31-day months
  else
    return([Date[1]-1, Date[2], Date[3], newday]):
  fi:
fi:
end:




#5 When you try NEXG(w) on a 0-1 vector of length <=3261, you get a very fast answer w:=RBW(3261): NEXG(w): But when I did w:=RBW(3262): NEXG(w): I got an error Maple, exceeding the "stack" length that handles recursion in Maple. Is there a way to change it?

#For my computer, w:=RBW(13780) worked with time(NEXG(w))=3.567, but initially w:=RBW(13781) produced a 'too many levels of recursion' error. I could not find online or anywhere in the help settings, online forums, or looking through settings a way to increase levels of recursion. 


################
# FROM C3.TXT  #
################

UCG:=proc(n) local B:
option remember:
if n=0 then
 RETURN([[]]):
fi:
B:=UCG(n-1):
CAT(PreP(0,B),PreP(1,REV(B))):
end:

REV:=proc(L) local i: [seq(L[-i],i=1..nops(L))]:end:
CAT:=proc(L1,L2): [op(L1),op(L2)]:end:
PreP:=proc(a,L) local i:  [ seq([a, op(L[i])],i=1..nops(L))]:end:

NEXG:=proc(w)  local n,w1, w1Next,w1Prev:
n:=nops(w):
if n=1 then
 if w[1]=0 then
   RETURN([1]):
else
  RETURN(FAIL):
 fi:
fi:
w1:=[op(2..n,w)]:
if w[1]=0 then
 w1Next:=NEXG(w1): 
 if w1Next=FAIL then
  RETURN([1,op(w1)]):
 else
  RETURN([0,op(w1Next)]):
fi:
elif w[1]=1 then
 w1Prev:=PREG(w1):
  if w1Prev=FAIL then
   RETURN(FAIL):
  else
    RETURN([1,op(w1Prev)]):
  fi:
else
print(`Something is wrong`):
 RETURN(FAIL):
fi:
end:

PREG:=proc(w)  local n,w1, w1Prev,w1Next:
n:=nops(w):
if n=1 then
 if w[1]=0 then
   RETURN(FAIL):
else
  RETURN([0]):
 fi:
fi:
w1:=[op(2..n,w)]:
if w[1]=0 then
 w1Prev:=PREG(w1):
 if w1Prev=FAIL then
   RETURN(FAIL):
 else
  RETURN([0,op(w1Prev)]):
fi:
elif w[1]=1 then
 w1Next:=NEXG(w1):
  if w1Next=FAIL then
   RETURN([0,op(w1)]):
  else
    RETURN([1,op(w1Next)]):
  fi:
else
print(`Something is wrong`):
 RETURN(FAIL):
fi:
end:

RBW:=proc(n) local ra,i:
ra:=rand(0..1):
[seq(ra(),i=1..n)]:
end:

Box:=proc(L) local k,i,L1,B1,b1:
if not type(L,list) then
print(L, `should be a list `):
RETURN(FAIL):
fi:
k:=nops(L):
if k=0 then 
RETURN([[]]):
fi:
if not ({seq(type(L[i],integer),i=1..nops(L))}={true} and min(op(L))>=0) then
print(`bad input`):
RETURN(FAIL):
fi:
L1:=[op(1..k-1,L)]:
B1:=Box(L1):
 [ seq(seq([op(B1[j]),i],i=0..L[k]),j=1.. nops(B1))]:
end: