Regreso del Asesino de Hidra

13

Ha pasado un tiempo desde que mataste esa hidra , disfrutaste de la gloria durante años, pero ahora la gente te llama lavado, ha sido. Bueno, es hora de que demuestres que están equivocados, has escuchado el paradero de otra hidra. Simplemente mátalo y se te otorgará toda la gloria que mereces.

Llegas a la armería para recibir tus espadas, pero todas están fuera de las espadas normales, todo lo que les queda son Sectores. Un sector n dividirá el número de cabezas en una Hidra por n, pero solo se puede usar si el número de cabezas es divisible por n.

Una vez más, vas a escribir un código para ayudarte a matar la hidra. Su código tomará como entrada el número de cabezas de la hidra, comienza la pelea, el número de cabezas que la hidra crece en cada turno y una lista de n-sectores que puede usar. Su código generará un patrón óptimo de movimientos para matar la hidra lo más rápido posible

En cada turno de la pelea, puede seleccionar una sola espada para usar, si después de un corte la hidra tiene solo una cabeza que gana, si no crece las cabezas. Nunca puedes hacer ningún movimiento, y si no hay movimientos posibles disponibles, pierdes.

Si no es posible una solución, puede generar otra cosa que no sea una solución, por ejemplo, una lista vacía, nada, el número cero, etc.

Este es el por lo que las respuestas se puntuarán como recuento de bytes, y menos será mejor.

Casos de prueba

Aquí hay algunos casos de prueba súper básicos, se agregarán más casos de prueba a pedido.

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]
Post Rock Garf Hunter
fuente
¿Puede la hidra tener solo 1 cabeza para comenzar?
ETHproductions
@ETHproductions No tiene que manejar ese caso.
Post Rock Garf Hunter
¿Podemos suponer que la lista está ordenada?
ETHproductions
@ETHproductions Sí, puedes. No veo por qué no.
Post Rock Garf Hunter
¿Un 1-sector es básicamente una espada "skip turn"?
Neil

Respuestas:

5

JavaScript (ES6), 111 bytes

Guardado 4 bytes gracias a @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}}

Eliminé la recursión de profundidad primero que intentaba usar para los bucles de amplitud mucho más seguros. Muestra la solución como una matriz si existe, se ejecuta para siempre si no existe Si esto no está permitido, aquí hay uno que finalmente se detiene (en la mayoría de los casos, de todos modos):

(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}}
ETHproductions
fuente
3

JavaScript, 191 190 bytes

Salvó un byte gracias a 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])}]`);



fuente
2

Python 2 , 169 195 222 bytes

+26 bytes para manejar adecuadamente la regeneración cíclica de la cabeza en púas de armas malas. (Gracias a @ThePirateBay por señalarlo)

+27 bytes para arreglar ciertos casos extremos que causan errores.

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]

Pruébalo en línea!

Arnold Palmer
fuente
Por lo general, la parte valiosa significa que no puede crear variables globales, modificarlas y asumir que volverán al valor original la próxima vez. No sé cuál es la política de error aquí: definitivamente se permitiría que los programas completos produzcan errores para la salida vacía.
Stephen
210 bytes
Sr. Xcoder
Posibles 208 bytes .
Jonathan Frech
1

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

Requiere 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

La función Ztoma dos Int64(número de cabezas y tasa de regeneración de cabezales) y a List(Of Int64)(Sectores), y devuelve unList(Of Int64) (the ordered choice of Sectors). Returns Nothing` si no hay solución.

Asume que los sectores se presentan en orden de mayor a menor.

Los Optionalparámetros son para las llamadas recursivas para guardar el estado. Rastrean el orden actual de los Sectores en uso, el orden más corto de Sectores de la historia y la cantidad de cabezas encontradas. Si volvemos a encontrar el mismo número de cabezas, debe haber una forma más corta de alcanzarlo.

El único ordenamiento de Sectores que importa es que debo 1ser el último si existe. De lo contrario, la hidra podría crecer sin límites porque en cada momento podría usar el 1Sector y nunca probar otro.

Declaré una constante Npara representar Nothing, reduciendo 6 bytes cada vez que quería usar Nothing.

And/ Orno están en cortocircuito, por lo que utilizo el operador condicional nulo ( ?.) para evitar errores de objeto nulo. En código real, usaría AndAlso/ OrElseque hace cortocircuito.

Pruébalo en línea!


Z sin golf para facilitar la lectura

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
Brian J
fuente