#This package is for the exploration of self avoiding walks in k- dimensions.

print(`SELF AVOIDING WALKS`):
print(`A Maple package by Anne E. Edlin`):
print(`Version - 27th April 1998.`):
print(`This package is designed to explore self avoiding walks.`): 
print(`For a list of procedures type   Help();`):
print(`For help using a specific procedure type   Help(procedure name);`):

Help:=proc():
  if args=NULL then 
    print(`Contains the following procedures:`):
    print(`avoid, avoid1, create, avoidmist, mistwalk, runmist,`):
    print(`symmset, errlist, syminus, runmistA.`):
  elif nargs=1 and args[1]=`avoid` then 
    print(`This procedure tests an individual walk`):
    print(`to see if it is self avoiding.`):
    print(`For example to see if the walk [1,-1] is self avoiding,`):
    print(`you type:  avoid([1,-1]);`):
    print(`This gives the output:`):
    print(`"This walk is not self avoiding."`):
  elif nargs=1 and args[1]=`avoid1` then 
    print(`This procedure tests only part of an individual walk`):
    print(`to see if it is self avoiding.`):
    print(`It tests to see if the last step has made the walk self avoiding`):
    print(`For example if you type:`):
    print(`  avoid1([1,-1,7,8,9,]);`):
    print(`You will get the output:`):
    print(`1`):
  elif nargs=1 and args[1]=`create` then 
    print(`This procedure creates all self avoiding walks`):
    print(`of a given length in a given dimension.`):
    print(`To use it input the length required, followed by the dimension.`):
    print(`For example if you want all self avoiding walks of length 2,`):
    print(`in 3 dimensions then type`):
    print(`create(2,3);`):
    print(`You will get the output:`):
    print(`{[-2, -1], [2, 2], [1, 1], [-1, -1], [-1, 2], [-1, -2], [2, 1],`):
    print(`[2, -1], [-2, -2], [-1, -3], [-1, 3], [1, -3], [1, 3], [3, 3],`):
    print(`[3, -1], [3, 2], [3, 1], [-2, 3], [-2, -3], [2, -3], [2, 3],`):
    print(`[-3, -3], [-3, -1], [-3, 2], [-3, 1], [-3, -2], [3, -2],`):
    print(`[-2, 1], [1, -2], [1, 2]}`):
  elif nargs=1 and args[1]=`avoidmist` then 
    print(`This procedure tests only part of an individual walk`):
    print(`to see if it is self avoiding and mistake free.`):
    print(`It tests to see if the last step has made the walk self avoiding`):
    print(`For example if you type:`):
    print(`  avoidmist([1,-1,7,8,9],{[1,2],[-1,-2]});`):
    print(`You will get the output:`):
    print(`1`):
  elif nargs=1 and args[1]=`mistwalk` then 
    print(`This procedure creates all self avoiding walks`):
    print(`of a given length in a given dimension,`):
    print(`that avoid a certain set of mistakes.`):
    print(`To use it input the length required, followed by the dimension,`):
    print(`followed by the set of mistakes.`):
    print(`For example if you want all self avoiding walks of length 2,`):
    print(`in 3 dimensions`):
    print(`that avoid [1, 1], [2, 2], [3, 3],`):
    print(`[-1 ,-1], [-2, -2], and [-3, -3] then type`):
    print(`mistwalk(2,3,{[1, 1], [2, 2], [3, 3],`):
    print(` [-1 ,-1], [-2, -2], [-3, -3]});`):
    print(`You will get the output:`):
    print(`{[-2, -1], [-1, 2], [-1, -2], [2, 1], [2, -1], [-1, -3],`):
    print(`[-1, 3], [1, -3], [1, 3], [3, -1], [3, 2], [3, 1], [-2, 3],`):
    print(`[-2, -3], [2, -3], [2, 3],[-3, -1], [-3, 2], [-3, 1],`):
    print(` [-3, -2], [3, -2], [-2, 1], [1, -2], [1, 2]}`):
  elif nargs=1 and args[1]=`runmist` then
    print(`This procedure produces the number of self avoiding walks`):
    print(`of all lengths up to size n,`):
    print(`that are mistake free.`):
    print(`For example to find the number of mistake free,`):
    print(`self avoiding walks of length 0 through 4`):
    print(`in 2 dimensions, that avoid the steps`):   
    print(`{[1,1],[2,2],[-1,-1],[-2,-2]}, you type:`):
    print(`runmist(4,2,{[1,1],[2,2],[-1,-1],[-2,-2]});`):
    print(`and the output will be:`):
    print(`[1, 4, 8, 16, 24]`):
  elif nargs=1 and args[1]=`symmset` then
    print(`This procedure produces the subset of the input set`):
    print(`that includes all elements of the set up to geometric symmetry`):
    print(`For example the input:`):
    print(`symmset({[-1,2],[2,1],[-1,-2],[-2,-1],[1,1],[2,2],[-2,-2],[2,-1],`):
    print(`[1,-2],[-1,-1],[1,2],[-2,1]});`):
    print(`produces the output:`):
    print(`{[1, 1], [2, -1]}`):
  elif nargs=1 and args[1]=`errlist` then
    print(`This procedure produces all subsets of a given set`):
    print(`of the required size`):
    print(`errlist(inputset,size of subsets);`):
  elif nargs=1 and args[1]=`symm1` then
    print(`This procedure produces all dihedral symmetries of the input`):
    print(`eg symm1([1,1])={[1,1],[2,2],[-1,-1],[-2,-2]}`):
  elif nargs=1 and args[1]=`syminus` then
    print(`This procedure converts all input sets to sets that are symmetric`):
    print(`with respect to negatives by adding the necessary elements`):
    print(`syminus(set1);`):
  elif nargs=1 and args[1]=`runmistA` then
    print(`This procedure is similar to runmist,`):
    print(`but first checks that the mistakes to not automatically`):
    print(`generate a self-avoiding walk.`):
    print(`This is achieved by implementing a procedure`):
    print(`from the Maple Package: DAVID_IAN,`):
    print(`written by John Noonan and Doron Zeilberger.`):
  else 
    print(`There is no Help available on`, args):
  fi:
