Étant donné un entier et une fonction de boîte noire, trouvez un point fixe de dans la séquence définie par .x1 f: ℤ → ℤfxk+1 := f(xk)

Détails

• On xdit qu'une valeur est un point fixe de fif x = f(x).

  Par exemple, si f(x) := round(x/pi)et nous avons un point de départ, nous obtenons alors , puis , et enfin, ce qui signifie que la soumission doit revenir .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

• Vous pouvez supposer que la séquence générée contient en fait un point fixe.
• Vous pouvez utiliser le type natif pour les entiers à la place de ℤ.
• Vous pouvez utiliser n'importe quelle langue pour laquelle il existe des valeurs par défaut pour les fonctions de boîte noire entrées dans la méta-publication IO standard . S'il n'y a pas de défaut par défaut pour votre langue, n'hésitez pas à en ajouter un dans le sens de la définition des fonctions de boîte noire , et assurez-vous de lier vos propositions dans cette définition. N'oubliez pas non plus de voter sur eux.

Exemples

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

En fait , 1 octet

Y

Essayez-le en ligne!

Yest la fonction de point fixe en fait. Dans l'exemple TIO, la fonction est représentée comme étant une chaîne et £est utilisée pour la transformer en fonction sur la pile. Il est également possible de simplement pousser la fonction dans la pile comme ceci . Ce sont les deux seules façons d'obtenir une entrée de fonction dans Actually.

APL (Dyalog) , 2 octets

⍣=

Essayez-le en ligne!

NB: Je définis O←⍣=dans la section d'entrée en raison d'un bug dans lequel les opérateurs monadiques dérivés ne peuvent pas être définis de la manière dont TIO aime définir les choses.

⍣ Est un opérateur qui peut être utilisé comme (function⍣condition) ⍵

Elle applique la function, fpour ⍵que le (f ⍵) condition ⍵rendement vrai.

⍣=est un opérateur monadique dérivé qui prend une fonction monadique fcomme argument de gauche et l'applique à son argument de droite ⍵jusqu'à ce quef ⍵ = ⍵

Haskell, 17 octets

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

Essayez-le en ligne!

MATLAB , 41 octets

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

Il y a aussi cette beauté qui n'a pas besoin de fichiers de fonction. Malheureusement, c'est un peu plus long:

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)

Essayez-le en ligne!

ML standard (MLton) , 30 octets

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

Essayez-le en ligne! Utiliser comme & n blackbox.

Les fonctions de la boîte noire sont définies comme suit:

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

Version non golfée:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g

R , 36 35 octets

merci à JayCe pour avoir parcouru un octet

function(f,x){while(x-(x=f(x)))0;x}

Essayez-le en ligne!

Vérifiez les fonctions d'exemple!

Port R de la solution de flawr.

Mathematica, 11 octets

#2//.x_:>#&

Essayez-le en ligne!

Mathematica, 10 octets

FixedPoint

Essayez-le en ligne!

Python 2 , 39 37 33 octets

merci à @ Mr.Xcoder pour -2 octets

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

Essayez-le en ligne!

suppose que la fonction de boîte noire sera nommée f

JavaScript (Node.js) , 25 22 21 octets

merci Herman Lauenstein de m'avoir montré ce consensus
grâce à @ l4m2 pour -1 octet

Suppose que la fonction de boîte noire doit être nommée f.

g=k=>f(k)-k?g(f(k)):k

Essayez-le en ligne!

Gelée , 3 octets

vÐL

Essayez-le en ligne!

Prend l'argument de gauche comme une chaîne représentant un lien Jelly ( 2_par exemple) et l'argument de droite comme un entier

Comment ça marche

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given

Brain-Flak , 24 octets

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

Essayez-le en ligne!

(pour la fonction boîte noire x -> 2-xdans l'exemple ci-dessous)

La fonction de boîte noire fournie doit être un programme, celui donné xen haut de la pile, pop xet push f(x)- en d'autres termes, elle doit évaluer la fonction fsur la valeur en haut de la pile.

Mini-Flak équivalent est de 26 octets (merci à Wheat Wizard pour avoir économisé 2 octets):

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

(sans compter les commentaires et les espaces)

Prenez la fonction (à l'intérieur du <>) et un nombre en entrée. (notez que Brain-Flak est un langage ésotérique et ne peut pas prendre d'argument fonctionnel en entrée)x0

Exemples de fonctions de boîte noire:

x -> 2-x: Essayez-le en ligne!

Explication:

(()){{}(({})<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.

Swift , 47 42 octets

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

Approche naïve, suppose que la fonction de boîte noire est nommée f

C (gcc) , 40 octets

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

Essayez-le en ligne!Notez que les drapeaux ne sont pas nécessaires, ils sont là pour vous aider à tester la fonction fixpoint définie ci-dessus.

Il s'agit d'une fonction qui prend un int net un pointeur de fonction b : int → int. Abuser du fait que l'écriture dans le premier argument de variable définit le eaxregistre, ce qui équivaut à retourner ^† . Sinon, c'est assez standard en ce qui concerne le golf C. n^b(n)vérifie l'inégalité de net la boîte noire appliquée n. Lorsqu'elle est inégale, elle appelle à fnouveau la fonction fixpoint de manière récursive avec l'application et la boîte noire comme arguments. Sinon, il renvoie le point fixe.

^{† Une citation était nécessaire, je me souviens vaguement d'avoir lu ceci quelque part et google semble confirmer mes soupçons}

Il déclare l'entrée avec le typage des paramètres de style K & R:

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

Le bit arcanique sur la deuxième ligne ci-dessus déclare bêtre un pointeur de fonction qui prend un paramètre entier - le type par défaut de _est supposé être un entier. De même, nest supposé être un entier et fest supposé renvoyer un entier. Hourra pour la frappe implicite?

Nettoyer , 46 octets

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

Suppose que la fonction est définie comme f :: !Int -> Int

Il prend la tête de la liste infinie d'applications f f f ... xfiltrées pour les éléments oùf el == el .

Essayez-le en ligne!

Si vous souhaitez modifier la fonction dans le TIO, la syntaxe lambda de Clean est:

\argument = expression

(en fait, c'est beaucoup plus compliqué, mais heureusement, nous n'avons besoin que de fonctions unaires)

APL (Dyalog Unicode) , 14 octets

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

Essayez-le en ligne!

La fonction à l'en-tête est équivalente à f(x) = floor(sqrt(abs(x)))

Merci @ Adám d'avoir souligné que la réponse originale n'était pas valide selon le consensus du PPCG.

Comment ça marche:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ 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(⍵)

Octave , 37 octets

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

Essayez-le en ligne!

Octave a une affectation en ligne, mais pas MATLAB, il s'agit donc d'un port Octave de golfier de la solution de flawr .

Il a également des ports bien à R .

Kotlin , 50 octets

{f,k->var a=k;var b=a+1;while(b!=a){b=a;a=f(a)};a}

Essayez-le en ligne!

Forth (gforth), 36 octets

Cette version suppose simplement qu'elle fest prédéfinie. Ce n'est pas aussi cool que la solution en dessous. Les deux programmes se terminent avec un débordement de pile s'il n'est pas trouvé, ou un débordement de pile s'il est trouvé (après l'impression du résultat).

Essayez-le en ligne

: g dup f over = IF . THEN recurse ;

Forth (gforth), 52 octets

Cela permet de passer un jeton d'exécution d'une fonction en tant que paramètre, et c'est certainement la solution la plus cool.

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

Essayez-le en ligne

Explication:

: 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

Rubis , 31 28 octets

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

Essayez-le en ligne!

tinylisp repl , 28 octets

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

Suppose que la fonction fest prédéfinie.

Essayez-le en ligne! (L'exemple de fonction estf(x) = (x*2) mod 10 .)

Non golfé

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

Si f(x)égal x, alors xest un point fixe; rends le. Sinon, recherchez récursivement un point fixe à partir de f(x)au lieu de x.

APL NARS 65 caractères

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

L'opérateur v retournerait ∞ (ou éventuellement -oo ou Nan) pour erreur, sinon une valeur x avec x = f (x). Dans le test f = sol (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) avec 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

Clojure, 45 43 octets

Eh bien, c'est le plus court et le plus laid:

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

+est là au lieu d'un nombre de sorte qu'il n'est égal à aucune valeur de x0.

55 octets et fonctionnel:

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

Exemple:

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

opcode x86, 8 octets

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

Prendre l'entrée: ecx(valeur ), (adresse de fonction, prendre l'entrée de , écrire le résultat dans sans modifier la valeur de etx0edxecxeaxecxedx )

8086 opcode, 7 octets (mais lent)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

S'il existe un point fixe, une boucle 65536 fois le conduit toujours là.
Prendre l'entrée: ax(valeur initiale ), (adresse de la fonction, prendre l'entrée de , écrire la sortie dans sans modifier la valeur de etx0dxaxaxcxdx ).
Sortie du point fixe dans le registre ax.

Perl 5, 18 + 1 (-p )

$_=f$_ while$_^f$_

essayez-le en ligne

Java 8, 42 octets

Cela prend un Function<Integer, Integer>ou IntFunction<Integer>et un intou Integer(curry) et renvoie le point fixe.

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

Essayez-le en ligne

Profite du fait que Java évalue les sous-expressions de gauche à droite (donc l'ancien iest comparé au nouveau), une propriété que je ne connaissais pas en écrivant ceci!