Temukan Titik Tetap

24

Diberikan bilangan bulat dan beberapa fungsi kotak hitam menemukan titik tetap dalam urutan yang ditentukan oleh .x1 f: ℤ → ℤfxk+1 := f(xk)

Detail

  • Nilai xdikatakan titik tetap fjika x = f(x).

    Misalnya jika f(x) := round(x/pi)dan kita memiliki titik awal maka kita dapatkan , lalu , lalu , dan akhirnya yang berarti pengiriman harus kembali .x1 = 10x2 = f(x1) = f(10) = 3x3 = f(x2) = f(3) = 1x4 = f(x3) = f(1) = 0x5 = f(x4) = f(0) = 00

  • Anda dapat mengasumsikan bahwa urutan yang dihasilkan sebenarnya berisi titik tetap.
  • Anda dapat menggunakan tipe asli untuk bilangan bulat sebagai pengganti .
  • Anda dapat menggunakan bahasa apa pun yang ada default untuk input fungsi kotak hitam di pos meta IO standar . Jika tidak ada standar untuk bahasa Anda, jangan ragu untuk menambahkannya dalam arti fungsi kotak hitam , dan pastikan untuk menautkan proposal Anda dalam definisi itu. Juga jangan lupa untuk memilih mereka.

Contohnya

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
cacat
sumber
Perhatikan bahwa sementara itu tersirat dalam detail bahwa fungsi kotak hitam akan menyatu pada titik tetap, contoh terakhir mengatakan sebaliknya
phflack
1
@ phflack Kotak hitam hanya perlu menyatu untuk input yang diberikan.
flawr
Oh, awalnya saya berpikir bahwa pengiriman tidak diberikan x_0, yang menyebabkan saya kebingungan. Saya pikir solusinya harus (Jelly) ~Nƭ⁻Ç$¿, yang merupakan sesuatu seperti, (kode semu) for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x); . Itu mungkin bernilai tantangan lain.
user202729
1
Catatan untuk pengunjung masa depan: Menemukan titik tetap apa pun tidak berfungsi, Anda harus menemukan titik tetap dapat dijangkau dari x_0. Dijamin ada satu.
user202729
Dan jika tidak ada titik tetap, untuk fungsi f, dan satu nilai awal x0 ... Apa yang harus menjadi nilai yang harus dikembalikan? Dan jika x0 = 0 dan f = int (9 / (x-1)) dengan untuk x1 = x0 + 1 f (x1) = f (1) sudah satu kesalahan ... Apa yang harus mengembalikan operator untuk f itu, x0?
RosLuP

Jawaban:

16

Sebenarnya 1 byte

Y

Cobalah online!

Yadalah fungsi titik tetap di Sebenarnya. Dalam contoh TIO, fungsi ditampilkan diambil sebagai string, dan £digunakan untuk mengubahnya menjadi fungsi pada stack. Mungkin juga untuk hanya mendorong fungsi ke tumpukan seperti itu . Ini adalah dua cara hanya untuk mendapatkan input fungsi di Sebenarnya.

Mego
sumber
7
Anda baru tahu bahwa suatu hari tantangan ini akan diposting, bukan? : P
Erik the Outgolfer
2
@EriktheOutgolfer Saya sebenarnya telah menggunakan Ybeberapa tantangan. Saya tampaknya sangat paham : P
Mego
11

APL (Dyalog) , 2 byte

⍣=

Cobalah online!

NB: Saya mendefinisikan O←⍣=di bagian input karena bug di operator monadik turunan tidak dapat didefinisikan dengan cara TIO suka mendefinisikan sesuatu.

Adalah operator yang bisa digunakan suka (function⍣condition) ⍵

Ini berlaku function, f, untuk sampai(f ⍵) condition ⍵ kembali benar.

⍣=adalah operator turunan monadik yang menggunakan fungsi monadik f,, sebagai argumen kiri dan menerapkannya pada argumen kanannya ,, hinggaf ⍵ = ⍵

H.Piz
sumber
Mungkin perlu dicatat bahwa itu ⍣=adalah operator monadik turunan yang mengambil fungsi sebagai operan kiri dan menemukan titik perbaikan pada nilai awal yang diberikan. Saya akan menggunakan huruf yang berbeda untuk ⍣=dibandingkan fkarena merupakan o perator, bukan f pengurapan.
Adem
Ya. Saya akan. Sangat membingungkan bahwa Anda memanggil fungsi "input" fdalam deskripsi Anda, tetapi kemudian pada TIO, fadalah operator solusi Anda. Anda juga dapat memindahkan bagian O←⍣=atas dalam bidang Kode untuk membiarkannya dihitung dan menunjukkan bahwa itu adalah solusi aktual, dan sisanya (Input) hanya mengujinya.
Adem
Tampak seperti bug bagi saya. Saya akan berbicara dengan rekan yang relevan besok.
Adám
@ Adám Diperbarui. Beri tahu saya jika bug diperbaiki
H.PWiz
10

