X + Y = Z - ale w jakiej bazie?

20

Wyzwanie

Biorąc pod uwagę 3 numery X, Ya Zw bazie B, znaleźć BASE, w którym dodawanie Xi Yrentowności Z. Wejścia x = 20, Y = 12i Z = 32może przynieść 5ponieważ 20 + 12 = 32w podstawie 5.

  • Możesz założyć, że zawsze będzie podstawa, w której dodanie jest poprawne (są przypadki, w których nie istnieje podstawa, dzięki @ MasonWheeler i @ Not that Charles za kilka przykładów tego).
  • Najniższa możliwa podstawa to 1. Możesz użyć 1 lub 0 jako cyfr w jedności, ale nie możesz ich mieszać.

I / O

  • Cyfry liczb wejściowych będą nieujemnymi liczbami całkowitymi.
  • Możesz założyć, że liczby wejściowe zawierają zera wiodące, więc mają określoną (lub taką samą) długość.
  • Możesz wziąć liczby w najwygodniejszym formacie, o ile nie są one wstępnie przetworzone. Obejmuje to ogólny format trzech liczb wejściowych i format cyfr każdej z tych liczb. Wyjaśnij, którego formatu używasz.
  • Jeśli istnieje wiele możliwych zasad, możesz wypisać wszystkie lub tylko jedną z nich.
  • Możesz założyć, że numery bazowe i wejściowe mieszczą się w granicach liczbowych twojego języka.

Zasady

Przypadki testowe

Format wejściowy to lista liczb całkowitych reprezentujących każdą liczbę. Trzy listy są oddzielone przecinkami.
Pamiętaj, że czasami istnieje wiele baz. Wyświetlane jest tylko jedno (losowe) rozwiązanie.

[12, 103], [4, 101], [16, 204] -> 349
[4, 21, 25], [5, 1, 20], [9, 23, 17] -> 28
[16, 11], [25, 94], [41, 105] -> 147
[2, 140], [21, 183], [24, 100] -> 223
[8, 157], [1, 28], [9, 185] -> 227
[2, 158], [88], [3, 12] -> 234
[8, 199], [1, 34], [9, 233] -> 408
[3, 247], [7, 438], [11, 221] -> 464
[3, 122], [3, 2], [6, 124] -> 480
[6, 328], [3, 31], [9, 359] -> 465
[2, 1, 0, 0, 0, 0], [1, 2, 0, 0, 1, 0, 1, 0], [1, 2, 2, 1, 1, 0, 1, 0] - > 3
[16, 105], [16, 120], [33, 84] -> 141
[15, 60], [9, 30], [24, 90] -> 268
[2, 0], [1, 2], [3, 2] -> 5
[1, 3, 3, 7], [1, 2, 3], [1, 4, 6, 0] -> 10
[0], [1, 12, 8], [1, 12, 8] -> 16
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1], [1, 0, 0, 1, 0, 1, 1, 1, 0, 0 , 1], [1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0] -> 2
[1], [1], [1,1] -> 1

Za pomocą tego programu Pyth można generować dodatkowe przypadki testowe . Wpisz bazę na pierwszej linii i wartości dziesiętnych Xi Yna dwóch liniach.
Możesz także użyć tego programu Pyth do tworzenia wielu przypadków testowych jednocześnie przy użyciu losowych wartości. Wystarczy wprowadzić żądaną liczbę przypadków testowych w danych wejściowych.

Happy Coding!

Denker
źródło

Odpowiedzi:

12

Galaretka, 16 11 7 bajtów

_/N,‘FṀ

To podejście jest w dużej mierze oparte na odpowiedzi Octave @ zlewki .

Format wejściowy to Z, Y, X , z kolejnością cyfr little-endian, przy użyciu cyfry 0 dla jedności.

Wypróbuj online! lub uruchom wszystkie przypadki testowe .

Jak to działa

Zamiast stopniowo testowania potencjalnych zasady, to rozwiązuje wielomianu który odpowiada tablicy P: = X + Y - . Zwraca albo największy współczynnik P ≠ 0 - który musi być pierwiastkiem, ponieważ istnieje co najmniej jedna ważna podstawa - lub najwyższą cyfrą X , Y i Z , zwiększoną o 1 .

_/N,‘FṀ  Main link. Argument: [Z, Y, X]

_/       Reduce by subtraction; yield Z - X - Y.
         This works since Z must have at least as many digits as X and Y.
  N      Negate to yield X + Y - Z.
    ‘    Yield [Z, Y, X], with all digits increments by 1.
   ,     Pair the results to the left and to the right.
     F   Flatten the resulting, nested list.
      Ṁ  Compute the maximum.
Dennis
źródło
11

Pyth, 13 bajtów

f!-FiRTQheSsQ

Oczekuje Z, a następnie X i Y.

Zestaw testowy

Zasadniczo testujemy każdą możliwą bazę, zaczynając od jednej więcej niż największej cyfry. Test polega na tym, że konwertujemy każdą liczbę na daną podstawę, a następnie rozkładamy odejmowanie na liczbach i logicznie negujemy wynik.

isaacg
źródło
5
Więc ten przyjmuje nieatrakcyjne jako zera?
Pozew Fund Moniki w dniu
3
@QPaysTaxes Zgaduję, że miałeś na myśli jedność i tak.
Mego
4
@Mego Miałem na myśli jedność, autokorekta oznaczała wszystko, co chciała znaczyć.
Pozew Fund Moniki w dniu
10

