13
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ The number of heads grown each turn is constant, yes? Not dependent on the number of heads cut off? \$\endgroup\$ – KSmarts Aug 7 '17 at 16:27
  • 1
    \$\begingroup\$ @KSmarts That's correct. \$\endgroup\$ – Wheat Wizard Aug 7 '17 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 '17 at 18:20
  • 1
    \$\begingroup\$ @dj0wns The Bisector cannot be used when they are odd. \$\endgroup\$ – Wheat Wizard Aug 7 '17 at 18:21
  • \$\begingroup\$ @Nnnes That seems to be correct, incidently [/2, -2, /2, -2, -4] also works. \$\endgroup\$ – Wheat Wizard Aug 7 '17 at 19:09
3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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