Esse desafio foi inspirado em um blog de programação que eu frequento. Veja o post original aqui: Um quebra-cabeça de programação
Desafio
Defina uma função f:Q->Q
tal que f(f(n)) = -n
para todos os números diferentes de zero n
e onde Q
está o conjunto de números racionais.
Detalhes
Em qualquer idioma que você preferir, defina uma função ou programa f
que aceite como parâmetro um número n
e retorne ou produza um número f(n)
.
A entrada pode ser fornecida por qualquer mecanismo que seja mais natural para o seu idioma: argumento de função, leitura de STDIN, argumento de linha de comando, posição da pilha, entrada de voz, sinais de gangue, etc.
A saída deve ser um valor de retorno de uma função / programa ou impresso em STDOUT.
Gostaria de restringir respostas a funções que não tiram vantagem do estado do programa ou da memória / dados globais visíveis de fora da função f
. Por exemplo, manter um contador fora do f
que conta quantas vezes f
foi chamado e apenas fazer uma negação com base nessa contagem não é muito desafiador ou interessante para ninguém. As decisões tomadas f
devem depender apenas de dados dentro f
do escopo lexical.
No entanto, essa restrição provavelmente é inadequada para alguns idiomas orientados a pilha ou outros tipos de idiomas que não distinguem esses tipos de dados ou escopos. Por favor, use seu melhor julgamento para manter o espírito desse desafio.
Pontuação
Aplicam-se regras comuns de golfe com código - sua pontuação é o número de bytes no seu código-fonte.
A resposta mínima requer que o domínio e o codomain f
sejam um subconjunto dos racionais Q
. Se você restringir seu domínio e seu código f
aos números inteiros Z
, sua pontuação será o limite de 90% do número de bytes no seu código-fonte.
Tiebreak
Em caso de empate, o seguinte será usado na ordem:
- Menor número de símbolos que não sejam espaços em branco para impressão no código-fonte
- Data e hora do envio da resposta mais cedo
Editar
Você não é obrigado a suportar números de tamanho arbitrário. Por favor, interprete os conjuntos Z
e Q
como tipos de dados no idioma escolhido (geralmente inteiro e ponto flutuante, respectivamente).
Se sua solução depende inteiramente da estrutura subjacente ou padrão de bits de um tipo de dados, descreva suas limitações e como está sendo usada.
f:Q->Q
significa?f
é uma função que mapeia membros deQ
(números racionais) para outros membros (possivelmente o mesmo) deQ
. veja en.wikipedia.org/wiki/Function_(mathematics)#NotationRespostas:
J, 9 pontos (10 caracteres)
Com base na resposta do stackoverflow :
Primeira ideia (13 caracteres):
fonte
Python:
61 34 30 2927 pontosf: Q -> Q
em matemática:
em Python:
testado com
lógica por trás disso:
Quando você pega um número inteiro
n
e o coloca,f
receberáx+0.5
. Como não é mais um número inteiro, a próxima aplicação será0.5-(x+0.5)
qual é-x
.Créditos
Graças a
Notas
Primeiro eu pensei que isso seria ok
mas é f: N-> C e isso não é permitido: - /
fonte
f=lambda x:x%1>0and(-x+x%1)or x+.1
que possui apenas 34 caracteres.f=lambda x:[x+.1,x%1-x](x%1>0)
é apenas 30f=lambda x:[x+.5,.5-x][x%1>0]
. Observe o uso de .5 em vez de .1 para solucionar problemas de precisãof:Q->Q
significa apenas que f mapeia o número racional para números racionais. Qual minha definição de f faz.C, 41 pontos (41 ou 45 caracteres)
Funciona usando 32 e 64 bits.
f : Z -> Z
(excetoINT_MAX
):Se não precisarmos incluir
0
, podemos raspar alguns caracteres (41 caracteres):f : Z -> Z
(exceto0
&INT_MAX
):Essa função funciona dividindo todos os números inteiros em 4 grupos, com base no sinal e na paridade.
Portanto, temos as 4 combinações diferentes:
Como precisamos mudar o sinal do número, mas não a paridade após duas passagens, obtemos duas sequências possíveis diferentes:
Neste exemplo, eu escolhi o primeiro.
Primeiro, precisamos mapear todos os números inteiros positivos para números inteiros negativos. Fazemos isso alterando o sinal e incrementando o número (você também pode optar por diminuir o número):
Em seguida, precisamos mapear todos os números inteiros negativos ímpares para números inteiros negativos pares. Precisamos garantir que
f2(f1(n)) = -n
:Usando os mesmos métodos, encontramos
f3
ef4
:Para combinar essas funções em uma única função, observamos que sempre
n
que trocamos o sinaln
e sempren
que positivo, aumentamos em um e diminuímos em um:Assim, isso pode ser reescrito como:
onde
odd(n)
retorna1
para números ímpares e-1
números pares.Existem 4 soluções no total:
INT_MIN
pode sempre ser considerado um caso extremo em todas as 4 funções como-INT_MIN == INT_MIN
=>f(f(INT_MIN)) = INT_MIN
.fonte
0
e outros 3 números.Z
bônus se cobrir pelo menos 0.Aqui está a minha chance.
Exemplo ao vivo :
Os tipos de entrada podem ser arbitrariamente adaptados para atender às suas necessidades. Esta versão funciona para literais inteiros menores em magnitude que 2 ^ 32-1.
fonte
f:Q->Q
nãof:Z->Z
.f:Z->Z
, pena do texto confusoreturn -i
JavaScript, 18
Usando a nova notação de seta gorda (Firefox 22).
Outra versão (18):
Versão anterior (20):
Exemplo:
fonte
Mathematica 18
Aqui
⌊...⌋
está a função de piso. Ele usa apenas números racionais (não listas, números complexos, etc.)fonte
linguagem de montagem x86 (FASM). O argumento e o resultado estão no registro eax.
Funciona corretamente para -2 ^ 30 <N <+ 2 ^ 30-1
Código executável de 16 bytes.
fonte
Lisp comum: 35 bytes
Esquema (e raquete): 36 bytes
Ungolfed com comentários e explicação:
Para qualquer número no vai se transformar na fração que é um número exato reais em ambas as línguas.
x
[1,->]
if
1/2
A parte de divisão se tornará
(/ 1/2 x)
então a fração1/(x*2)
que sempre estará abaixo1
. Pois1
será1/2
,2
pois é1/4
, etc.Para qualquer número abaixo de 1,
if
ele retornará à fração-1/2
, o que faz com que a função faça o(/ -1/2 x)
que é,-1/(2*x)
mas como podemos esperar que o valor seja o resultado da execução anterior, podemos substituir x por 1 / (x * 2) fazendo uma aplicação dupla-1/((1/(x*2))*2) = -x
Por exemplo, uma vez que se
1
transforma na1/2
segunda aplicação, é(/ -1/2 1/2) ==> -1
fonte
C, 60 (⌈66 * .9⌉)
Aqui está uma versão sem condensação:
Esse método funciona usando apenas números inteiros, portanto, ele recebe o bônus de pontuação de 90%. Eu estava originalmente escrevendo em java, mas percebi que esse programa em particular poderia se beneficiar de operadores lógicos no estilo C.
Como não há um número inteiro correspondente a
-INT_MIN
,f(f(INT_MIN))
retornaINT_MIN
.O mapeamento subjacente é algebricamente bastante simples. A execução da instrução
x=f(x)
substitui x por:x+1
, sex
é positivo e ímpar-x+1
, sex
for positivo e uniformex-1
, sex
for negativo e ímpar-x-1
, sex
for negativo e uniformeO resultado de cada caso cairá no próximo caso na próxima vez que a função for aplicada a x.
Como você pode ver, compor um caso com o caso a seguir produz
-x
.O código é o resultado de alguma simplificação inteligente da função para tirar proveito da estrutura de bits dos números inteiros de dois elogios.
fonte
> <> , 21 + 3 = 24 bytes, 22 pontos
Use o intérprete oficial do Python e use a
-v
opção de linha de comando para inserir entrada, a um custo de 3 bytes.Tenho a sensação de que isso poderia ser melhor - continuarei olhando para ele e tentarei jogar com calma.
Dada a entrada
n
, o programa geraonde
(n>0)
e(n<0)
são booleanos. Isso é equivalente à resposta Python da Gelatinamas
><>
não tem um operador de exponenciação built-in por isso usamos(1 - 2*(n%2))
no lugar de(-1)**n
.A seguir, é apresentada a teoria matemática - leia se (e somente se) você está interessado:
Dada qualquer função
f: Z -> Z
de tal forma quef(f(n)) = -n
para todosn
emZ
, vemos imediatamente quef(f(f(f(n)))) = n
, ou em outras palavras,f^4
é a função identidade. Em particular,f
é invertível e sua função inversa éf^3
. Assim,f
é uma permutação deZ
, e uma vez quef^4 = Id
, segue-se que cada órbita (ou ciclo), daf
tem tamanho quer1
,2
, ou4
.A seguir, vemos isso
f(0) = 0
. Prova:,f(0) = f(-0) = f(f(f(0))) = -f(0)
entãof(0) = 0
, conforme desejado. Por outro lado, suponha quex
esteja em um ciclo de duração1
ou2
maisf(f(x)) = x
. Então-x = x
simx = 0
.Assim,
f
é composto inteiramente de 4 ciclos, exceto pelo ponto fixo (1 ciclo) em0
.Além disso, todo ciclo de quatro deve ter a forma
(x, y, -x, -y)
e, girando o ciclo ao redor, podemos assumir issox
ey
somos ambos positivos. Por outro lado, todo produto de 4 ciclos particionando números inteiros diferentes de zero determina uma escolha def
.Assim, cada escolha de
f
corresponde exclusivamente a um gráfico direcionado cujos vértices são números inteiros positivos, de modo que todo vértice é incidente em exatamente uma seta, entrando ou saindo. Mais precisamente, no gráfico não direcionado subjacente, todo vértice tem grau exatamente1
. (Cada 4 ciclos(x y -x -y)
comx
ey
positivo corresponde à setax --> y
.)A função desta resposta (e várias outras respostas aqui) corresponde ao gráfico onde
1 --> 2
,3 --> 4
e, em geral2k-1 --> 2k
.Tais gráficos estão em bijeção com infinitas seqüências de pares ordenados
(a_n, p_n)
, onde cadaa_n
um é um número inteiro positivo e cada ump_n
é um0
ou1
: ou seja, dada uma sequência(a_1, p_1), (a_2, p_2), (a_3, p_3), ...
, primeiro emparelhamos1
com1 + a_1
e, em seguida, formamos a flecha1 --> 1 + a_1
ou a flecha1 + a_1 --> 1
dependendo de sep_1
é0
ou1
. Essencialmente, a seta é um<
sinal ou um>
sinal, dependendo da paridade dep_1
.Em seguida, pegue o menor número inteiro positivo não emparelhado
k
e contek
, exatamentea_2
, das etapas, SALTANDO qualquer número que já esteja emparelhado com algo. Emparelhek
com o resultado e defina a direção da seta, conformep_2
acima. Repita com(a_3, p_3)
, etc.Cada flecha será determinada dessa maneira, para que o processo seja bem definido. A função nesta resposta corresponde à sequência
(1,0), (1,0), (1,0), ...
, uma vez que na etapan
o menor inteiro não emparelhado é2n-1
e nenhum número inteiro maior que o2n-1
emparelhado com alguma coisa, então obtemos2n-1 --> 2n
para cada umn
(as setas são orientadas dessa maneira porque cada ump_n
é igual0
).A cardinalidade desse conjunto é
(N*2)^N = N^N
que, no último parágrafo desta resposta2^N
, é igual à cardinalidade dos números reais.fonte
Para corrigir a resposta J anterior (não tenho reputação suficiente para comentar no original):
Apenas substitui o
_1&^
por1-~2*2|]
, que dá o sinal oposto. Então mudei o-
para a+
(o que importa apenas na entrada de1
e_1
).Aqui estão os testes:
Como você pode ver, o domínio e o intervalo são todos de números reais, mas funciona apenas para números inteiros (incluindo 0).
Explicação:
fonte
GolfScript
ceiling(26*.9)=24
O Golfscript manipula apenas números inteiros; portanto, aplique o
Z
bônus para um total de 24 pontos:O caso especial de 0 representa 8 caracteres. Ignorando 0, podemos obter uma resposta de 17 pontos:
Este código faz o seguinte em um número inteiro
x
no topo da pilha:x
for 0, deixe0
na pilha e não aplique mais regras.x
for par, neguex
.x
for positivo, adicione1
.x
for negativo, subtraia1
.Isso conecta logicamente conjuntos de 4 números em um ciclo, onde
f
percorre elementos do ciclo e os cantos opostos do ciclo são negativos um do outro. Todo número inteiro faz parte de exatamente 1 desses ciclos, exceto 0, que é especial. Por exemplo, para{-8, -7, 7, 8}
:7 f -> 8
8 f -> -7
-7 f -> -8
-8 f -> 7
Os únicos casos de teste relevantes em que pude pensar foram um ímpar negativo, par negativo, ímpar positivo, par positivo
0
e, em seguida, entrei-1
e1
já que a proximidade deles0
pode ter causado problemas:Tenho certeza de que o GolfScript real pode ser melhorado um pouco. Não parece que deva ter 26 caracteres! Gostaria de ouvir algumas sugestões.
fonte
Java, apenas por diversão
Aqui está uma implementação que faz uma bijeção real entre ℤ e ℤ², que é uma função ímpar ao mesmo tempo (g (-x) == -g (x)). Ele trata o elemento ℤ² correspondente como um número complexo e o multiplica por "i" e depois volta a converter em ℤ.
(f (x)) = f (x) =
f (x) = g - (x) = - x
A função é executada em O (1).
PS Feliz Ano Novo!
fonte
Python 3-38
Semelhante à resposta de @ moose, mas
f(n) == n
,. Funciona para todos os valores inteiros.fonte
Perl, 33 (sem espaço em branco)
Editar:
$=.".1"
encurtado para"$=.1"
(obrigado ardnew).Matemática:
Ungolfed:
Exemplos:
fonte
sub f{yzxzzc?-$_:x.$_}
sub f{yzxzzc?-$_:x.$_}
é não estado livre, ele usa um estado através da variável$_
. Por essef
motivo , não é mais uma função (no sentido matemático), porque valores diferentes são possíveis para o mesmo valor de entrada, dependendo do estado (o clima$_
contémx
ou não). Meu algoritmo não usa um estado. As informações são codificadas no valor de saída. Os números inteiros são convertidos em números reais adicionando.1
. E os números reais são convertidos novamente em números inteiros com o sinal alternado.$=
?f
seria definidoQ->Q
) com essex
caractere. também$=.".1"
pode ser reduzido para"$=.1"
$=
é apenas que leva apenas números inteiros. O mesmo pode ser conseguido usando uma variável comum:$a=int$_[0]
. Mas isso custa três bytes adicionais por causa da funçãoint
.Julia, 26
Não é super competitivo, mas muito juliano, uma vez que depende de vários envios. Apenas cria um Rational se for um Int, ou um int com um sinal de menos se for qualquer outra coisa. Alguém pode objetar que se trata de 2 funções, mas Julia considera que se trata de uma função com dois métodos, e é equivalente a definir uma função com uma declaração if no tipo de
n
.fonte
3==3//1
retorna,true
masf(3//1)==f(3)
retornafalse
.Doces ,
2018 bytesUsa o truque 3 -> 4 -> -3 -> -4 -> 3.
Para invocá-lo, use a opção -i no intérprete
Exemplo de invocação dupla:
Forma longa:
fonte
Dyalog APL, 9 pontos
A fonte tem 9 bytes e se qualifica para o bônus (o que não ajuda em nada). Ele também usa a fórmula da resposta SO principal.
fonte
Python: 32 bytes (29 pontos)
f: Z -> Z
Usando o método de Ben Reich.
fonte
(n>0)-(n<0)
porcmp(n,0)
, para salvar alguns bytes. (Mas não em Python 3: docs.python.org/3/whatsnew/3.0.html#ordering-comparisons )GTB , 22
fonte
Java, 113 bytes
A abordagem é bastante simples. Acabou com mais bytes do que eu imaginava, mas talvez possa ser um pouco mais complicado.
Ele basicamente cria 4 "áreas" diferentes de x, utilizando o fato de que Java permite que as variáveis sejam contornadas. Eu tive que fazer uma conversão complicada para números negativos, que é a principal razão pela qual isso acabou sendo maior do que o esperado.
Funciona para todos os x além de -2147483648.
fonte
Mesma sequência de números (3, 4, -3, -4, 3 ...) que a resposta golfscript, mas implementada em perl (42 caracteres após o espaço em branco ser removido)
Mais legível:
Ou ainda mais legível:
Resultado:
fonte
Sed, 25 bytes.
Uso:
fonte
Matlab, 26 caracteres
fonte
C ++ -
6355,8É assim que o código se parece:
Ele não funciona em números inteiros cujo quarto byte é igual a 0xB, pois usa esse valor para acompanhar as passagens. Caso contrário, funciona em qualquer membro de Z, incluindo zero.
fonte
f
com uma variável estática. mas então qual é o sentido dasqrt
?sqrt
, pois é arredondado de qualquer maneira com a conversão de tipo. Vou refatorá-lo para que ele funcione sem a variável estática.55.8
código, mas seu código atual tem 62 bytes. Edit: Não importa, eu não li a pergunta corretamente.Atualizado com a função fornecida pela Synthetica (obviamente quem deve obter crédito por isso agora)
Idioma: Python
Número de caracteres: 41 incluindo espaço em branco
fonte
f=lambda x:-float(x) if str(x)==x else`x`
é um pouco mais curto: 41 incluindo espaço em brancof
retorna uma string; a especificação diz que deve retornar um número racional.Prolog, 36 bytes
Código:
Explicado:
Exemplo:
fonte
Javascript ES6,
2726 bytesfonte
Mouse-2002 ,
211912 bytesDefine uma função
A
; chame-o como#A,#A,?;;
(que esperará o usuário digitar qualquer número). Como alternativa, chame-o como#A,#A,n;;
onden
está qualquer número.fonte
Julia, 21
Então
p // q é a notação literal de julia de números racionais.
fonte