### Pat Devlin - Homework 11 - 25 February 2012 - I have no preferrences about keeping my work private ###

# This may be buggy #

Help:=proc():
  print(`CS(n, giveupdatesWhen:=-1), naiveRec(n, L, sanity_check, giveUpdatesWhen, biggestSoFar)`):
  print(`depthUntil1(L), curlingNumber(L), curlingNumberGivenTailLength(L, tailLength)`):
  print(`curlingNumberGivenTail(L, tail)`):
end proc:

CS:=proc(n, giveUpdatesWhen:=-1) local answer:
  answer:=naiveRec(n, [], 0, giveUpdatesWhen, 1):
  printf(`CS(%d)=%d`, n, answer):
  return answer:
end proc:

naiveRec:=proc(n, L, sanity_check, giveUpdatesWhen, biggestSoFar) local maxBelowThisNode, nextL:
  if(n<=0) then
    if((sanity_check mod 2^(nops(L) - giveUpdatesWhen)) = 0) then
      print(`Checking L=`, L, ` Biggest curling number found so far was`, biggestSoFar):
    fi:
    return depthUntil1(L):
  fi:
  
  maxBelowThisNode:=0:
  
  nextL:=[op(L), 2]:
  if(curlingNumber(nextL) <= 3) then # if the curling number is bigger than 3, then this starting string doesn't lead to a maximum by Sloane's paper
    maxBelowThisNode:=naiveRec(n-1, nextL, sanity_check, giveUpdatesWhen, biggestSoFar):
  fi: 
  
  nextL:=[op(L), 3]:
  if(curlingNumber(nextL) <= 3) then # again, if curling number > 3, we don't have to check this
    maxBelowThisNode:=max(maxBelowThisNode, naiveRec(n-1, nextL, sanity_check+2^(n-1) , giveUpdatesWhen, max(biggestSoFar, maxBelowThisNode))):
  fi:
 
  return maxBelowThisNode:
end proc:

depthUntil1:=proc(L) local lastEntry, L2:
  if(nops(L) < 1) then return 0: fi:
  lastEntry:=min(L):
  L2:=L:

  while((lastEntry>1) and (nops(L2) < 1000)) do
    lastEntry:=curlingNumber(L2):
    L2:=[op(L2), lastEntry]:
  od:

  return nops(L2) -1:
end proc:


curlingNumber:=proc(L) local bestSoFar, tailLength:
  if (nops(L) = 0) then return 1: fi:
  bestSoFar:=1:
  for tailLength from 1 to nops(L) do
    bestSoFar:=max(bestSoFar, curlingNumberGivenTailLength(L, tailLength)):
  od:
  return bestSoFar:
end proc:


curlingNumberGivenTailLength:=proc(L, tailLength) local tail:
  if(tailLength > nops(L)) then return 0: fi:
  tail:=L[(nops(L)-tailLength+1)..nops(L)]:
  return curlingNumberGivenTail(L, tail):
end proc:

curlingNumberGivenTail:=proc(L,tail):
  if(nops(tail) > nops(L)) then return 0: fi:
  if (L[(nops(L)-nops(tail)+1)..nops(L)] = tail) then
   return 1+ curlingNumberGivenTail(L[1..(nops(L)-nops(tail))], tail):
  fi:
  return 0:
end proc: