24
\$\begingroup\$

Given an integer x1 and some black box function f: ℤ → ℤ find a fixed point of f in the sequence defined by xk+1 := f(xk).

Details

  • A value x is said to be a fixed point of f if x = f(x).

    For instance if f(x) := round(x/pi)and we have a starting point x1 = 10 then we get x2 = f(x1) = f(10) = 3, then x3 = f(x2) = f(3) = 1, then x4 = f(x3) = f(1) = 0, and finally x5 = f(x4) = f(0) = 0 which means the submission should return 0.

  • You can assume that the generated sequence actually contains a fixed point.
  • You can use the native type for integers in place of .
  • You can use any language for which there are defaults for black box functions input in the standard IO meta post. If there are no such default for your language feel free to add one in the sense of the definition of black box functions, and make sure to link your proposals in that definition. Also don't forget to vote on them.

Examples

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
\$\endgroup\$
  • \$\begingroup\$ Note that while it's implied in the details that the black box function will converge on the fixed point, the last example says otherwise \$\endgroup\$ – phflack Dec 8 '17 at 20:03
  • 1
    \$\begingroup\$ @phflack The blackbox only has to converge for the given input. \$\endgroup\$ – flawr Dec 8 '17 at 20:09
  • \$\begingroup\$ Oh, originally I thought that the submission is not given x_0, which caused me some confusion. I thought a solution should be (Jelly) ~Nƭ⁻Ç$¿, which is something like, (pseudo code) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . That may worth another challenge. \$\endgroup\$ – user202729 Dec 9 '17 at 4:44
  • 1
    \$\begingroup\$ Note for future visitors: Finding any fixed point doesn't work, you must find a fixed point reachable from x_0. It's guaranteed that there exists one. \$\endgroup\$ – user202729 Dec 9 '17 at 4:46
  • \$\begingroup\$ And if not exist a fixed point, for a function f, and one initial value x0... What should be the value it have to return? And if x0=0 and f=int(9/(x-1)) with for x1=x0+1 f(x1)=f(1) is already one error... What should return the operator for that f , x0? \$\endgroup\$ – RosLuP Dec 11 '17 at 8:33

25 Answers 25

16
\$\begingroup\$

Actually, 1 byte

Y

Try it online!

Y is the fixed point function in Actually. In the TIO example, the function is shown being taken as a string, and £ is used to transform it to a function on the stack. It's also possible to just push the function to the stack like so. These are the only two ways to get a function input in Actually.

\$\endgroup\$
  • 7
    \$\begingroup\$ You just knew that some day this challenge was going to be posted, didn't you? :P \$\endgroup\$ – Erik the Outgolfer Dec 8 '17 at 20:01
  • 2
    \$\begingroup\$ @EriktheOutgolfer I've actually used Y for several challenges. I'm apparently extremely precognizant :P \$\endgroup\$ – Mego Dec 8 '17 at 20:08
11
\$\begingroup\$

APL (Dyalog), 2 bytes

⍣=

Try it online!

NB: I define O←⍣= in the the input section due to a bug in that derived monadic operators can't be defined in the way that TIO likes to define things.

Is an operator that can be used like (function⍣condition) ⍵

It applies the function, f, to until (f ⍵) condition ⍵ returns true.

⍣= is a derived monadic operator that takes a monadic function, f, as its left argument and applies it to its right argument, , until f ⍵ = ⍵

\$\endgroup\$
  • \$\begingroup\$ Maybe note that ⍣= is a derived monadic operator which takes a function as left operand and finds the fix point on the given initial value. I would use a different letter for ⍣= than f as it is an operator, not a function. \$\endgroup\$ – Adám Dec 10 '17 at 21:13
  • \$\begingroup\$ Yeah. I would. It is confusing that you call the "input" function f in your description, but then on TIO, f is your solution operator. You can also move the O←⍣= up in the Code field to let it be counted and to point out that that is the actual solution, and that the rest (Input) is just testing it. \$\endgroup\$ – Adám Dec 10 '17 at 21:20
  • \$\begingroup\$ Looks like a bug to me. I'll speak with relevant colleague tomorrow. \$\endgroup\$ – Adám Dec 10 '17 at 21:56
  • \$\begingroup\$ @Adám Updated. Let me know if the bug gets fixed \$\endgroup\$ – H.PWiz Dec 12 '17 at 18:35
10
\$\begingroup\$

Haskell, 17 bytes

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

Try it online!

\$\endgroup\$
  • 3
    \$\begingroup\$ In case someone is interested: here is an explanation why until=<<((==)=<<) finds a fix point of a given function. \$\endgroup\$ – Laikoni Dec 9 '17 at 10:12
9
\$\begingroup\$

MATLAB, 41 bytes

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

There is also this beauty that does not need function files. Unfortunately it is a little bit longer:

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)

Try it online!

\$\endgroup\$
  • 7
    \$\begingroup\$ This answer was meant as an example and does not prevent anyone from answering. \$\endgroup\$ – flawr Dec 8 '17 at 21:04
  • \$\begingroup\$ Of course, if you called this Octave, you could remove two ;s. Try it online!. \$\endgroup\$ – Sanchises Dec 14 '17 at 8:37
  • \$\begingroup\$ And in your anonymous function, you can remove the @() before x for 50 bytes. Kudos too for the way you wrap your helper function (with the g(g) in the end), I only managed to do 51 bytes @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). I'm wondering if there's any combination of both approaches that's shorter still. \$\endgroup\$ – Sanchises Dec 14 '17 at 8:55
6
\$\begingroup\$

Standard ML (MLton), 30 bytes

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

Try it online! Use as & n blackbox.

The black box functions are defined as following:

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

Ungolfed version:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g
\$\endgroup\$
  • 1
    \$\begingroup\$ Good to see SML in the wild! We use it for our functional programming class at our university. \$\endgroup\$ – vijrox Dec 10 '17 at 20:29
6
\$\begingroup\$

R, 36 35 bytes

thanks to JayCe for golfing down a byte

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

Try it online!

Verify the example functions!

R port of flawr's solution.

\$\endgroup\$
  • \$\begingroup\$ For what it's worth... function(f,x){while(x-(x=f(x)))0;x} saves one byte. \$\endgroup\$ – JayCe Jul 12 '18 at 16:55
  • \$\begingroup\$ Oh, 0, nice. Thanks much! \$\endgroup\$ – Giuseppe Jul 12 '18 at 19:07
5
\$\begingroup\$

Mathematica, 11 bytes

#2//.x_:>#&

Try it online!

Mathematica, 10 bytes

FixedPoint

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 2, 39 37 33 bytes

thanks to @Mr.Xcoder for -2 bytes

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

Try it online!

assumes the black-box function to be named f

\$\endgroup\$
  • \$\begingroup\$ Doesn't the function need to be passed as a parameter? I don't think pre-defined variables is an accepted input method. \$\endgroup\$ – mbomb007 Dec 8 '17 at 22:37
  • \$\begingroup\$ I'm not sure you're allowed to assume the function is f, isn't that a form of assuming input is in a variable? (edit: ninja'd by mbomb) \$\endgroup\$ – FlipTack Dec 8 '17 at 22:37
  • \$\begingroup\$ @mbomb007 There is a consensus which allows it for black-box functions \$\endgroup\$ – ovs Dec 8 '17 at 22:41
4
\$\begingroup\$

JavaScript (Node.js), 25 22 21 bytes

thanks Herman Lauenstein for showing me this consensus
thanks to @l4m2 for -1 byte

Assumes the black-box function to be named f.

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

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Jelly, 3 bytes

vÐL

Try it online!

Takes the left argument as a string representing a Jelly link (2_ for instance), and the right argument as an integer

How it works

 ÐL - While the output is unique...
v   -   Evaluate the function with the argument given
\$\endgroup\$
4
\$\begingroup\$

Brain-Flak, 24 bytes

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

Try it online!

(for the black box function x -> 2-x in the example below)

The provided black box function should be a program, that given x on the top of the stack, pop x and push f(x) - in other word, it should evaluate the function f on the value on the top of the stack.

Equivalent Mini-Flak is 26 bytes (thanks to Wheat Wizard for saving 2 bytes):

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

(not counting the comments and spaces)

Take the function (inside the <>) and a number x0 from input. (note that Brain-Flak is an esoteric language and can't take functional argument as input)


Example blackbox functions:

x -> 2-x: Try it online!


Explanation:


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

\$\endgroup\$
3
\$\begingroup\$

Swift, 47 42 bytes

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

Naive approach, assumes that the black box function is named f

\$\endgroup\$
  • \$\begingroup\$ I am in doubt regarding your second attempt, because it is a complex closure and its type is ambiguous unless you explicitly cast it to {...}as(<parameter types>)-><return type>. If you don't specify its return type, it will throw build-time errors so I don't think it is valid as of now (note that the cast must be included in the byte count). Your first submission is fine, though. \$\endgroup\$ – Mr. Xcoder Dec 8 '17 at 19:55
2
\$\begingroup\$

C (gcc), 40 bytes

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

Try it online! Note that the flags are not necessary, they are there to aid with testing the fixpoint function defined above.

This is a function that takes an int n and a function pointer b : int → int. Abusing the fact that writing to the first variable argument sets the eax register, which is equivalent to returning. Otherwise, this is pretty standard as far as C golf goes. n^b(n) checks for the inequality of n and the black box applied to n. When unequal, it calls the fixpoint function f again recursively with the application and black box as arguments. Otherwise, it returns the fixpoint.

†Citation needed, I vaguely remember reading this somewhere and google seems to confirm my suspicions

It declares input with K&R-style parameter typing:

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

The arcane bit on the second line above declares b to be a function pointer that takes an integer parameter—the default type of _ is assumed to be an integer. Similarly, n is assumed to be an integer, and f is assumed to return an integer. Hooray for implicit typing?

\$\endgroup\$
2
\$\begingroup\$

Clean, 46 bytes

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

Assumes the function is defined as f :: !Int -> Int

It takes the head of the infinite list of applications of f f f ... x filtered for those elements where f el == el.

Try it online!

If you want to change the function in the TIO, Clean's lambda syntax is:

\argument = expression

(actually it's far more complicated, but thankfully we only need unary functions)

\$\endgroup\$
2
\$\begingroup\$

APL (Dyalog Unicode), 14 bytes

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

Try it online!

The function at the header is equivalent to f(x) = floor(sqrt(abs(x)))

Thanks @Adám for pointing out that the original answer wasn't valid according to PPCG consensus.

How it works:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} ⍝ 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(⍵)
\$\endgroup\$
  • \$\begingroup\$ {⍵=f⍵:⍵⋄∇(f⍵)} would be ok for separate anonymous function from its name (n) \$\endgroup\$ – RosLuP Dec 9 '17 at 10:22
  • 2
    \$\begingroup\$ This assumes that f is preassigned, which I think is prohibited by PPCG consensus. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵} would be a valid operator solution. \$\endgroup\$ – Adám Dec 10 '17 at 21:18
1
\$\begingroup\$

Octave, 37 bytes

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

Try it online!

Octave has inline assignment but MATLAB doesn't, so this is a golfier Octave port of flawr's solution.

It also ports nicely to R.

\$\endgroup\$
1
\$\begingroup\$

Kotlin, 50 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Forth (gforth), 36 bytes

This version just assumes f is predefined. It's not as cool as the solution below it. Both programs exit with a stack overflow if not found, or a stack underflow if found (after printing the result).

Try it online

: g dup f over = IF . THEN recurse ;

Forth (gforth), 52 bytes

This allows a function's execution token to be passed as a parameter, and is definitely the cooler solution.

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

Try it online

Explanation:

: 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
\$\endgroup\$
1
\$\begingroup\$

Ruby, 31 28 bytes

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 25 bytes - ->x,f{1while x!=x=f[x];x} \$\endgroup\$ – G B Dec 14 '17 at 7:39
1
\$\begingroup\$

tinylisp repl, 28 bytes

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

Assumes that the function f is predefined.

Try it online! (The example function is f(x) = (x*2) mod 10.)

Ungolfed

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

If f(x) equals x, then x is a fixed point; return it. Otherwise, recursively look for a fixed point starting from f(x) instead of x.

\$\endgroup\$
1
\$\begingroup\$

APL NARS 65 chars

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 operator would return ∞ (or possibly -oo or Nan) for error, else one value x with x=f(x). In test f=floor(sqrt(abs(x))), f1=2-x, f2=c(c(c(x))) with 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
\$\endgroup\$
1
\$\begingroup\$

Clojure, 45 43 bytes

Well, this is the shortest and ugliest:

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

+ is there instead of a number so that it is not equal to any value of x0.

55 bytes and functional:

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

Example:

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

x86 opcode, 8 bytes

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

Take input: ecx (value x0), edx (function address, take input from ecx, write result to eax without modifying the value of ecx and edx)

8086 opcode, 7 bytes (but slow)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

If there exists a fixed point, looping 65536 times always drive it there.
Take input: ax (initial value x0), dx (function address, take input from ax, write output to ax without modifying the value of cx and dx).
Output the fixed point in register ax.

\$\endgroup\$
  • \$\begingroup\$ It would certainly help if you make the answer more readable. \$\endgroup\$ – user202729 Dec 14 '17 at 7:04
  • \$\begingroup\$ more edit to make it correct \$\endgroup\$ – l4m2 Dec 14 '17 at 7:33
0
\$\begingroup\$

Perl 5, 18 + 1 (-p)

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

try it online

\$\endgroup\$
0
\$\begingroup\$

Java 8, 42 bytes

This takes a Function<Integer, Integer> or IntFunction<Integer> and an int or Integer (curried) and returns the fixed point.

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

Try It Online

Takes advantage of the fact that Java evaluates subexpressions from left to right (so the old i is compared to the new), a property which I was unaware of while writing this!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.