Liczby całkowite gaussowskie są liczbami zespolonymi w postaci a+bigdzie ai boba są liczbami całkowitymi. W bazie -1 + i wszystkie liczby całkowite Gaussa mogą być jednoznacznie reprezentowane za pomocą cyfr 0i 1bez potrzeby oznaczania znaku symbolem.

Na przykład 1100w podstawie -1 + i reprezentuje liczbę dziesiętną 2, ponieważ

1*(-1+i)^3 + 1*(-1+i)^2 + 0*(-1+i)^1 + 0*(-1+i)^0
= (2+2i) + (-2i) + 0 + 0
= 2

Wejściami będą dwie liczby całkowite Gaussa w podstawie -1 + i reprezentowane za pomocą cyfr 01. Może to mieć jedną z następujących postaci:

• Dwa oddzielne ciągi cyfr,
• Dwie liczby całkowite dziesiętne polegające na 01reprezentowaniu liczb podstawowych -1 + i (np. 1100Dla 2 w bazie -1 + i),
• Dwie binarne liczby całkowite reprezentujące liczby podstawowe -1 + i (np. Dziesiętne 12lub 0b1100dla 2 w bazie -1 + i)
• Pojedynczy ciąg oddzielający dwucyfrowe ciągi / binarne liczby całkowite przez pojedynczy niealfanumeryczny separator (np. 1100 1100Lub 12,12dla 2 + 2)

Wyprowadza sumę dwóch liczb całkowitych Gaussa, również w bazie -1 + i, reprezentowanych za pomocą cyfr 01(w jednym z formatów dozwolonych jako dane wejściowe, niekoniecznie ten sam wybór). Dane wyjściowe mogą zawierać skończoną liczbę zer wiodących.

Twoja funkcja lub program musi zakończyć się w ciągu 2 sekund dla wprowadzania co najwyżej 30 cyfr.

Dodatkowe wyjaśnienia

• Możesz założyć, że dane wejściowe nie zawierają zewnętrznych zer wiodących. W specjalnym przypadku 0 możesz wybrać jeden 0lub pusty ciąg jako reprezentację.

Przypadki testowe

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)

Dłuższe przypadki testowe:

11011011010110101110010001001, 111100010100101001001010010101 => 0
111111111111111111111111111111, 111111111111111111111111111111 => 100100100100100100100100100100
101101110111011101110111011101, 101101110111011101110111011101 => 11101001010001000100010001000100011100
100100010101001101010110101010, 100010011101001011111110101000 => 110000110010101100001100111100010

Python 2, 98 97 91 84 bajtów

s=input();L=1
for _ in`s`*8:s+=1098*int(str(s).translate('0011'*64));L*=10
print s%L

Robi to we / wy dziesiętnie. Liczby całkowite muszą być oddzielone znakiem niealfanumerycznym +.

Dzięki @xnor za grę w golfa z 2 bajtów!

Wypróbuj na Ideone .

Jak to działa

W Arytmetyki w złożonych bazach autor pokazuje, jak dodawać i pomnożyć liczby zespolone w bazach postaci -n + i .

Dla podstawy -1 + i dodawanie odbywa się podobnie do zwykłego dodawania binarnego z przeniesieniem, z dwiema różnicami:

• Zamiast przenosić 1 do następnej wyższej pozycji, przenosimy 110 do następnych trzech.

• Przenoszenie cyfr może się rozprzestrzeniać w nieskończoność. Jednak bez zer wiodących suma a + b ma najwyżej osiem cyfr więcej niż maksimum a i b .

Postępujemy następująco.

1. Najpierw dodamy A i B tak, jakby były ich cyfr po przecinku.

   W przypadku a = 10101 i B = 11011 , daje 21112 .

2. Następnie tworzymy nowy numer, zamieniając cyfry większe niż 1 na 1 , inne na 0 . ¹

   Dla sumy 21112 daje to 10001 .

3. Dla każdej cyfry większej niż 1 musimy odjąć 2 od tej cyfry i przenieść 110 do następnych trzech wyższych pozycji. Ponieważ 1098 = 10 * 110 - 2 , możemy to osiągnąć, mnożąc wynik z kroku 2 przez 1098 , a następnie dodając ten produkt do sumy. ²⁾

   Dla sumy 21112 daje to 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .

4. Powtarzamy kroki 2 i 3 łącznie d * 8 razy, gdzie d jest liczbą cyfr a + b . ³⁾

   Dla sumy początkowej 21112 wyniki są następujące

                         11002210
                         12210010
                       1220010010
                     122000010010
                   12200000010010
                 1220000000010010
               122000000000010010
             12200000000000010010
           1220000000000000010010
         122000000000000000010010
       12200000000000000000010010
     1220000000000000000000010010
   122000000000000000000000010010
                                .
                                .
                                .
   

5. Bierzemy końcową sumę modulo 10 ^{d + 8} , odrzucając wszystkie oprócz ostatnich d + 8 cyfr.

   W przypadku kwoty początkowej 21112 końcowy wynik to 10010 .

¹ _{Osiąga się to dzięki tłumaczeniu . Powtarzanie ciągu 0011 64 razy tworzy jedną linię powtórzenia z sekwencją znaków ASCII 0123 , osiągając pożądaną zamianę.}

² _{Zauważ, że cyfry tej sumy nie mogą przekraczać 3 (wartość początkowa 1 plus dwa 1 -te z przeniesień).}

³ _{Dzieje się tak, gdy działa dla d = 1 , a d * 8> d + 8 w przeciwnym razie. Kod może powtórzyć kroki (d + 1) * 8 razy, ponieważ s ma końcowe L, jeśli s jest długą liczbą całkowitą.}

Pyth, 34 bajty

_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ

Wypróbuj online: pakiet demonstracyjny lub testowy (zajmuje to sporo czasu). Powinien jednak łatwo spełniać ograniczenia czasowe, ponieważ kompilator online jest dość powolny w porównaniu z normalnym (offline) kompilatorem.

Wyjaśnienie:

Mój algorytm jest w zasadzie implementacją dodawania z przenoszeniem. Ale zamiast nosić 1muszę nosić 110( 1100w bazie -1+ijest to samo, co 2w bazie -1+i). Działa to głównie dobrze, ale możesz utknąć w nieskończonej pętli drukującej zera. Na przykład, jeśli dodajesz za 1pomocą 11i obecnie masz carry 110. Więc w zasadzie dodaję, aż utknę w pętli, a potem przestanę. Myślę, że pętla, w której pętla zawsze będzie drukować zera, dlatego powinna być w porządku.

_shM.u,%J/eMeN\12-+PMeNm.B6/J2k,kQ   implicit: Q = input list of strings
                               ,kQ   create the pair ["", Q]
    .u                               modify the pair N (^) until loop:
      ,                                replace N with a new pair containing:
            eN                           N[1] (the remaining summand)
          eM                             take the last digits of each summand
         /    \1                         count the ones
        J                                store the count in J
       %J       2                        J % 2 (this is the first element of the new pair)
                   PMeN                  remove the last digit of each summand
                  +    m   /J2           and add J / 2 new summand:
                        .B6                 with the value "110" (binary of 6)
                 -            k          remove empty summand
    .u                               returns all intermediate results
  hM                                 extract the digits
 s                                   sum them up to a long string
_                                    reverse

Python 2, 69 67 bajtów

f=lambda a,b:a*a+b*b^58and 2*f(a*b%2*6,f(a/2,b/2))|a+b&1if a else b

I / O odbywa się przy użyciu liczb całkowitych bazowych 2.

-2 dzięki @Dennis.

Siatkówka , 100 bajtów

r+`(.*)(\d|(?!\4))( .*)(.?)
$2$4:$1$3
T` 0
+`1:11(1*:1*)11
:$1
^:*
:::
}`:(1*:1*:)11
1:1$1
(1)*:
$#1

Spowoduje to oddzielenie danych wejściowych przecinkiem. Wyjście zawsze zaczyna się od trzech wiodących zer.

Wypróbuj online!

Naprawdę zastanawiam się, czy istnieje krótsze rozwiązanie dla pierwszego etapu ...

Galaretka, 29 28 26 24 21 20 bajtów

DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ

Robi to we / wy dziesiętnie. Liczby całkowite muszą być oddzielone znakiem niealfanumerycznym +.

Wypróbuj online! lub zweryfikuj wszystkie przypadki testowe .

tło

W Arytmetyki w złożonych bazach autor pokazuje, jak dodawać i pomnożyć liczby zespolone w bazach postaci -n + i .

Dla podstawy -1 + i dodawanie odbywa się podobnie do zwykłego dodawania binarnego z przeniesieniem, z dwiema różnicami:

• Zamiast przenosić 1 do następnej wyższej pozycji, przenosimy 110 do następnych trzech.

• Przenoszenie cyfr może się rozprzestrzeniać w nieskończoność. Jednak bez zer wiodących suma a + b ma najwyżej osiem cyfr więcej niż maksimum a i b .

Postępujemy następująco.

1. Najpierw dodamy A i B tak, jakby były ich cyfr po przecinku.

   W przypadku a = 10101 i B = 11011 , daje 21112 .

2. Dla każdej cyfry większej niż 1 musimy odjąć 2 od tej cyfry i przenieść 110 do następnych trzech wyższych pozycji. Można to osiągnąć przez przeprowadzenie każdej cyfry dziesiętnej binarnego powstałe tablice binarne z podstawy 1100, do liczby całkowitej, i interpretowania otrzymanej listy 0 „s, 1 ” S, 1100 -tych i 1101 -tych, jako Niekanoniczne 10 numer. ¹

   Dla sumy 21112 daje to 21112 + 1098 * 10001 = 21112 + 10981098 = 11002210 .

3. Powtarzamy kroki 2 łącznie d + 8 razy, gdzie d jest liczbą cyfr a + b .

   Dla sumy początkowej 21112 wyniki są następujące

                         11002210
                         12210010
                       1220010010
                     122000010010
                   12200000010010
                 1220000000010010
               122000000000010010
             12200000000000010010
           1220000000000000010010
         122000000000000000010010
       12200000000000000000010010
     1220000000000000000000010010
   122000000000000000000000010010
   

4. Odrzucamy wszystkie oprócz ostatnich d + 8 cyfr z wyniku końcowego. Osiąga się to poprzez odrzucenie wszystkiego po ostatnich 2 . ²⁾

   W przypadku kwoty początkowej 21112 końcowy wynik to 10010 .

Jak to działa

DBḅ1100ḌµDL+8µ¡Dṣ2ṪḌ  Main link. Argument: a + b (implicit sum)

        µ    µ¡       Execute the chain before the first µ n times, where n is
                      the result of executing the chain before the second µ.
         D            Convert a + b to base 10.
          L           Length; count the decimal digits.
           +8         Add 8 to the number of digits.
D                     Convert the initial/previous sum to base 10.
 B                    Convert each digit (0 - 3) to binary.
  ḅ1100               Convert each binary array from base 1100 to integer.
       Ḍ              Interpret the resulting list as a base 10 number.
               D      Convert the final sum to base 10.
                ṣ2    Split at occurrences of 2.
                  Ṫ   Select the last chunk.
                   Ḍ  Convert from base 10 to integer.

¹ _{Zauważ, że cyfry tej sumy nie mogą przekraczać 3 (wartość początkowa 1 plus dwa 1 -te z przeniesień).}

² _{Działa, ponieważ ostatnia cyfra, która anuluje, nie może być 3 .}

Python 3, 289 bajtów

Dokonuje cyfrowego dodawania od najmniej znaczącej cyfry (innymi słowy dokładnie ten sam algorytm, którego nauczyłeś się w szkole podstawowej). Różnice polegają na tym, że (a) ma postać binarną, a nie dziesiętną, więc przenosisz za każdym razem, gdy cyfra ma 2 lub więcej, i (b) 1 + 1 = 1100nie 10.

W rzeczywistości należy również zauważyć, że 11 + 111 = 0w przeciwnym razie sumy, które powinny być zerowe, nigdy się nie zakończą.

from collections import*
def a(*s,p=0):
 r=defaultdict(int,{0:0})
 for S in s:
  n=0
  for d in S[::-1]:r[n]+=d=='1';n+=1
 while p<=max(r):
  while r[p]>1:
   r[p]-=2
   if r[p+1]>1<=r[p+2]:r[p+1]-=2;r[p+2]-=1
   else:r[p+2]+=1;r[p+3]+=1
  p+=1
 return str([*map(r.get,sorted(r))])[-2::-3]

Z pewnością więcej golfa jest możliwe.

Siatkówka, 157 151 134 133 124 124 123 bajtów

1 bajt off dzięki Martinowi Büttnerowi.

(.+),(.+)
$.1$*0$2,$.2$*0$1,
1
0x
+`(0x*)(,.*)0(x*),
$2,$1$3
{`,

(^|0x0xx0xx)
000
(0x*)(0x*)(0x*0)xx
$1x$2x$3
)`^0+
0
0x
1

Wypróbuj online!

Konwertuje na unary, a następnie powtórz następujące zamiany (pokazane tutaj po przecinku):

122 -> 000
0002 -> 1100 (this can also be 0012 -> 1110 and 1112 -> 2210 or even 2222 -> 3320 or even 3333 -> 4431)

Zasadniczo, gdy jest większy niż dwa: zabierz dwa, nie dodawaj nic do poprzedniej cyfry, dodaj jeden do poprzedniej cyfry, a następnie dodaj jeden do poprzedniej cyfry.

W pseudokodzie:

if(a[n]>2):
    a[n] -= 2;
    a[n-2] += 1;
    a[n-3] += 1;

Jednolite wdrożenie:

Każda cyfra (np. 3) Jest pokazana jako liczba xs (np. xxx), A następnie poprzedzona znakiem 0.

Na przykład 1234byłby wyrażony jako 0x0xx0xxx0xxxx.

Pozostawia to 0bez zmian, jak 101by to wyraził 0x00x.

Ponieważ początkowo i na końcu jest tylko 0i 1, konwersja może być łatwo wykonana przez 1->0xi 0x->1.

Kliknij tutaj, aby zobaczyć każdy krok .

JavaScript (ES6), 146 126 bajtów

r=n=>n&&n%2-r(n>>=1)-i(n)
i=n=>n&&r(n>>=1)-i(n)
g=(x,y,b=(x^y)&1)=>x|y&&b+2*g(b-x+y>>1,b-x-y>>1)
(x,y)=>g(r(x)+r(y),i(x)+i(y))

gprzekształca Gaussa całkowitą (rzeczywista i urojona) do podstawy i-1, a ri iprzetwarza podstawy i-1całkowitą w całkowitej Gaussa (części rzeczywistych i urojonych, odpowiednio). Kiedy konwersje są na miejscu, muszę tylko wykonać arytmetykę.

Edycja: Zapisano 20 bajtów, obliczając osobno rzeczywistą i urojoną część.

C ++ 416 bajtów plus #include <vector>\n#include <algorithm>\n(kolejne 40)

using I=int;using v=std::vector<I>;void r(v&x){v r{rbegin(x),rend(x)};x=r;}v a(v L,v R){r(L);r(R);L.resize(std::max(L.size(),R.size()));for(int&r:R)L[&r-R.data()]+=r;while(1){L.resize(L.size()+3);auto it=find(rbegin(L),rend(L),2);if(it==rend(L))break;I i=-1+it.base()-begin(L);i&&L[i+1]&&L[i-1]/2?L[i+1]=L[i]=L[i-1]=0:(++L[i+2],++L[i+3],L[i]=0);}L.erase( std::find(rbegin(L),rend(L),1).base(),end(L));r(L);return L;}

lub z większą ilością białych znaków:

using I=int;
using v=std::vector<I>;

void r(v&x){v r{rbegin(x),rend(x)};x=r;}
v a(v L,v R) {
  r(L);r(R);
  L.resize(std::max(L.size(),R.size()));
  for(int&r:R)
    L[&r-R.data()]+=r;
  while(1) {
    L.resize(L.size()+3);
    auto it=find(rbegin(L), rend(L), 2);
    if(it==rend(L)) break;
    I i=-1+it.base()-begin(L);
    i&&L[i+1]&&L[i-1]/2?
      L[i+1]=L[i]=L[i-1]=0
    :
      (++L[i+2],++L[i+3],L[i]=0);
  }
  L.erase( std::find(rbegin(L),rend(L),1).base(), end(L));
  r(L);
  return L;
}

Ledwo grał w golfa. Pobiera dane wejściowe jako wektor liczb całkowitych i zwraca wektor liczb całkowitych.

Przykład na żywo .