Help:=proc(): print(` SAW(n), IsBad(w1) , DrawWalk(w), RSAW(n) `): 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)

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:

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: