Return of the Hydra Slayer

Question

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 code-golf 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]
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]

Answer 1

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])}]`);

---

Answer 2

Python 2, 169 195 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!

Answer 3

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

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)
        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

Answer 4

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!

Answer 5

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