end:



avoid:=proc(walk)
  local dim,i,j,k,n,walk1,counter,step,counter1:
  if not type(walk, list) then
    ERROR(`A walk must be entered in the form of a list.`):
  fi:
  n:=nops(walk):
  for i from 1 to n do
    if not type(op(i,walk),integer) then
      ERROR(`A walk is made up of integers.`):
    fi:
  od:
  dim:= 0:
  for i from 1 to n do
    if abs(op(i,walk)) > dim then
      dim:=abs(op(i,walk)):
    fi:
  od:
  for j from 1 to n-1 do
    for k from j to n do
      walk1:=[op(j..k,walk)]:
      counter:=[seq(0, i=0..dim)]:
      counter1:=counter:
      for i from 1 to nops(walk1) do
        step:=op(i,walk1):
        counter:=subsop(abs(step)=op(abs(step),counter)+step,counter):
      od:
      if counter=counter1 then
        RETURN(`This walk is not self avoiding.`):
      fi:
    od:
  od:
print(`This walk is self avoiding.`): 
end:




avoid1:=proc(walk)
  local dim,i,j,n,walk1,counter,step,counter1:
  if not type(walk, list) then
    ERROR(`A walk must be entered in the form of a list.`):
  fi:
  n:=nops(walk):
  for i from 1 to n do
    if not type(op(i,walk),integer) then
      ERROR(`A walk is made up of integers.`):
    fi:
  od:
  dim:= 0:
  for i from 1 to n do
    if abs(op(i,walk)) > dim then
      dim:=abs(op(i,walk)):
    fi:
  od:
  for j from 1 to n-1 do
    walk1:=[op(j..n,walk)]:
    counter:=[seq(0, i=0..dim)]:
    counter1:=counter:
    for i from 1 to nops(walk1) do
      step:=op(i,walk1):
      counter:=subsop(abs(step)=op(abs(step),counter)+step,counter):
    od:
    if counter=counter1 then
      RETURN(`This walk is not self avoiding.`):
    fi:
  od:
RETURN(1):       
end:





create:=proc(steps,dim)
  local i, walks, walk,j,dirs,walk1,walks1:
  if not type(steps, integer) then
    ERROR(`The length of a walk must be an integer`):
  fi:
  if steps<=0 then
    ERROR(`A walk must be made up of a positive number of steps`):
  fi:
  if not type(dim, integer) then
    ERROR(`The dimension of a walk must be an integer`):
  fi:
  if dim<=0 then
    ERROR(`Dimension must be positive.`):
  fi:
  dirs:=[]:
  for i from 1 to dim do
    dirs:=[op(dirs),i,-i]:
  od:
  walks:={}:
  for i from 1 to (2*dim) do
    walks:=walks union {[op(i,dirs)]}:
  od:
  walks1:=walks:
  if steps > 1 then
    walks1:={}:
    walks:=convert(create(steps-1,dim),list):
    for j from 1 to nops(walks) do
      walk:=op(j,walks):
      for i from 1 to (2*dim) do
        walk1:=[op(walk), op(i,dirs)]: 
        if avoid1(walk1)=1 then
          walks1:=walks1 union {walk1}:
        fi:
      od:
    od:
  fi:
walks1: 
end:


avoidmist:=proc(walk,mist)
  local dim,i,j,n,walk1,counter,step,counter1:
  if not type(walk, list) then
    ERROR(`A walk must be entered in the form of a list.`):
  fi:
  n:=nops(walk):
  for i from 1 to n do
    if not type(op(i,walk),integer) then
      ERROR(`A walk is made up of integers.`):
    fi:
  od:
  dim:= 0:
  for i from 1 to n do
    if abs(op(i,walk)) > dim then
      dim:=abs(op(i,walk)):
    fi:
  od:
  for j from 1 to n-1 do
    walk1:=[op(j..n,walk)]:
    if member(walk1, mist) then
      RETURN(`This walk is not mistake avoiding`):
    else
      counter:=[seq(0, i=0..dim)]:
      counter1:=counter:
      for i from 1 to nops(walk1) do
        step:=op(i,walk1):
        counter:=subsop(abs(step)=op(abs(step),counter)+step,counter):
      od:
      if counter=counter1 then
        RETURN(`This walk is not self avoiding.`):
      fi:
    fi:
  od:
RETURN(1):       
end:




mistwalk:=proc(steps,dim,mist)
  local i, walks, walk,j,dirs,walk1,walks1:
  if not type(steps, integer) then
    ERROR(`The length of a walk must be an integer`):
  fi:
  if steps<=0 then
    ERROR(`A walk must be made up of a positive number of steps`):
  fi:
  if not type(dim, integer) then
    ERROR(`The dimension of a walk must be an integer`):
  fi:
  if dim<=0 then
    ERROR(`Dimension must be positive.`):
  fi:
  if not type(mist, set) then
    ERROR(`The mistakes must be given as a set`):
  fi:
  dirs:=[]:
  for i from 1 to dim do
    dirs:=[op(dirs),i,-i]:
  od:
  walks:={}:
  for i from 1 to (2*dim) do
    if not member([op(i,dirs)], mist) then
      walks:=walks union {[op(i,dirs)]}:
    fi:
  od:
  walks1:=walks:
  if steps > 1 then
    walks1:={}:
    walks:=convert(mistwalk(steps-1,dim,mist),list):
    for j from 1 to nops(walks) do
      walk:=op(j,walks):
      for i from 1 to (2*dim) do
        walk1:=[op(walk), op(i,dirs)]:
        if not member(walk1, mist) then
          if avoidmist(walk1,mist)=1 then
            walks1:=walks1 union {walk1}:
          fi:
        fi:
      od:
    od:
  fi:
walks1: 
end:

mistwalk1:=proc(steps,dim,mist,prev)
  local i,walks, walk,j,dirs,walk1,walks1:
  if not type(steps, integer) then
    ERROR(`The length of a walk must be an integer`):
  fi:
  if steps<=0 then
    ERROR(`A walk must be made up of a positive number of steps`):
  fi:
  if not type(dim, integer) then
    ERROR(`The dimension of a walk must be an integer`):
  fi:
  if dim<=0 then
    ERROR(`Dimension must be positive.`):
  fi:
  if not type(mist, set) then
    ERROR(`The mistakes must be given as a set`):
  fi:
  dirs:=[]:
  for i from 1 to dim do
    dirs:=[op(dirs),i,-i]:
  od:
  if steps = 1 then
    walks:={}:
    for i from 1 to (2*dim) do
      if not member([op(i,dirs)], mist) then
        walks:=walks union {[op(i,dirs)]}:
      fi:
    od:
    walks1:=walks:
  elif steps > 1 then
    walks1:={}:
    walks:=prev:
    for j from 1 to nops(walks) do
      walk:=op(j,walks):
      for i from 1 to (2*dim) do
        walk1:=[op(walk), op(i,dirs)]:
        if not member(walk1, mist) then
          if avoidmist(walk1,mist)=1 then
            walks1:=walks1 union {walk1}:
          fi:
        fi:
      od:
    od:
  fi:
walks1: 
end:


#The preceeding procedure is used when the number of mistake free self avoiding 
#walks of a given length is needed.

