# Fighting an N-headed monster with recursion

Posted on Oct 7, 2012

A while back, I came upon this problem:

“You need to kill an N-headed monster. To do that, you have two swords. The first sword(A) cuts `cutA` heads, however, in case the monster doesn’t die(ie `no. of heads > 0`), it will grow `growA` heads. The second sword works the same way, except that it’ll cut `cutB` heads and in case the monster is still alive, it’ll grow `growB` heads. If a sword is used to result in the no. of monster heads being less than 0, you die.”

The problem is to find the shortest combination of swords that can be used to kill the monster(without killing yourself).

This is a paraphrase of the original question(so the question might have sounded a bit awkward). Here’s my solution to it, in Scheme(Racket):

``````(define cutA 7)
(define growA 3)
(define cutB 5)
(define growB 2)

(define (use-sword n grow s)
(cond ((< n 0) '())
((= n 0)
(list s))
(else
(append
(use-sword (- (+ n grow) cutA) growA (append s (list 'a)))
(use-sword (- (+ n grow) cutB) growB (append s (list 'b)))))))

``````> (shortest-way 23)