Divida um número por 3 sem usar os operadores *, /, +, -,%

48

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__ou add()). Isso também se aplica a operadores de incremento e decremento, como i++ou i--. 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
Gaffi
fonte
11
Como o resultado deve ser arredondado quando positivo? Como quando negativo?
dfeuer 22/06

Respostas:

15

J, 45 44 10 caracteres

".,&'r3'":

Trabalha com negativos:

".,&'r3'": 15
5
   ".,&'r3'": _9
_3
   ".,&'r3'": 3e99
1e99

": - formatar como texto

,&'r3'- anexar r3ao final

". - execute a string, por exemplo 15r3

defhlt
fonte
11
Funciona se você fizer 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.
Gareth
11
Talvez ##~3=_3#\i.para 11 caracteres?
Gareth
11
Na verdade, você pode reduzir o seu para 10 caracteres ##~0 0 1$~.
Gareth
11
Você pode reduzir isso usando um gancho, 3#.}:(#:~$&3)mas ainda é mais longo e não resolve o problema de número negativo.
Gareth
11
Sim, você pode usar a função Power ^: ou Agenda @. para uma ifou if...elsesubstituiçã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.
Gareth
56

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:

#!/usr/bin/env python3
import sys

# 71
sys.stdout.write('''#include <stdint.h>
#include <stdio.h>
int32_t div_by_3(int32_t input){''')

# 39 * 2**32
for i in range(-2**31, 2**31):
    # 18 + 11 + 10 = 39
    sys.stdout.write('if(input==%11d)return%10d;' % (i, i / 3))

# 95
sys.stdout.write(r'''return 7;}int main(int c,char**v){int32_t n=atoi(a[1]);printf("%d / 3 = %d\n",n, div_by_3(n));}''')

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:

  • Tempo de execução do script - A execução ./test.py | pv --buffer-size=1M --average-rate > /dev/nullpor 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.
  • Tempo de compilação - O compilador TCC pretende compilar o código C a 29,6 MB / s , o que resulta em um tempo de compilação de 167503724710 B / (29,6 * 1048576 B / s) ≈ 5397 s. (É claro que isso pode ser executado em um pipeline com o script.)
  • Tamanho do código compilado - tentei estimar usando ./test.py | tcc -c - -o /dev/stdout | pv --buffer-size=1M --average-rate > /dev/null, mas parece tccque não gera nada até ler todo o arquivo de origem.
  • Uso da memória a ser executada - Como o algoritmo é linear (e o tcc não otimiza através das linhas), a sobrecarga da memória deve ser de apenas alguns kilobytes (além do próprio código, é claro).
Caracol mecânico
fonte
22
Este é o epítome da codificação. ++++++++++
Joe Z.
4
Dito isto, tenho certeza que se você fornecesse um arquivo de origem de 160 GB e pedisse para compilar e testá-lo, eles olhariam para você como se você fosse louco.
Joe Z.
16
Se meu chefe me pedisse para calcular uma divisão por três sem - + / *%, eu pensaria que ele é louco.
Mikaël Mayer
E, no entanto, a[b]é um açúcar sintático para *(a + b), que faz a adição.
precisa saber é o seguinte
12
@NicolasBarbulesco Há uma restrição de tamanho nas respostas do Stack Exchange.
Timtech
38

Ruby 28

b=->n{n.to_s(3).chop.to_i 3}

Para dividir por 3, basta remover o zero à direita no número base 3: 120 -> 11110 -> 1111 -> 40

Trabalha com negativos:

ice distantstar:~/virt/golf [349:1]% ruby ./div3.rb
666
222
ice distantstar:~/virt/golf [349]% ruby ./div3.rb
-15        
-5

Ruby, 60 45

Como 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}

