#OK to post homework
#Blair Seidler, 2021-01-31, Assignment 3

with(combinat):

Help:=proc():
print(` NewUCG(n) `,` CheckUCGs(n) `,` BoxG(L) `,` MyNEXG(w) `):
print(` Tomorrow([DayOfTheMonth , Month , Year, DayOfTheWeek]) `):
print(` Yesterday([DayOfTheMonth , Month , Year, DayOfTheWeek]) `):
print(`FindDOW([DayOfTheMonth , Month , Year]) `): end:

# 1.

#NewUCG(n) 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. 
NewUCG:=proc(n) local w,W:
if not (type(n,integer) and n>0) then
 return FAIL:
fi:

W:=[]:
w:=[0$n]:
while not w=FAIL do
 W:=[op(W),w]:
 w:=MyNEXG(w):
od:
W:
end:


##### Next task: Check that UCG(n)=NewUCG(n) are the same for n from 1 to 14. ####
#CheckUCGs(n): Checks equivalence of UCG and NewUGC on all inputs for 1 to n
CheckUCGs:=proc(n) local i:
if not (type(n,integer) and n>0) then
 return FAIL:
fi:

if {seq(evalb(UCG(i)=NewUCG(i)),i=1..n)}={true} then
  return(true):
else
  return(false):
fi:
end:
#### Yes, CheckUGCs(14) returned true ####

# 2.

#BoxG(L): 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
BoxG:=proc(L) local i,k,W:
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:

W:=[]:
for i from 0 to L[1] do
  if (i mod 2)=0 then
    W:=[op(W),op(PreP(i,BoxG(L[2..k])))]:
  else
    W:=[op(W),op(PreP(i,REV(BoxG(L[2..k]))))]:
  fi:
od:
W:

end:

#### Output of 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.
#Tomorrow(Date): Date=[DayOfTheMonth , Month , Year, DayOfTheWeek ]
#outputs the next day
Tomorrow:=proc(Date) local i,DayOfTheMonth,Month,Year,DayOfTheWeek,mi:
if not (type(Date,list) and nops(Date)=4 and {seq(type(Date[i],integer),i=1..4)}={true}) then
 RETURN(FAIL):
fi:

DayOfTheMonth:=Date[1]:
Month:=Date[2]:
Year:=Date[3]:
DayOfTheWeek:=Date[4]:

mi:=[31,28,31,30,31,30,31,31,30,31,30,31]:
if ((Year mod 4)=0 and not (Year mod 100)=0) or (Year mod 400)=0 then
  mi[2]:=29:
fi:

if DayOfTheWeek<1 or DayOfTheWeek>7 or Month<1 or Month>12 or DayOfTheMonth<1
                  or DayOfTheMonth>mi[Month] then
 RETURN(FAIL):
fi:


DayOfTheWeek:=(DayOfTheWeek mod 7)+1:

DayOfTheMonth:=(DayOfTheMonth mod mi[Month])+1:
if DayOfTheMonth=1 then
  Month:=(Month mod 12)+1:
  if Month=1 then
    Year:=Year+1:
  fi:
fi:

[DayOfTheMonth,Month,Year,DayOfTheWeek]:

end:

#Yesterday(Date): Date=[DayOfTheMonth , Month , Year, DayOfTheWeek ]
#outputs the previous day
Yesterday:=proc(Date) local i,DayOfTheMonth,Month,Year,DayOfTheWeek,mi:
if not (type(Date,list) and nops(Date)=4 and {seq(type(Date[i],integer),i=1..4)}={true}) then
 RETURN(FAIL):
fi:

DayOfTheMonth:=Date[1]:
Month:=Date[2]:
Year:=Date[3]:
DayOfTheWeek:=Date[4]:

mi:=[31,28,31,30,31,30,31,31,30,31,30,31]:
if ((Year mod 4)=0 and not (Year mod 100)=0) or (Year mod 400)=0 then
  mi[2]:=29:
fi:

if DayOfTheWeek<1 or DayOfTheWeek>7 or Month<1 or Month>12 or DayOfTheMonth<1
                  or DayOfTheMonth>mi[Month] then
 RETURN(FAIL):
fi:


DayOfTheWeek:=DayOfTheWeek-1:
if DayOfTheWeek=0 then DayOfTheWeek:=7: fi:

DayOfTheMonth:=DayOfTheMonth-1:
if DayOfTheMonth=0 then
  Month:=Month-1:
  if Month=0 then Month:=12: fi:
  DayOfTheMonth:=mi[Month]:
  if Month=12 then
    Year:=Year-1:
  fi:
fi:

[DayOfTheMonth,Month,Year,DayOfTheWeek]:

end:

#### A really inefficient way to find the day of the week of an arbitrary date ####
FindDOW:=proc(Date) local i,DayOfTheMonth,Month,Year,d,dm,m,y:
d:=[30,1,2021,7]:
dm:=d[1]: m:=d[2]: y:=d[3]:
DayOfTheMonth:=Date[1]:
Month:=Date[2]:
Year:=Date[3]:

if (DayOfTheMonth+32*Month+400*Year)=(dm+32*m+400*y) then
 RETURN(7):
