Codegolf - Возвращение Истребителя Гидры

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

Вы приходите в арсенал, чтобы получить свои мечи, но у них нет обычных мечей, и у них остались только Секторы. 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, 191 190 байт

Сэкономил байт благодаря Степ Хен

 
 
 
 
 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
 
 
 
 
 

Питон 2, 169 195 222 байт

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

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

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

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

Требует AndAlso

Функция Or takes two And (количество голов и скорость отрастания головок), а также Nothing (Sectors), and returns a Nothing Ничего`, если нет решения.

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

N parameters are for the recursive calls to save state. They track the current order of Sectors in use, the shortest order of Sectors ever, and the number of heads ever encountered. If we encounter the same number of heads again, there has to have been a shorter way to reach it.

Единственный порядок секторов, который имеет значение, — это то, что мне нужно. 1 to be last if it exists. Otherwise, the hydra will might grow without bounds because I could at every turn just use the 1 Сектор и никогда не пробуйте другой.

Я объявил константу Optional to represent List(Of Int64) (the ordered choice of Sectors). Returns , сокращая 6 байт каждый раз, когда я хотел использовать List(Of Int64) .

Int64 / Z не являются коротким замыканием, поэтому я использую нулевой условный оператор ( 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 ) to avoid object null errors. In real code, I would use Imports System.Collections.Generic / 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] which do short-circuit.

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

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])}]`); un-golfed for readability