You are the best and most famous hero of the area. Lately there have been rumors that a Hydra has been hanging out in a nearby ravine. Being the brave and virtuous hero that you are you figure you'll go check it out sometime later today.

The problem with hydrae is that every time you try to cut off their heads some new ones grow back. Luckily for you you have swords that can cut off multiple heads at once. But there's a catch, if the hydra has less heads than your sword cuts, you wont be able to attack the hydra. When the hydra has exactly zero heads, you have killed it.

There is also a special sword called The Bisector that will cut off half of the Hydra's heads, but only if the number of heads is even. The Bisector cannot be used at all when the number of heads is odd. This is different from cutting off zero heads.

So you have decided you will write a computer program to figure out the best way to slay the hydra.


You will be given as input

  • the number of heads the Hydra starts with
  • the number of heads the Hydra regrows each turn
  • a list of swords available for use each (each either is a bisector or cuts a fixed number of heads each turn)

You should output a list of moves that will kill the hydra in the least number of turns possible. If there is no way to kill the hydra you must output some other value indicating so (and empty list is fine if your language is strongly typed). If there are multiple optimal ways to kill the hydra you may output any one of them or all of them.

This is a question so answers will be scored in bytes, with fewer bytes being better.

Test Cases

More available upon request

5 heads, 9 each turn,  [-1,-2,-5] -> [-5]
12 heads, 1 each turn, [/2,-1] -> No solution
8 heads, 2 each turn,  [-9, -1] -> [-1,-9]
3 heads, 23 each turn, [/2,-1,-26] -> [-1,-1,-26,-26,-26,-26,-26,-26,-26,-26]
16 heads, 1 each turn, [/2, 4, 2] -> [/2,-4,/2,-4]

This question is a simplified version of the main mechanic of HydraSlayer. If you like this type of puzzle I recommend checking it out, its pretty fun. I do not have any affiliation with the game.

  • 2
    \$\begingroup\$ The number of heads grown each turn is constant, yes? Not dependent on the number of heads cut off? \$\endgroup\$
    – KSmarts
    Aug 7, 2017 at 16:27
  • 2
    \$\begingroup\$ @KSmarts That's correct. \$\endgroup\$
    – Wheat Wizard
    Aug 7, 2017 at 16:28
  • \$\begingroup\$ If the bisector only works if the heads are even does that mean it does nothing if they are odd? Solution to @ThePirateBay would then be [/2,-26] \$\endgroup\$
    – dj0wns
    Aug 7, 2017 at 18:20
  • 1
    \$\begingroup\$ @dj0wns The Bisector cannot be used when they are odd. \$\endgroup\$
    – Wheat Wizard
    Aug 7, 2017 at 18:21
  • \$\begingroup\$ @Nnnes That seems to be correct, incidently [/2, -2, /2, -2, -4] also works. \$\endgroup\$
    – Wheat Wizard
    Aug 7, 2017 at 19:09

2 Answers 2


JavaScript, 230 223 bytes

f=(h,t,s)=>{m=h-Math.min(...s),d=1,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>!(a=w?h+w:h/2)?d=w:!(a%1)&a>0&a<m&!f[a+=t]?f[q.push([...p,w],a),a]=1:0);d<1?(q=[],p).push(d):0}return d<1?p:[]}

_=_=>f=(h,t,s)=>{m=h-Math.min(...s),d=1,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>!(a=w?h+w:h/2)?d=w:!(a%1)&a>0&a<m&!f[a+=t]?f[q.push([...p,w],a),a]=1:0);d<1?(q=[],p).push(d):0}return d<1?p:[]}

console.log(`[${_()(5, 9,  [-1,-2,-5])}]`);
console.log(`[${_()(12, 1, [0,-1])}]`);
console.log(`[${_()(8, 2,  [-9,-1])}]`);
console.log(`[${_()(1, 2,  [0,-4])}]`);
console.log(`[${_()(3, 2,  [0,-4,-1])}]`);
console.log(`[${_()(3, 4,  [0,-4,-1])}]`);
console.log(`[${_()(3, 23, [0,-1,-26])}]`);
console.log(`[${_()(16, 1, [0,-4,-2])}]`);

Ungolfed version:





      }else if(!(after%1)&after>0&after<max&!flags[after+=turn]){


  return found<1?path:[];

The bisector is represented as 0.


Python3, 197 bytes:

def f(h,H,s):
 while q:
  if 0==h:return m
  if m:h+=H
  for S in s:
   if((S==0.5 and 0==h%2)or(S!=0.5 and h>=abs(S)))and(h,S)not in m:q+=[([h/2,h+S][S!=0.5],m+[(h,S)])]

Try it online!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.