Sie sind der beste und berühmteste Held der Region. In letzter Zeit gab es Gerüchte, dass sich eine Hydra in einer nahe gelegenen Schlucht aufgehalten hat. Da Sie der mutige und tugendhafte Held sind, den Sie sich vorstellen, werden Sie es sich später noch einmal ansehen.

Das Problem mit Hydrae ist, dass jedes Mal, wenn Sie versuchen, ihre Köpfe abzuschneiden, einige neue nachwachsen. Zum Glück haben Sie Schwerter, die mehrere Köpfe gleichzeitig abschneiden können. Aber es gibt einen Haken, wenn die Hydra weniger Köpfe als Ihre Schwertschnitte hat, werden Sie nicht in der Lage sein, die Hydra anzugreifen. Wenn die Hydra genau null Köpfe hat, haben Sie sie getötet.

Es gibt auch ein spezielles Schwert namens The Bisector , das die Hälfte der Köpfe der Hydra abschneidet, aber nur, wenn die Anzahl der Köpfe gerade ist. Der Bisector kann überhaupt nicht verwendet werden, wenn die Anzahl der Köpfe ungerade ist. Dies unterscheidet sich vom Abschneiden von Nullköpfen.

Sie haben beschlossen, ein Computerprogramm zu schreiben, um herauszufinden, wie Sie die Hydra am besten töten können.

Aufgabe

Sie werden als Eingabe gegeben

• Die Anzahl der Köpfe, mit denen die Hydra beginnt
• Die Anzahl der Köpfe, die die Hydra in jeder Runde nachwächst
• Eine Liste der Schwerter, die jeweils zur Verwendung zur Verfügung stehen (jedes ist entweder eine Halbierende oder schneidet in jeder Runde eine feste Anzahl von Köpfen)

Sie sollten eine Liste von Zügen ausgeben, die die Hydra in möglichst wenigen Zügen töten. Wenn es keine Möglichkeit gibt, die Hydra zu töten, müssen Sie einen anderen Wert ausgeben, der dies anzeigt (und eine leere Liste ist in Ordnung, wenn Ihre Sprache stark geschrieben ist). Wenn es mehrere optimale Möglichkeiten gibt, die Hydra zu töten, können Sie eine oder alle davon ausgeben.

Dies ist eine Code-Golf- Frage, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

Weitere auf Anfrage

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]

Diese Frage ist eine vereinfachte Version der Hauptmechanik von HydraSlayer . Wenn Sie diese Art von Rätsel mögen, empfehle ich, es zu überprüfen, es ist ziemlich lustig. Ich habe keine Verbindung zum Spiel.

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

Die Halbierende ist dargestellt als 0.