runmist:=proc(n,dim,mistakes)
  local mem1,mem2,i,ls:
  mem1:={[]}:
  ls:=[nops(mem1)]:
  for i from 1 to n do
    mem2:=mistwalk1(i,dim,mistakes,mem1);
    mem1:=mem2:
    ls:=[op(ls),nops(mem1)]:
    print(ls):
  od:
  mem1;
  ls;
end:  




#This procedue produces the subset of a set that contains all elements up to 
#geometric symmetry.

symmset:=proc(set1)
local i,n,type1,types,symms,set2:
n:=nops(set1):
set2:=set1:
types:={}:
for i from 1 to n while nops(set2)>0 do
  type1:=op(1,set2):
  types:=types union {type1}:
  symms:=symm1(type1):
  set2:=set2 minus symms:
od:
types:
end:

#This procedure produces all symmetries of an input element

symm1:=proc(type1)
local a,b,c,d,typei,symms,typeb,typebb,typebbb,typea,typeab,typeabb,typeabbb:
typei:=subs({1=a,2=b,-1=c,-2=d},type1):
symms:={type1}:
typeb:=subs({a=2,b=-1,c=-2,d=1},typei):
symms:=symms union {typeb}:
typebb:=subs({a=-1,b=-2,c=1,d=2},typei):
symms:=symms union {typebb}:
typebbb:=subs({a=-2,b=1,c=2,d=-1},typei):
symms:=symms union {typebbb}:
typea:=subs({a=-1,b=2,c=1,d=-2},typei):
symms:=symms union {typea}:
typeab:=subs({a=-2,b=-1,c=2,d=1},typei):
symms:=symms union {typeab}:
typeabb:=subs({a=1,b=-2,c=-1,d=2},typei):
symms:=symms union {typeabb}:
typeabbb:=subs({a=2,b=1,c=-2,d=-1},typei):
symms:=symms union {typeabbb}:
end:


#This procedure produces all subsets of a given set of a given size

errlist:=proc(Sin,n)
local Sout,i,m,el,Sprev,k,j;
if n<1 then
  ERROR(`A subset of two steps must have a positive number of elements`):
fi:
Sout:={}:
m:=nops(Sin):
if n=1 then
  for i from 1 to m do
    el:={op(i,Sin)}:
    Sout:=Sout union {el}:
   od:
elif n>1 then       
  Sprev:=errlist(Sin,n-1):
  k:=nops(Sprev):
  for i from 1 to k do
    for j from 1 to m do
      el:=op(i,Sprev) union {op(j,Sin)}:
      if nops(el)>nops(op(i,Sprev)) then
        Sout:=Sout union {el}:
      fi:
    od:
  od:
fi:
Sout:
end:
                             
#The following procedures produce sets that are symmetric with respect to taking 
#minuses.

syminus:=proc(set1)
local i,n,type1,types,symms,symms1,j,item1;
n:=nops(set1);
types:={};
for i from 1 to n  do
  type1:=op(i,set1);
  symms1:={}:
  for j from 1 to nops(type1) do
    item1:=op(j,type1);
    symms:=symm2(item1);
    symms1:=symms1 union symms;
    types:=types union {symms1};
  od:
od:
types:
end:

symm2:=proc(type1)
local a,b,c,d,typei,symms,typem:
typei:=subs({1=a,2=b,-1=c,-2=d},type1):
symms:={type1}:
typem:=subs({a=-1,b=-2,c=1,d=2},typei):
symms:=symms union {typem}:

end:


#Applying DAVID_IAN to check to see if the walk generated is automatically
#self-avoiding or not.


runmistA:=proc(n,dim,mistakes)
  local mem1,mem2,i,ls,lsA:
  read DAVID_IAN;
  mem1:={[]}:
  ls:=[nops(mem1)]:
  for i from 1 to min(6,n) do
    mem2:=mistwalk1(i,dim,mistakes,mem1);
    mem1:=mem2:
    ls:=[op(ls),nops(mem1)]:
  od:
  lsA:=GJseries(4,(mistakes union {[1,-1],[2,-2],[-1,1],[-2,2]}),6):
  if ls=lsA then
      print(`These mistakes seem to guarantee that the walk is`);
      print(`self-avoiding.`);
      print(ls):
      RETURN(0);
  fi: 
  for i from min(6,n) to n do
    mem2:=mistwalk1(i,dim,mistakes,mem1);
    mem1:=mem2:
    ls:=[op(ls),nops(mem1)]:
    print(ls):
  od:
  mem1;
  ls;
end: