Encuentra un punto fijo

24

Dado un número entero y alguna función de recuadro negro, encuentre un punto fijo en la secuencia definida por .x1 f: ℤ → ℤfxk+1 := f(xk)

Detalles

  • Se xdice que un valor es un punto fijo de fif x = f(x).

    Por ejemplo, si f(x) := round(x/pi)y tenemos un punto de partida después conseguimos , entonces , a continuación , y, finalmente, lo que significa que la presentación debe devolver .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

  • Puede suponer que la secuencia generada en realidad contiene un punto fijo.
  • Puede usar el tipo nativo para enteros en lugar de .
  • Puede usar cualquier idioma para el que haya valores predeterminados para la entrada de funciones de recuadro negro en la meta publicación de E / S estándar . Si no existe dicho valor predeterminado para su idioma, siéntase libre de agregar uno en el sentido de la definición de funciones de recuadro negro , y asegúrese de vincular sus propuestas en esa definición. Tampoco olvides votar sobre ellos.

Ejemplos

f(x) = floor(sqrt(abs(x)))
0 -> 0,  all other numbers -> 1

f(x) = c(c(c(x))) where c(x) = x/2 if x is even; 3*x+1 otherwise
all positive numbers should result in 1,2 or 4 (Collatz conjecture)

f(x) = -42
all numbers -> -42

f(x) = 2 - x
1 -> 1
falla
fuente
Tenga en cuenta que si bien está implícito en los detalles que la función de cuadro negro convergerá en el punto fijo, el último ejemplo dice lo contrario
phflack
1
@phflack El blackbox solo tiene que converger para la entrada dada.
flawr
Oh, originalmente pensé que la presentación no se da x_0, lo que me causó cierta confusión. Pensé que una solución debería ser (Jelly) ~Nƭ⁻Ç$¿, que es algo así como (pseudocódigo) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . Eso puede valer otro desafío.
user202729
1
Nota para futuros visitantes: Encontrar cualquier punto fijo no funciona, debe encontrar un punto fijo accesible desde x_0. Se garantiza que existe uno.
user202729
Y si no existe un punto fijo, para una función f, y un valor inicial x0 ... ¿Cuál debería ser el valor que debe devolver? Y si x0 = 0 yf = int (9 / (x-1)) con para x1 = x0 + 1 f (x1) = f (1) ya es un error ... ¿Qué debería devolver el operador para esa f, x0?
RosLuP

Respuestas:

16

En realidad , 1 byte

Y

Pruébalo en línea!

Yes la función de punto fijo en realidad. En el ejemplo de TIO, la función se muestra como una cadena y £se usa para transformarla en una función en la pila. También es posible simplemente empujar la función a la pila de esta manera . Estas son las dos únicas formas de obtener una entrada de función en realidad.

Mego
fuente
77
Sabías que algún día este desafío se publicaría, ¿no? : P
Erik the Outgolfer
2
@EriktheOutgolfer Realmente he usado Ypara varios desafíos. Aparentemente soy extremadamente precognitante : P
Mego
11

APL (Dyalog) , 2 bytes

⍣=

Pruébalo en línea!

NB: defino O←⍣=en la sección de entrada debido a un error en que los operadores monádicos derivados no se pueden definir de la manera en que a TIO le gusta definir las cosas.

Es un operador que puede usarse como (function⍣condition) ⍵

Se aplica el function, f, de hasta (f ⍵) condition ⍵vuelve verdadera.

⍣=es un operador monádico derivado que toma una función monádica f, como argumento izquierdo y la aplica a su argumento derecho , hastaf ⍵ = ⍵

H.PWiz
fuente
Quizás tenga en cuenta que ⍣=es un operador monádico derivado que toma una función como operando izquierdo y encuentra el punto fijo en el valor inicial dado. Me gustaría utilizar una letra diferente para ⍣=que f, ya que es una o perator, no una f unción.
Adám
Sí. Me gustaría. Es confuso que llame a la función "input" fen su descripción, pero luego, en TIO, fes su operador de solución. También puede moverlo O←⍣=hacia arriba en el campo Código para permitir que se cuente y señalar que esa es la solución real, y que el resto (Entrada) solo lo está probando.
Adám
Me parece un error. Hablaré con un colega relevante mañana.
Adám
@ Adám actualizado. Avíseme si se solucionó el error
H.PWiz
10

Haskell, 17 bytes

until=<<((==)=<<)

Pruébalo en línea!

nimi
fuente
3
En caso de que alguien esté interesado: aquí hay una explicación de por qué until=<<((==)=<<) encuentra un punto fijo de una función determinada.
Laikoni
9

MATLAB , 41 bytes

function x=g(f,x);while f(x)-x;x=f(x);end

También existe esta belleza que no necesita archivos de funciones. Lamentablemente es un poco más largo:

i=@(p,c)c{2-p}();g=@(g,f,x)i(f(x)==x,{@()x,@()g(g,f,f(x))});q=@(f,x)g(g,f,x)

Pruébalo en línea!

falla
fuente
77
Esta respuesta fue un ejemplo y no impide que nadie responda.
flawr
Por supuesto, si llamaste a esta octava, podrías eliminar dos ;s. Pruébalo en línea! .
Sanchises
Y en su función anónima, puede eliminar el @()antes xpor 50 bytes. Felicitaciones también por la forma en que ajusta su función de ayuda (con g(g)el final), solo logré hacer 51 bytes @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). Me pregunto si hay alguna combinación de ambos enfoques que sea aún más corta.
Sanchises
6

ML estándar (MLton) , 30 bytes

fun& $g=if$ =g$then$else&(g$)g

Pruébalo en línea! Usar como & n blackbox.

Las funciones del cuadro negro se definen de la siguiente manera:

fun blackbox1 x = floor(Math.sqrt(Real.fromInt(abs x)))

fun blackbox2 x = c(c(c(x))) 
and c x = if x mod 2 = 0 then x div 2 else 3*x+1

fun blackbox3 _ = ~42

fun blackbox4 x = 2-x

Versión sin golf:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g
Laikoni
fuente
1
¡Es bueno ver SML en la naturaleza! Lo usamos para nuestra clase de programación funcional en nuestra universidad.
vijrox
4

Python 2 , 39 37 33 bytes

gracias a @ Mr.Xcoder por -2 bytes

s=lambda k:s(f(k))if k-f(k)else k

Pruébalo en línea!

asume que la función de caja negra se llamará f

