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

5 Answers 5


JavaScript, 191 190 bytes

Saved a byte thanks to Step Hen



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 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:
	 	if l and l[-1]!=0:return l

Try it online!

  • \$\begingroup\$ 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. \$\endgroup\$
    – Stephen
    Commented Aug 10, 2017 at 21:25
  • \$\begingroup\$ 210 bytes \$\endgroup\$
    – Mr. Xcoder
    Commented Aug 22, 2017 at 22:08
  • \$\begingroup\$ Possible 208 bytes. \$\endgroup\$ 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
End If
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

    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

            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

    If weapons.Contains(1) Then

        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

Python3, 150 bytes

def f(h,H,s):
 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]

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.