Sudah lama sejak Anda membunuh hydra itu , Anda berjemur dalam kemuliaan selama bertahun-tahun, tetapi sekarang orang-orang memanggil Anda mandi, sudah. Nah saat Anda membuktikannya salah, Anda pernah mendengar keberadaan hydra lain. Cukup bunuh saja dan Anda akan diberikan semua kemuliaan yang layak Anda dapatkan.

Anda tiba di gudang senjata untuk menerima pedang Anda tetapi mereka semua kehabisan pedang biasa yang tersisa adalah Sektor. Suatu n-sektor akan membagi jumlah kepala pada Hydra dengan n, tetapi hanya dapat digunakan jika jumlah kepala dibagi dengan n.

Sekali lagi Anda akan menulis beberapa kode untuk membantu Anda membunuh hydra. Kode Anda akan diambil sebagai input jumlah head hydra, mulai pertarungan dengan, jumlah head hydra tumbuh setiap belokan, dan daftar n-sektor yang dapat Anda gunakan. Kode Anda akan menampilkan pola gerakan optimal untuk membunuh hydra secepat mungkin

Setiap putaran pertarungan Anda dapat memilih satu pedang untuk digunakan, jika setelah irisan hydra hanya memiliki satu kepala Anda menang, jika tidak itu menumbuhkan kepala. Anda mungkin tidak pernah bergerak, dan jika tidak ada gerakan yang tersedia, Anda kalah.

Jika tidak ada solusi yang mungkin Anda dapat menampilkan apa pun selain solusi, misalnya daftar kosong, tidak ada, angka nol, dll.

Ini adalah kode-golf sehingga jawaban akan dinilai sebagai jumlah byte mereka, dengan lebih sedikit lebih baik.

Uji kasus

Berikut adalah beberapa kasus uji super dasar, lebih banyak kasus uji akan ditambahkan berdasarkan permintaan.

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 byte

Disimpan 4 byte berkat @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}}

Saya telah membuang rekursi kedalaman-pertama yang saya coba gunakan untuk loop pertama yang jauh lebih aman. Outputs solusi sebagai array jika ada, berjalan selamanya jika tidak. Jika ini tidak diijinkan, inilah yang akhirnya berhenti (pada kebanyakan kasus, bagaimanapun):

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

Menyimpan satu byte berkat Langkah Hen

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

+26 byte untuk menangani regenerasi kepala siklik dengan benar pada pilihan senjata yang buruk. (Terima kasih kepada @ThePirateBay untuk menunjukkannya)

+27 byte untuk memperbaiki kasus tepi tertentu yang menyebabkan kesalahan.

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]

Cobalah online!

VB.NET (.NET 4.5), 439 + 35 (impor) = 474 byte

Membutuhkan 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

Fungsi ini Zmengambil dua Int64(jumlah head dan head regrow rate), dan a List(Of Int64)(Sektor), dan mengembalikan List(Of Int64) (the ordered choice of Sectors). ReturnsNothing` jika tidak ada solusi.

Asumsikan Sektor disajikan dalam urutan diurutkan dari terbesar ke terkecil.

The Optionalparameter untuk panggilan rekursif untuk menyelamatkan negara. Mereka melacak urutan Sektor saat ini yang digunakan, urutan Sektor terpendek yang pernah ada, dan jumlah kepala yang pernah ditemui. Jika kita menemukan jumlah kepala yang sama lagi, pasti ada cara yang lebih pendek untuk mencapainya.

Satu-satunya pemesanan Sektor yang penting adalah saya harus 1menjadi yang terakhir jika ada. Kalau tidak, hydra akan tumbuh tanpa batas karena saya bisa setiap saat hanya menggunakan1 Sektor dan tidak pernah mencoba yang lain.

Saya menyatakan konstanta Nuntuk diwakili Nothing, mencukur 6 byte setiap kali saya ingin menggunakannya Nothing.

And/ Orbukan hubungan arus pendek, jadi saya menggunakan operator kondisional null ( ?.) untuk menghindari objek null error. Dalam kode nyata, saya akan menggunakan AndAlso/ OrElseyang melakukan hubungan pendek.

Cobalah online!

Z un-golfed untuk keterbacaan

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