Fighting an N-headed monster with recursion

• 2 min read

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 (attack-monster heads)
  (use-sword heads 0 '()))

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

(define (shortest-way heads)
  (first (sort (attack-monster heads) (lambda (x y) (< (length x) (length y))))))

Here’s how to use it:

> (shortest-way 23)
'(a a a a a)

Thanks to skeeto on Reddit for helping me out with this, and more importantly for not showing me his code :)

Also, I’d love to see how you guys do this in a more efficient and more elegant ways.

Now look what you've done 🌋
Stop clicking and run for your life! 😱
Uh oh, I don't think the system can't handle it! 🔥
Stop it, you're too kind 😄
Thanks for the love! ❤️
Thanks, glad you enjoyed it! Care to share?
Hacker News Reddit

×

Recommended Posts ✍🏻

See All »
• 6 min read
TIL: Sum Types With `instructor_ex`
Read Post »
• 1 min read
TIL: Creating `sentence-transformers` Embedding...
Read Post »
• 1 min read
TIL: File Uploads Using the Req Elixir Library
Read Post »