Conviértete en el asesino de hidra

13

Eres el mejor y más famoso héroe de la zona. Últimamente ha habido rumores de que una Hidra ha estado pasando el rato en un barranco cercano. Siendo el héroe valiente y virtuoso que eres, imaginas que irás a verlo más tarde hoy.

El problema con las hidra es que cada vez que intentas cortarles la cabeza, algunas nuevas vuelven a crecer. Afortunadamente para ti, tienes espadas que pueden cortar varias cabezas a la vez. Pero hay una trampa, si la hidra tiene menos cabezas que los cortes de tu espada, no podrás atacar a la hidra. Cuando la hidra tiene exactamente cero cabezas, la has matado.

También hay una espada especial llamada The Bisector que cortará la mitad de las cabezas de la Hidra, pero solo si el número de cabezas es par. El Bisector no se puede usar en absoluto cuando el número de cabezas es impar. Esto es diferente de cortar cabezas cero.

Así que ha decidido escribir un programa de computadora para descubrir la mejor manera de matar la hidra.

Tarea

Se le dará como entrada

  • el número de cabezas con las que comienza la Hidra
  • la cantidad de cabezas que la Hidra vuelve a crecer cada turno
  • una lista de espadas disponibles para usar cada una (cada una es una bisectriz o corta un número fijo de cabezas cada turno)

Deberías generar una lista de movimientos que matarán a la hidra en el menor número de turnos posible. Si no hay forma de matar a la hidra, debe generar algún otro valor que lo indique (y una lista vacía está bien si su idioma está muy bien escrito). Si hay varias formas óptimas de matar la hidra, puede generar cualquiera de ellas o todas ellas.

Esta es una pregunta de , por lo que las respuestas se puntuarán en bytes, con menos bytes mejor.

Casos de prueba

Más disponible bajo petición

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]

Esta pregunta es una versión simplificada de la mecánica principal de HydraSlayer . Si te gusta este tipo de rompecabezas, te recomiendo echarle un vistazo, es bastante divertido. No tengo ninguna afiliación con el juego.

Post Rock Garf Hunter
fuente
1
El número de cabezas crecidas en cada turno es constante, ¿sí? ¿No depende del número de cabezas cortadas?
KSmarts
1
@KSmarts Eso es correcto.
Post Rock Garf Hunter
Si la bisectriz solo funciona si las cabezas son pares, ¿eso significa que no hace nada si son impares? La solución para @ThePirateBay sería entonces [/ 2, -26]
dj0wns
1
@ dj0wns El Bisector no se puede usar cuando son impares.
Post Rock Garf Hunter
@Nnnes Eso parece ser correcto, incidentalmente [/2, -2, /2, -2, -4]también funciona.
Post Rock Garf Hunter

Respuestas:

3

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])}]`);

Versión sin golf:

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:[];
}

La bisectriz se representa como 0.


fuente