Become the Hydra Slayer

Question

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.

Task

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 code-golf 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.

Answer 1

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:

f=(heads,turn,swords)=>{
  max=heads-Math.min(...swords);

  found=1;
  flags=[];
  queue=[];
  swords.map(a=>queue.push([],heads));

  while(queue.length){
    path=queue.shift();
    heads=queue.shift();

    swords.map(sword=>{
      after=sword?heads+sword:heads/2;

      if(!after){
        found=sword;
      }else if(!(after%1)&after>0&after<max&!flags[after+=turn]){
        flags[after]=1;
        queue.push([...path,sword],after);
      }
    });

    if(found<1){
      path.push(found);
      break;
    }
  }

  return found<1?path:[];
}

The bisector is represented as 0.

Answer 2

Python3, 197 bytes:

def f(h,H,s):
 q=[(h,[])]
 while q:
  h,m=q.pop(0)
  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!