Es ist schon eine Weile her, seit du diese Hydra getötet hast , du hast dich jahrelang in der Herrlichkeit gebadet, aber jetzt rufen die Leute dich angespült. Nun, es ist an der Zeit, dass Sie ihnen das Gegenteil beweisen. Sie haben den Aufenthaltsort einer anderen Hydra gehört. Töte es einfach und du bekommst den Ruhm, den du verdienst.

Du kommst in die Waffenkammer, um deine Schwerter zu erhalten, aber sie bestehen nur noch aus Sektoren. Ein n-Sektor teilt die Anzahl der Köpfe einer Hydra durch n, kann jedoch nur verwendet werden, wenn die Anzahl der Köpfe durch n teilbar ist.

Wieder einmal werden Sie Code schreiben, der Ihnen hilft, die Hydra zu töten. Ihr Code verwendet als Eingabe die Anzahl der Köpfe der Hydra, beginnt den Kampf mit, die Anzahl der Köpfe, mit denen die Hydra in jeder Runde wächst, und eine Liste von n Sektoren, die Sie verwenden können. Ihr Code gibt ein optimales Bewegungsmuster aus, um die Hydra so schnell wie möglich zu töten

In jeder Runde des Kampfes kannst du ein einzelnes Schwert auswählen, wenn die Hydra nach einer Scheibe nur einen Kopf hat, den du gewinnst, wenn sie nicht wächst, wächst der Kopf. Du darfst niemals keinen Zug machen, und wenn keine möglichen Züge verfügbar sind, verlierst du.

Wenn keine Lösung möglich ist, können Sie etwas anderes als eine Lösung ausgeben, z. B. eine leere Liste, nichts, die Zahl Null usw.

Dies ist Codegolf, daher werden Antworten nach der Anzahl ihrer Bytes bewertet, wobei weniger besser ist.

Testfälle

Hier sind einige Super-Basic-Testfälle, weitere Testfälle werden auf Anfrage hinzugefügt.

24 heads, 1  heads per turn, [2,3] -> [3,3,2,3]
25 heads, 2  heads per turn, [2,3] -> No solutions
4  heads, 2  heads per turn, [2]   -> No solutions
4  heads, 3  heads per turn, [2,5] -> [2,5]
10 heads, 17 heads per turn, [2, 3, 7, 19] -> No solutions
10 heads, 6  heads per turn, [1,16] -> [1,16]
6  heads, 2  heads per turn, [2, 3, 5] -> [2, 5]
125 heads, 1  head per turn, [1, 2, 3, 127] -> [1, 1, 127]

JavaScript (ES6), 111 bis 105 Byte

4 Bytes dank @ThePirateBay gespart

(h,p,a)=>{for(b={[h]:[]};c=b,b=[];)for(d in c)for(e of a){d%e?0:q=b[d/e+p]=[...c[d],e];if(d==e)return q}}

Ich habe die Tiefenrekursion, die ich für die viel sichereren Breitenrekursionen verwenden wollte, über Bord geworfen. Gibt die Lösung als Array aus, falls vorhanden, und wird für immer ausgeführt, wenn dies nicht der Fall ist. Wenn dies nicht zulässig ist, ist hier eine, die schließlich anhält (in den meisten Fällen jedenfalls):

(h,p,a)=>{for(b={[h]:[]};c=b,b=[],c+c;)for(d in c){for(e of a){a[[,d]]||d%e?0:q=b[d/e+p]=[...c[d],e];if(d==e)return q}a[[,d]]=1}}

JavaScript, 191 190 Bytes

Dank Step Hen wurde ein Byte gespeichert

(h,t,s)=>eval(`r=[],d=0,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>(a=h/w)==1?d=w:!(a%1)&!r[a+=t]?r[q.push([...p,w],a),a]=1:0);d?(q=[],p).push(d):0}d?p:[]`)

f=(h,t,s)=>eval(`r=[],d=0,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>(a=h/w)==1?d=w:!(a%1)&!r[a+=t]?r[q.push([...p,w],a),a]=1:0);d?(q=[],p).push(d):0}d?p:[]`)

console.log(`[${f(24, 1, [2,3])}]`);
console.log(`[${f(25, 2, [2,3])}]`);
console.log(`[${f(4, 2, [2])}]`);
console.log(`[${f(4, 3, [2,5])}]`);
console.log(`[${f(10, 17, [2, 3, 7, 19])}]`);
console.log(`[${f(10, 6, [1,16])}]`);
console.log(`[${f(125, 1, [1, 16])}]`);
console.log(`[${f(1024, 3, [1, 2, 137])}]`);

Python 2 , 169 195 222 Bytes

+26 Bytes, um die zyklische Kopfregeneration bei schlechten Waffenpicks richtig zu handhaben. (Danke an @ThePirateBay für den Hinweis)

+27 Bytes, um bestimmte Randfälle zu beheben, die Fehler verursachen.