ovs
fuente
¿No es necesario pasar la función como parámetro? No creo que las variables predefinidas sean un método de entrada aceptado.
mbomb007
No estoy seguro de que pueda asumir que la función es f, ¿no es una forma de asumir que la entrada está en una variable? (editar: ninja'd por mbomb)
FlipTack
4

Jalea , 3 bytes

vÐL

Pruébalo en línea!

Toma el argumento izquierdo como una cadena que representa un enlace Jelly ( 2_por ejemplo), y el argumento derecho como un entero

Cómo funciona

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given
caird coinheringaahing
fuente
4

Brain-Flak , 24 bytes

(()){{}(({})<>[({})])}{}

Pruébalo en línea!

(para la función de recuadro negro x -> 2-xen el ejemplo a continuación)

La función de recuadro negro que se proporciona debe ser un programa, que aparece xen la parte superior de la pilax y empuja f(x); en otras palabras, debe evaluar la función fen el valor en la parte superior de la pila.

Mini-Flak equivalente es de 26 bytes (gracias a Wheat Wizard por guardar 2 bytes):

(()){{}(({})( )[{}({})])}{}
             ^ put the function f here

(sin contar los comentarios y espacios)

Tome la función (dentro de <>) y un númerox0 de entrada. (tenga en cuenta que Brain-Flak es un lenguaje esotérico y no puede tomar argumentos funcionales como entrada)


Ejemplo de funciones de blackbox:

x -> 2-x: ¡ Pruébelo en línea!


Explicación:


(()){{}(({})<f>[({})])}{}   Main program.
                            Implicit input from stdin to stack.
(  )                        Push
 ()                         literal number 1.
                            Now the content of the stack: [1, x0]
    {                 }     While stack top ≠ 0:
                            current stack content: [something ≠ 0, x]
     {}                       Pop stack top (something). stack = [x]
       (             )        Push
        ({})                    Stack top = x. Current stack = [x]
             f                  Evaluate f. Current stack = [f(x)]
            < >                   (suppress the value of f(x), avoid adding it)
               [    ]           plus the negative of
                ({})            the top of the stack ( = -f(x) )
                              In conclusion, this change (x) on the stack to
                              (f(x)), and then push (x + -f(x))
                            If it's 0, break loop, else continue.
                       {}   Pop the redundant 0 on the top.
                            Implicit output stack value to stdout.

usuario202729
fuente
3

Swift , 47 42 bytes

func h(_ n:Int){f(n)==n ?print(n):h(f(n))}

Enfoque ingenuo, supone que la función de cuadro negro se llama f

Herman L
fuente
Tengo dudas sobre su segundo intento, porque es un cierre complejo y su tipo es ambiguo a menos que lo expulse explícitamente {...}as(<parameter types>)-><return type>. Si no especifica su tipo de retorno, arrojará errores de tiempo de construcción, por lo que no creo que sea válido a partir de ahora (tenga en cuenta que el reparto debe incluirse en el recuento de bytes). Sin embargo, su primera presentación está bien.
Sr. Xcoder
2

C (gcc) , 40 bytes

f(n,b)int(*b)(_);{n=n^b(n)?f(b(n),b):n;}

Pruébalo en línea! Tenga en cuenta que los indicadores no son necesarios, están allí para ayudar a probar la función de punto de fijación definida anteriormente.

Esta es una función que toma un int ny un puntero de función b : int → int. Abusar del hecho de que escribir en el primer argumento variable establece el eaxregistro, que es equivalente a devolver . De lo contrario, esto es bastante estándar en lo que respecta al golf C. n^b(n)comprueba la desigualdad de ny el cuadro negro aplicado a n. Cuando es desigual, vuelve a llamar a la función de punto fijo de forma frecursiva con la aplicación y el cuadro negro como argumentos. De lo contrario, devuelve el punto de fijación.

† Cita necesaria, recuerdo vagamente haber leído esto en algún lugar y Google parece confirmar mis sospechas

Declara la entrada con la escritura de parámetros de estilo K y R:

f(n, b)
int(*b)(_);
{
    n=n^b(n)?f(b(n),b):n;
}

El bit arcano en la segunda línea de arriba declara bser un puntero de función que toma un parámetro entero; _se supone que el tipo predeterminado de es un entero. Del mismo modo, nse supone que es un número entero y fse supone que devuelve un número entero. ¿Hurra por escribir implícitamente?

Conor O'Brien
fuente
2

Limpio , 46 bytes

import StdEnv
p x=hd[n\\n<-iterate f x|f n==n]

Asume que la función se define como f :: !Int -> Int

Toma la cabecera de la infinita lista de aplicaciones de f f f ... xfiltrado para aquellos elementos donde f el == el.

Pruébalo en línea!

Si desea cambiar la función en el TIO, la sintaxis lambda de Clean es:

\argument = expression

(en realidad es mucho más complicado, pero afortunadamente solo necesitamos funciones unarias)

Οurous
fuente
2

APL (Dyalog Unicode) , 14 bytes

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}

Pruébalo en línea!

La función en el encabezado es equivalente a f(x) = floor(sqrt(abs(x)))

Gracias @ Adám por señalar que la respuesta original no era válida de acuerdo con el consenso de PPCG.

Cómo funciona:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}  Main 'function' (this is actually an operator)
      :          if
 ⍵=⍺⍺⍵           the right argument (⍵) = the left function (⍺⍺, which is f) of 
                return 
                else
         ∇⍺⍺⍵    return this function (∇) with argument f(⍵)
J. Sallé
fuente
{⍵ = f⍵: ⍵⋄∇ (f⍵)} estaría bien para separar la función anónima de su nombre (n)
RosLuP
2
Esto supone que festá preasignado, lo que creo que está prohibido por el consenso de PPCG. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}Sería una solución válida para el operador.
Adám
1

Adelante (gforth), 36 bytes

Esta versión solo asume que festá predefinida. No es tan genial como la solución que se encuentra debajo. Ambos programas salen con un desbordamiento de pila si no se encuentra, o un desbordamiento de pila si se encuentra (después de imprimir el resultado).

Pruébalo en línea

: g dup f over = IF . THEN recurse ;

