# Samrat Man Singh

Email: mail@samrat.me

Hi! I’m Samrat, a programmer from Nepal.

# Fighting an N-headed monster with recursion

### 2012-10-07

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)))))))

(first (sort (attack-monster heads) (lambda (x y) (< (length x) (length y))))))
> (shortest-way 23)
'(a a a a a)