Este desafío fue inspirado por un blog de programación que frecuente. Vea la publicación original aquí: Un rompecabezas de programación
Reto
Defina una función f:Q->Q
tal que f(f(n)) = -n
para todos los enteros distintos de cero n
, y dónde Q
está el conjunto de números racionales.
Detalles
En el idioma que prefiera, defina una función o programa f
que acepte como parámetro un número n
y devuelva o genere un número f(n)
.
La entrada se puede proporcionar a través del mecanismo más natural para su idioma: argumento de función, lectura de STDIN, argumento de línea de comando, posición de pila, entrada de voz, signos de pandillas, etc.
La salida debe ser un valor de retorno de una función / programa o impreso en STDOUT.
Me gustaría restringir las respuestas a las funciones que no aprovechan el estado del programa o la memoria / datos globales que son visibles desde el exterior de la función f
. Por ejemplo, mantener un contador fuera de f
eso cuenta cuántas veces f
se llamó y simplemente hacer una negación basada en este conteo no es muy desafiante o interesante para nadie. Las decisiones f
que se tomen deben basarse únicamente en datos dentro f
del alcance léxico.
Sin embargo, esta restricción es probablemente inapropiada para algunos lenguajes orientados a la pila u otros tipos de idiomas que no distinguen estos tipos de datos o ámbitos. Utiliza tu mejor criterio para seguir con el espíritu de este desafío.
Tanteo
Se aplican reglas comunes de golf de código: su puntaje es el número de bytes en su código fuente.
La respuesta mínima requiere que el dominio y el codominio f
sean un subconjunto de los racionales Q
. Si restringe su dominio y codominio f
a los enteros Z
, su puntaje es el límite del 90% del número de bytes en su código fuente.
Desempate
En caso de empate, se utilizará lo siguiente en orden:
- Poca cantidad de símbolos imprimibles que no sean espacios en blanco en su código fuente
- Fecha y hora más tempranas de envío de respuestas
Editar
No está obligado a admitir números de tamaño arbitrario. Interprete los conjuntos Z
y los Q
tipos de datos en el idioma elegido (normalmente, entero y coma flotante, respectivamente).
Si su solución se basa completamente en la estructura subyacente o el patrón de bits de un tipo de datos, describa sus limitaciones y cómo se está utilizando.
f:Q->Q
significa?f
es una función que asigna miembros deQ
(números racionales) a otros miembros (posiblemente los mismos) deQ
. ver en.wikipedia.org/wiki/Function_(mathematics)#NotationRespuestas:
J, 9 puntos (10 caracteres)
Según la respuesta de stackoverflow :
Primera idea (13 caracteres):
fuente
Python:
61 34 30 2927 puntosf: Q -> Q
en matemáticas:
en Python:
probado con
lógica detrás de esto:
Cuando tomas un número entero
n
y lof
pones, obtendrásx+0.5
. Esto ya no es un entero, por lo que la siguiente aplicación será0.5-(x+0.5)
cuál es-x
.Créditos
Gracias a
Notas
Primero pensé que esto estaría bien
pero es f: N-> C y eso no está permitido: - /
fuente
f=lambda x:x%1>0and(-x+x%1)or x+.1
que tiene solo 34 caracteres de longitud.f=lambda x:[x+.1,x%1-x](x%1>0)
es solo 30f=lambda x:[x+.5,.5-x][x%1>0]
. Tenga en cuenta el uso de .5 en lugar de .1 para solucionar problemas de precisiónf:Q->Q
solo significa que f asigna un número racional a números racionales. Lo que hace mi definición de f.C, 41 puntos (41 o 45 caracteres)
Funciona con 32 y 64 bits.
f : Z -> Z
(exceptoINT_MAX
):Si no tenemos que incluir
0
podemos eliminar algunos caracteres (41 caracteres):f : Z -> Z
(excepto0
&INT_MAX
):Esta función funciona dividiendo todos los enteros en 4 grupos según su signo y paridad.
Entonces tenemos las 4 combinaciones diferentes:
Como necesitamos cambiar el signo del número, pero no la paridad después de dos pasadas, obtenemos dos posibles secuencias diferentes:
En este ejemplo, he elegido el primero.
Primero necesitamos mapear todos los enteros positivos pares a enteros negativos impares. Hacemos esto cambiando el signo e incrementando el número (también puede optar por disminuir el número):
Luego necesitamos asignar todos los enteros negativos impares a los enteros negativos pares. Necesitamos asegurarnos de que
f2(f1(n)) = -n
:Usando los mismos métodos encontramos
f3
yf4
:Para combinar estas funciones en una sola función, observamos que cada vez
n
que incluso cambiamos el signo den
y cada vez quen
es positivo, incrementamos en uno y de lo contrario disminuimos en uno:Esto puede reescribirse así como:
donde
odd(n)
regresa1
para números impares y-1
para números pares.Hay 4 soluciones en total:
INT_MIN
siempre se puede considerar un caso límite en las 4 funciones como-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.fuente
0
otros 3 números.Z
bono si cubres 0, al menos.Aquí está mi intento.
Ejemplo en vivo :
Los tipos de entrada pueden adaptarse arbitrariamente para satisfacer sus necesidades. Esta versión funciona para literales enteros de menor magnitud que 2 ^ 32-1.
fuente
f:Q->Q
nof:Z->Z
.f:Z->Z
, lo siento por la redacción confusareturn -i
JavaScript, 18
Usando la nueva notación de flecha gorda (Firefox 22).
Otra versión (18):
Versión anterior (20):
Ejemplo:
fuente
Mathematica 18
Aquí
⌊...⌋
está la función de piso. Utiliza solo números racionales (no listas, números complejos, etc.)fuente
lenguaje ensamblador x86 (FASM). El argumento y el resultado están en registro eax.
Funciona correctamente para -2 ^ 30 <N <+ 2 ^ 30-1
Código ejecutable de 16 bytes.
fuente
Lisp común: 35 bytes
Esquema (y raqueta): 36 bytes
Ungolfed con comentarios y explicaciones:
Para cualquier número
x
en[1,->]
elif
se convertirá en la fracción1/2
que es un número exacto real en ambos idiomas.La parte dividida se convertirá entonces en
(/ 1/2 x)
la fracción1/(x*2)
que siempre será inferior1
. Porque1
será1/2
, porque2
es1/4
, etc.Para cualquier número por debajo de 1,
if
se convertirá en la fracción-1/2
, lo que hace que la función haga lo(/ -1/2 x)
que es,-1/(2*x)
pero como podemos esperar que el valor sea el resultado de la ejecución anterior, podemos sustituir x por 1 / (x * 2) haciendo una aplicación doble-1/((1/(x*2))*2) = -x
Por ejemplo, ya que se
1
convierte en1/2
la segunda aplicación es(/ -1/2 1/2) ==> -1
fuente
C, 60 (⌈66 * .9⌉)
Aquí hay una versión sin condensar:
Este método funciona utilizando solo enteros, por lo que obtiene el bono de puntuación del 90%. Originalmente lo escribía en Java, pero me di cuenta de que este programa en particular podría beneficiarse de los operadores lógicos de estilo C.
Como no hay un número entero correspondiente a
-INT_MIN
,f(f(INT_MIN))
devuelve en suINT_MIN
lugar.El mapeo subyacente es algebraicamente bastante simple. La ejecución de la declaración
x=f(x)
reemplaza x con:x+1
, six
es positivo e impar-x+1
, six
es positivo e inclusox-1
, six
es negativo e impar-x-1
, six
es negativo e inclusoEl resultado de cada caso se incluirá en el siguiente caso la próxima vez que se aplique la función a x.
Como puede ver, componer un caso con el siguiente caso produce
-x
.El código es el resultado de una simplificación inteligente de la función para aprovechar la estructura de bits de los enteros complementarios de dos.
fuente
> <> , 21 + 3 = 24 bytes, 22 puntos
Use el intérprete oficial de Python y use la
-v
opción de línea de comando para ingresar la entrada, a un costo de 3 bytes.Tengo la sensación de que esto podría ser mejor. Seguiré mirándolo e intentaré jugarlo.
Dada entrada
n
, el programa saledonde
(n>0)
y(n<0)
son booleanos. Esto es equivalente a la respuesta Python de gelatinapero
><>
no tiene un operador de exponenciación incorporado, por lo que utilizamos(1 - 2*(n%2))
en lugar de(-1)**n
.Lo que sigue es la teoría matemática: lee si (y solo si) estás interesado:
Dado cualquier función
f: Z -> Z
tal quef(f(n)) = -n
para todosn
enZ
, vemos inmediatamente quef(f(f(f(n)))) = n
, o en otras palabras,f^4
es la función identidad. En particular,f
es invertible, y su función inversa esf^3
. Por lo tantof
es una permutación deZ
, y desdef^4 = Id
, se sigue que cada órbita (o ciclo) def
tiene tamaño, ya sea1
,2
o4
.A continuación, vemos eso
f(0) = 0
. Prueba:f(0) = f(-0) = f(f(f(0))) = -f(0)
asíf(0) = 0
, como se desee. Por el contrario, supongamos quex
está en un ciclo de longitud1
o2
, entoncesf(f(x)) = x
. Entonces-x = x
entoncesx = 0
.Por
f
lo tanto, se compone completamente de 4 ciclos, excepto el punto fijo (1 ciclo) en0
.Además, cada 4-ciclo debe tener la forma
(x, y, -x, -y)
, y mediante la rotación del ciclo alrededor podemos suponer quex
yy
son ambos positivos. Por el contrario, cada uno de esos productos de particiones de 4 ciclos de los enteros distintos de cero determina una elección def
.Por lo tanto, cada elección de
f
corresponde únicamente a un gráfico dirigido cuyos vértices son los enteros positivos, de modo que cada vértice incide exactamente en una flecha, ya sea entrando o saliendo. Más precisamente, en el gráfico subyacente no dirigido, cada vértice tiene un grado exacto1
. (Cada 4 ciclos(x y -x -y)
conx
yy
positivo corresponde a la flechax --> y
).La función de esta respuesta (y varias otras respuestas aquí) se corresponde con el gráfico donde
1 --> 2
,3 --> 4
y, en general2k-1 --> 2k
.Tales gráficos están en biyección con secuencias infinitas de pares ordenados
(a_n, p_n)
, donde cadaa_n
es un entero positivo y cada unop_n
es o bien0
o1
: dada una secuencia de(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, en primer lugar par1
con1 + a_1
, y luego formar o bien la flecha1 --> 1 + a_1
o en la flecha1 + a_1 --> 1
en función de sip_1
es0
o1
. Esencialmente, la flecha es un<
signo o un>
signo, dependiendo de la paridad dep_1
.A continuación, tome el entero positivo no emparejado más pequeño
k
y cuente desdek
, exactamente losa_2
pasos, SALTANDO cualquier número que ya esté emparejado con algo. Emparejek
con el resultado y establezca la dirección de la flecha segúnp_2
lo anterior. Luego repite con(a_3, p_3)
, etc.Cada flecha finalmente se determinará de esta manera, por lo que el proceso está bien definido. La función en esta respuesta corresponde a la secuencia
(1,0), (1,0), (1,0), ...
, ya que en el pason
el número entero más pequeño sin emparejar es2n-1
y no hay enteros más grandes que los que2n-1
se hayan emparejado con algo, por lo que obtenemos2n-1 --> 2n
para cada unon
(las flechas están orientadas de esta manera porque cada unap_n
es igual0
).La cardinalidad de este conjunto es
(N*2)^N = N^N
, que en el último párrafo de esta respuesta es igual2^N
, la cardinalidad de los números reales.fuente
Para arreglar la respuesta J anterior (no tengo suficiente reputación para comentar sobre el original):
Simplemente reemplaza el
_1&^
con1-~2*2|]
, que da el signo opuesto. Así que cambié el-
a a+
(que solo importa en la entrada de1
y_1
).Aquí están las pruebas:
Como puede ver, el dominio y el rango son de todos los números reales, pero solo funciona para enteros (incluido 0).
Explicación:
fuente
GolfScript
ceiling(26*.9)=24
Golfscript solo maneja números enteros, así que aplique la
Z
bonificación por un total de 24 puntos:El caso especial de 0 representa 8 caracteres. Ignorando 0, podemos tener una respuesta de 17 puntos:
Este código hace lo siguiente a un número entero
x
en la parte superior de la pila:x
es 0, déjelo0
en la pila y no aplique más reglas.x
es par, negarx
.x
es positivo, agregue1
.x
es negativo, resta1
.Esto conecta lógicamente conjuntos de 4 números en un ciclo, donde
f
atraviesa elementos del ciclo y las esquinas opuestas del ciclo son negativas entre sí. Cada entero es parte de exactamente 1 de estos ciclos, excepto 0, que está en mayúsculas especiales. Por ejemplo, para{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Los únicos casos de prueba relevantes que se me ocurrieron fueron negativos impares, negativos pares, positivos impares, positivos pares
0
, y luego presenté-1
y1
dado que su proximidad0
puede haber causado problemas:Estoy seguro de que el GolfScript real se puede mejorar un poco. ¡No parece que deba ocupar 26 caracteres! Me encantaría escuchar algunas sugerencias.
fuente
Java, solo por diversión
Aquí hay una implementación que realiza una biyección real entre ℤ y ℤ², que es una función extraña al mismo tiempo (g (-x) == -g (x)). Trata el elemento ℤ² correspondiente como un número complejo y lo multiplica por "i", luego lo convierte de nuevo a ℤ.
f (x) = g⁻¹ (ig (x))
f (f (x)) = g⁻¹ (-g (x)) = - x
La función se ejecuta en O (1).
PD ¡Feliz año nuevo!
fuente
Python 3 - 38
Similar a la respuesta de @ alce, pero
f(n) == n
,. Funciona para todos los valores enteros.fuente
Perl, 33 (sin espacios en blanco)
Editar:
$=.".1"
acortado a"$=.1"
(gracias ardnew).Mates:
Sin golf:
Ejemplos:
fuente
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
está libre de estado, usa un estado a través de la variable . Debido a esto, ya no es una función (en el sentido matemático), porque son posibles diferentes valores para el mismo valor de entrada dependiendo del estado (el clima contiene o no). Mi algoritmo no usa un estado. La información está codificada en el valor de salida. Los enteros se convierten en números reales mediante la suma . Y los números reales se convierten de nuevo a enteros con el signo cambiado.$_
f
$_
x
.1
$=
?f
se definiráQ->Q
) con esex
char. también$=.".1"
se puede acortar a"$=.1"
$=
es que solo toma números enteros. El mismo se puede conseguir mediante el uso de una variable ordinaria:$a=int$_[0]
. Pero eso cuesta tres bytes adicionales debido a la funciónint
.Julia, 26
No es súper competitivo, pero es muy juliano, ya que depende del envío múltiple. Simplemente hace que sea Racional si es un Int, o un int con un signo menos si es cualquier otra cosa. Se podría objetar que se trata de 2 funciones, pero Julia considera que se trata de una función con dos métodos, y es equivalente a definir una función con una declaración if sobre el tipo de
n
.fuente
3==3//1
regresatrue
perof(3//1)==f(3)
regresafalse
.Candy ,
2018 bytesUtiliza el truco 3 -> 4 -> -3 -> -4 -> 3.
Para invocarlo, use el modificador -i en el intérprete
Ejemplo de doble invocación:
Forma larga:
fuente
Dyalog APL, 9 puntos
La fuente tiene una longitud de 9 bytes y califica para la bonificación (que no ayuda en absoluto). También utiliza la fórmula de la respuesta SO superior.
fuente
Python: 32 bytes (29 puntos)
f: Z -> Z
Usando el método de Ben Reich.
fuente
(n>0)-(n<0)
concmp(n,0)
, para guardar algunos bytes. (Pero no en Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
fuente
Java, 113 bytes
El enfoque es bastante simple. Terminó más bytes de lo que esperaba, pero tal vez se pueda reducir un poco.
Básicamente crea 4 "áreas" diferentes de x, utilizando el hecho de que Java felizmente deja que las variables se envuelvan. Tuve que hacer una conversión complicada para números negativos, que es la razón principal por la que esto terminó más grande de lo previsto.
Funciona para todas las x además de -2147483648.
fuente
Misma secuencia de números (3, 4, -3, -4, 3 ...) que la respuesta de golfscript, pero implementada en perl (42 caracteres después de que se elimine el espacio en blanco)
Más legible:
O incluso más legible:
Salida:
fuente
Sed, 25 bytes.
Uso:
fuente
Matlab, 26 caracteres
fuente
C ++ -
6355.8Así es como se ve el código:
No funciona en números enteros cuyo cuarto byte es igual a 0xB, ya que usa ese valor para realizar un seguimiento de los pases. De lo contrario, funciona en cualquier miembro de Z, incluido cero.
fuente
f
con una variable estática. pero entonces, ¿cuál es el punto de lasqrt
?sqrt
ya que de todos modos se redondea con el tipo de conversión. Lo refactorizaré para que funcione sin la variable estática.55.8
, pero tu código actual tiene 62 bytes de longitud. Editar: No importa, no leí la pregunta correctamente.Actualizado con la función suministrada por Synthetica (obviamente, quien debería obtener crédito por esto ahora)
Lenguaje: Python
Número de caracteres: 41 incluyendo espacios en blanco
fuente
f=lambda x:-float(x) if str(x)==x else`x`
es bastante más corto: 41 incluyendo espacios en blancof
devuelve una cadena; La especificación dice que debe devolver un número racional.Prólogo, 36 bytes
Código:
Explicado:
Ejemplo:
fuente
Javascript ES6,
2726 bytesfuente
Mouse-2002 ,
211912 bytesDefine una función
A
; llámalo como#A,#A,?;;
(que esperará a que el usuario ingrese cualquier número). Alternativamente, llámelo como#A,#A,n;;
donden
está cualquier número.fuente
Julia, 21
Luego
p // q es la notación literal de números racionales de julia.
fuente