Dodawanie w bazie -1 + i

64

Liczby całkowite gaussowskieliczbami 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
Sp3000
źródło
Brak list cyfr?
CalculatorFeline
@CatsAreFluffy Przepraszamy, brak list cyfr.
Sp3000
96
Możesz zapisać jeden bajt, zmieniając -1+ina i-1w tytule.
mbomb007
1
Teraz potrzebujemy konwersji na odwrót. : P
Rɪᴋᴇʀ
3
Na świecie jest 1100 rodzajów ludzi. Ci, którzy rozumieją binarne, ci, którzy nie, ci, którzy mylą go z trójskładnikiem, ci, którzy mylą go z bazą 4, ci, którzy mylą go z bazą 5, ci, którzy mylą go z bazą -1 + i, ci, którzy mylą go z bazą 3 baza 6, ci, którzy mylą ją z bazą 7, ci, którzy mylą ją z bazą 8, ci, którzy mylą ją z bazą 9 ...
wizzwizz4 27.03.16

Odpowiedzi:

42

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 . 1

    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. 2)

    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 . 3)

    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 .


1 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ę.

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

3 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ą.

Dennis
źródło
7
To jest głęboka magia . Jakiego formatu input()oczekuje? (Dostaję, 21112gdy wprowadzę 10101, 11011.)
Tim Pederick
1
Nieważne; z uruchomioną wersją przetłumaczoną (wydaje się, że bezskutecznie) na Python 3. Działa poprawnie pod Pythonem 2 .
Tim Pederick
9
...W jaki sposób. Proszę. Wyjaśnić.
Nic Hartley
@QPaysTaxes Zredagowałem swoją odpowiedź.
Dennis
@Dennis Czy mógłbyś teraz wyjaśnić, dlaczego to działa? Na przykład dlaczego, d+8a nie powiedzmy d+9? W jaki sposób????
Nic Hartley,
16

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
Jakube
źródło
13

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.

feersum
źródło
Biorę to, a*a+b*b^58==0kiedy ai bsą odwrócone? Jak to działa?
xnor
@xnor Nie, a*a+b*b==58gdy jeden z nich ma 3, a drugi 7
feersum
1
Nie jest dla mnie oczywiste, że (3,7)to jedyna para, która daje cykl i potrzebuje specjalnej obudowy. Jeśli to prawda, musisz tylko sprawdzić (a,b)==(3,7)w tej kolejności, ponieważ (7,3)powtarza się (3,7), i może jest na to krótsze wyrażenie.
xnor
1
Teraz to jest gwarantowana mylić kogoś, kto nie wie (lub zapomina), że (a) ^jest XOR, nie potęgowanie, lub (b) XOR ma niższy priorytet niż +.
Tim Pederick
12

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 ...

Martin Ender
źródło
2
Nie, nie, wynik jest taki, jaki jest;)
Conor O'Brien
2
Niezły wynik -2i!
Nic Hartley
Łał. Nie widziałem tego rozwiązania, kiedy opublikowałem moje ... Znacznie lepsze od mojego rozwiązania.
Leaky Nun
@KennyLau Właśnie na to patrzyłem i pomyślałem: „hm, chyba powinienem był kiedyś wyjaśnić ...”
Martin Ender
...- 2i? Jest to liczba dziesiętna, ale program używa podstawy, która tego nie robi.
user75200
12

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. 1

    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 . 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.

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

2 Działa, ponieważ ostatnia cyfra, która anuluje, nie może być 3 .

Dennis
źródło
6

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.

Tim Pederick
źródło
Czy jesteś pewien, że Twój „detektor zerowy” jest wystarczający?
Jak
4
@Yakk: Może w skali od jednego do recenzowanego czasopisma, może dać to jeszcze bez kontrprób?
Tim Pederick
2

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 .

Leaky Nun
źródło
1

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ęść.

Neil
źródło
1

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 .

Jak
źródło