Buscando alternativas más cortas al `rango (...)`

La mejor solución que he encontrado hasta ahora para un rompecabezas de código de golf en el que estoy trabajando incluye dos invocaciones de aspecto bastante gordorange . Soy muy nuevo en code golf, especialmente en Python, por lo que podría usar algunos consejos.

El fragmento relevante es este

[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))]

El límite superior del primero rangeno es fuerte. Debe ser al menos 98690, y todo lo demás es igual (en cuanto al golf, es decir), cuanto menor sea la diferencia entre este límite superior y 98690, mejor, en cuanto al rendimiento ¹ . Estoy usando 7 ⁶ (= 117649) porque 7**6es la expresión de Python más corta que se me ocurre que se ajusta a la factura.

En contraste, el límite inferior en el primero range, así como ambos límites en el segundo, son firmes. IOW, el programa (en su forma actual) producirá resultados incorrectos si se cambian esos límites.

¿Hay alguna manera de acortar una o ambas expresiones?

range(n+1,7**6)
range(2,x)

?

Por cierto, en este caso, el alias rangepara, por ejemplo, rno gana nada:

r=range;rr
rangerange

EDITAR: FWIW, el programa completo es este:

p=lambda n:[x for x in range(n+1,7**6)if`x`==`x`[::-1]*all(x%i for i in range(2,x))][0]

p(n)debe ser el primo palindrómico más pequeño mayor que n. Además, pno debe ser recursivo. Advertencia: ¡ya es obscenamente lento!

_{¹ Sí, lo sé: el rendimiento es irrelevante en el golf de código, pero es por eso que escribí "todo lo demás es igual (en cuanto al golf, eso es)". Por ejemplo, mi elección de 7**6, y no la alternativa más obvia, pero de menor rendimiento, "equivalente al golf" 9**9. Me gusta ejecutar realmente mis intentos de golf de código, lo que significa no permitir que el rendimiento se degrade hasta el punto de que llevará años ejecutar el código. Si puedo evitarlo, por supuesto.}

Hazlo un solo bucle

Como es, tiene dos bucles: uno iterando sobre xeso podría ser primos palindrómicos, otro iterando ipara verificar si xes primo por división de prueba. Como notó, los bucles son Python toman muchos caracteres, a menudo para escribir range, pero también para escribir while _:o for x in _. Por lo tanto, una solución de Python con golf debería esforzarse por usar la menor cantidad de bucles posible.

El comentario de feersum "Los mejores programas de golf a menudo hacen conexiones sorprendentes entre diferentes partes de los programas" es muy aplicable aquí. La comprobación principal puede parecer una subrutina separada para la cual all(x%i for i in range(2,x))es la expresión clásica. Pero lo haremos de otra manera.

La idea es usar el teorema de Wilson . Para cada potencial prime k, mantenemos un producto en ejecución (k-1)!y verificamos si es un múltiplo de k. Podemos hacer un seguimiento (k-1)!mientras probamos el potencial kde ser palíndromos principales manteniendo un producto en funcionamiento P.

En realidad, usaremos la versión más fuerte del Teorema de Wilson que (k-1)! % kes igual a 0 para los compuestos ky solo para los números compuestos, excepto los k=4dados 2, por lo que (k-1)!**2 % kes 0exactamente igual para los números compuestos. Actualizaremos Pa igual a k!**2través de la actualización P*=k*k.

(Consulte esta respuesta para este método utilizado para encontrar primos en Python).

Poniendolo todo junto:

def p(n):
 k=P=1
 while(`k`!=`k`[::-1])+(k<=n)+(P%k==0):P*=k*k;k+=1
 return k

Esto aún no está totalmente desarrollado: la condición en particular se escribe de manera ineficiente. Podemos comprimir la condición para verificar que ksea ​​un palíndromo mientras que al mismo tiempo hacemos cumplir las otras condiciones a través de una desigualdad encadenada.

def p(n):
 k=P=1
 while`k`*(P%k>0>n-k)!=`k`[::-1]:P*=k*k;k+=1
 return k

AFAIK, no realmente.

El rango se usa comúnmente en los golfs de python porque es la forma más corta de generar listas de números crecientes / decrecientes.

Dicho esto, parece ser un poco (7 bytes) más corto para evitar usar el rango y, en su lugar, llamar a un ciclo while envuelto:

def p(n):
    n+=1
    while`n`*all(n%i for i in range(2,n))!=`n`[::-1]:n+=1
    return n

Gracias a @xnor (como siempre) por mejorar la lógica de la condición while :)

Cuando se utilizan algoritmos iterativos como el método de Newton o el cálculo de fractales, en los que generalmente debe realizar iteraciones sin preocuparse realmente por el índice , puede guardar algunos caracteres iterando sobre cadenas cortas.

for i in range(4):x=f(x)
for i in'asdf':x=f(x)

A las siete iteraciones esto se iguala con range. Para más iteraciones use backtics y números grandes

for i in`9**9**5`:pass

Esto se ejecuta 56349 veces, lo que debería ser suficiente para todos los fines prácticos. Jugar con números y operadores le permite codificar una amplia gama de números de esta manera.