Прошло много времени с тех пор, как вы убили эту гидру , вы годами грелись в славе, но теперь люди зовут вас вымытыми. Что ж, пришло время доказать, что они не правы, вы слышали о местонахождении другой гидры. Просто убейте его, и вы получите всю славу, которую заслуживаете.

Вы прибываете в арсенал, чтобы получить свои мечи, но все они из обычных мечей, все, что у них осталось, это Секторы. N-сектор разделит число голов гидры на n, но может использоваться только в том случае, если количество голов делится на n.

Еще раз вы собираетесь написать код, который поможет вам убить гидру. Ваш код будет принимать в качестве входных данных число голов гидры, с которых начинается бой, количество голов гидры растет с каждым ходом и список n-секторов, которые вы можете использовать. Ваш код выведет оптимальную схему ходов, чтобы убить гидру как можно быстрее

Каждый ход боя вы можете выбрать один меч для использования, если после среза у гидры есть только одна голова, которую вы выигрываете, если нет, у нее вырастают головы. Вы можете никогда не сделать ход, и если нет доступных ходов, вы потеряете.

Если решение невозможно, вы можете вывести что-либо кроме решения, например, пустой список, ничего, ноль и т. Д.

Это код-гольф, поэтому ответы будут оцениваться по мере подсчета байтов, при этом меньше будет лучше.

Контрольные примеры

Вот несколько супер базовых тест-кейсов, по запросу будет добавлено больше тест-кейсов.

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 байт

Сохранено 4 байта благодаря @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}}

Я отбросил рекурсию первой глубины, которую я пытался использовать для более безопасных петель первой ширины. Выводит решение в виде массива, если оно существует, работает вечно, если его нет. Если это недопустимо, вот тот, который в конечном итоге останавливается (в большинстве случаев, во всяком случае):

(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 байт

Спас байт благодаря Step 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 байта

+26 байт для правильной обработки циклической регенерации головы при неудачном выборе оружия. (Спасибо @ThePirateBay за указание на это)

+27 байт, чтобы исправить некоторые крайние случаи, вызывающие ошибки.

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]

Попробуйте онлайн!

VB.NET (.NET 4.5), 439 + 35 (импорт) = 474 байта

требует 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

Функция Zпринимает два Int64(число головок и скорость повторного роста головок) и a List(Of Int64)(секторы) и возвращает List(Of Int64) (the ordered choice of Sectors). ReturnsNothing`, если решения не существует.

Предполагается, что сектора представлены в отсортированном порядке от наибольшего к наименьшему.

Эти Optionalпараметры являются рекурсивными вызовами для сохранения состояния. Они отслеживают текущий порядок использования Секторов, самый короткий порядок Секторов за все время и количество когда-либо встреченных голов. Если мы снова столкнемся с таким же количеством голов, должен был быть более короткий путь к нему.

Единственный порядок Секторов, который имеет значение, это то, что я должен 1быть последним, если он существует. В противном случае гидра может расти без границ, потому что я мог бы на каждом шагу просто использовать 1Сектор и никогда не пробовать другой.

Я объявил константу Nдля представления Nothing, сбрасывая 6 байтов каждый раз, когда я хотел использовать Nothing.

And/ Orне являются короткими замыканиями, поэтому я использую условный оператор null ( ?.), чтобы избежать ошибок null объекта. В реальном коде я бы использовал AndAlso/ OrElseкоторые делают короткое замыкание.

Попробуйте онлайн!

Z не-гольф для удобства чтения

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