#Dayoon Kim, OK to Post
#C28.txt, April-29-2024
Help:=proc(): print(`RW(N),Num(w,W),GS(w1,w2,N)`): end:

#2nd Challenge:
#Inspired by Alice and Bob toss a fair coin n times
#Alice bets that there would be more HH's in the sequence 
#and Bob bet's that would be more HT's.
#Find the sequence Number of n-letter words in {H,T}
#such that #HH > #HT
#
#Given two words w1 and w2 in {0,1}, write a procedure
#GS(w1,w2,N) that outputs the first N terms starting at n=1
#of the words {0,1}^n with strictly more (consec) w1 than w2
#GS([0,0],[0,1],N);


#1st: Generate all the words
RW:=proc(N) local i,S,v,a:
option remember:
if N=0 then
 RETURN({[]}):
fi:
 S:=RW(N-1):
 {seq(seq([op(v),a],a=0..1), v in S)}:
end:

#2nd: Count how many subword w is in a element of RW(N)
#Num(w,W): the number of subsword w in a word W. W is an element of RW(N)
Num:=proc(w,W) local i,n:
n:=0:
for i from 1 to nops(W) - nops(w) + 1 do
 if W[i .. i+nops(w)-1] = w then
  n := n + 1:
 fi:
od:
n:
end:

#3rd: 
#GS(w1,w2,N): inputs (w1,w2,N) and 
#compare Num(w1) and Num(w2) for all the words in RW(N),
#outputs all the words in RW(N) such that N(w1) > N(w2)
GS:= proc(w1,w2,N) local W, result:
result:= {}:
for W in RW(N) do
 if Num(w1,W) > Num(w2,W) then
  result:= result union {W}:
 fi:
od:
result:
end: