Los enteros gaussianos son números complejos de la forma a+bi
donde a
y b
son ambos enteros. En la base -1 + i, todos los enteros gaussianos se pueden representar de forma única utilizando los dígitos 0
y 1
, sin la necesidad de un símbolo para indicar el signo.
Por ejemplo, 1100
en base -1 + i representa el número decimal 2, ya que
1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2
La entrada será dos enteros gaussianos en base -1 + i representados usando los dígitos 01
. Esto puede tomar una de las siguientes formas:
- Dos cadenas de dígitos separadas,
- Dos enteros decimales que consisten en
01
representar los números base -1 + i (por ejemplo,1100
para 2 en base -1 + i), - Dos enteros binarios que representan los números base -1 + i (por ejemplo, decimal
12
o0b1100
para 2 en base -1 + i) - Una sola cadena que separa cadenas de dos dígitos / enteros binarios por un solo separador no alfanumérico (por ejemplo,
1100 1100
o12,12
para 2 + 2)
Genere la suma de los dos enteros gaussianos, también en base -1 + i y representados usando los dígitos 01
(en uno de los formatos permitidos como entrada, no necesariamente la misma opción). La salida puede contener un número finito de ceros a la izquierda.
Su función o programa debe finalizar en 2 segundos para entradas de 30 dígitos como máximo cada una.
Aclaraciones adicionales
- Puede suponer que la entrada no contiene ceros iniciales extraños. Para el caso especial de 0, puede elegir una
0
cadena vacía o la representación.
Casos de prueba
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 prueba más largos:
11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010
fuente
-1+i
ai-1
en el título.Respuestas:
Python 2,
98979184 bytesEsto hace E / S en decimal. Los enteros deben estar separados por el carácter no alfanumérico
+
.¡Gracias a @xnor por jugar 2 bytes!
Pruébalo en Ideone .
Cómo funciona
En Aritmética en bases complejas , el autor muestra cómo sumar y multiplicar números complejos en bases de la forma -n + i .
Para la base -1 + i , la suma se realiza de manera similar a la suma binaria regular con carry, con dos diferencias:
En lugar de llevar 1 a la siguiente posición más alta, llevamos 110 a las siguientes tres.
Los dígitos de transporte pueden propagarse indefinidamente. Sin embargo, sin ceros a la izquierda, la suma a + b tiene como máximo ocho dígitos más que el máximo de a y b .
Procedemos de la siguiente manera.
En primer lugar, añadimos una y b como si sus cifras eran dígitos decimales.
Para a = 10,101 y b = 11,011 , esto da 21.112 .
A continuación, formamos un nuevo número reemplazando los dígitos mayores que 1 con un 1 , otros con un 0 . 1
Para la suma 21112 , esto da 10001 .
Para cada dígito mayor que 1 , tenemos que restar 2 de ese dígito y llevar 110 a las siguientes tres posiciones más altas. Como 1098 = 10 * 110 - 2 , podemos lograr esto multiplicando el resultado del paso 2 por 1098 , y luego sumando ese producto a la suma. 2
Para la suma 21112 , esto da 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Repetimos los pasos 2 y 3 un total de d * 8 veces, donde d es el número de dígitos de a + b . 3
Para la suma inicial 21112 , los resultados son
Tomamos el módulo de suma final 10 d + 8 , descartando todos excepto los últimos d + 8 dígitos.
Para la suma inicial 21112 , el resultado final es 10010 .
1 Esto se logra con traducir . Repetir la cadena 0011 64 veces hace que una repetición se alinee con la secuencia de caracteres ASCII 0123 , logrando el reemplazo deseado.
2 Tenga en cuenta que los dígitos de esta suma no pueden exceder 3 (valor inicial 1 más dos 1 'de acarreos).
3 Esto funciona para d = 1 , y d * 8> d + 8 de lo contrario. El código puede repetir los pasos (d + 1) * 8 veces, ya que s tiene una L final si s es un entero largo .
fuente
input()
espera? (Recibo21112
cuando ingreso10101, 11011
.)d+8
y no, por ejemplod+9
? ¿¿¿¿Cómo????Pyth, 34 bytes
Pruébelo en línea: Demostración o Test Suite (lleva bastante tiempo). Debería satisfacer la restricción de tiempo aunque fácilmente, ya que el compilador en línea es bastante lento en comparación con el compilador normal (fuera de línea).
Explicación:
Mi algoritmo es básicamente una implementación de adición con transporte. Pero en lugar de llevar
1
, tengo que llevar110
(1100
en la base-1+i
es lo mismo que2
en la base-1+i
). Esto funciona principalmente bien, pero puede quedar atrapado en un bucle de impresión de ceros infinitos. Por ejemplo, si está agregando1
con11
y actualmente tiene el carry110
. Así que básicamente agrego hasta quedar atrapado en un bucle y luego me detengo. Creo que un bucle que un bucle siempre imprimirá ceros y, por lo tanto, esto debería estar bien.fuente
Python 2,
6967 bytesLa E / S se realiza con enteros de base 2.
-2 gracias @Dennis.
fuente
a*a+b*b^58==0
cuandoa
yb
son inversas? ¿Cómo funciona?a*a+b*b==58
cuando uno de ellos es 3 y el otro es 7.(3,7)
es el único par que da un ciclo y necesita una carcasa especial. Si es cierto, entonces solo necesita verificar(a,b)==(3,7)
en ese orden, ya que(7,3)
recurre a(3,7)
, y tal vez haya una expresión más corta para eso.^
es XOR, no exponenciación, o (b) XOR tiene menor prioridad que+
.Retina , 100 bytes
Esto toma la entrada separada con una coma. La salida siempre comienza con tres ceros a la izquierda.
Pruébalo en línea!
Realmente me pregunto si hay una solución más corta para la primera etapa ...
fuente
Gelatina,
292826242120 bytesEsto hace E / S en decimal. Los enteros deben estar separados por el carácter no alfanumérico
+
.Pruébalo en línea! o verificar todos los casos de prueba .
Antecedentes
En Aritmética en bases complejas , el autor muestra cómo sumar y multiplicar números complejos en bases de la forma -n + i .
Para la base -1 + i , la suma se realiza de manera similar a la suma binaria regular con carry, con dos diferencias:
En lugar de llevar 1 a la siguiente posición más alta, llevamos 110 a las siguientes tres.
Los dígitos de transporte pueden propagarse indefinidamente. Sin embargo, sin ceros a la izquierda, la suma a + b tiene como máximo ocho dígitos más que el máximo de a y b .
Procedemos de la siguiente manera.
En primer lugar, añadimos una y b como si sus cifras eran dígitos decimales.
Para a = 10,101 y b = 11,011 , esto da 21.112 .
Para cada dígito mayor que 1 , tenemos que restar 2 de ese dígito y llevar 110 a las siguientes tres posiciones más altas. Podemos lograr esto al convertir cada dígito decimal a binario, las matrices binarias resultantes de base 1100 a entero, e interpretar la lista resultante de 0 's, 1 ' s, 1100 's y 1101 ' s como una base no canónica 10 número. 1
Para la suma 21112 , esto da 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .
Repetimos los pasos 2 un total de d + 8 veces, donde d es el número de dígitos de a + b .
Para la suma inicial 21112 , los resultados son
Descartamos todos menos los últimos d + 8 dígitos del resultado final. Esto se logra descartando todo después de los últimos 2 . 2
Para la suma inicial 21112 , el resultado final es 10010 .
Cómo funciona
1 Tenga en cuenta que los dígitos de esta suma no pueden exceder 3 (valor inicial 1 más dos 1 'de acarreos).
2 Esto funciona porque el último dígito que se cancelará no puede ser un 3 .
fuente
Python 3, 289 bytes
Esto lleva a cabo la suma de dígitos a dígitos de menor a mayor importancia (en otras palabras, exactamente el mismo algoritmo que le enseñaron en la escuela primaria). Las diferencias son que (a) está en binario, no decimal, por lo que llevas siempre que un dígito sea 2 o más, y (b)
1 + 1 = 1100
, no10
.En realidad, también es necesario tener en cuenta que
11 + 111 = 0
, de lo contrario, las sumas que deberían convertirse en cero nunca terminarán.Más golf es seguramente posible.
fuente
Retina,
157151134133124123 bytes1 byte apagado gracias a Martin Büttner.
Pruébalo en línea!
Convierte a unario y luego repite los siguientes reemplazos (mostrados aquí en decimal):
Básicamente, cuando es mayor que dos: quite dos, no agregue nada en el dígito anterior, agregue uno al dígito anterior, luego agregue uno al dígito anterior.
En pseudocódigo:
Implementación unaria:
Cada dígito (p
3
. Ej. ) Se muestra como el número dex
s (pxxx
. Ej. ) Y luego se antepone con0
.Por ejemplo,
1234
se expresaría como0x0xx0xxx0xxxx
.Esto deja
0
sin cambios, como101
se expresaría por0x00x
.Como inicialmente y finalmente, solo hay
0
y1
, la conversión podría hacerse fácilmente por1->0x
y0x->1
.Haga clic aquí para ver cada paso .
fuente
JavaScript (ES6),
146126bytesg
convierte un entero gaussiano (partes reales e imaginarias) en basei-1
, mientras quer
yi
convierte uni-1
entero base en un entero gaussiano (partes reales e imaginarias respectivamente). Una vez que las conversiones están en su lugar, solo tengo que hacer la aritmética.Editar: ahorró 20 bytes calculando las partes real e imaginaria por separado.
fuente
C ++ 416 bytes, más
#include <vector>\n#include <algorithm>\n
(otros 40)o, con más espacios en blanco:
Apenas golfizado. Toma la entrada como un vector de entradas y devuelve un vector de entradas.
Ejemplo en vivo .
fuente