Determine se um número inteiro é divisível por 3

20

Seu objetivo é determinar se um número é divisível por 3 sem usar condicionais. A entrada será um número de 8 bits não assinado de 0 a 255. Criatividade incentivada!

Você só tem permissão para usar

  • Igualdade / desigualdade ( ==, !=, >, <, >=, <=)

  • Aritmética ( +, -, x)

  • Operadores lógicos ( !não, &&e, || ou)

  • Bit a bit Operadores ( ~não, &e, |ou, ^xor, <<, >>, >>>mudanças certas aritmética e lógica esquerda e)

  • Constantes (seria melhor se você mantivesse essas pequenas)

  • Atribuição variável

Saída 0se falsa, 1se verdadeira.

Aplicam-se as regras atômicas de código-golfe padrão. Se você tiver alguma dúvida, deixe-a nos comentários. Métodos de exemplo aqui . Um token é uma das alternativas e variáveis ​​excluídas acima.

qwr
fonte
@GregHewgill Meu erro de digitação, deve ser um número de 8 bits.
QWR
2
Só podemos usar os operadores acima? Caso contrário, o módulo tornaria isso muito fácil.
Jwosty
Além disso, que tal a pesquisa de tabela?
Greg Hewgill
3
Você pode esclarecer o que você quer dizer com sem condicionais? É limitado a declarações IF, ou se aplica a coisas como loops também?
Ruslan
1
@Ruslan Você só pode usar o acima.
QWR

Respostas:

31

C - 2 fichas

int div3(int x) {
    return x * 0xAAAAAAAB <= x;
}

Parece funcionar até 2 31 -1.

Créditos zalgo("nhahtdh")para a ideia inversa multiplicativa.

aditsu
fonte
1
+1. Fiquei um pouco confuso com o modo como <=funciona e lembre-se de que 0xAAAAAAAB é considerado como sendo do unsigned inttipo, portanto, o resultado da multiplicação não é assinado.
N
Operadores de desigualdade de trauma @DigitalTrauma são permitidos, não são banidos
aditsu
@aditsu Oops! Às vezes preciso ler com mais cuidado! +1 ótima resposta!
Digital Trauma
@aditsu, desculpe, eu sou noob, como exatamente isso funciona?
Kartik_Koro
2
@Kartik_Koro 0xAAAAAAAB * 3 == 1 devido ao estouro, portanto, para qualquer int x, x * 0xAAAAAAAB * 3 == x. Além disso, y * 3 tem valores diferentes para y diferentes, portanto, y = x * 0xAAAAAAAB deve ser o único y tal que y * 3 == x. Se x é um múltiplo de 3, então y deve ser x / 3, caso contrário, ele deve estar passando pelo estouro. Uma maneira simples de verificar é comparar y com x. Veja também en.wikipedia.org/wiki/Modular_multiplicative_inverse
aditsu
17

Python, 3 2 tokens

Solução de força bruta, mas funciona.

0x9249249249249249249249249249249249249249249249249249249249249249>>x&1

Obrigado a Howard pela redução de 1 token.

Greg Hewgill
fonte
Uau! Sua solução é provavelmente a mais curta (três fichas), mas também quero incentivar outras respostas.
QWR
11
Há até mesmo uma solução de token 2: 0x9......>>x&1.
Howard
6

Fichas C - 5 4 (?)

int div3_m2(uint32_t n) {
    return n == 3 * (n * 0xAAAAAAABull >> 33);
}

Funciona para qualquer número de 32 bits não assinado .

Este código utiliza o módulo inverso multiplicativo 2 32 de um divisor para converter a operação de divisão em operação de multiplicação.

Editar

Minha solução (publicada 2 minutos depois) tem o mesmo espírito da solução da aditsu. O crédito a ele pelo uso ==disso melhora minha solução em 1 token.

Referência

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
fonte
1
Isto é incrível. Eu sabia sobre números mágicos do famoso truque inverso de quadratura, mas não sabia que poderia ser usado para um divisor arbitrário. Isto é Bull: P
qwr
Sim, 0xAAAAAAAB = (2 ^ 33 + 1) / 3 e 171 = (2 ^ 9 + 1) / 3. Eu escolhi a menor constante que faz o truque. Hmm, na verdade também parece funcionar com 86 = (2 ^ 8 + 2) / 3
aditsu
Ratos, mesmo 43 = (2 ^ 7 + 1) / 3 funcionam, não sei como eu errei. Editado agora.
Aditsu
4

Fichas C - 15 (?)

int div3_m1(unsigned int n) {
    n = (n & 0xf) + (n >> 4);
    n = (n & 0x3) + (n >> 2);
    n = (n & 0x3) + (n >> 2);
    return n == 0 || n == 3;
}