lambda n,p,w:g(n,n,p,w[::-1])[:-1]
def g(n,b,p,w,a=[]):
 if b<2:return[1]
 for x in w:
	if n%x<1and n/x+p!=n and n not in a:
	 try:
		l=[x]+g(n/x+p,n/x,p,w,[n]+a)
	 	if l and l[-1]!=0:return l
	 except:return[0]
 return[0]

Probieren Sie es online!

VB.NET (.NET 4.5), 439 + 35 (Importe) = 474 Byte

Benötigt Imports System.Collections.Generic

Const N=Nothing
Function Z(h,r,a,Optional c=N,Optional p=N,Optional ByRef s=N)
If c Is N Then
c=New List(Of Long)
p=New List(Of Long)
End If
If s IsNot N And s?.Count<c.Count Then Return N
If p.Contains(h)Then Return N
p.Add(h)
For i=0To a.Count-1
Dim w=a(i)
If h Mod w=0Then
c.Add(w)
If h\w=1And(s Is N Or s?.Count>c.Count)Then
s=New List(Of Long)
s.AddRange(c)
End If
Z(h\w+r,r,a,c,p,s)
c.RemoveAt(c.Count-1)
End If
Next
Z=s
End Function

Die Funktion Znimmt zwei Int64(Anzahl der Köpfe und Kopfnachwuchsrate) und a List(Of Int64)(Sektoren) und gibt ein List(Of Int64) (the ordered choice of Sectors). ReturnsNichts zurück, wenn es keine Lösung gibt.

Angenommen, die Sektoren werden in sortierter Reihenfolge vom größten zum kleinsten dargestellt.

Die OptionalParameter sind für die rekursiven Aufrufe zum Speichern des Status. Sie verfolgen die aktuelle Reihenfolge der verwendeten Sektoren, die kürzeste Reihenfolge aller Sektoren und die Anzahl der jemals angetroffenen Köpfe. Wenn wir wieder auf die gleiche Anzahl von Köpfen stoßen, muss es einen kürzeren Weg geben, um dorthin zu gelangen.

Die einzige Reihenfolge der Sektoren, die von Bedeutung ist, muss 1die letzte sein, wenn sie existiert. Andernfalls könnte die Hydra grenzenlos wachsen, da ich jederzeit nur den 1Sektor nutzen und niemals einen anderen ausprobieren könnte.

Ich habe eine Konstante Nzum Darstellen deklariert und Nothingjedes Mal, wenn ich sie verwenden möchte, 6 Byte gespart Nothing.

And/ OrNicht kurzgeschlossen, so dass ich die Null - Bedingungsoperator (Verwendung ?.) zu vermeiden Objekt null Fehler. In echtem Code würde ich AndAlso/ OrElsewhat do short-circuit verwenden.

Probieren Sie es online!

Z Aus Gründen der Lesbarkeit nicht Golf gespielt

Public Function Z(currentHeads As Long, regrowRate As Integer, weapons As ISet(Of Long), Optional currentWeapons As List(Of Long) = Nothing, Optional previousHeads As List(Of Long) = Nothing, Optional shortestWeapons As List(Of Long) = Nothing) As List(Of Long)

    ' initial call
    If currentWeapons Is Nothing Then
        currentWeapons = New List(Of Long)
        previousHeads = New List(Of Long)
    End If

    ' we've made more moves than our best so far
    If shortestWeapons IsNot Nothing AndAlso shortestWeapons.Count <= currentWeapons.Count Then
        Return Nothing
    End If

    ' exit, we've been here before
    If previousHeads.Contains(currentHeads) Then
        Return Nothing
    End If

    ' keep track of previous state to prevent duplicate paths
    previousHeads.Add(currentHeads)

    For Each w In weapons

        ' save 1 for last
        If w = 1 Then Continue For

        If currentHeads Mod w = 0 Then
            currentWeapons.Add(w)

            If currentHeads \ w = 1 Then
                If shortestWeapons Is Nothing OrElse shortestWeapons.Count > currentWeapons.Count Then
                    shortestWeapons = New List(Of Long)(currentWeapons)
                End If
            End If

            Dim answer = A(currentHeads \ w + regrowRate, regrowRate, weapons, currentWeapons, previousHeads, shortestWeapons)
            If answer IsNot Nothing Then
                If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
                    shortestWeapons = New List(Of Long)(answer)
                End If
            End If

            currentWeapons.RemoveAt(currentWeapons.Count - 1)
        End If
    Next

    If weapons.Contains(1) Then
        currentWeapons.Add(1)

        Dim answer = A(currentHeads \ 1 + regrowRate, regrowRate, weapons, currentWeapons, previousHeads, shortestWeapons)
        If answer IsNot Nothing Then
            If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
                shortestWeapons = New List(Of Long)(answer)
            End If
        End If

        currentWeapons.RemoveAt(currentWeapons.Count - 1)
    End If

    Return shortestWeapons
End Function