fi:
if (DayOfTheMonth+32*Month+400*Year)<(dm+32*m+400*y) then
 while (DayOfTheMonth+32*Month+400*Year)<(dm+32*m+400*y) do
   d:=Yesterday(d):
   dm:=d[1]:
   m:=d[2]:
   y:=d[3]:
  od:
 RETURN(d[4]):
fi:
while (DayOfTheMonth+32*Month+400*Year)>(dm+32*m+400*y) do
  d:=Tomorrow(d):
  dm:=d[1]:
  m:=d[2]:
  y:=d[3]:
od:
d[4]:

end:

# 4.

#MyNEXG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the NEXT one in the the Gray Code given by UCG(n).
#Functionality equivalent to NEXG(w) without recursion
MyNEXG:=proc(w)  local n,i,t,w1:
n:=nops(w):
t:=add(i,i in w):

#If the first digit is 1 and all others are 0, we are at the last element in Gray Code order
if (t=1) and (w[1]=1) then
 return FAIL:
fi:

w1:=w:
if (t mod 2)=0 then
 w1[n]:=(1+w[n]) mod 2:
else
 for i from 0 to n-2 do
   if w[n-i]=1 then
     w1[n-i-1]:=(w[n-i-1]+1) mod 2:
     break:
   fi:
 od:
fi:

w1:

end:


#### You didn't ask us to do this one, but I wanted to see if I could ####

#MyPREG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the PREVIOUS one in the the Gray Code
#given by UCG(n). Functionality equivalent to PREG(w) without recursion
MyPREG:=proc(w)  local n,i,t,w1:
n:=nops(w):
t:=add(i,i in w):

#If all digits are 0, we are at the first element in Gray Code order
if (t=0) then
 return FAIL:
fi:

w1:=w:
if (t mod 2)=1 then
 w1[n]:=(1+w[n]) mod 2:
else
 for i from 0 to n-2 do
   if w[n-i]=1 then
     w1[n-i-1]:=(w[n-i-1]+1) mod 2:
     break:
   fi:
 od:
fi:

w1:

end:


# 5. I sent this in an email, but I am also including it here.

# The stack limit is likely to be very machine dependent. I was able to run (using your code)

# w := RBW(50000);time(NEXG(w));

# It took about 4.5 minutes, but it completed. It also used 5GB of memory to do it, so I was
# almost certainly using swap space. The combination of RAM and available swap space on your
# machine may be small enough that you can't boost that limit.





#### Code included from C3.txt ####

#Box(L): Inputs a list L (where k=nops(L)) of non-negative integers L outputs
#the  LIST of all LISTS [a1,a2,..., ak] in LEX ORDER such that ai is in {0,1,.., L[i])
#In particular the n-dim UNIT cube would be Box([1$n]);
Box:=proc(L) local k,i,L1,B1,j:
option remember:

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:


#NEXG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the NEXT one in the the Gray Code given by UCG(n).
#Try: NEXG([1,0,1]);
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

#Since w[1]=1, we are going BACKWARDS

 w1Prev:=PREG(w1):
  if w1Prev=FAIL then

  #IF THERE IS NO WAY TO GO WE RETURN FAIL
   RETURN(FAIL):

  else
    RETURN([1,op(w1Prev)]):
  fi:
else
print(`Something is wrong`):
 RETURN(FAIL):
fi:

end:


#PREG(w): inputs a word in {0,1}^n (n=nops(w)) and outputs the PREVIOUS one in the the Gray Code given by UCG(n).
#Try: NEXG([1,0,1]);
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

#Since w[1]=1, we are going FORWARD

 w1Next:=NEXG(w1):
  if w1Next=FAIL then
   #WE CHANGE THE first bit
   RETURN([0,op(w1)]):
  else
    RETURN([1,op(w1Next)]):
  fi:
else
print(`Something is wrong`):
 RETURN(FAIL):
fi:

end:



#RBW(n): A random binary word in {0,1} of length n
RBW:=proc(n) local ra,i:
ra:=rand(0..1):
[seq(ra(),i=1..n)]:
end:

#UCG(n): inputs a non-neg. integer n, and outputs the n-dim unit cube [0,1]^n
#USING THE GRAY-CODE WHERE ONLY ONE BIT CHANGES AT A TIME
#AS A LIST OF 0-1 vectors in Lex-order (same as Box([1$n])
UCG:=proc(n) local B:

if n=0 then
 RETURN([[]]):
fi:
B:=UCG(n-1):

CAT(PreP(0,B),PreP(1,REV(B))):

end:

#CAT(L1,L2): joining two lists in order
CAT:=proc(L1,L2): [op(L1),op(L2)]:end:

#REV(L):
REV:=proc(L) local i: [seq(L[-i],i=1..nops(L))]:end:

#PreP(a,L): Given a list L  of lists, outputs the list where
#sticks a to the beginnin of each of them
#For example
#PreP(0,[[1,2,3],[1,3,4]])= [[0,1,2,3],[0,1,3,4]]
PreP:=proc(a,L) local i:  [ seq([a, op(L[i])],i=1..nops(L))]:end:



#### End of included code from C3.txt ####