Desde 4 ≡ 1 (mod 3), temos 4 n ≡ 1 (mod 3). A regra de soma de dígitos não se limita à soma dos dígitos, mas também nos permite dividir arbitrariamente o número em seqüências de dígitos e somar todos eles, mantendo a congruência.

Um exemplo na base 10, divisor = 9:

1234 ≡ 12 + 34 ≡ 1 + 2 + 3 + 4 ≡ 123 + 4 ≡ 1 (mod 9)

Todas as instruções no programa fazem uso dessa propriedade. Na verdade, pode ser simplificado para um loop que executa a instrução n = (n & 0x3) + (n >> 2);até n < 4, pois a instrução simplesmente quebra o número na base-4 no dígito menos significativo e soma as duas partes.

n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
fonte
+1: curiosamente, isso funciona para n até 512 (na verdade n = 590), mas não sei ao certo por quê.
Paul R
@PaulR: Não funcionará para números maiores devido ao transporte (observe que eu usei adição no cálculo). Observe também as linhas repetidas.
N
Sim, não sei por que ele funciona com valores de 9 bits, pois parece estar testando apenas 8 bits?
Paul R
para números de 9 bits após a primeira adição, ela se torna no máximo 5 bits; após a primeira, n = (n & 0x3) + (n >> 2);o resultado é reduzido para 3 bits e a repetição faz com que permaneça apenas 2 bits. stackoverflow.com/a/3421654/995714
phuclv
1
oh eu cometi um erro. Um número de 5 bits + um número de 4 bits pode resultar em um número de 6 bits. Mas se n <= 588 adicionando os 4 bits superiores e os 2 bits inferiores desse número de 6 bits produzem uma soma apenas de 4 bits. Adicionar novamente isso resulta em um número de 2 bits. 589 e 590 resultados em 3 bits na última soma, mas aliás eles não são divisíveis por 3 assim que o resultado está correto
phuclv
2

Python (2 tokens?)

1&66166908135609254527754848576393090201868562666080322308261476575950359794249L>>x

Ou

1&0x9249249249249249249249249249249249249249249249249249249249249249L>>x

Ou

1&0b1001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001001>>x
ɐɔıʇǝɥʇuʎs
fonte
2
Duplicata do comentário de Howard
aditsu 23/06
@aditsu ... Grandes mentes pensam da mesma forma? Juro que não vi isso antes de publicar isso.
ɐɔıʇǝɥʇuʎs
2

JavaScript - 3 tokens

function div3(n) {
    var a = n * 0.3333333333333333;
    return (a | 0) == a;
}

Isso abusa do fato de que o uso de operadores bit a bit em um número o trunca para um número inteiro em JavaScript.

Tyilo
fonte
Deve ser de 4 fichas: =, *, |,==
n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
1
Eu não acho que a atribuição de variáveis ​​conta como um token.
Tyilo
1

C - 4 fichas

int div3(int x) {
    return ((x * 43) >> 7) * 3 == x;
}

Funciona até 383.

Versão anterior (constantes maiores):

int div3(int x) {
    return ((x * 171) >> 9) * 3 == x;
}

Funciona até 1535

aditsu
fonte
1

bash - ???

Não sei como pontuar isso.

seq 0 85 | awk '{print $1 * 3}' | grep -w [number] | wc -l

por exemplo

$ seq 0 85 | awk '{print $1 * 3}' | grep -w 11 | wc -l
0

$ seq 0 85 | awk '{print $1 * 3}' | grep -w 12 | wc -l
1

$seq 0 85 | awk '{print $1 * 3}' | grep -w 254 | wc -l
0

$seq 0 85 | awk '{print $1 * 3}' | grep -w 255 | wc -l
1

fonte
1

Befunge 93 - 5 fichas

Divisão fixa removida.

v      @._1.@
         \   
         0   
         +   
         3   