d=->n{(r=1.step(n.abs,3).to_a.size);n>0?r:-r}
defhlt
fonte
11
A alternativa sem conversão de base fez com que o /operador banido se Float::INFINITYtornasse 1.0/0. Com Ruby 2.1, um golf de maio (0..1.0/0).step(3)em 0.step(p,3), removendo o /. O problema maior é que -ros usos -para negar. Custa 5 caracteres para mudar -rpara ~r.pred, abusando Integer # pred para subtrair 1 sem o operador de subtração.
kernigh
26

Mathematica, 13 caracteres

Mean@{#,0,0}&
alefalpha
fonte
Isso é ruim: acho que você pode salvar &e usar uma variável simples (outras pessoas também fazem isso).
precisa saber é o seguinte
3
@YvesKlett: A média é inerentemente má.
GuitarPicker #
18

JavaScript, 56

alert(Array(-~prompt()).join().replace(/,,,/g,1).length)

Faz uma sequência de nrepetições se ,substitui ,,,por 1. Em seguida, mede o comprimento resultante da string. (Espero que unário -seja permitido!)

Casey Chu
fonte
+1 mas não funciona com valores negativos
Francesco Casula
Pergunta ... como isso conta? Ele usa o -operador de negação.
Patrick Roberts
@ Patrick Eu levei a especificação para significar nenhuma subtração - se você quiser, você pode substituir -~com #parseInt()
Casey Chu
@CaseyChu o valor retornado por -~prompt()é maior que parseInt(prompt()). Não tenho certeza de como você lidaria com isso.
Patrick Roberts
alert(Array(parseInt(prompt())).slice(1).join().replace(/,,,/g,1).length)
Casey Chu
16

Python, 41 38

print"-"[x:]+`len(xrange(2,abs(x),3))`

xrange parece ser capaz de lidar com grandes números (acho que o limite é o mesmo que por muito tempo em C) quase instantaneamente.

>>> x = -72
-24

>>> x = 9223372036854775806
3074457345618258602
grc
fonte
2
10/3é igual a 3, não 4.
Joel Cornett
Como fazer print" -"[x<0]+len (range (2, abs (x), 3)) `` reduzirá para 39 caracteres
Joel Cornett
A formatação dos comentários do golfexchange está atrapalhando. sobre o acima eu usei backticks para incluir len()como abreviação pararepr()
Joel Cornett
Eu atualizei. Não posso usar range, porque na verdade criará a lista. xrangeapenas finge que é capaz de lidar com grandes números sem perder tempo / memória.
grc
2
Finja que é Python 3;) Eu gosto do único char slicing btw.
Joel Cornett
11

Haskell, 90 106

d n=snd.head.dropWhile((/=n).fst)$zip([0..]>>=ν)([0..]>>=replicate 3>>=ν);ν q=[negate q,q]

Cria 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 correspondem n( /=há desigualdade em Haskell) e retorna o primeiro que corresponde.

Isso fica muito mais simples se não houver números negativos:

25 27

(([0..]>>=replicate 3)!!)

simplesmente retorna o nth elemento da lista [0,0,0,1,1,1,2, ...].

deixou de girar contra-relógio
fonte
3
Eu nunca pensei nessa segunda solução. Eu poderia ser capaz de implementar algo parecido em python
acólito
8

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.

class l:System.Collections.Generic.List<int>{}class p{static void Main(string[] g){int n=int.Parse(g[0]);l b,a=new l();b=new l();while(a.Count<n)a.Add(1);while(a.Count>2){a.RemoveRange(0,3);b.Add(1);}System.Console.Write(b.Count);}}

Ungolfed

class l : System.Collections.Generic.List<int>
{ }
class p
{
    static void Main(string[] g)
    {
        int n = int.Parse(g[0]);
        l b, a = new l();
        b = new l();
        while (a.Count < n) a.Add(1);
        while (a.Count > 2)
        {
            a.RemoveRange(0, 3);
            b.Add(1);
        }
        System.Console.Write(b.Count);
    }
}
Drake Clarris
fonte
2
Cerca de 5 anos mais tarde .. Você pode salvar 1 byte, removendo o espaço de string[] g, transformando-astring[]g
Metoniem
Citação "Não use operadores não baseados em texto *, /, +, - ou% (ou seus equivalentes, como div ou add ()" - você não está usando um equivalente - .Add?
Jonathan Frech
@JonathanFrech Esse método add não funciona em dois números, apenas agrega um valor a uma coleção
Modalidade de Ignorância
7

