Um bit de paridade , é uma das formas mais simples de uma soma de verificação. Primeiro, você deve escolher a paridade, par ou ímpar. Digamos que escolhemos par. Agora, precisamos de uma mensagem para transmitir. Digamos que nossa mensagem seja "Foo". Isso está escrito em binário como:
01000110 01101111 01101111
Agora, contamos o número total de 1
's' lá, que é 15. Como 15 é um número ímpar, devemos adicionar um bit extra ao final de nossa mensagem e agora teremos um número par de bits 'on' . Este último bit adicionado é conhecido como "bit de paridade". Se tivéssemos escolhido uma paridade ímpar para nossa soma de verificação, teríamos que adicionar um '0' extra para que o número de bits permanecesse ímpar.
O desafio:
Você deve escrever um programa ou função que determine qual é o bit de paridade correto para uma string. Seu programa deve receber duas entradas:
Uma corda
s
. Essa é a mensagem na qual a soma de verificação será calculada. Isso será restrito aos 95 caracteres imprimíveis ASCII.Um caractere ou sequência de caracteres única
p
, que seráe
paridade par ouo
paridade ímpar.
e produza um valor truthy-falsey representando o bit de paridade correto. Verdadeiramente se for um 1
, e falsey se for um 0
.
Construções internas que contam o número de bits "ativados" em uma sequência ou caractere não são permitidas. Por exemplo, uma função f
que faz isso: f('a') == 3
ou f('foo') == 16
é banida. Qualquer outra coisa, como a conversão de base, é um jogo justo.
Teste de E / S:
(without the quotes)
s: "0"
p: 'e'
output: 0
s: "Foo"
p: 'e'
output: 1
s: "Hello World!"
p: 'o'
output: 0
s: "Alex is right"
p: 'e'
output: 1
s: "Programming Puzzles and Code-Golf"
p: 'e'
output: 0
s: "Programming Puzzles and Code-Golf"
p: 'o'
output: 1
Este é um codegolf, então as brechas padrão se aplicam e a resposta mais curta em bytes vence.
o
tem até paridade.str(int(s, 2)).count('1')
:? Não, eu não consideraria essa uma única função interna que viola essa regra. Minha edição deixa mais claro?char == single_char_string
. Eu também editei isso no post.Respostas:
MATL ,
87 bytesExperimente online! Ou verifique todos os casos de teste de uma só vez .
fonte
Java, 97 bytes
Porque, você sabe, Java.
Este é um lambda para a
BiFunction<String, Character, Boolean>
.e
eo
parece estar invertida na declaração de retorno porque, aparentemente, minha lógica estava ao contrário.fonte
Python 2, 51 bytes
Isso se baseia na idéia do Sp3000 de contar 1 na representação de seqüência de caracteres da lista de códigos de caracteres em binário, em vez de somar para cada caractere.
O novo truque é pega
e
eo
neste também. See
fosse ímpar eo
par, poderíamos simplesmente acrescentar o bit de paridade à string antes de fazer a contagem (invertê-los porque '1' é Truthy). Infelizmente, eles não são. Mas, se removermos todos, exceto os dois últimos bits, agora é verdade.Isso é feito removendo o primeiro
9
caractere da representação em cadeia.fonte
eo
!Geléia,
98 bytesExperimente online!
Obrigado ao Dennis por um byte!
fonte
V}
... aquele foi muito legal !!! (Dennis é um verdadeiro jogador de golfe) +1 Ele venceu todas as minhas tentativas.C, 62 bytes
O XOR tem a propriedade legal de que ele pode ser usado para reduzir cadeias de caracteres para um caractere, preservando a paridade.
Ideone.
fonte
27030>>((p^p>>4)&15)&1
deve calcular a paridade de p e é ainda 1 byte mais curtochar *s
é necessáriof(s,p)char*s;{for(p/=8;*s;)p^=*s>>4^*s++;p^=p/4;return p%4%3;}
O%3
sempre retornará 0 para um 0, mas pode retornar 1 ou 2 para a 1. Isto é aceitável sob as regras:truthy if it's a 1
27030>>((p^p>>4)&15)&1
. Bem, erre, obviamente. ;-)Python,
5857 bytesfonte
lambda s,p:`map(bin,map(ord,s))`.count('1')%2^(p>'e')
!=p>'e'
.lambda s,p:`map(bin,map(ord,p+s))`[8:].count('1')%2
Pitão, 12 bytes
Suíte de teste.
fonte
JavaScript (ES6),
8472 bytesO ajuste de bits acabou sendo mais curto do que converter para a base 2 e contar
1
s.fonte
Perl, 29 bytes
Inclui +2 para
-p
Execute com a entrada STDIN como sequência de espaço de caracteres de paridade, por exemplo
parity.pl
fonte
J, 27 bytes
Uso
fonte
JavaScript (ES6), 69 bytes
fonte
PowerShell v2 +, 91 bytes
/ eu chora no canto
Sim ... então, a conversão de base não é um ponto forte para o PowerShell. A conversão da sequência de entrada para representação binária
$a|%{[convert]::toString(+$_,2)}
é de 32 bytes por si só ...Recebe entrada
$a
e$b
, explicitamente, lança$a
como um char-array no processo. Em seguida, verificamos se$b
é-eq
necessárioo
e-xor
com a outra metade do programa. Para essa parte, pegamos a string de entrada, passamos$a
por um loop para converter cada letra em binário,-join
todos juntos para formar uma string sólida e-replace
todos os0
s sem nada. Contamos então a.length
sequência e a usamos mod-2 para determinar se é par ou ímpar, o que será convenientemente um0
ou outro1
, perfeito para o-xor
.Voltará
True
ou emFalse
conformidade. Veja os casos de teste abaixo:fonte
Fator, 85 bytes
Por alguma razão, eu não conseguia entender isso até alguns minutos atrás, quando simplifiquei (e talvez abreviei?) O código.
?
é como um operador ternário: ele testa a veracidade do terceiro item da pilha e seleciona otrue
valor ou ofalse
valor.É aproximadamente equivalente ao seguinte pseduocode do tipo C:
O restante do código é bem simples:
fonte
Código de máquina IA-32, 15 bytes
Hexdump:
Código de montagem:
Esta é uma função que recebe seu primeiro argumento (string)
ecx
e o segundo argumento (char) emdl
. Ele retorna o resultado emeax
, portanto, é compatível com ofastcall
convenção de chamada.Este código dobra as regras quando usa a
setpo
instrução:Esta instrução define
al
o bit de paridade calculado pela instrução anterior - então eu tenho esses dois detalhes sobre as regras:xor
) que calcula o bit de paridade. Asetpo
instrução apenas a move para oal
registrador.Esses detalhes semânticos estão fora do caminho, aqui está a explicação sobre o que o código faz.
As representações dos personagens são:
Se adicionarmos 1 a eles, eles terão a paridade certa:
Então,
XOR
todos os caracteres da string são inicializadosal
com esses valores, o que fornece a resposta.A primeira instrução é, em
movzx eax, dl
vez da mais óbvia (e mais curta)mov al, dl
, porque eu quero ter o número 0 em um registro (ah
neste caso) para poder compará-lo na ordem correta (0, [ecx]
e não[ecx], 0
).fonte
Julia,
58474540 bytesEsta é uma função que aceita uma string e um caractere e retorna um número inteiro.
Para obter o número de unidades na representação binária, primeiro aplicamos a
bin
função a cada caractere na cadeia, o que nos fornece uma matriz de cadeias binárias. Em seguida, reduza-os para um único usoprod
(já que*
é concatenação de string em Julia) e faça a interseção definida dessa string e o código de caractere para1
, o que nos fornece uma string de uns. O último índice dessa sequência é o número de unidades. Nós o XORamos com 1 se o caractere fornecido é o e 0, caso contrário, obtemos a paridade usando AND 1 bit a bit.Experimente online! (inclui todos os casos de teste)
Economizou 18 bytes graças a Dennis!
fonte
05AB1E ,
15, 13 bytesCódigo:
Exemplo de entrada:
Saída de exemplo:
Explicação:
Agradecimentos a Adnan por salvar 2 bytes.
fonte
²
comando Isso empurra automaticamente a segunda entrada no topo da pilha. Além disso, seqüências de caracteres de dois caracteres podem ser reduzidas usando„
. Então"oe"
é equivalente a„
. Para 13 bytes:€ÇbSOÈ„oe²k<^
:)Ruby, 57 bytes
Se
0
foi falsey em Ruby,==
provavelmente poderia ser alterado para apenas-
, ou pode haver outras otimizações, mas não é.fonte
Retina , 102 bytes
Pega a corda na primeira linha e a letra na segunda linha. Usa codificação ISO 8859-1.
Experimente online
A classe de caracteres na primeira linha corresponde a qualquer caractere com um número ímpar de um na representação binária.
Descrição de como a detecção par / ímpar com regex funciona aqui .
fonte
Oitava, 56 bytes
A
bitunpack
função, para caracteres ASCII, os retorna em ordem little-endian. Então, colocando a bandeira de paridade no final de nossa string, descompactando a coisa toda e soltando os últimos 5 bits, podemos então resumir a coisa toda mod 2 para a nossa resposta final.Uso:
fonte
Lisp comum, 87
s
.p
na sequência"oe"
(0 ou 1). Por exemplo, se houver 4, o restante será zero. Se p foro
, nenhum bit adicional deverá ser adicionado e o teste retornará falso.Pretty-impresso
fonte
Java, 91 bytes
Fiz o mesmo que o @ CAT97, mas retirei alguns caracteres usando o módulo 8 e a concatenação de @Luis Mendo e o uso de int em vez de booleano.
Este é um lambda para a
BiFunction<String, Character, Boolean>
.fonte
Matlab, 49 bytes
Onde:
Por exemplo:
fonte
Ferramentas Bash e Unix (72 bytes)
Excepta
s
como o primeiro ep
o segundo argumento. Felizmente, os últimos 3 bitso
ee
tem paridade ímpar e par, respectivamente.O fornecimento da entrada via
<<<
adiciona um caractere de avanço de linha, mas a paridade de\n
é par e, portanto, não é um problema.fonte