>&>3-:0\`|   
  ^      <   

Obtém entrada, continua subtraindo 3 até que seja menor que 0, direcione o ponteiro para cima ('|') e adicione 3. Se o valor for 0, o ponteiro se moverá para a direita (" 1. @" gera '1') e se move para a esquerda ("@. " gera '0'). '@' finaliza o programa.

AndoDaan
fonte
1

Lote - 7 fichas

eu acho que

@echo off
for /L %%a in (0,3,%1) do set a=%%a
if %a%==%1 echo 1

Retorna 1se o número fornecido (como stdin) é divisível por três.

desgrudar
fonte
São permitidos loops?
sergiol 28/01
1

Ruby, 6 (?) Tokens

Realmente não sei como contar tokens. OP, você pode me marcar?

Eu acho que é 6 ... 1, 0, 0, *, 255,x

Observe que a *multiplicação não é inteira.

def div3(x)
  ([1,0,0]*255)[x]
end
Não que Charles
fonte
Um token no sentido do OP não seria apenas um dos listados acima na pergunta?
C5H8NNaO4
@ C5H8NNaO4 E daí? 0?
Não que Charles
@ C5H8NNaO4 talvez 4 para constantes?
Não que Charles
1

Python 0

Postei eariler, mas usei condicionais. Aqui é para usar sem condicionais e sem tokens, apenas palavras-chave

def g(x): return ([[lambda : g(sum(int(y) for y in list(str(x)))),lambda: 0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda: 1][[False,True].index((lambda y: y in[3,6,9])(x))])()

usa o truque que múltiplos de 3s têm dígitos que somam 3

Edit: Removido lambda desnecessário

def g(x):return([[lambda: g(sum(int(y) for y in list(str(x)))),lambda:0][[False,True].index(x in[0,1,2,4,5,7,8])], lambda:1][[False,True].index(x in[3,6,9])])()

Edit: Golfe adicional (117 caracteres) ainda sem tokens

exec"g=`x:(((`:g(sum(int(y)for y in str(x)),`:0)[x in[0,1,2,4,5,7,8]],`:1)[x in[3,6,9]])()".replace('`','lambda ')

Matou o acesso direto ao getitem bacana do python Longer at 132 char

exec"g={0}x:((({0}:g(sum(int(y)for y in str(x))),{0}:0{1}0,1,2,4,5,7,8]),{0}:1{1}3,6,9]))()".format('lambda ',').__getitem__(x in[')

http://www.codeskulptor.org/#user34_uUl7SwOBJb_0.py

Dylan Madisetti
fonte
[]Entretanto, o acesso à matriz não é permitido.
n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
Isto é? Após essas regras, codegolf.stackexchange.com/tags/atomic-code-golf/info #
Dylan Madisetti
Bem, a pergunta não usa a regra na tag wiki. A pergunta tem restrição de operações permitidas. Observe a palavra only.
n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳
@ n̴̖̋h̷͉a̷̭̿h̸̡̅ẗ̵̨d̷̰ĥ̷̳ Bem, é uma coisa boa python tem um atributo nativa para isso também
Dylan Madisetti
0

Python - 25 fichas

Para começar, tenho uma solução longa que é a implementação de uma das respostas no link no meu primeiro post. né entrada.

a = (n>>7)-((n&64)>>6)+((n&32)>>5)-((n&16)>>4)+((n&8)>>3)-((n&4)>>2)+((n&2)>>1)-(n&1)
print(a==0 or a==3)

oré equivalente a ||.

qwr
fonte
0

JavaScript - 3 tokens

Teste-o no console do seu navegador:

a = prompt().split('');
sum = 0;

do {
  sum = a.reduce(function(p, c) {
     return parseInt(p) + parseInt(c); 
  });

  a = sum.toString().split('');

} while(a.length > 1)

alert([3, 6, 9].indexOf(+sum) > -1)
William Barbosa
fonte
Como você chegou a essa conclusão? Eu conto cerca de 37 fichas.
nyuszika7h
"Um token é uma das alternativas e variáveis ​​excluídas acima". Como você contou 37?
William Barbosa
1
Ah eu vejo. O OP parece discordar da página de informações do código atômico-golfe .
nyuszika7h
Na verdade, agora não tenho certeza se estou certo ou não. Minha pontuação seria mais de 70, de acordo com o violino de código atômico do golfe.
William Barbosa
1
O problema não é sobre o número de tokens, mas sobre quais operações você está usando. Eu não acho que toString, parseInt, loops, matrizes, etc. são permitidos.
aditsu
0

JavaScript
não tem certeza sobre o token #

function mod3 (i) { return {'undefined':'100','0':'0'}[[0][i]][i.toString (3).split('').pop ()]}

ou se a saída para 0 puder ser 1;

function mod3 (i) { return '100'[i.toString (3).split('').pop ()]}

C5H8NNaO4
fonte
2
Devo dizer que não tenho certeza de quais regras se aplicam a esse desafio. São permitidas chamadas de função e acessórios de propriedade?
C5H8NNaO4
0

Tcl , 83 bytes

proc T n {while \$n>9 {set n [expr [join [split $n ""] +]]};expr {$n in {0 3 6 9}}}

Experimente online!

sergiol
fonte
Outgolf com falha: 96 bytes proc T n {set n [expr [join [split [expr [join [split $n ""] +]] ""] +]];expr {$n in {0 3 6 9}}} Experimente online!
Sergiol # 10/18
Outra falha: ** 87 bytes ** proc T n {expr {[expr [join [split [expr [join [split $n ""] +]] ""] +]] in {0 3 6 9}}} Experimente online!
sergiol