#This package is primarily made up of two procedures;  cubefr, which produces all sequences 
#on an input alphabet that are of length n and cube free, and mistcube, that produces all 
#'mistakes', that is words that are cubes, but contain no sub-cubes.

print(`CUBE FREE`):
print(`A Maple package by Anne E. Edlin`):
print(`Version - 22nd September 1997.`):
print(`This package is designed to produce cube free words`):
print(`and provide list of the most basic cube words of a desired length`):
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(`cubefr, mistcube.`):
  elif nargs=1 and args[1]=cubefr then 
    print(`cubefr requires two inputs, the length of words required`):
    print(`and the alphabet from which the words are to be formed input as a list.`):
    print(`The output is a set of words of the requested length that are cube free.`):
    print(`Example:   cubefr(3,[a,b]);`):
    print(`{[b, a, a], [b, b, a], [a, b, a], [a, b, b], [b, a, b], [a, a, b]}`):
  elif nargs=1 and args[1]=mistcube then
    print(`mistcube requires two inputs, the maximum length of required words`):
    print(`and the alphabet from which the words are to be derived in the form of a lise`):
    print(`The output is a set of words that are cubes,`):
    print(`and contain no other cubes as sub words.`): 
    print(`Example:    mistcube(6,[a,b]);`):
    print(`{[a, a, a], [b, b, b], [a, b, a, b, a, b], [b, a, b, a, b, a]}`):
  else 
    print(`There is no Help available on`, args):
  fi:
end:


#The following procedure generates all cube free words of length n on the given alphabet.

cubefr:=proc(n,alph)
  local out,i,j,step,test:
  option remember:
  if not type(n, integer) then				
    ERROR(`A word can only have integer length.`):
  fi:							#check length is an integer
  if n<1 then	          				
    ERROR(`The length requested for the output words must be at least 1.`):
  fi:							#checks length requested is positive
  if not type(alph,list) then				
    ERROR(`The input alphabet must be in the form of a list`):
  fi:							#checks alphabet is in list form
  if nops(convert(alph, set))<>nops(alph) then		
    ERROR(`The same character can not appear twice in the input alphabet`):
  fi:							#checks list contains no repeats
  out:={}:						#initializes the out put as an empty 	
							#set
  if n=1 then
    for i from 1 to nops(alph) do
      out:=out union {[op(i,alph)]}:			
    od:							#produces all words of length 1
    elif n=2 then
    for i from 1 to nops(alph) do
      for j from 1 to nops(alph) do
        out:= out union {[op(i,alph),op(j,alph)]}:	
      od:
    od:							#produces all words of length 2
    else step:=convert(cubefr(n-1,alph),list);		#calls up cubefree words of 1 less 	
							#length as a list so can be used in 	
							#order
      for i from 1 to nops(step) do
        for j from 1 to nops(alph) do
          test:=[op(j,alph),op(op(i,step))]:		#adjoins each letter to the start of 	
							#previous cube free words
          if cubefr1(test)=1 then			#tests to see if new word is still 	
							#cube free
            out:=out union {test}			#adds new cube free words to output
          fi:  
        od:
      od:
    fi:
  out;
end:



#The following procedure tests to see if a word formed by adding one new letter at the start 
#of a cube free word is cube free.

cubefr1:=proc(word)
  local i:
  for i from 1 to trunc(nops(word)/3) do
    if op(1..i,word)=op(i+1..2*i,word) and op(1..i,word)=op(2*i+1..3*i,word) then
      RETURN(0);
    fi:
  od:							#looks for cubes starting with the 	
							#first letter of all possible 		
							#lengths
  1:
end:



#The following procedure produces all the basic cube words of length at most n on the input 
#alphabet.

mistcube:=proc(n,alph)
  local i,out,test,j,testlist,testcube,k,l,check:
  option remember:
  if not type(n, integer) then				
    ERROR(`A word can only have integer length.`):
  fi:							#check length is an integer
  if n<3 then	          				
    ERROR(`The length requested for the output cube words must be at least 3.`):
  fi:							#checks length is at least 3
    if not type(alph,list) then				
    ERROR(`The input alphabet must be in the form of a list`):
  fi:							#checks alphabet is in list form
  if nops(convert(alph, set))<>nops(alph) then		
    ERROR(`The same character can not appear twice in the input alphabet`):
  fi:							#checks list contains no repeats
  out:={}:
  if n=3 then						#produces initial cube list
    testlist:=convert(cubefr(1,alph),list);		#by taking single letters
    for j from 1 to nops(testlist) do			#and tripling them
      test:=op(j,testlist):
      testcube:=[op(test),op(test),op(test)]:
      out:=out union {testcube}:
    od:
  elif n>3 then						#checks n is large enough for back 	
							#step
    out:=mistcube(n-1,alph):				#finds all cubes of length at most 	
							#n-1 by calling itself 
    if n-1<3*trunc(n/3) then
      testlist:=convert(cubefr(trunc(n/3),alph),list);	#collects a list of cube free words 	
							#of length at most one third 		
							#requested length
      for j from 1 to nops(testlist) do
        test:=op(j,testlist):
        testcube:=[op(test),op(test),op(test)]:		#produces cubes of cube free words
        check:=0:					#initializes check tag
        for k from 1 to nops(testcube)-2 do
          for i from k+2 to nops(testcube) do
            if member([op(k..i,testcube)],mistcube(n-1,alph))  then
              check:=check+1
            fi:						#tests to see if new word contains 
            						#any sub-cubes and if it does  		
          od:			 			#increases the check tag by one
        od:
        if check=0 then
          out:=out union {testcube}:			#adds words whose check tag remained 
        fi:						#0 to output, they are sub cube free
      od:
    fi:
  fi:
  out:
end: