Inteiros gaussianos são números complexos da forma em a+bi
que a
e b
são os dois inteiros. Na base -1 + i, todos os números inteiros gaussianos podem ser representados exclusivamente usando os dígitos 0
e 1
, sem a necessidade de um símbolo para indicar sinal.
Por exemplo, 1100
na base -1 + i representa o número decimal 2, pois
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2
A entrada será dois números inteiros gaussianos na base -1 + i representada usando os dígitos 01
. Isso pode assumir uma das seguintes formas:
- Duas cadeias de dígitos separadas,
- Dois números inteiros decimais que consistem em
01
representar os números da base -1 + i (por exemplo,1100
para 2 na base -1 + i), - Dois números inteiros binários representando os números da base -1 + i (por exemplo, decimal
12
ou0b1100
para 2 na base -1 + i) - Uma única cadeia que separa duas cadeias de dígitos / números inteiros binários por um único separador não alfanumérico (por exemplo,
1100 1100
ou12,12
para 2 + 2)
Emita a soma dos dois números inteiros gaussianos, também na base -1 + ie representados usando os dígitos 01
(em um dos formatos permitidos como entrada, não necessariamente a mesma escolha). É permitido que a saída contenha um número finito de zeros à esquerda.
Sua função ou programa deve terminar dentro de 2 segundos para entradas de no máximo 30 dígitos cada.
Esclarecimentos adicionais
- Você pode assumir que a entrada não contém zeros iniciais estranhos. Para o caso especial de 0, você pode escolher uma
0
ou a sequência vazia como a representação.
Casos de teste
0, 0 => 0 # 0 + 0 = 0
0, 1 => 1 # 0 + 1 = 1
1, 1 => 1100 # 1 + 1 = 2
1100, 1100 => 111010000 # 2 + 2 = 4
1101, 1101 => 111011100 # 3 + 3 = 6
110111001100, 1110011011100 => 0 # 42 + (-42) = 0
11, 111 => 0 # i + (-i) = 0
11, 110 => 11101 # i + (-1-i) = -1
10101, 11011 => 10010 # (-3-2i) + (-2+3i) = (-5+i)
1010100101, 111101 => 1110100000100 # (-19+2i) + (3-4i) = (-16-2i)
Casos de teste mais longos:
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010
fonte
-1+i
parai-1
no título.Respostas:
Python 2,
98979184 bytesIsso faz E / S em decimal. Os números inteiros devem ser separados pelo caractere não alfanumérico
+
.Graças a @xnor por jogar fora 2 bytes!
Experimente em Ideone .
Como funciona
Em Aritmética em bases complexas , o autor mostra como adicionar e multiplicar números complexos em bases da forma -n + i .
Para a base -1 + i , a adição é feita de maneira semelhante à adição binária regular com carry, com duas diferenças:
Em vez de carregar 1 para a próxima posição mais alta, transportamos 110 para as próximas três.
Os dígitos de transporte podem se propagar indefinidamente. No entanto, sem zeros à esquerda, a soma a + b tem no máximo oito dígitos a mais do que o máximo de a e b .
Nós procedemos da seguinte maneira.
Primeiro, adicionamos um e b como se seus dígitos eram dígitos decimais.
Para a = 10101 e b = 11011 , o que dá 21112 .
Em seguida, formamos um novo número substituindo os dígitos maiores que 1 por 1 , outros por 0 . 1
Para a soma 21112 , isso fornece 10001 .
Para cada dígito maior que 1 , temos que subtrair 2 desse dígito e transportar 110 para as próximas três posições mais altas. Como 1098 = 10 * 110-2 , podemos conseguir isso multiplicando o resultado da etapa 2 por 1098 e adicionando esse produto à soma. 2
Para a soma 21112 , isso fornece 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Repetimos as etapas 2 e 3 um total de d * 8 vezes, em que d é o número de dígitos de a + b . 3
Para a soma inicial 21112 , os resultados são
Tomamos a soma final do módulo 10 d + 8 , descartando todos, exceto os últimos dígitos d + 8 .
Para a soma inicial 21112 , o resultado final é 10010 .
1 Isso é conseguido com a tradução . Repetir a sequência 0011 64 vezes faz uma repetição alinhada com a sequência de caracteres ASCII 0123 , alcançando a substituição desejada.
2 Note-se que os dígitos desta soma não pode exceder 3 (valor inicial 1 , mais dois 1 's a partir carrega).
3 Isso funciona para d = 1 e d * 8> d + 8 caso contrário. O código pode repetir as etapas (d + 1) * 8 vezes, pois s tem um L à direita se s for um número inteiro longo .
fonte
input()
esperando? (Eu recebo21112
quando eu entrada10101, 11011
.)d+8
e não, digamosd+9
,? Como????Pitão, 34 bytes
Experimente on-line: Demonstration ou Test Suite (leva um bom tempo). Ele deve satisfazer a restrição de tempo com facilidade, pois o compilador online é bastante lento em comparação com o compilador normal (offline).
Explicação:
Meu algoritmo é basicamente uma implementação de adição com carry. Mas, em vez de carregar
1
, eu tenho que carregar110
(1100
na base-1+i
é o mesmo que2
na base-1+i
). Isso funciona muito bem, mas você pode ficar preso em zeros de impressão de loop infinito. Por exemplo, se você está adicionando1
com11
e atualmente tem o carry110
. Então eu basicamente adiciono até ficar preso em um loop e depois parar. Eu acho que um loop que um loop sempre imprimirá zeros e, portanto, isso deve ficar bem.fonte
Python 2,
6967 bytesA E / S é feita com números inteiros de base 2.
-2 obrigado @Dennis.
fonte
a*a+b*b^58==0
quandoa
eb
são inversos? Como isso funciona?a*a+b*b==58
quando um deles é 3 eo outro é 7.(3,7)
é o único par que dá um ciclo e precisa de revestimento especial. Se for verdade, você só precisará fazer o check-(a,b)==(3,7)
in nessa ordem, pois se(7,3)
repete a(3,7)
, e talvez haja uma expressão mais curta para isso.^
é XOR, não exponenciação, ou (b) XOR tem precedência menor que+
.Retina , 100 bytes
Isso leva a entrada separada por vírgula. A saída sempre começa com três zeros à esquerda.
Experimente online!
Eu realmente me pergunto se existe uma solução mais curta para a primeira etapa ...
fonte
Geléia,
292826242120 bytesIsso faz E / S em decimal. Os números inteiros devem ser separados pelo caractere não alfanumérico
+
.Experimente online! ou verifique todos os casos de teste .
fundo
Em Aritmética em bases complexas , o autor mostra como adicionar e multiplicar números complexos em bases da forma -n + i .
Para a base -1 + i , a adição é feita de maneira semelhante à adição binária regular com carry, com duas diferenças:
Em vez de carregar 1 para a próxima posição mais alta, transportamos 110 para as próximas três.
Os dígitos de transporte podem se propagar indefinidamente. No entanto, sem zeros à esquerda, a soma a + b tem no máximo oito dígitos a mais do que o máximo de a e b .
Nós procedemos da seguinte maneira.
Primeiro, adicionamos um e b como se seus dígitos eram dígitos decimais.
Para a = 10101 e b = 11011 , o que dá 21112 .
Para cada dígito maior que 1 , temos que subtrair 2 desse dígito e transportar 110 para as próximas três posições mais altas. Podemos conseguir isso convertendo cada dígito decimal em binário, as matrizes binárias resultantes da base 1100 em número inteiro e interpretando a lista resultante de 0 ', 1 ', 1100 'e 1101 ' como uma base não canônica 10 número. 1
Para a soma 21112 , isso fornece 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Repetimos as etapas 2 um total de d + 8 vezes, em que d é o número de dígitos de a + b .
Para a soma inicial 21112 , os resultados são
Nós descartamos todos, exceto os últimos d + 8 dígitos do resultado final. Isso é conseguido descartando tudo após os últimos 2 . 2
Para a soma inicial 21112 , o resultado final é 10010 .
Como funciona
1 Note-se que os dígitos desta soma não pode exceder 3 (valor inicial 1 , mais dois 1 's a partir carrega).
2 Isso funciona porque o último dígito que será cancelado não pode ser um 3 .
fonte
Python 3, 289 bytes
Isso realiza a adição digital a menos do dígito mais significativo (em outras palavras, exatamente o mesmo algoritmo que você aprendeu na escola primária). As diferenças são que (a) é binário, não decimal, então você carrega sempre que um dígito é 2 ou mais e (b)
1 + 1 = 1100
não10
.Na verdade, também é necessário observar que
11 + 111 = 0
, caso contrário, as somas que devem se tornar zero nunca serão encerradas.Mais golfe é certamente possível.
fonte
Retina,
157151134133 133124123 bytes1 byte de desconto, graças a Martin Büttner.
Experimente online!
Converte em unário e repita as seguintes substituições (mostradas aqui em decimal):
Basicamente, quando maiores que dois: retire dois, não adicione nada no dígito anterior, adicione um ao dígito anterior e adicione outro ao dígito anterior.
No pseudocódigo:
Implementação unária:
Cada dígito (por exemplo
3
) é mostrado como o número dex
s (por exemploxxx
) e, em seguida, prefixado com0
.Por exemplo,
1234
seria expresso como0x0xx0xxx0xxxx
.Isso deixa
0
inalterado, como101
seria expresso por0x00x
.Como inicialmente e finalmente, existe apenas
0
e1
, a conversão pode ser facilmente feita por1->0x
e0x->1
.Clique aqui para ver todas as etapas .
fonte
JavaScript (ES6),
146126 bytesg
converte um número inteiro de Gauss (partes reais e imaginárias) para a basei-1
, ao mesmo tempor
ei
se converte uma basei-1
número inteiro em um número inteiro de Gauss (partes real e imaginária, respectivamente). Uma vez que as conversões estão no lugar, eu apenas tenho que fazer a aritmética.Editar: salvou 20 bytes calculando as partes reais e imaginárias separadamente.
fonte
C ++ 416 bytes, mais
#include <vector>\n#include <algorithm>\n
(outros 40)ou, com mais espaço em branco:
Mal jogou golfe. Ele recebe entrada como um vetor de ints e retorna um vetor de ints.
Exemplo ao vivo .
fonte