I enjoyed this too and also got stuck a bit on the banana. I think also one problem is (ROT13)
V nffbpvngrq onananf jvgu gebcvpny pyvzngrf naq fabj jvgu nepgvp pyvzngrf, fb V qvqa'g rknzvar gur fabj hagvy V gevrq rirelguvat ryfr.
And yes I agree once I saw it, it was clearly meant not to be hard.
I poked at the hints once when I needed the banana and Zeus did say "you have pretty much everything you need"
So I think it's just a matter of pseudocoding
(if player has sword and player does not have banana)Zeus says, "an embellishment for the sword has to be around somewhere. Search everywhere."(endif)