Perl (26 22)

$_=3x pop;say s|333||g

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 de 3s 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 uma gbandeira 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 sem 3, mas a versão acima parece mais engraçada.

$ perl -E '$_=3x pop;say s|333||g' 42
14
memowe
fonte
2
Hey @memowe, bom trabalho! Você pode salvar mais alguns caracteres (4) fazendo isso $_=3x pop;say s|333||g.
Dom Hastings
2
Quando a entrada é 0, 1 ou 2, ela imprime uma sequência vazia. Se precisa de imprimir 0, então ele precisa de mais de 3 caracteres (total de 25): '$_=3x pop;say s|333||g||0. Lenta com números grandes como 99999999 e não funciona com números negativos.
Kernigh 25/05
11
Use -pna linha de comando e você pode: $_=3x$_;$_=0|s|...||gpara um total de 22, incluindo a cobertura das entradas 0, 1 ou 2.
Xcali
6

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.

main(int n,char**a){
char*s=a[1],*x=0;
if(*s==45)s=&s[1];
for(;*s;s=&s[1])n=&x[*s&15],x="036"[(int)x],*s=&x["000111222333"[n]&3],x="012012012012"[n]&3;
puts(a[1]);
}

Nota:

  • abusa do acesso à matriz para implementar a adição.
  • compila com o clang 4.0, outros compiladores podem vomitar.

Testando:

./a.out -6            -2
./a.out -5            -1
./a.out -4            -1
./a.out -3            -1
./a.out -2            -0
./a.out -1            -0
./a.out 0             0
./a.out 1             0
./a.out 2             0
./a.out 3             1
./a.out 4             1
./a.out 5             1
./a.out 6             2
./a.out 42            14
./a.out 2011          0670
coelho bebê
fonte
6

Python 42

int(' -'[x<0]+str(len(range(2,abs(x),3))))

Como todas as soluções postadas aqui que eu verifiquei truncam casas decimais aqui é a minha solução que faz isso.

Python 50 51

int(' -'[x<0]+str(len(range([2,0][x<0],abs(x),3))))

Como 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.

Matt
fonte
+1 por oferecer as duas alternativas à situação de valor negativo. Como já existem muitas respostas, não ajustarei as especificações para excluir uma ou outra opção, embora eu pessoalmente concorde que essa -3é a resposta correta -10/3.
Gaffi
Para aqueles que se preocupam com a divisão de pisos em python: python-history.blogspot.com/2010/08/…
Matt
o que há com a multiplicação e subtração em sua segunda solução?
usar o seguinte comando
@ boothby A segunda solução implementa a divisão de pisos. Eu queria fazer intervalo (0, abs (x), 3) para números negativos e intervalo (2, abs (x), 3) para números positivos. Para fazer isso, eu tinha alcance (2 ... então subtraí 2 quando x é negativo. X <0 é verdadeiro quando x é negativo, (verdadeiro) * 2 == 2
Matt
Não estou entendendo a diferença entre divisão do piso e decimais truncados. Isso tem a ver com divisão negativa?
Joel Cornett
6

JavaScript, 55

alert(parseInt((~~prompt()).toString(3).slice(0,-1),3))

Se alguém não pode usar -1, então aqui está uma versão substituindo-a por ~0(obrigado Peter Taylor!).

alert(parseInt((~~prompt()).toString(3).slice(0,~0),3))
Inkbug
fonte
11
@ArtemIce One ~é 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).
Inkbug
11
Eu sinto que o uso de análise / conversão de strings é trapaça, pois é a) um processo muito complicado e caro comparado às operações bit a bit, b) usa os operadores proibidos internamente ec) ocuparia mais caracteres do que uma solução homerolled. Assim como as pessoas ficam mal-humoradas quando você usa o tipo incorporado quando solicitado a implementar uma classificação rápida.
Wug
11
@ Sam Também ~~converte em um número inteiro, por oposição a +.
Inkbug
11
@ Wug É codegolf, portanto, não se trata de eficiência, a menos que especificado na tarefa.
defhlt
3
+1 para tirar proveito de diferentes bases. É uma das minhas técnicas favoritas de golfe em JavaScript.
DocMax
6

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)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:I(~a);for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?I(~c):c;}

Se for negado unário, é permitido: (123)

I(unsigned a){a=a&1?I(a>>1)<<1:a|1;}main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=I(I(I(a))))c=I(c);b=b<0?-c:c;}

EDIT: ugoren apontou para mim que - ~ é um incremento ...

83 caracteres se a negação unária for permitida: D

main(a,b,c){scanf("%i",&b);a=b;a=a<0?a:-a;for(c=0;a<~1;a=-~-~-~a)c=-~c;b=b<0?-c:c;}
Kaslai
fonte
Se negar unário é permitido, x+3é -~-~-~x.
Ugoren
Obrigado por isso. Não sei por que isso nunca me ocorreu. Eu acho que não sabia que você poderia empilhar unários tão gratuitamente hehe.
Kaslai
5

C, 139 caracteres

t;A(a,b){return a?A((a&b)<<1,a^b):b;}main(int n,char**a){n=atoi(a[1]);for(n=A(n,n<0?2:1);n&~3;t=A(n>>2,t),n=A(n>>2,n&3));printf("%d\n",t);}

Executar com número como argumento da linha de comando

  • Lida com números negativos e positivos

Testando:

 ./a.out -6            -2
 ./a.out -5            -1
 ./a.out -4            -1
 ./a.out -3            -1
 ./a.out -2            0
 ./a.out -1            0
 ./a.out 0             0
 ./a.out 1             0
 ./a.out 2             0
 ./a.out 3             1
 ./a.out 4             1
 ./a.out 5             1
 ./a.out 6             2
 ./a.out 42            14
 ./a.out 2011          670

Editar% s:

  • salvou 10 caracteres ao embaralhar a adição (A) para remover variáveis ​​locais.
coelho bebê
fonte
11
Bem feito. Eu tentei o meu melhor em um pouco de brincadeira e cheguei a 239. Eu simplesmente não consigo entender minha 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?
shiona 1/08/12
11
C assumirá int se não for especificado.
Wug
5

ZSH - 31 20/21

echo {2..x..3}|wc -w

Para números negativos:

echo {-2..x..3}|wc -w

Com números negativos (ZSH + bc) -62 61

Eu provavelmente não deveria dar dois programas como minha resposta, então aqui está um que funciona para qualquer sinal de número:

echo 'obase=10;ibase=3;'`echo 'obase=3;x'|bc|sed 's/.$//'`|bc

Isso usa o mesmo truque de conversão de base da resposta de Artem Ice .

Jon Gauthier
fonte
5

C, 81 73 caracteres

Suporta apenas números não negativos.

char*x,*i;
main(){
    for(scanf("%d",&x);x>2;x=&x[~2])i=&i[1];
    printf("%d",i);
}

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. iconta o número de vezes que isso é feito ( &i[1]= i+1).

Ugoren
fonte
Tentando entender o código, alguém lançou alguma luz? Obrigado
Cong Hui
@Chui, explicação adicionada.
ugoren
@ugoren, tanto quanto eu entendo, não deve printf ("% d") imprimir o ponteiro de endereço de memória que eu tenho em Hex? por que está imprimindo um número inteiro? ou char * foi inicializado para apontar para o endereço de memória 0 por padrão? Obrigado
Cong Hui
5

Java 86 79

Suponha 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.

System.out.print(~2<y&y<3?0:Long.valueOf(Long.toString(y,3).split(".$")[0],3));

Primeira postagem no código de golfe. =) Portanto, não posso comentar ainda.

Obrigado Kevin Cruijssen pelas dicas.

Vetorizado
fonte
Sei que já faz mais de dois anos, mas você pode jogar golfe em algumas partes: &&para &e 2x Integerpara Long. (Além disso, por que você usa ~2em vez de apenas -3Eles são o mesmo byte-count?.)
Kevin Cruijssen
11
@KevinCruijssen Tão nostálgico para editar meu primeiro post depois de tanto tempo. Não sabia ao certo por que pensei que ~ 2 era melhor naquela época.
Vetorizado
2
@KevinCruijssen bem, o desafio diz que você não pode usar -, mas não sei se isso conta com negação unária.
FlipTack
@FlipTack Ah, você está completamente certo. Nesse caso, esqueça que eu já disse isso. :)
Kevin Cruijssen
4

Python2.6 ( 29 ) ( 71 ) ( 57 ) ( 52 ) (43)

z=len(range(2,abs(x),3))
print (z,-z)[x<0]

print len(range(2,input(),3))

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

elssar
fonte
Vá em frente comabs()
defhlt
mais curto para fazerprint z if x==abs(x) else -z
Joel Cornett
ainda melhor,print (z,-z)[x<0]
Joel Cornett
@ArtemIce obrigado, só percebi que poderia usar isso depois de ler outra resposta acima.
elssar
@JoelCornett humm, não sabia que, graças
elssar
4

Javascript, 47 29

Usa evalpara gerar dinamicamente a /. Usa +apenas para concatenação de cadeias, não adição.

alert(eval(prompt()+"\57"+3))

EDIT: Usado em "\57"vez deString.fromCharCode(47)

Peter Olson
fonte
-1 para alert(eval(prompt()+"\573"))?
Shieru Asakoto 24/06
4

Rubi ( 43 22 17)

Não apenas golfe, mas também elegância :)

p Rational gets,3

A saída será como (41/1). Se ele deve ser inteiro, devemos adicionar .to_iao resultado e, se mudarmos to_ipara to_f, também podemos obter saída para floats.

Hauleth
fonte
11
Funciona sem a rationallinha de solicitação no Ruby 1.9.3. Omitir os parênteses economiza mais um caractere .
steenslag
4

TI-Basic, 8 bytes

Vencedora? :)

int(mean({Ans,0,0

PS Arredonda para o infinito para números negativos (veja aqui o porquê). Para arredondar para zero, substitua int(por iPart(para não alterar os bytes.

Casos de teste

-4:prgmDIVIDE
              -2
11:prgmDIVIDE
               3
109:prgmDIVIDE
              36
Timtech
fonte
3

Python 2.x, 54 53 51

print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))

Onde _ está o dividendo e é inserido como tal.

>>> x=-19
>>> print' -'[x<0],len(range(*(2,-2,x,x,3,-3)[x<0::2]))
- 6

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.

Joel Cornett
fonte
Funciona em python 3 também?
Caracol mecânico
Não precisa ser subscrito; ter __len__é suficiente.
Caracol mecânico
len(range(100,1000))900no 3.2.3 no linux.
Caracol mecânico
Isso não funciona para números negativos. E len(xrange(0,_,3))é mais curto e massivamente mais rápido de qualquer maneira.
grc 01/08/2012
@ Mecanicalsnail: ponto tomado. Eu concordo. Ele funciona no 3.
Joel Cornett
3

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.

#include<iostream>
#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U d(U i){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}U main(){U i;std::cin>>i,std::cout<<d(i);R 0;}

usa turnos para dividir o número por 4 repetidamente e calcula a soma (que converge para 1/3)

Pseudo-código:

// typedefs and #defines for brevity

function a(x, y):
    magically add x and y using recursion and bitwise things
    return x+y.

function d(x):
    if x = 3:
        return 1.
    variable total, remainder
    until x is zero:
        remainder = x mod 4
        x = x / 4
        total = total + x
    if total and remainder both zero:
        return 0.
    else:
        return a(total, d(remainder)).

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:

#define R return
typedef unsigned int U;U a(U x,U y){R y?a(x^y,(x|y^x^y)<<1):x;}U main(U i,char**q){if(i==3)R 1;U t=i&3,r=i>>=2;t=a(t,i&3);while(i>>=2)t=a(t,i&3),r=a(r,i);R r&&t?a(r,d(t)):0;}
Wug
fonte
3

Golfscript - 13 caracteres

~3base);3base
mordedor
fonte
parece não lidar com entradas negativas
res
11
@res s/seem to //:( eu vou ter que ter um pensar sobre isso.
gnibbler
3

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.

(-join(1..(Read-Host)|%{1})-replace111,0-replace1).Length

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.

("1"*(Read-Host)-replace111,0-replace1).Length
Joseph Alcorn
fonte
Se você voltar, postei uma correção de bug. Se você quiser que eu exclua a minha e incorpore a alteração à sua, informe-me.
Veskah 25/06
3

R

Eles funcionam apenas com números inteiros positivos:

max(sapply(split(1:x,1:3), length))
# Gives a warning that should be ignored

Ou:

min(table(rep(1:3, x)[1:x]))

Ou:

length((1:x)[seq(3,x,3)])

Ou:

sum(rep(1,x)[seq(3,x,3)])

[[EDIT]] E um feio:

trunc(sum(rep(0.3333333333, x)))

[[EDIT2]] Além disso, provavelmente o melhor - inspirado no código do matlab acima, de Elliot G:

length(seq(1,x,3))
lebatsnok
fonte
Eu queria implementar a mesma idéia em sua EDIT2 mas ele não funciona para números negativos:wrong sign in 'by' argument
Andreï Kostyrka
3

SmileBASIC, 58 51 36 bytes (sem funções matemáticas!)

INPUT N
BGANIM.,4,-3,N
WAIT?BGROT(0)

Explicação:

INPUT N           'get input
BGANIM 0,"R",-3,N 'smoothly rotate background layer 0 by N degrees over 3 frames
WAIT              'wait 1 frame
PRINT BGROT(0)    'display angle of layer 0

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:

INPUT N
BGANIM.,7,-3,N
WAIT?BGVAR(0,7)

Explicação:

INPUT N           'input
BGANIM 0,"V",-3,N 'smoothly change layer 0's internal variable to N over 3 frames
WAIT              'wait 1 frame
PRINT BGVAR(0,7)  'display layer 0's internal variable
12Me21
fonte
3

Haskell 41 39 chars

Funciona com o conjunto completo de números inteiros positivos e negativos

f n=sum[sum$1:[-2|n<0]|i<-[3,6..abs n]]

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.

Charl Kruger
fonte
Não funciona com números negativos (-3/3 é -1, não 1).
Cormac
Bom que você tenha trabalhado com números negativos, mas não pode usar /, leia a especificação.
Cormac
Oh Deus, você me pegou duas vezes. Tudo fixo;)
Charl Kruger 23/06
Agradável! Btw Você pode obter 39 caracteres com fn = soma [soma $ 1: [- 2 | n <0] | i <- [3,6..abs n]]
Cormac
2

Clojure, 87; trabalha com negativos; com base em lazyseqs

(defn d[n](def r(nth(apply interleave(repeat 3(range)))(Math/abs n)))(if(> n 0)r(- r)))

Ungolfed:

(defn d [n]
  (let [r (nth (->> (range) (repeat 3) (apply interleave))
               (Math/abs n))]
        (if (pos? n)
          r
          (- r))))
defhlt
fonte