Oktawa, 67 75 38 32 bajty

Ponieważ „zapętlenie WSZYSTKICH rzeczy” to zbyt wiele pracy.

@(x,y,z)max([m=max(x+y-z) z])+~m

Wymaga wypełnienia 0, aby tablice wejściowe miały ten sam rozmiar, np .:

[2, 158],[88],[3, 12]
becomes
[2, 158],[0, 88],[3, 12]

Ponieważ 0jest używany do wypełniania, 1służy jako token dla unary.

(Podziękowania dla @DenkerAffe za wyjaśnienie w pytaniu.)

Próbka uruchomiona na ideone .


Krótkie wyjaśnienie:

Weź sprawę bez noszenia:

   [ 8, 199]
 + [ 1,  34]
 -------------
     9, 233
 - [ 9, 233]
 -------------
     0,   0 --- no carries

W takim przypadku nie ma żadnych ograniczeń bazowych, o ile jest ona większa niż jakakolwiek „cyfra”. Po prostu weź maksymalny element z(as z >= x,y) i dodaj 1 (lub dowolną dodatnią liczbę całkowitą).

W przypadku przeprowadzenia (bez przeniesienia) przekroczyliśmy bazę w jednej z kolumn, a różnica między x+yi zjest bazą:

   [ 2, 140]
 + [21, 183]
--------------
    23, 323
 - [24, 100]
 -------------
    -1  223
     ^   ^------ base
     |---------- carry in

Gdyby suma drugiej kolumny również przekroczyła podstawę, wymagając zarówno przeniesienia, jak i przeniesienia, jego wartość wyniosłaby base+(-1). Będziemy mieć kolumnę gdzieś po prawej stronie z przeprowadzeniem i żadne przeniesienie, które ma poprawną (większą) wartość bazową.

zlewka
źródło
9

Haskell, 90 73 bajtów

f l=[b|b<-[1..],all(<b)$id=<<l,[x,y,z]<-[foldl((+).(b*))0<$>l],x+y==z]!!0

Przykład użycia: f [[3, 247],[7, 438],[11, 221]]-> 464.

Po prostu wypróbuj wszystkie zasady b(gdzie bjest większa niż maksymalna liczba cyfr). Wybierz pierwszy gdzie x+y==z.

Edycja: @xnor zapisał wiele bajtów, przede wszystkim pozbywając się import Data.Digits.

nimi
źródło
1
Jeśli unDigits bzrobi to, co myślę, wdrożenie powinno być krótsze foldl(\x y->b*x+y)0lub równoważne foldl((+).(b*))0.
xnor
1
Jest krótszy do podjęcia maximumpo spłaszczeniu: b<-[1+(maximum$id=<<l)..].
xnor
1
Lub test na maximumjak b<-[1..],all(<b)$id=<<l.
xnor
Czy to działa w przypadku danych wejściowych, gdzie jedyne rozwiązanie to podstawa 1? Nie mogę wykonać tego za pomocą kompilatorów internetowych, które znalazłem, więc nie mogę się przetestować.
Denker,
@DenkerAffe: czy cyfry numeru dpodstawowego nie powinny bbyć 0 <= d < b, więc dla podstawy 1jedyną możliwą cyfrą jest 0? f [[0],[0],[0,0]]ocenia na 1.
nimi
8

MATL , 20 bajtów

`GY:@XJZQ2:"wJZQ-]]J

Dane wejściowe mają format (zwróć uwagę na zewnętrzne nawiasy klamrowe):

{[4, 21, 25],[5, 1, 20],[9, 23, 17]}

Działa to w aktualnej wersji (15.0.0) .

Wypróbuj online!

Wyjaśnienie

`        % do...while index
  G      %   push input. First time pushed nothing but asks for input implicitly
  Y:     %   unpack the cell array, pushing the three numeric arrays
  @      %   loop index: candidate base
  XJ     %   copy into clipboard J
  ZQ     %   evaluate polynomial: interpret third array in that base
  2:"    %   for loop: do this twice (subtract the other numbers from the third)
    w    %     swap, to process another array
    J    %     push base
    ZQ   %     evaluate polynomial: interpret array in that base
    -    %     subtract
  ]      %   end for loop. A result 0 indicates a solution has been found
]        % end do....while loop. Exit if top of stack is 0
J        % push found base. Implicitly display
Luis Mendo
źródło
8

MATL, 13 12 bajtów

--X>t~1G+hX>

Tłumaczenie mojej odpowiedzi Octave na MATL. (Moja pierwsza odpowiedź MATL!)

  • Kolejność wprowadzania jest Z, X, Y(lub Z, Y, Xjeśli wolisz, jestem łatwa)
  • Tablice wejściowe są wypełnione zerami do równych długości
  • Traktuje jako nieatrakcyjne jako 1

Wypróbuj online!

Wyjaśnienie

--X>t~1G+hX>

--            % M = Z - X - Y
  X>          % P = max(M)
    t~        % Duplicate and negate
      1G      % Push 1st argument (Z) 
        +     % ~P + Z
         h    % Concatenate [P (~P + Z)]
          X>  % Return max
zlewka
źródło
3
unary jest obecnie bardzo nieatrakcyjne przez Autokorekty
Charlie