Haskell, 17 byte

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

Cobalah online!

nimi
sumber
3
Jika seseorang tertarik: inilah penjelasan mengapa until=<<((==)=<<) menemukan titik perbaikan dari fungsi yang diberikan.
Laikoni
9

MATLAB , 41 byte

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

Ada juga keindahan ini yang tidak membutuhkan file fungsi. Sayangnya ini sedikit lebih lama:

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)

Cobalah online!

cacat
sumber
7
Jawaban ini dimaksudkan sebagai contoh dan tidak mencegah siapa pun untuk menjawab.
flawr
Tentu saja, jika Anda memanggil Oktaf ini, Anda bisa menghapus dua ;s. Cobalah online! .
Sanchises
Dan dalam fungsi anonim Anda, Anda dapat menghapus @()sebelum xuntuk 50 byte. Kudos juga untuk cara Anda membungkus fungsi pembantu Anda (dengan g(g)pada akhirnya), saya hanya berhasil melakukan 51 byte @(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x). Saya bertanya-tanya apakah ada kombinasi dari kedua pendekatan yang masih lebih pendek.
Sanchises
6

ML Standar (MLton) , 30 byte

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

Cobalah online!Gunakan sebagai & n blackbox.

Fungsi kotak hitam didefinisikan sebagai berikut:

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 tidak disatukan:

fun fixpoint n g = if n = g n then n else fixpoint (g n) g
Laikoni
sumber
1
Senang melihat SML di alam liar! Kami menggunakannya untuk kelas pemrograman fungsional kami di universitas kami.
vijrox
6

R , 36 35 byte

terima kasih kepada JayCe untuk bermain golf satu byte

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

Cobalah online!

Verifikasi contoh fungsi!

R port solusi flawr.

Giuseppe
sumber
Untuk apa nilainya ... function(f,x){while(x-(x=f(x)))0;x}menghemat satu byte.
JayCe
Oh 0bagus Terimakasih banyak!
Giuseppe
4

Python 2 , 39 37 33 byte

terima kasih kepada @ Mr.Xcoder untuk -2 byte

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

Cobalah online!

mengasumsikan fungsi kotak hitam diberi nama f

ovs
sumber
Tidakkah fungsi tersebut harus diteruskan sebagai parameter? Saya tidak berpikir variabel yang didefinisikan sebelumnya adalah metode input yang diterima.
mbomb007
Saya tidak yakin Anda diizinkan untuk menganggap fungsinya f, bukankah itu bentuk asumsi input dalam variabel? (sunting: ninja'd oleh mbomb)
FlipTack
4

Jelly , 3 byte

vÐL

Cobalah online!

Mengambil argumen kiri sebagai string yang mewakili tautan Jelly (2_ misalnya), dan argumen kanan sebagai integer

Bagaimana itu bekerja

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

Brain-Flak , 24 byte

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

Cobalah online!

(untuk fungsi kotak hitam x -> 2-xpada contoh di bawah ini)

Fungsi kotak hitam yang disediakan harus berupa program, yang diberikan xdi bagian atas tumpukan, pop, xdan tekan f(x)- dengan kata lain, harus mengevaluasi fungsi fpada nilai di bagian atas tumpukan.

Mini-Flak Setara adalah 26 byte (terima kasih kepada Wheat Wizard karena telah menyimpan 2 byte):

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

(tidak termasuk komentar dan spasi)

Ambil fungsi (di dalam <>) dan angka dari input. (perhatikan bahwa Brain-Flak adalah bahasa esoterik dan tidak dapat mengambil argumen fungsional sebagai masukan)x0


Contoh fungsi kotak hitam:

x -> 2-x: Coba online!


Penjelasan:


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

pengguna202729
sumber
3

Swift , 47 42 byte

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

Pendekatan naif, mengasumsikan bahwa fungsi kotak hitam diberi nama f

Herman L.
sumber
Saya ragu tentang upaya kedua Anda, karena ini adalah penutupan yang kompleks dan tipenya ambigu kecuali Anda secara eksplisit menyerahkannya {...}as(<parameter types>)-><return type>. Jika Anda tidak menentukan tipe kembalinya, ia akan memunculkan error build-time jadi saya tidak berpikir itu valid seperti sekarang (perhatikan bahwa para pemain harus dimasukkan dalam jumlah byte). Kiriman pertama Anda baik-baik saja.
Tn. Xcoder
2

C (gcc) , 40 byte

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

Cobalah online! Perhatikan bahwa flag tidak diperlukan, mereka ada di sana untuk membantu menguji fungsi fixpoint yang didefinisikan di atas.

Ini adalah fungsi yang mengambil int ndan pointer fungsi b : int → int. Menyalahgunakan fakta bahwa menulis ke argumen variabel pertama menetapkan eaxregister, yang setara dengan mengembalikan . Kalau tidak, ini cukup standar sejauh C golf berlangsung. n^b(n)memeriksa ketimpangan ndan kotak hitam yang diterapkan n. Ketika tidak sama, itu memanggil fungsi fixpoint flagi secara rekursif dengan aplikasi dan kotak hitam sebagai argumen. Kalau tidak, ia mengembalikan fixpoint.

† Kutipan diperlukan, saya samar-samar ingat membaca ini di suatu tempat dan google tampaknya mengkonfirmasi kecurigaan saya

Ini menyatakan input dengan mengetik parameter K & R-style:

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

Bit misterius pada baris kedua di atas menyatakan bsebagai pointer fungsi yang mengambil parameter integer — tipe default _diasumsikan bilangan bulat. Demikian pula, ndiasumsikan bilangan bulat, dan fdiasumsikan mengembalikan bilangan bulat. Bagaimana mengetik secara implisit?

Conor O'Brien
sumber
2

Bersih , 46 byte

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

Mengasumsikan fungsi didefinisikan sebagai f :: !Int -> Int

Dibutuhkan kepala dari daftar aplikasi tak terbatas yang f f f ... xdifilter untuk elemen mana f el == el.

Cobalah online!

Jika Anda ingin mengubah fungsi di TIO, sintaks Clean's lambda adalah:

\argument = expression

(sebenarnya jauh lebih rumit, tapi untungnya kita hanya perlu fungsi unary)

Suram
sumber
2

APL (Dyalog Unicode) , 14 byte

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

Cobalah online!

Fungsi di header setara dengan f(x) = floor(sqrt(abs(x)))

Terima kasih @ Adm karena telah menunjukkan bahwa jawaban asli tidak valid sesuai dengan konsensus PPCG.

Bagaimana itu bekerja:

{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}  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é
sumber
{⍵ = f⍵: ⍵⋄∇ (f⍵)} akan baik-baik saja untuk fungsi anonim yang terpisah dari namanya (n)
RosLuP
2
Ini mengasumsikan yang fditugaskan, yang saya pikir dilarang oleh konsensus PPCG. {⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}akan menjadi solusi operator yang valid.
Adem
1

Keempat (gforth), 36 byte

Versi ini hanya mengasumsikan fsudah ditentukan sebelumnya. Ini tidak sekeren solusi di bawahnya. Kedua program keluar dengan stack overflow jika tidak ditemukan, atau stack underflow jika ditemukan (setelah mencetak hasilnya).

Cobalah online

: g dup f over = IF . THEN recurse ;

Keempat (gforth), 52 byte

Ini memungkinkan token eksekusi fungsi dilewatkan sebagai parameter, dan jelas merupakan solusi yang lebih keren.

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

Cobalah online

Penjelasan:

: 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
sumber
1

Ruby , 31 28 byte

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

Cobalah online!

Pasang kembali Monica iamnotmaynard
sumber
25 byte - -> x, f {1 saat x! = X = f [x]; x}
GB
1

tinylisp repl, 28 byte

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

Diasumsikan bahwa fungsi fsudah ditentukan sebelumnya.

Cobalah online! (Fungsi contohnya adalah f(x) = (x*2) mod 10.)

Tidak disatukan

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

Jika f(x)sama x, maka xadalah titik tetap; Kembalikan. Jika tidak, cari titik tetap secara rekursif mulai dari f(x)bukan x.

DLosc
sumber
1

APL NARS 65 karakter

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

operator v akan mengembalikan ∞ (atau mungkin -oo atau Nan) untuk kesalahan, jika tidak satu nilai x dengan x = f (x). Dalam pengujian f = lantai (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) dengan 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
sumber
1

Clojure, 45 43 byte

Nah, ini yang terpendek dan paling jelek:

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

+apakah ada bukannya angka sehingga tidak sama dengan nilai apa pun dari x0.

55 byte dan fungsional:

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

Contoh:

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

opcode x86, 8 byte

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

Ambil input: ecx(nilai ), (alamat fungsi, ambil input dari , tulis hasil tanpa mengubah nilai danx0edxecxeaxecxedx )

8086 opcode, 7 byte (tetapi lambat)

    xor     cx,     cx
    call    dx
    loop    $-2
    ret

Jika ada titik tetap, looping 65536 kali selalu mengendarainya di sana.
Ambil input: ax(nilai awal ), (alamat fungsi, ambil input dari , tulis output ke tanpa mengubah nilai dan ). Keluarkan titik tetap dalam register .x0dxaxaxcxdx
ax

l4m2
sumber
Tentu akan membantu jika Anda membuat jawabannya lebih mudah dibaca.
user202729
lebih banyak edit untuk membuatnya benar
l4m2
0

Java 8, 42 byte

Ini membutuhkan a Function<Integer, Integer>atau IntFunction<Integer>dan intatau Integer(kari) dan mengembalikan titik tetap.

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

Cobalah secara Online

Mengambil keuntungan dari fakta bahwa Java mengevaluasi subekspresi dari kiri ke kanan (jadi yang lama idibandingkan dengan yang baru), properti yang saya tidak sadari ketika menulis ini!

Jakob
sumber