### 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: