Big O and Algorithm Analysis: The Hydra Problem

This time I wanted to present a more challenging problem in an open-ended way; I have a solution but I'm not sure if it's the best solution.

A while ago I stumbled upon the hydra problem, specifically this version.  (Go ahead and read that page now.)

The proof that the hydra will eventually be defeated requires transfinite induction, which we're not covering in this course, but I was curious about defeating the hydra efficiently.  (Let's consider a step to be chopping off a single head, since it's nicely independent of the hydra size and easy to track.)  So I tried my first guess at an efficient algorithm, and then tried the autoplay function.

The results?  Ba gur fnzr fgnegvat ulqen, zl svefg-thrff nytbevguz svavfurq va gjb uhaqerq naq friragl-guerr fgrcf (gurer'f fbzr inevngvba orgjrra ehaf qhr gb gur enaqbzvmngvba bs tebjvat onpx urnqf, ohg vg fgnlf jryy jvguva guvf beqre bs zntavghqr) naq gur nhgbcynl nytbevguz tbg gb bire n zvyyvba fgrcf (gnxvat jryy bire n jrrx!) orsber zl oebjfre penfurq.  (Take a guess first if you want to, then decode the above here.)

Clearly there is a huge difference in efficiency, and the multiple orders of magnitude involved show why efficiency matters.  I haven't done a big-O analysis of this problem, but I suspect the worst-case performance bound would be a function of starting hydra depth h, maximum recursive depth (when growing back from dire necks) r, and maximum copies allowed (when growing back from normal necks) m.

But which algorithms are efficient on this problem?  I invite you to guess; I'll present my solution at the end.

Hints:

1. What could you do to minimize the hydra's ability to grow back?
2. What could you do to maximize the hydra's ability to grow back?  (Pretend that after a while your worst enemy was going to fight it and you wanted to make the fight as hard as possible, if that helps.)
3. Observe the autoplay algorithm.  Are there any moves it makes which help it defeat the hydra quickly?  Are there any moves it makes which make more work for itself?

My solution: Ng rnpu fgrc, pbafvqre bayl gur uvturfg yriry bs urnqf.  Phg nal qver arpxf svefg, sbyybjrq ol abezny arpxf.  Erfbyir gvrf ol phggvat arpxf jvgu gur fznyyrfg ahzore bs fvoyvat arpxf svefg (erphefviryl vs arprffnel).  Vs guvf qbrfa'g erfbyir gur gvr, cvpx ng enaqbz orgjrra gur gvrq arpxf.  (Again, decode here.)