13
\$\begingroup\$

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

JavaScript (ES6), 111 105 bytes

Saved 4 bytes thanks to @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}}

I've ditched the depth-first recursion I was attempting to use for the much safer breadth-first loops. Outputs the solution as an array if it exists, runs forever if it doesn't. If this isn't allowable, here's one that eventually halts (on most cases, anyway):

(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}}
\$\endgroup\$
3
\$\begingroup\$

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


\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
  • \$\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 Aug 10 '17 at 21:25
  • \$\begingroup\$ 210 bytes \$\endgroup\$ – Mr. Xcoder Aug 22 '17 at 22:08
  • \$\begingroup\$ Possible 208 bytes. \$\endgroup\$ – Jonathan Frech Jun 11 '18 at 18:48
1
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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