Trouver un point fixe

24

É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
flawr
la source
Notez que bien qu'il soit implicite dans les détails que la fonction de boîte noire converge sur le point fixe, le dernier exemple dit le contraire
phflack
1
@phflack La blackbox n'a qu'à converger pour l'entrée donnée.
flawr
Oh, à l'origine, je pensais que la soumission n'était pas donnée x_0, ce qui m'a causé une certaine confusion. Je pensais qu'une solution devrait être (Jelly) ~Nƭ⁻Ç$¿, qui est quelque chose comme, (pseudo code) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . Cela peut valoir un autre défi.
user202729
1
Remarque pour les futurs visiteurs: la recherche d' un point fixe ne fonctionne pas, vous devez trouver un point fixe accessible à partir de x_0. Il est garanti qu'il en existe un.
user202729
Et s'il n'existe pas un point fixe, pour une fonction f, et une valeur initiale x0 ... Quelle devrait être la valeur qu'elle doit renvoyer? Et si x0 = 0 et f = int (9 / (x-1)) avec pour x1 = x0 + 1 f (x1) = f (1) est déjà une erreur ... Qu'est-ce qui devrait retourner l'opérateur pour ce f, x0?
RosLuP

Réponses:

16

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.

Mego
la source
7
Vous saviez juste qu'un jour ce défi allait être publié, n'est-ce pas? : P
Erik the Outgolfer
2
@EriktheOutgolfer J'ai déjà utilisé Yplusieurs défis. Je suis apparemment extrêmement précognitif : P
Mego
11

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 ⍵ = ⍵

H.PWiz
la source
Notez peut-être qu'il ⍣=s'agit d'un opérateur monadique dérivé qui prend une fonction comme opérande gauche et trouve le point fixe sur la valeur initiale donnée. J'utiliser une autre lettre pour ⍣=que fcomme il est un o pérateur, pas f Onction.
2017
Ouais. Je voudrais. Il est déroutant d'appeler la fonction "entrée" fdans votre description, mais sur TIO, fc'est votre opérateur de solution. Vous pouvez également déplacer le O←⍣=haut dans le champ Code pour qu'il soit compté et pour signaler que c'est la solution réelle, et que le reste (Input) est juste en train de le tester.
2017
Ça ressemble à un bug pour moi. Je parlerai avec un collègue pertinent demain.
2017 à
@ Adám Mis à jour. Faites-moi savoir si le bug est corrigé
H.PWiz
10

Haskell, 17 octets

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

Essayez-le en ligne!

nimi
la source
3
Dans le cas où quelqu'un est intéressé: voici une explication pour laquelle until=<<((==)=<<) trouve un point fixe d'une fonction donnée.
Laikoni
9

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!

flawr
la source
7
Cette réponse était donnée à titre d'exemple et n'empêche personne de répondre.
flawr
Bien sûr, si vous appelez cet octave, vous pouvez supprimer deux ;s. Essayez-le en ligne! .
Sanchises
Et dans votre fonction anonyme, vous pouvez supprimer l' @()avant xpour 50 octets. Bravo aussi pour la façon dont vous encapsulez votre fonction d'aide (avec le g(g)à la fin), je n'ai réussi qu'à faire 51 octets @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). Je me demande s'il existe une combinaison des deux approches qui est encore plus courte.
Sanchises
6

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
Laikoni
la source
1
C'est bon de voir SML dans la nature! Nous l'utilisons pour notre cours de programmation fonctionnelle dans notre université.
vijrox
4

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

ovs
la source
La fonction ne doit-elle pas être passée en paramètre? Je ne pense pas que les variables prédéfinies soient une méthode d'entrée acceptée.
mbomb007
Je ne suis pas sûr que vous soyez autorisé à supposer que la fonction est f, n'est-ce pas une forme de supposer que l'entrée est dans une variable? (modifier: ninja'd par mbomb)
FlipTack
4

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
caird coinheringaahing
la source
4

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.

user202729
la source
3

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

Herman L
la source
Je doute de votre deuxième tentative, car il s'agit d'une fermeture complexe et son type est ambigu, à moins que vous ne l'utilisiez explicitement {...}as(<parameter types>)-><return type>. Si vous ne spécifiez pas son type de retour, il générera des erreurs au moment de la construction, donc je ne pense pas qu'il soit valide pour l'instant (notez que le transtypage doit être inclus dans le nombre d'octets). Votre première soumission est très bien, cependant.
M. Xcoder
2

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?

Conor O'Brien
la source
2

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)

Οurous
la source
2

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(⍵)
J. Sallé
la source
{⍵ = f⍵: ⍵⋄∇ (f⍵)} serait acceptable pour une fonction anonyme distincte de son nom (n)
RosLuP
2
Cela suppose qu'il fest préaffecté, ce qui, à mon avis, est interdit par le consensus du PPCG. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}serait une solution opérateur valide.
2017
1

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
mbomb007
la source
1

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.

DLosc
la source
1

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
RosLuP
la source
1

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
NikoNyrh
la source
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.

l4m2
la source
Il serait certainement utile que vous rendiez la réponse plus lisible.
user202729
plus modifier pour le rendre correct
l4m2
0

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!

Jakob
la source