Dado entero positivo n > 2
. Lo convertimos en una matriz de la siguiente manera:
- Si es igual a
2
devolver una matriz vacía - De lo contrario, cree una matriz de todos
n
los factores primos ordenados de forma ascendente, luego cada elemento reemplace con su índice en la secuencia de números primos y finalmente convierta cada elemento en matriz
Por ejemplo, vamos a convertir el número 46
a la matriz. En primer lugar, conviértalo en una matriz de sus factores primos:
[2, 23]
El número 23
es el 9
primo, así que reemplácelo 2
con una matriz vacía y 23
con [9]
. La matriz ahora se convierte en:
[[], [9]]
Los factores primos de 9
son 3
y 3
, entonces:
[[], [3, 3]]
Haz lo mismo para ambos 3
:
[[], [[2], [2]]]
Y finalmente:
[[], [[[]], [[]]]]
Ahora, para codificarlo, simplemente reemplazamos cada corchete abierto con 1
y cada corchete de cierre con 0
, luego eliminamos todos los ceros finales y soltamos uno 1
desde el final. Este es nuestro número binario. Usando el ejemplo anterior:
[ ] [ [ [ ] ] [ [ ] ] ]
| | | | | | | | | | | |
| | | | | | | | | | | |
V V V V V V V V V V V V
1 0 1 1 1 0 0 1 1 0 0 0
Ahora simplemente suelte los últimos tres ceros y el último 1
. El número se convierte en 10111001
lo que es 185
en decimal. Esa es la salida esperada. Observe que en la matriz a paréntesis de conversión binarios de la matriz principal no están incluidos.
Entrada
Entero positivo n
mayor que 2
.
Salida
Entero codificado n
.
Reglas y formato IO
- Aplican reglas estándar.
- La entrada puede ser cadena o número (pero en caso de cadena debe estar en la base 10).
- La salida puede ser cadena o número (pero en caso de cadena debe estar en la base 10).
- Este es el código de golf , ¡la respuesta más corta en bytes gana!
Casos de prueba
Más casos de prueba a pedido.
3 ---> 1
4 ---> 2
5 ---> 3
6 ---> 5
7 ---> 6
8 ---> 10
9 ---> 25
10 ---> 11
10000 ---> 179189987
10001 ---> 944359
10002 ---> 183722
10003 ---> 216499
10004 ---> 2863321
10005 ---> 27030299
10006 ---> 93754
10007 ---> 223005
10008 ---> 1402478
2
ya que no se requieren los envíos para manejarlo.Respuestas:
Casco ,
3531302926252422201915 bytes-7 bytes gracias a @Zgarb!
Ahorró 4 bytes adicionales, indirectamente, gracias a Zgarb
Pruébalo en línea!
Explicación
fuente
φ
el punto fijo lambda!`:0:1
puede ser`Jḋ2
.Jalea ,
22 2019 bytes-1 gracias a Erik the Outgolfer (ceros de cola desde ambos lados
t
, en lugar de desde la derechaœr
)Un enlace monádico que toma un entero mayor que 2 y devuelve un entero mayor que 0 (2 devolvería 0 según la especificación original también).
Pruébalo en línea!
¿Cómo?
Esto replica casi exactamente la descripción dada, solo con alguna manipulación ordinal para la creación de la matriz binaria ...
fuente
Python 2 ,
212177 bytesPruébalo en línea!
La falta de primos incorporados realmente perjudica el recuento de bytes, y se agota en TIO con primos más grandes. Usos XNOR 's cheque primalidad.
Python 2 + gmpy2 , 175 bytes
Pruébalo en línea!
Esta versión no agota el tiempo en los casos de prueba más grandes (es decir, 10000 - 10008).
fuente
Mathematica,
125119 bytesUtiliza un enfoque ligeramente diferente; convierte índices primos a
{1, index, 0}
, y 2 a{1, 0}
.Pruébalo en Wolfram Sandbox
Uso:
fuente
Jalea , 35 bytes
Pruébalo en línea!
fuente
J,
747366 bytesPruébalo en línea!
Este es un verdadero desastre que ciertamente necesita más golf (por ejemplo, la eliminación de la definición de función explícita). Creo que el boxeo que he estado haciendo es especialmente lo que está haciendo aparecer el bytecount ya que realmente no sé lo que estoy haciendo allí (ha sido mucha prueba y error). Además, estoy bastante seguro de que hay algunos complementos que me estoy olvidando (por ejemplo, creo que
_2,~_1,
probablemente tiene uno incorporado).Explicación (sin golf)
Preámbulo
Siéntate bien, porque esto no será una breve explicación. Irónicamente, un lenguaje breve se ha emparejado con una persona detallada.
Lo dividiré en algunas funciones
encode
codifica el entero usando _1 y _2 en lugar de [y]convert
convierte una lista de _1 y _2 en una lista de 1 y 0drop
elimina el último 1 y ceros finalesdecode
convierte de una lista binaria a un númeroRevisaré una llamada de muestra para 46, que se expresa en el formato no golfizado.
Codificar
Hay mucho que explicar aquí.
Tenga en cuenta que la definición de función explícita
3 : '[function]'
evalúa la función como si estuviera en REPL con el argumento correcto reemplazando cada instancia dey
(esto significa que puedo evitar tener que usar mayúsculas ([:
), atops (@
) y ats (@:
) a costa de unos pocos bytes).Esto es lo que parece para cada iteración sucesiva en la entrada de 46
Esta función hace uso de adversos (
::
) para anidar los valores entre "paréntesis" (los paréntesis utilizados aquí son -1 y -2). Básicamente, cada vez que factorizamos y convertimos a índices de números primos, _1 se antepone y _2 se agrega, que actúan como paréntesis. Cuando se llama a la función en esos elementos, solo los devuelve tal cual, ya que seq:
producirá un error al intentar factorizar un número negativo. También es una suerte queq:
no se equivoque al intentar factorizar 1 y en su lugar devuelve la matriz vacía (como se desee).Convertir
Convertir es mucho más simple. Simplemente elimina todo el boxeo, así como el primer elemento, y luego convierte todo a 1s y 0s (simplemente agregando 2)
soltar
Esto invierte la lista, encuentra el primero y luego cae todos los valores hasta ese, luego invierte la lista nuevamente.
Descodificar
Decode es la función incorporada
#.
que toma una lista de 1s y 0s y la convierte en un número binario.fuente
Retina ,
244227225 bytesPruébalo en línea!
Este es un enfoque directo siguiendo el algoritmo demostrado en la pregunta. La generación del índice principal es una complejidad exponencial, por lo que se agota el tiempo de espera para entradas más grandes
Explicación:
fuente
Haskell ,
162160155 bytesPruébalo en línea!
Explicación:
r=zip[1..][x|x<-[2..],all((>0).mod x)[2..x-1]]
define una lista infinita de tuplas de números primos y sus índices:[(1,2),(2,3),(3,5),(4,7),(5,11),(6,13), ...]
.La función
(%)
toma esta listar
y un númeron
y convierte el número en la representación de matriz de factores invertida. Esto se hace avanzandor
hasta encontrar un primo que dividen
. A continuación, determinar de forma recursiva la representación del índice de este primer y encerrarlo entre0
y1
y anteponer la representación den
dividido por el mejor momento.Para
n=46
, esto produce la lista[0,0,0,1,1,0,0,1,1,1,0,1]
de la que luego se eliminan los ceros iniciales (snd.span(<1)
) y el siguiente1
(tail
). Posteriormente la lista se convierte a un número decimal multiplicando elemento a gota con una lista de potencias de dos y sumando la lista resultante:sum.zipWith((*).(2^))[0..]
.fuente
JavaScript, 289 bytes
Los bytes son la suma del código JavaScript sin saltos de línea después de las comas (que se insertan solo para un mejor formato y legibilidad) (256 bytes) y los caracteres adicionales para el cambio de línea de comando, que se requiere cuando se usa Chrome (33 bytes).
Y una versión más larga y mejor legible:
Algunas breves explicaciones:
f
es un algoritmo de factorización recursivo de cola puramente funcional.c
cuenta en qué lugar se produce elr
número primop
en la secuencia de números primos y devuelve[]
(sip=2
yr=1
) o factoriza y procesa másr
mediante recursividad.h
es una pequeña función auxiliar que desafortunadamente es necesaria ya quemap
llama a la función proporcionada connumberOfCurrentElement
el segundo ywholeArray
el tercer argumento, anulando así los valores predeterminados proporcionadosc
si pasamos esta función directamente (me tomó algo de tiempo llegar después de esta trampa; reemplazarh
por su definición sería unos pocos bytes más largos).s
transforma la matriz generada en una cadena. Utilizamosblank
en lugar de0
por lo que podemos utilizartrim()
eno
.o
es la función que se llamará con el valor de entradai
que devuelve la salida. Genera la representación de cadena binaria requerida por la especificación y la convierte en un número (decimal).Editar: Chrome debe iniciarse
chrome --js-flags="--harmony-tailcalls"
para permitir la optimización de la recursividad de cola (consulte https://v8project.blogspot.de/2016/04/es6-es7-and-beyond.html ). Esto también requiere usar el modo estricto.La siguiente prueba muestra que el cálculo es un poco lento para algunos valores (el más largo es más de seis segundos para
10007
mi computadora). Curiosamente, sin la optimización de la recursividad de la cola, el cálculo es mucho más rápido (sobre el factor 5) cuando no hay desbordamiento de la pila.fuente
tinylisp , 209 bytes
La última línea es una función sin nombre que calcula la codificación especificada. Pruébalo en línea!
Versión pre-golf
Este es el código que tenía antes de comenzar a jugar golf:
fuente
05AB1E , 18 bytes
Pruébalo en línea!
Explicación:
fuente