Citando esta pergunta no SO (alerta de spoiler!):
Esta pergunta foi feita em uma entrevista da Oracle.
Como você dividiria um número por 3 sem usar os operadores *, /, +, -,%?
O número pode ser assinado ou não assinado.
A tarefa é solucionável, mas veja se você pode escrever o código mais curto.
Regras:
- Execute a divisão inteira necessária (
/3
) - Não use os operadores não baseados em texto
*
,/
,+
,-
, ou%
(ou seus equivalentes, como__div__
ouadd()
). Isso também se aplica a operadores de incremento e decremento, comoi++
oui--
. O uso de operadores para concatenação e formatação de string está OK. Usar esses caracteres para diferentes operadores, como-
operador unário para números negativos, ou*
para representar um ponteiro em C também é bom. - O valor de entrada pode ser arbitrariamente grande (seja qual for o seu sistema), tanto positivo quanto negativo
- A entrada pode ser em STDIN ou ARGV ou inserida de qualquer outra maneira
- Crie o código mais curto possível para fazer o acima
Respostas:
J,
45 4410 caracteres".,&'r3'":
Trabalha com negativos:
":
- formatar como texto,&'r3'
- anexarr3
ao final".
- execute a string, por exemplo15r3
fonte
3 3 3 #: 9
. Parece que você precisa saber quanto tempo seu número ternário será._3]\i.
também é um possível ponto de partida para algo, mas não sei se seria mais curto do que sua solução aqui. O problema com#_3]\i.
o que está é que ele sempre arredonda para cima em vez de para baixo.##~3=_3#\i.
para 11 caracteres?##~0 0 1$~
.3#.}:(#:~$&3)
mas ainda é mais longo e não resolve o problema de número negativo.^:
ou Agenda@.
para umaif
ouif...else
substituição. Nesse caso, você poderá usar@.
dois verbos conectados a um caractere `` '' (um gerúndio no J-speak) para selecionar um ou outro com base em uma condição.C, 167503724710
Aqui está a minha solução para o problema. Eu admito que é improvável que ganhe uma competição estrita de golfe com código, mas não usa truques para chamar indiretamente a funcionalidade de divisão interna, ela é escrita em C portátil (como a pergunta original do Stack Overflow solicitada), funciona perfeitamente para números negativos e o código é excepcionalmente claro e explícito.
Meu programa é a saída do seguinte script:
Contagem de caracteres: 71 + 39 * 2 ** 32 + 95 = 167503724710
Benchmarks
Foi perguntado quanto tempo isso levaria e quanta memória seria usada, então aqui estão alguns parâmetros de referência:
./test.py | pv --buffer-size=1M --average-rate > /dev/null
por cerca de 30 segundos fornece uma taxa de cerca de 14,8 MB / s. A taxa de saída pode ser razoavelmente considerada constante, portanto o tempo de execução deve ser de 167503724710 B / (14,8 * 1048576 B / s) ≈ 10794 s../test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null
, mas parecetcc
que não gera nada até ler todo o arquivo de origem.fonte
a[b]
é um açúcar sintático para*(a + b)
, que faz a adição.Ruby 28
Para dividir por 3, basta remover o zero à direita no número base 3:
120 -> 11110 -> 1111 -> 40
Trabalha com negativos:
Ruby,
6045Como alternativa, sem a conversão base:
d = -> n {x = n.abs; r = (0..1,0 / 0) .step (3) .take (x). índice x; n> 0? r: -r}fonte
/
operador banido seFloat::INFINITY
tornasse1.0/0
. Com Ruby 2.1, um golf de maio(0..1.0/0).step(3)
em0.step(p,3)
, removendo o/
. O problema maior é que-r
os usos-
para negar. Custa 5 caracteres para mudar-r
para~r.pred
, abusando Integer # pred para subtrair 1 sem o operador de subtração.Mathematica, 13 caracteres
fonte
&
e usar uma variável simples (outras pessoas também fazem isso).JavaScript, 56
Faz uma sequência de
n
repetições se,
substitui,,,
por1
. Em seguida, mede o comprimento resultante da string. (Espero que unário-
seja permitido!)fonte
-
operador de negação.-~
com #parseInt()
-~prompt()
é maior queparseInt(prompt())
. Não tenho certeza de como você lidaria com isso.alert(Array(parseInt(prompt())).slice(1).join().replace(/,,,/g,1).length)
Python,
4138xrange
parece ser capaz de lidar com grandes números (acho que o limite é o mesmo que por muito tempo em C) quase instantaneamente.fonte
10/3
é igual a 3, não 4.print" -"[x<0]+
len (range (2, abs (x), 3)) `` reduzirá para 39 caractereslen()
como abreviação pararepr()
range
, porque na verdade criará a lista.xrange
apenas finge que é capaz de lidar com grandes números sem perder tempo / memória.Haskell, 90
106Cria uma lista de pesquisa infinita (lenta)
[(0,0),(0,0),(-1,0),(1,0),(-2,0),(2,0),(-3,-1),(3,1), ...]
, apara todos os elementos que não correspondemn
(/=
há desigualdade em Haskell) e retorna o primeiro que corresponde.Isso fica muito mais simples se não houver números negativos:
25
27simplesmente retorna o
n
th elemento da lista[0,0,0,1,1,1,2, ...]
.fonte
C #, 232 bytes
Meu primeiro código de golfe ... E como não havia nenhum C # e eu queria tentar um método diferente não tentado aqui, pensei em tentar. Como alguns outros aqui, apenas números não negativos.
Ungolfed
fonte
string[] g
, transformando-astring[]g
.Add
?Perl (
2622)Esta versão (ab) usa o mecanismo de expressão regular do Perl. Ele lê um número como o último argumento da linha de comando (
pop
) e cria uma sequência de3
s deste comprimento ("3" x $number
). O operador de substituição de expressão regular (s///
aqui escrito com delimitadores diferentes por causa das regras do quebra-cabeça e com umag
bandeira global) substitui três caracteres pela string vazia e retorna o número de substituições, que é o número de entrada inteiro dividido por três. Poderia até ser escrito sem3
, mas a versão acima parece mais engraçada.fonte
$_=3x pop;say s|333||g
.'$_=3x pop;say s|333||g||0
. Lenta com números grandes como 99999999 e não funciona com números negativos.-p
na linha de comando e você pode:$_=3x$_;$_=0|s|...||g
para um total de 22, incluindo a cobertura das entradas 0, 1 ou 2.C, 160 caracteres
Solução de divisão longa caractere a caractere usando tabelas de pesquisa, ou seja, sem a seqüência atoi () ou printf () para converter entre as seqüências base 10 e os inteiros.
Às vezes, a saída inclui um zero inicial - parte de seu charme.
Nota:
Testando:
fonte
Python 42
Como todas as soluções postadas aqui que eu verifiquei truncam casas decimais aqui é a minha solução que faz isso.
Python
5051Como o python faz a divisão de pisos, eis a minha solução que implementa isso.
O número inteiro de entrada está na variável x.
Testado em Python 2.7, mas suspeito que funcione em 3 também.
fonte
-3
é a resposta correta-10/3
.JavaScript, 55
Se alguém não pode usar
-1
, então aqui está uma versão substituindo-a por~0
(obrigado Peter Taylor!).fonte
~
é um operador Bitwise que inverte os bits do operando (primeiro converte-o em um número). Esta é a maneira mais curta de converter uma string em um número (tanto quanto eu sei).~~
converte em um número inteiro, por oposição a+
.Caracteres C 83
O número a ser dividido é passado através de stdin e o retorna como o código de saída de
main()
(% ERRORLEVEL% no CMD). Esse código abusa de algumas versões do MinGW, pois quando as otimizações não estão ativadas, ele trata o último valor da atribuição como uma declaração de retorno. Provavelmente pode ser um pouco reduzido. Suporta todos os números que podem caber em umint
Se o negativo unário (-) não for permitido: (129)
Se for negado unário, é permitido: (123)
EDIT: ugoren apontou para mim que - ~ é um incremento ...
83 caracteres se a negação unária for permitida: D
fonte
x+3
é-~-~-~x
.C, 139 caracteres
Executar com número como argumento da linha de comando
Testando:
Editar% s:
fonte
A
, minha função apenas verifica o bit i no número n. O padrão C permite omitir declarações de tipo ou isso é algo do compilador?ZSH -
3120/21Para números negativos:
Com números negativos (ZSH +
bc
) -6261Eu provavelmente não deveria dar dois programas como minha resposta, então aqui está um que funciona para qualquer sinal de número:
Isso usa o mesmo truque de conversão de base da resposta de Artem Ice .
fonte
C,
8173 caracteresSuporta apenas números não negativos.
A idéia é usar o ponteiro aritêmico. O número é lido no ponteiro
x
, que não aponta para lugar nenhum.&x[~2]
=&x[-3]
=x-3
é usado para subtrair 3. Isso é repetido desde que o número esteja acima de 2.i
conta o número de vezes que isso é feito (&i[1]
=i+1
).fonte
Java
8679Suponha que o número inteiro esteja em y:
Converte em uma string na base 3, remove o último caractere (shift à direita ">>" na base 3) e depois converte novamente em número inteiro.
Funciona para números negativos.
Se o número, y, é <3 ou> -3, fornece 0.
Primeira postagem no código de golfe. =) Portanto, não posso comentar ainda.
Obrigado Kevin Cruijssen pelas dicas.
fonte
&&
para&
e 2xInteger
paraLong
. (Além disso, por que você usa~2
em vez de apenas-3
Eles são o mesmo byte-count?.)-
, mas não sei se isso conta com negação unária.Python2.6 (
29) (71) (57) (52) (43)Editar - Acabamos de perceber que também precisamos lidar com números inteiros negativos. Consertará isso mais tarde
Edit2 - Fixed
Edit3 - Salvo 5 caracteres seguindo o conselho de Joel Cornett
Edit4 - Como a entrada não precisa ser necessariamente de STDIN ou ARGV, salvou 9 caracteres por não receber nenhuma entrada de stdin
fonte
abs()
print z if x==abs(x) else -z
print (z,-z)[x<0]
Javascript,
4729Usa
eval
para gerar dinamicamente a/
. Usa+
apenas para concatenação de cadeias, não adição.EDIT: Usado em
"\57"
vez deString.fromCharCode(47)
fonte
alert(eval(prompt()+"\573"))
?Rubi (
432217)Não apenas golfe, mas também elegância :)
A saída será como
(41/1)
. Se ele deve ser inteiro, devemos adicionar.to_i
ao resultado e, se mudarmosto_i
parato_f
, também podemos obter saída para floats.fonte
rational
linha de solicitação no Ruby 1.9.3. Omitir os parênteses economiza mais um caractere .TI-Basic, 8 bytes
Vencedora? :)
PS Arredonda para o infinito para números negativos (veja aqui o porquê). Para arredondar para zero, substitua
int(
poriPart(
para não alterar os bytes.Casos de teste
fonte
Python 2.x,
545351print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
Onde
_
está o dividendo e é inserido como tal.Nota: Não tenho certeza se o uso do intérprete interativo é permitido, mas de acordo com o OP: "A entrada pode estar em STDIN ou ARGV ou inserida de qualquer outra maneira"
Edit: Agora para python 3 (funciona em 2.x, mas imprime uma tupla). Trabalha com negativos.
fonte
__len__
é suficiente.len(range(100,1000))
dá900
no 3.2.3 no linux.len(xrange(0,_,3))
é mais curto e massivamente mais rápido de qualquer maneira.C ++, 191
Com main e includes, seu 246, sem main e includes, é apenas 178. As novas linhas contam como 1 caractere. Trata todos os números como não assinados. Não recebo avisos por ter um retorno principal int sem sinal, portanto é um jogo justo.
Minha primeira submissão de codegolf.
usa turnos para dividir o número por 4 repetidamente e calcula a soma (que converge para 1/3)
Pseudo-código:
Como um aparte, eu poderia eliminar o método principal nomeando d main e fazendo com que fosse necessário um caractere ** e usando o valor de retorno dos programas como saída. Ele retornará o número de argumentos da linha de comando dividido por três, arredondado para baixo. Isso leva seu comprimento aos 191 anunciados:
fonte
Golfscript - 13 caracteres
fonte
s/seem to //
:( eu vou ter que ter um pensar sobre isso.PowerShell 57 ou 46
Em 57 caracteres, usando
%
como o operador foreach do PowerShell, não o módulo. Esta solução pode aceitar números inteiros positivos ou negativos.Em 46 caracteres, se
*
for permitido como operador de repetição de cadeia, não multiplique. Esta opção requer números inteiros positivos como valores de entrada.fonte
R
Eles funcionam apenas com números inteiros positivos:
Ou:
Ou:
Ou:
[[EDIT]] E um feio:
[[EDIT2]] Além disso, provavelmente o melhor - inspirado no código do matlab acima, de Elliot G:
fonte
wrong sign in 'by' argument
SmileBASIC,
585136 bytes (sem funções matemáticas!)Explicação:
O programa move a camada de fundo suavemente por 3 quadros e, em seguida, obtém o ângulo após 1 quadro, quando percorre 1/3 da sua distância total.
Versão de divisão flutuante, 38 bytes:
Explicação:
fonte
Haskell
4139 charsFunciona com o conjunto completo de números inteiros positivos e negativos
Primeiro, cria uma lista 1 ou (-1) '(dependendo do sinal da entrada) para cada terceiro número inteiro, de 0 até a entrada
n
.abs(n)
para números negativos, inclusive.por exemplo
n=8 -> [0,3,6]
Em seguida, ele retorna a soma desta lista.
fonte
Clojure, 87; trabalha com negativos; com base em lazyseqs
Ungolfed:
fonte
Caderno prudente (21)
fonte