Minęło trochę czasu, odkąd zabiłeś tę hydrę , przez lata pławiłeś się w chwale, ale teraz ludzie nazywają cię wyrzuconym, tak było. Cóż, czas, abyś udowodnił, że się mylą, słyszałeś o miejscu pobytu innej hydry. Po prostu go zabij, a otrzymasz całą chwałę, na jaką zasługujesz.

Przybywasz do zbrojowni, aby odebrać miecze, ale wszystkie mają nieregularne miecze, pozostały tylko sektory. Sektor n podzieli liczbę głów na Hydrze przez n, ale można go użyć tylko wtedy, gdy liczbę głów można podzielić przez n.

Po raz kolejny napiszesz kod, który pomoże ci zabić hydrę. Twój kod weźmie jako dane wejściowe liczbę głów hydry, rozpocznie walkę, liczbę głów hydry rośnie z każdą turą oraz listę n-sektorów, których możesz użyć. Twój kod wygeneruje optymalny wzorzec ruchów, aby zabić hydrę tak szybko, jak to możliwe

W każdej turze walki możesz wybrać jeden miecz do użycia, jeśli po wycięciu hydra ma tylko jedną głowę, którą wygrywasz, jeśli nie, rośnie głów. Nigdy nie możesz wykonać żadnego ruchu, a jeśli nie ma dostępnych ruchów, tracisz.

Jeśli żadne rozwiązanie nie jest możliwe, możesz wypisać cokolwiek innego niż rozwiązanie, np. Pusta lista, nic, liczba zero itp.

To jest golf golfowy, więc odpowiedzi będą naliczane według liczby bajtów, przy czym im mniej, tym lepiej.

Przypadki testowe

Oto kilka bardzo podstawowych przypadków testowych, więcej przypadków testowych zostanie dodanych na żądanie.

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 105 bajtów

Zaoszczędź 4 bajty dzięki @ThePirateBay

(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}}

Porzuciłem rekurencję z pierwszej głębokości, której próbowałem użyć dla znacznie bezpieczniejszych pętli z pierwszą szerokością. Wysyła rozwiązanie jako tablicę, jeśli istnieje, działa zawsze, jeśli nie istnieje. Jeśli nie jest to dozwolone, oto taki, który ostatecznie zatrzymuje się (w większości przypadków w każdym razie):

(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 bajtów

Oszczędność bajtu dzięki Stepowi Henowi

(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 bajtów

+26 bajtów, aby poprawnie obsługiwać cykliczną regenerację głowy przy złych typach broni. (Dzięki @ThePirateBay za wskazanie tego)

+27 bajtów, aby naprawić niektóre przypadki krawędzi powodujące błędy.

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]

Wypróbuj online!

VB.NET (.NET 4.5), 439 + 35 (import) = 474 bajty

Wymaga 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

Funkcja Zprzyjmuje dwa Int64(liczba głowic i tempo odrastania głowicy) oraz a List(Of Int64)(Sektory) i zwraca List(Of Int64) (the ordered choice of Sectors). ReturnsNic, jeśli nie ma rozwiązania.

Zakłada, że ​​sektory są posortowane w kolejności od największej do najmniejszej.

Te Optionalparametry są dla wywołania rekurencyjne zapisać stan. Śledzą bieżącą kolejność sektorów w użyciu, najkrótszą kolejność sektorów w historii oraz liczbę napotkanych głów. Jeśli ponownie napotkamy tę samą liczbę głów, musi być krótszy sposób, aby ją osiągnąć.

Jedyne uporządkowanie sektorów, które ma znaczenie, to muszę 1być ostatni, jeśli istnieje. W przeciwnym razie hydra może rosnąć bez ograniczeń, ponieważ mógłbym na każdym kroku po prostu użyć 1Sektora i nigdy nie próbować innego.

Zadeklarowałem stałą Ndo reprezentowania Nothing, goląc 6 bajtów za każdym razem, gdy chciałem użyć Nothing.

And/ Ornie powodują zwarcia, więc używam operatora warunkowego zerowego ( ?.), aby uniknąć błędów zerowego obiektu. W prawdziwym kodzie użyłbym AndAlso/ OrElsektóre powodują zwarcie.

Wypróbuj online!

Z bez golfa dla czytelności

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