# Return of the Hydra Slayer

Its been a while since you killed that hydra, you basked in the glory for years, but now people are calling you washed up, a has been. Well its time you prove them wrong, you've heard the whereabouts of annother hydra. Simply kill it and you will be awarded all the glory you deserve.

You arrive at the armory to receive your swords but they're all out of regular swords all they have left are Sectors. An n-sector will divide the number of heads on a Hydra by n, but can only be used if the number of heads is divisible by n.

Once again you are going to write some code to help you slay the hydra. Your code will take as input the number of head the hydra, begins the fight with, the number of heads the hydra grows each turn, and a list of n-sectors you can use. Your code will output an optimal pattern of moves to slay the hydra as quickly as possible

Each turn of the fight you may select a single sword to use, if after a slice the hydra has only one head you win, if not it grows heads. You may never make no move, and if there are no possible moves available you lose.

If no solution is possible you may output anything other than a solution, e.g. an empty list, nothing, the number zero, etc.

This is so answers will be scored as their byte counts, with less being better.

# Test cases

Here are some super basic test-cases, more test-cases will be added upon request.

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

• Can the hydra only have 1 head to start? Commented Aug 10, 2017 at 20:18
• @ETHproductions You do not have to handle that case. Commented Aug 10, 2017 at 20:18
• Can we assume that the list is sorted? Commented Aug 10, 2017 at 20:33
• @ETHproductions Yes you may. I don't see why not. Commented Aug 10, 2017 at 20:33
• A 1-sector is basically a "skip turn" sword?
– Neil
Commented Aug 11, 2017 at 8:41

# JavaScript, 191 190 bytes

Saved a byte thanks to 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, 169195 222 bytes

+26 bytes to properly handle cyclic head regeneration on bad weapon picks. (Thanks to @ThePirateBay for pointing it out)

+27 bytes to fix certain edge cases causing errors.

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]


Try it online!

• Usually the resuable bit means you can't create global vars, modify them, and assume they are back to the original value next time. Dunno what the policy is on erroring here - full programs would definitely be allowed to error out for empty output. Commented Aug 10, 2017 at 21:25
• 210 bytes Commented Aug 22, 2017 at 22:08
• Possible 208 bytes. Commented Jun 11, 2018 at 18:48

# VB.NET (.NET 4.5), 439 + 35 (imports) = 474 bytes

Requires 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
For i=0To a.Count-1
Dim w=a(i)
If h Mod w=0Then
If h\w=1And(s Is N Or s?.Count>c.Count)Then
s=New List(Of Long)
End If
Z(h\w+r,r,a,c,p,s)
c.RemoveAt(c.Count-1)
End If
Next
Z=s
End Function


The function Z takes two Int64 (number of heads and head regrow rate), and a List(Of Int64) (Sectors), and returns a List(Of Int64) (the ordered choice of Sectors). ReturnsNothing if there is no solution.

Assumes the Sectors are presented in sorted order from largest to smallest.

The Optional 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.

The only ordering of Sectors that matters is I need 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 Sector and never try any other.

I declared a constant N to represent Nothing, shaving off 6 bytes each time I wanted to use Nothing.

And/Or are not short-circuiting, so I use the null conditional operator (?.) to avoid object null errors. In real code, I would use AndAlso/OrElse which do short-circuit.

Try it online!

Z un-golfed for readability

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)
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
Return Nothing
End If

' keep track of previous state to prevent duplicate paths

For Each w In weapons

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

If currentHeads Mod w = 0 Then

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

If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
End If
End If

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

If weapons.Contains(1) Then

If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
End If
End If

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

Return shortestWeapons
End Function


# Python3, 150 bytes

def f(h,H,s):
q=[(h,[],[])]
for h,m,p in q:
for S in s:
if 0==h%S and(h,S)not in p:
if 1==h/S:return m+[S]
q+=[(h/S+H,m+[S],p+[(h,S)])]


Try it online!

# Scala 3, 364 bytes

A port of @Ajax1234's Python answer in Scala.

364 bytes, it can be golfed more.

Golfed version. Attempt This Online!

(a,b,c)=>{var d=scala.collection.mutable.Queue(Q(a,List.empty[Int],Set.empty[(Int,Int)]));var r:Option[List[Int]]=None;while(d.nonEmpty&&r.isEmpty){val Q(g,k,p)=d.dequeue();c.foreach{e=>if(g%e==0&& !p.contains((g,e))){if(g/e==1){r=Some(k:+e)}else{d.enqueue(Q(g/e+b,k:+e,p+((g,e))))}}}};r.getOrElse(List.empty[Int])}
case class Q(h:Int,m:List[Int],p:Set[(Int,Int)])


Ungolfed version. Attempt This Online!

object Main {
case class State(h: Int, m: List[Int], p: Set[(Int, Int)])

def f(h: Int, H: Int, s: List[Int]): List[Int] = {
var queue = scala.collection.mutable.Queue(State(h, List.empty, Set.empty))
while (queue.nonEmpty) {
val State(h, m, p) = queue.dequeue()
s.foreach { S =>
if (h % S == 0 && !p.contains((h, S))) {
if (h / S == 1) return m :+ S
queue.enqueue(State(h / S + H, m :+ S, p + ((h, S))))
}
}
}
List.empty[Int] // Return empty list if no solution
}

def main(args: Array[String]): Unit = {
println(f(24, 1, List(2, 3)))
println(f(25, 2, List(2, 3)))
println(f(4, 2, List(2)))
println(f(4, 3, List(2, 5)))
println(f(10, 17, List(2, 3, 7, 19)))
println(f(10, 6, List(1, 16)))
println(f(6, 2, List(2, 3, 5)))
println(f(125, 1, List(1, 2, 3, 127)))
}
}
`