I came across a pretty interesting little puzzle yesterday posted on Hacker News, written by Tejas Dinkar.
The problem was stated as follows:
You are Hercules, about to fight the dreaded Hydra. The Hydra has 9 heads. When a head is chopped off, it spawns 8 more heads. When one of these 8 heads is cut off, each one spawns out 7 more heads. Chopping one of these spawns 6 more heads, and so on until the weakest head of the hydra will not spawn out any more heads.
Our job is to figure out how many chops Hercules needs to make in order to kill all heads of the Hydra. And no, it's not $n!$
The solution that Tejas implemented, which you can find on the page linked above, used an infinite list. I disagree with his solution, because the Hydra will always eventually run out of heads, which would make the remainder of the infinite list elements that were empty lists:
[, [2,2], [1,1,2], [1,2], , [1,1], , , , ... ]
It seems wasteful to me. Below I will show a simple tail-recursive solution written in Scheme.
;; hydra ;; creates a Hydra with n heads (define (hydra n) (make-list n n)) ;; chop ;; chops off a single Hydra head with value X ;; head X is replaced with X - 1 heads of value X - 1 (define (chop h) (cond ((null? h) '()) ((= 1 (car h)) (cdr h)) (else (append (hydra (- (car h) 1)) (cdr h))))) ;; count-chops ;; count the number of chops it takes to kill a Hydra with N heads (define (count-chops heads) (let loop ((h heads) (acc 0)) (if (null? h) acc (loop (chop h) (+ 1 acc)))))
This solution for a Hydra with 9 heads can be found using this:
(count-chops (hydra 9)) ;; computes 986409 in 1.57 seconds
For quick an easy testing of an number of Hydra-heads, I used this this timing function:
(define (test lengths) (map (lambda (n) (with-timings (lambda () (count-chops (hydra n))) (lambda (run-time gc-time real-time) (write (internal-time/ticks->seconds run-time)) (write-char #\space) (write (internal-time/ticks->seconds gc-time)) (write-char #\space) (write (internal-time/ticks->seconds real-time)) (newline)))) lengths) ) (test '(1 2 3 4 5 6 7 8 9)) ;; output: (1 4 15 64 325 1956 13699 109600 986409)