Adelante (gforth), 52 bytes

Esto permite que el token de ejecución de una función se pase como un parámetro, y definitivamente es la solución más genial.

: g 2dup execute rot over = IF . THEN swap recurse ;

Pruébalo en línea

Explicación:

: g             \ x1 f          Define g. Params on the stack. f is on top
2dup execute    \ x1 f x2       duplicate both params, execute f(x1)
rot over        \ f x2 x1 x2    move x1 to top and copy x2 to top
= IF . THEN                     compare, if equal, print
swap recurse ;                  otherwise, recurse
mbomb007
fuente
1

Ruby , 31 28 bytes

->x,f{x=f[x]until x==f[x];x}

Pruébalo en línea!

Restablecer a Monica iamnotmaynard
fuente
25 bytes - -> x, f {1while x! = X = f [x]; x}
GB
1

pequeña respuesta , 28 bytes

(d P(q((x)(i(e(f x)x)x(P(f x

Asume que la función festá predefinida.

Pruébalo en línea! (La función de ejemplo es f(x) = (x*2) mod 10).

Sin golf

(load library)
(def P
 (lambda (x)
  (if (equal? (f x) x)
   x
   (P (f x)))))

Si f(x)es igual x, entonces xes un punto fijo; devolverlo. De lo contrario, busque recursivamente un punto fijo a partir de en f(x)lugar de x.

DLosc
fuente
1

APL NARS 65 caracteres

r←(f v)n;c
   c←0⋄→B
E: r←∞⋄→0
A: n←r
B: r←f n⋄c+←1⋄→E×⍳c>1e3⋄→A×⍳r≠n

v operador devolvería ∞ (o posiblemente -oo o Nan) por error, de lo contrario, un valor x con x = f (x). En la prueba f = floor (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) con c = x% 2 == 0? X / 2: 3 * x +1

  f←⌊∘√∘|
  f v 0
0
  f v 9
1
  f1←{2-⍵}
  f1 v 1
1
  f1 v ¯10
∞
  f1 v 2
∞
  c1←{0=2∣⍵:⍵÷2⋄1+3×⍵}
  f2←c1∘c1∘c1
  f2 v 1
1
  f2 v 2
2
  f2 v 7
2
  f2 v 82
4
RosLuP
fuente
1

Clojure, 45 43 bytes

Bueno, este es el más corto y feo:

#(loop[a + b %2](if(= a b)a(recur b(% b))))

+está allí en lugar de un número para que no sea igual a ningún valor de x0.

55 bytes y funcional:

#(reduce(fn[a b](if(= a b)(reduced a)b))(iterate % %2))

Ejemplo:

(def f #(...))
(defn collaz [x] (if (even? x) (-> x (/ 2)) (-> x (* 3) (+ 1))))
(f (->> collaz (repeat 3) (apply comp)) 125)
; 1
NikoNyrh
fuente
1

código de operación x86, 8 bytes

fun:
        call    edx          ; 2B
        cmpxchg eax,    ecx  ; 3B, on 8086 use xchg and cmp instead
        jnz     fun          ; 2B
        ret                  ; 1B

Tomar entrada: ecx(valor ), (dirección de función, tomar entrada de , escribir resultado a sin modificar el valor de yx0edxecxeaxecxedx )

8086 código de operación, 7 bytes (pero lento)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

Si existe un punto fijo, el bucle 65536 veces siempre lo conduce allí.
Tomar entrada: ax(valor inicial ), (dirección de función, tomar entrada desde , escribir salida a sin modificar el valor de y ). Salida del punto fijo en el registro .x0dxaxaxcxdx
ax

l4m2
fuente
Sin duda ayudaría si hace que la respuesta sea más legible.
usuario202729
más edición para hacerlo correcto
l4m2
0

Java 8, 42 bytes

Esto toma un Function<Integer, Integer>o IntFunction<Integer>y un into Integer(curry) y devuelve el punto fijo.

f->i->{while(i!=(i=f.apply(i)));return i;}

Pruébalo en línea

Aprovecha el hecho de que Java evalúa las subexpresiones de izquierda a derecha (por lo que lo antiguo ise compara con lo nuevo), una propiedad que desconocía al escribir esto.

Jakob
fuente