Help:=proc(): print(` SAW(n), IsBad(w1) , DrawWalk(w), RSAW(n), OneStep(L) , sRSAW(n,K,C) , FabSn(a,b,S,n) `): 
print(`snab(n,a,b), sn(n), gIsGood(w,a,b,c,d), IsBadP1(w,p), IsBadP(w,P) `):
print(` gSAW(n,a,b,c,d,PAT) `):
end:
#2^n<=|SAW(n)|<=4*3^(n-1)
#mu:=limit s(n)^(1/n)
#2<=mu<=3

#s(n) is sympt. to mu^n*n^theta  (theta=11/32)

###Old stuff
SAW:=proc(n) local Sp,w1,S,w:
option remember:

if n=0 then
 RETURN({[]}):
fi:

Sp:=SAW(n-1):

S:={}:

for w in Sp do
 
w1:=[op(w),1]:
  if not IsBad(w1) then
    S:=S union {w1}:
  fi:

w1:=[op(w),-1]:
  if not IsBad(w1) then
    S:=S union {w1}:
  fi:

w1:=[op(w),2]:
  if not IsBad(w1) then
    S:=S union {w1}:
  fi:

w1:=[op(w),-2]:
  if not IsBad(w1) then
    S:=S union {w1}:
  fi:
od:


S:
end:


IsBad:=proc(w1) local j,x,w2,michael,i:

for j from nops(w1)-1 by -1 to 1 do
     w2:=[op(j..nops(w1),w1)]:
    michael:=add(x[w2[i]],i=1..nops(w2)):
     if coeff(michael,x[1],1)=coeff(michael,x[-1],1) and
    coeff(michael,x[2],1)=coeff(michael,x[-2],1) then
        RETURN(true):
     fi:
  od:

false:

end:



L:=
[4, 12, 36, 100, 284, 780, 2172,
5916, 16268, 44100, 120292, 324932, 881500, 
2374444, 6416596, 17245332, 46466676, 
124658732, 335116620, 897697164, 
2408806028, 6444560484, 17266613812, 46146397316, 123481354908, 329712786220, 
881317491628, 2351378582244, 6279396229332, 16741957935348, 44673816630956, 
119034997913020, 317406598267076, 845279074648708, 2252534077759844, 
5995740499124412, 15968852281708724, 42486750758210044, 113101676587853932, 
300798249248474268, 800381032599158340, 2127870238872271828, 
5659667057165209612, 15041631638016155884, 39992704986620915140, 
106255762193816523332, 282417882500511560972, 750139547395987948108, 
1993185460468062845836, 5292794668724837206644, 14059415980606050644844, 
37325046962536847970116, 99121668912462180162908, 263090298246050489804708, 
698501700277581954674604, 1853589151789474253830500, 4920146075313000860596140,
13053884641516572778155044, 34642792634590824499672196, 
91895836025056214634047716, 243828023293849420839513468, 
646684752476890688940276172, 1715538780705298093042635884, 
4549252727304405545665901684, 12066271136346725726547810652, 
31992427160420423715150496804, 84841788997462209800131419244, 
224916973773967421352838735684, 596373847126147985434982575724, 
1580784678250571882017480243636]:


#DrawWalk(w): draws the  SAW w
DrawWalk:=proc(w) local L,i,pt:
L:=[[0,0]]:
pt:=[0,0]:

for i from 1 to nops(w) do
 if w[i]=-1 then
   pt:=pt+[-1,0]:
 elif w[i]=1 then
   pt:=pt+[1,0]:
 elif w[i]=2 then
   pt:=pt+[0,1]:
 elif w[i]=-2 then
   pt:=pt+[0,-1]:
 fi:


L:=[op(L),pt]:
od:
plot(L,axes=none):
end:


#RSAW(n): a (not-guaranteed-to-be-uniform) random walk on n steps
#in the 2D lattice
RSAW:=proc(n) local L,pt,N,i:

L:=[[0,0]]:

pt:=[0,0]:


for i from 1 to n  do

N:={pt+[1,0],pt+[-1,0],pt+[0,1],pt+[0,-1]} minus {op(L)} :

if N={} then
  RETURN(FAIL,L):
fi:

pt:=N[rand(1..nops(N))()]:

L:=[op(L),pt]:

od:

L:

end:


###End old stuff

#OneStep(L): given an already constructed saw, takes it one step further, if possible, or returns FAIL
# (not-guaranteed-to-be-uniform) random walk on n steps
#in the 2D lattice
OneStep:=proc(L) local pt,N:

pt:=L[nops(L)]:

N:={pt+[1,0],pt+[-1,0],pt+[0,1],pt+[0,-1]} minus {op(L)} :

if N={} then
  RETURN(FAIL):
else
pt:=N[rand(1..nops(N))()]:
RETURN([op(L),pt]):
fi:

end:



#sRSAW(n,K,C) : an n-step random self-avoiding-walk on the square lattice,
#with the extra feature that if its gets stuck, it backtracks K steps back
#and tries again, up to C trials. If it fails, it returns FAIL
#back-tracking K steps back
sRSAW:=proc(n,K,C) local L,L1,c:
print(`Under construction`):
L:=[[0,0]]:
c:=0:
L1:=OneStep(L):
while nops(L)<=n and c<=C do
L1:=OneStep(L):

 if L1<>FAIL then
   L:=L1:
 else
c:=c+1:
  L:=[op(1..nops(L)-K,L)]:
 fi:
od:

if c=C+1 then
 RETURN(FAIL):
else
 RETURN(L):
fi:

end:





#FabSn(a,b,S,n): the number of self-avoiding-walks from the origin to point [a,b] with n steps
#avioding in addition the points in the set S. For example, try:
#FabSn(1,1,{[1,0]},4);
FabSn:=proc(a,b,S,n) option remember:

if n=0 and a=0 and b=0 then
  RETURN(1):
fi:


 if abs(a)+abs(b)>n then
    RETURN(0):
 fi:

if member([a,b],S) or member([0,0], S) then
 RETURN(0):
fi:

FabSn(a+1,b,S union {[a,b]},n-1)+
FabSn(a-1,b,S union {[a,b]},n-1)+
FabSn(a,b+1,S union {[a,b]},n-1)+
FabSn(a,b-1,S union {[a,b]},n-1):

end:

#snab(n,a,b): the number of self-avoiding walks with n steps from the origin to [a,b]
snab:=proc(n,a,b):FabSn(a,b,{},n):end:


#sn(n): the number of self-avoiding walks with n steps 
sn:=proc(n) local a,b:
add(add(snab(n,a,b),b=-(n-abs(a))..n-abs(a) ),a=-n..n):
end:





#EndPoint(w): the endpoint of w
EndPoint:=proc(w) local w1,pt,n:
if w=[] then
 RETURN([0,0]):
fi:
w1:=[op(1..nops(w)-1,w)]:
pt:=EndPoint(w1):
n:=nops(w):

if w[n]=1 then
 RETURN(pt+[1,0]):
elif w[n]=-1 then
 RETURN(pt+[-1,0]):
elif w[n]=2 then
 RETURN(pt+[0,1]):
elif w[n]=-2 then
 RETURN(pt+[0,-1]):
fi:
end:

#gIsGood(w,a,b,c,d): Does the endpoint of w lie in the region
#a<=x<=b, c<=y<=d
gIsGood:=proc(w,a,b,c,d) local pt:
pt:=EndPoint(w):

if a<=pt[1] and pt[1]<=b and c<=pt[2] and pt[2]<=d then
 RETURN(true):
else
  RETURN(false):
fi:

end:

#IsBadP1(w,p): does the word w end with the word p
IsBadP1:=proc(w,p)

if nops(w)<nops(p) then
 RETURN(false):
elif [op(nops(w)-nops(p)+1..nops(w),w)]=p then
      RETURN(true):
else
    RETURN(false):
fi:

end:

#IsBadP(w,P): Does w contain at least one of the patterns (at the end)
#in the set of
#patterns P?
IsBadP:=proc(w,P) local p:

for p in P do
 if IsBadP1(w,p) then
    RETURN(true):
 fi:
od:

false:

end:




#gSAW(n,a,b,c,d,PAT): The SET of self-avoiding walks on the
#2D sqare-lattice that lies in a<=x<=b and c<=y<=d
#avoiding the patterns in PAT. For example
#gSAW(5,-1,1,-1,1,{[1,1],[2,2],[-1,-1],[-2,-2]}) is the
#set of SAW with 5 steps confined to the finite rectangle
#-1<=x<=1, -1<=y<=1 and without two consecutive steps of the same type

gSAW:=proc(n,a,b,c,d,PAT) local Sp,w1,S,w:
option remember:

if n=0 then
 RETURN({[]}):
fi:

Sp:=gSAW(n-1,a,b,c,d,PAT):

S:={}:

for w in Sp do
 
w1:=[op(w),1]:
  if not IsBad(w1)   and gIsGood(w1,a,b,c,d)  and not  IsBadP(w1,PAT)   then
    S:=S union {w1}:
  fi:

w1:=[op(w),-1]:
  if not IsBad(w1)   and gIsGood(w1,a,b,c,d)  and not  IsBadP(w1,PAT) then
    S:=S union {w1}:
  fi:

w1:=[op(w),2]:
  if not IsBad(w1)  and gIsGood(w1,a,b,c,d)  and not  IsBadP(w1,PAT) then
    S:=S union {w1}:
  fi:

w1:=[op(w),-2]:
  if not IsBad(w1)  and gIsGood(w1,a,b,c,d)  and not  IsBadP(w1,PAT) then
    S:=S union {w1}:
  fi:
od:


S:
end: