Dado um número inteiro e alguma função de caixa preta, encontre um ponto fixo de na sequência definida por .x1
f: ℤ → ℤ
f
xk+1 := f(xk)
Detalhes
Um valor
x
é considerado um ponto fixo def
sex = f(x)
.Por exemplo, se
f(x) := round(x/pi)
e temos um ponto de partida , obtemos , então , então e finalmente, o que significa que a submissão deve retornar .x1 = 10
x2 = f(x1) = f(10) = 3
x3 = f(x2) = f(3) = 1
x4 = f(x3) = f(1) = 0
x5 = f(x4) = f(0) = 0
0
- Você pode assumir que a sequência gerada realmente contém um ponto fixo.
- Você pode usar o tipo nativo para números inteiros no lugar de
ℤ
. - Você pode usar qualquer idioma para o qual há padrões para as funções de caixa preta inseridas na meta post de E / S padrão . Se não houver esse padrão para o seu idioma, adicione um no sentido da definição de funções da caixa preta e certifique-se de vincular suas propostas nessa definição. Também não se esqueça de votar neles.
Exemplos
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
~Nƭ⁻Ç$¿
, que é algo como, (pseudo código)for x in [0, -1, 1, -2, 2, -3, 3, -4, 4, ...]: if (x == f(x)): break; print(x);
. Isso pode valer outro desafio.Respostas:
Na verdade , 1 byte
Experimente online!
Y
é a função de ponto fixo em Na verdade. No exemplo do TIO, a função é mostrada como uma sequência e£
é usada para transformá-la em uma função na pilha. Também é possível simplesmente empurrar a função para a pilha dessa maneira . Estas são as únicas duas maneiras de obter uma entrada de função no Actually.fonte
Y
para vários desafios. Eu sou aparentemente extremamente precognitivo : PAPL (Dyalog) , 2 bytes
Experimente online!
NB: Eu defino
O←⍣=
na seção de entrada devido a um erro em que os operadores monádicos derivados não podem ser definidos da maneira que o TIO gosta de definir.⍣
É um operador que pode ser usado como(function⍣condition) ⍵
Aplica-se a
function
,f
para⍵
até(f ⍵) condition ⍵
retornos verdade.⍣=
é um operador monádico derivado que assume uma função monádicaf
, como argumento à esquerda e a aplica ao argumento à direita⍵
, atéf ⍵ = ⍵
fonte
⍣=
é um operador monádico derivado que assume uma função como operando esquerdo e encontra o ponto de correção no valor inicial fornecido. Gostaria de usar uma letra diferente para⍣=
quef
, uma vez que é um o perator, não uma f unção.f
em sua descrição, mas no TIOf
é seu operador de solução. Você também pode mover aO←⍣=
seta para cima no campo Código para permitir que seja contada e apontar que essa é a solução real e que o restante (Entrada) está apenas testando-a.Haskell, 17 bytes
Experimente online!
fonte
until=<<((==)=<<)
encontrar um ponto de correção para uma determinada função.MATLAB , 41 bytes
Há também essa beleza que não precisa de arquivos de função. Infelizmente, é um pouco mais longo:
Experimente online!
fonte
;
s. Experimente online! .@()
antesx
por 50 bytes. Parabéns também pela forma como você agrupa sua função auxiliar (com ag(g)
no final), eu só consegui fazer 51 bytes@(g,x)(f=@(r,z){@()r(r,m),z}{(m=g(z)==z)+1}())(f,x)
. Gostaria de saber se existe alguma combinação das duas abordagens mais curta ainda.ML padrão (MLton) , 30 bytes
Experimente online! Use como
& n blackbox
.As funções da caixa preta são definidas da seguinte maneira:
Versão não destruída:
fonte
R ,
3635 bytesgraças a JayCe por jogar um byte
Experimente online!
Verifique as funções de exemplo!
Porta R da solução da flawr.
fonte
function(f,x){while(x-(x=f(x)))0;x}
economiza um byte.0
, que bom. Muito obrigado!Mathematica, 11 bytes
Experimente online!
Mathematica, 10 bytes
Experimente online!
fonte
Python 2 ,
393733 bytesgraças a @ Mr.Xcoder por -2 bytes
Experimente online!
assume que a função de caixa preta seja nomeada f
fonte
f
, não é que uma forma de assumir que a entrada está em uma variável? (edit: ninja'd por mbomb)JavaScript (Node.js) ,
252221 bytesobrigado Herman Lauenstein por me mostrar esse consenso
graças a @ l4m2 por -1 byte
Assume que a função de caixa preta seja nomeada
f
.Experimente online!
fonte
Gelatina , 3 bytes
Experimente online!
Aceita o argumento esquerdo como uma string que representa um link Jelly (
2_
por exemplo) e o argumento direito como um número inteiroComo funciona
fonte
Flak cerebral , 24 bytes
Experimente online!
(para a função caixa preta
x -> 2-x
no exemplo abaixo)A função de caixa preta fornecida deve ser um programa que, fornecido
x
na parte superior da pilha, popx
e pushf(x)
-in, ou seja, deve avaliar a funçãof
no valor na parte superior da pilha.Mini-Flak equivalente é de 26 bytes (graças ao Assistente de Trigo por salvar 2 bytes):
(sem contar os comentários e os espaços)
Pegue a função (dentro da
<>
) e um número da entrada. (observe que Brain-Flak é uma linguagem esotérica e não pode receber argumentos funcionais como entrada)x0
Exemplo de funções de caixa preta:
x -> 2-x
: Experimente online!Explicação:
fonte
Rápido ,
4742 bytesAbordagem ingênua, assume que a função caixa preta é denominada
f
fonte
{...}as(<parameter types>)-><return type>
. Se você não especificar seu tipo de retorno, ele lançará erros no tempo de compilação, então não acho que seja válido a partir de agora (observe que a conversão deve ser incluída na contagem de bytes). Sua primeira submissão é boa, no entanto.C (gcc) , 40 bytes
Experimente online!Observe que os sinalizadores não são necessários, eles estão lá para ajudar no teste da função de ponto de correção definida acima.
Esta é uma função que recebe um int
n
e um ponteiro de funçãob : int → int
. Abusar do fato de que gravar no primeiro argumento da variável define oeax
registro, o que equivale a retornar † . Caso contrário, isso é bastante padrão no que diz respeito ao golfe C.n^b(n)
verifica a desigualdaden
e a caixa preta aplicada an
. Quando desigual, chama a função de ponto fixof
novamente recursivamente com o aplicativo e a caixa preta como argumentos. Caso contrário, ele retornará o ponto de correção.† Citação necessária, lembro-me vagamente de ler isso em algum lugar e o Google parece confirmar minhas suspeitas
Ele declara a entrada com a digitação de parâmetros no estilo K & R:
O bit arcano na segunda linha acima declara
b
ser um ponteiro de função que aceita um parâmetro inteiro - o tipo padrão de_
é assumido como um número inteiro. Da mesma forma,n
é considerado um número inteiro ef
é retornado um número inteiro. Viva a digitação implícita?fonte
Limpo , 46 bytes
Assume que a função está definida como
f :: !Int -> Int
Leva a cabeça da lista infinita de aplicativos
f f f ... x
filtrados para os elementos em quef el == el
.Experimente online!
Se você deseja alterar a função no TIO, a sintaxe lambda do Clean é:
\argument = expression
(na verdade, é muito mais complicado, mas felizmente precisamos apenas de funções unárias)
fonte
APL (Dyalog Unicode) , 14 bytes
Experimente online!
A função no cabeçalho é equivalente a
f(x) = floor(sqrt(abs(x)))
Obrigado @ Adám por apontar que a resposta original não era válida de acordo com o consenso do PPCG.
Como funciona:
fonte
f
é pré-atribuído, o que eu acho que é proibido pelo consenso do PPCG.{⍵=⍺⍺⍵:⍵⋄∇⍺⍺⍵}
seria uma solução de operador válida.Oitava , 37 bytes
Experimente online!
O Octave possui atribuição em linha, mas o MATLAB não, portanto este é um porto octave de golfista de golfe Octave, solução flawr .
É também portas bem a R .
fonte
Kotlin , 50 bytes
Experimente online!
fonte
Adiante (gforth), 36 bytes
Esta versão assume apenas que
f
é predefinida. Não é tão legal quanto a solução abaixo dela. Ambos os programas são encerrados com um estouro de pilha, se não encontrado, ou um estouro de pilha, se encontrado (após a impressão do resultado).Experimente online
Quarto (gforth), 52 bytes
Isso permite que o token de execução de uma função seja transmitido como parâmetro e é definitivamente a solução mais legal.
Experimente online
Explicação:
fonte
Ruby ,
3128 bytesExperimente online!
fonte
repl do tinylisp , 28 bytes
Assume que a função
f
é predefinida.Experimente online! (A função de exemplo é
f(x) = (x*2) mod 10
.)Ungolfed
Se for
f(x)
igualx
, entãox
é um ponto fixo; devolver. Caso contrário, procure recursivamente um ponto fixo iniciando emf(x)
vez dex
.fonte
APL NARS 65 caracteres
v O operador retornaria ∞ (ou possivelmente -oo ou Nan) por erro, senão um valor x com x = f (x). No teste f = piso (sqrt (abs (x))), f1 = 2-x, f2 = c (c (c (x))) com c = x% 2 == 0? X / 2: 3 * x +1
fonte
Clojure,
4543 bytesBem, este é o mais curto e mais feio:
+
existe em vez de um número para que não seja igual a qualquer valor dex0
.55 bytes e funcional:
Exemplo:
fonte
x86 opcode, 8 bytes
Receber entrada:
ecx
(valor ), (endereço da função, receber entrada , gravar resultado sem modificar o valor de e )x0
edx
ecx
eax
ecx
edx
8086 opcode, 7 bytes (mas lento)
Se existe um ponto fixo, o loop 65536 vezes sempre o leva até lá.
Receber entrada:
ax
(valor inicial ), (endereço da função, receber entrada , gravar saída sem modificar o valor de e ). Emita o ponto fixo no registro .x0
dx
ax
ax
cx
dx
ax
fonte
Perl 5, 18 + 1 (
-p
)experimente online
fonte
Java 8, 42 bytes
Isso pega um
Function<Integer, Integer>
ouIntFunction<Integer>
e umint
ouInteger
(com curry) e retorna o ponto fixo.Experimente Online
Aproveita o fato de o Java avaliar subexpressões da esquerda para a direita (para que o antigo
i
seja comparado ao novo), uma propriedade que eu desconhecia ao escrever isso!fonte