X + Y = Z - aber in welcher Basis?

20

Die Herausforderung

In Anbetracht 3 Zahlen X, Yund Zin der Basis B, einen findet Base , in dem die Zugabe Xund YAusbeuten Z. Die Eingänge x = 20, Y = 12und Z = 32könnten ergeben , 5weil 20 + 12 = 32in Basis 5.

  • Sie können davon ausgehen, dass es immer eine Basis gibt, in der die Addition korrekt ist (es gibt Fälle, in denen keine Basis existiert, dank @ MasonWheeler und @ Not that Charles für einige Beispiele dafür).
  • Die niedrigstmögliche Basis ist 1. Sie können Einsen oder Nullen als Ziffern in unary verwenden, aber Sie dürfen diese nicht mischen.

I / O

  • Die Ziffern der eingegebenen Zahlen sind nicht negative ganze Zahlen.
  • Sie können davon ausgehen, dass die Eingabenummern führende Nullen enthalten, also eine bestimmte (oder alle gleichen) Länge haben.
  • Sie können die Zahlen im bequemsten Format verwenden, sofern sie nicht vorverarbeitet wurden. Dies schließt das Gesamtformat der drei eingegebenen Zahlen und das Format der Ziffern jeder dieser Zahlen ein. Bitte machen Sie deutlich, welches Format Sie verwenden.
  • Wenn es mehrere mögliche Basen gibt, können Sie alle oder nur eine davon ausgeben.
  • Sie können davon ausgehen, dass die Basis- und die Eingabenummer innerhalb der numerischen Grenzen Ihrer Sprache liegen.

Regeln

  • Funktion oder Vollprogramm erlaubt.
  • Standardregeln für die Eingabe / Ausgabe.
  • Es gelten Standardlücken .
  • Dies ist , also gewinnt die niedrigste Byte-Anzahl. Tiebreaker ist eine frühere Vorlage.

Testfälle

Das Eingabeformat ist hier eine Liste von ganzen Zahlen, die für jede Zahl stehen. Die drei Listen sind durch Kommas getrennt.
Beachten Sie, dass manchmal mehrere Basen möglich sind. Hier wird nur eine (zufällige) Lösung ausgegeben.

[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], [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, 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

Mit diesem Pyth-Programm können Sie zusätzliche Testfälle generieren . Geben Sie eine Basis in der ersten Zeile und die Dezimalwerte für Xund Yin den folgenden zwei Zeilen ein.
Sie können mit diesem Pyth-Programm auch mehrere Testfälle gleichzeitig erstellen, indem Sie zufällige Werte verwenden. Geben Sie einfach die gewünschte Anzahl von Testfällen in die Eingabe ein.

Viel Spaß beim Codieren!

Denker
quelle

Antworten:

12

Jelly, 16 11 7 Bytes

_/N,‘FṀ

Dieser Ansatz basiert stark auf der Octave-Antwort von @beaker .

Das Eingabeformat ist Z, Y, X mit einer Little-Endian-Ziffernreihenfolge, wobei die Ziffer 0 für Unary verwendet wird.

Probieren Sie es online! oder führen Sie alle Testfälle aus .

Wie es funktioniert

Anstatt potenzielle Basen inkrementell zu testen, wird das Polynom gelöst, das dem Array P: = X + Y - Z entspricht . Dies gibt entweder den größten Koeffizienten von P ≠ 0 zurück - der eine Wurzel sein muss, da es mindestens eine gültige Basis gibt - oder die höchste Ziffer von X , Y und Z , inkrementiert um 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
quelle
11

Pyth, 13 Bytes

f!-FiRTQheSsQ

Erwartet Z, gefolgt von X und Y.

Testsuite

Im Wesentlichen testen wir jede mögliche Basis, beginnend mit einer Stelle mehr als der größten. Der Test besteht darin, dass wir jede Zahl in die fragliche Basis umwandeln, dann Subtraktion über die Zahlen falten und das Ergebnis logisch negieren.

isaacg
quelle
5
Also nimmt dieser als Nullen unattraktiv?
Fund Monica Klage
3
@ QPaysTaxes Ich nehme an, Sie meinten unary, und ja.
Mego
4
@Mego Ich meinte unär, Autokorrektur meinte was immer es bedeuten wollte.
Fund Monica's Lawsuit
10

Oktave, 67 75 38 32 Bytes

Weil "Schleife über ALLE Dinge" zu viel Arbeit ist.

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

Erfordert ein Auffüllen mit 0, um die Eingabearrays gleich groß zu machen, z. B .:

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

Da 0wird zum Auffüllen verwendet, 1wird als Token für unary verwendet.

(Danke an @DenkerAffe für die Klarstellung in der Frage.)

Probelauf auf ideone .


Kurze Erklärung:

Nehmen Sie einen Fall ohne Übertragungen:

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

In diesem Fall gibt es keine Basisbeschränkungen, solange es größer als eine "Ziffer" ist. Nehmen Sie einfach das Element max von z(as z >= x,y) und addieren Sie 1 (oder eine beliebige positive ganze Zahl).

Im Falle eines Carry-Outs (ohne Carry-In) haben wir die Basis in einer der Spalten überschritten und die Differenz zwischen x+yund zist die Basis:

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

Wenn die Summe der zweiten Spalte auch die Basis überschreitet und sowohl eine Ausführung als auch die Einarbeitung erfordert, wäre ihr Wert base+(-1). Irgendwo rechts haben wir eine Spalte mit einem Übertrag und keinem Übertrag, der den richtigen (größeren) Basiswert hat.

Becherglas
quelle
9

Haskell, 90 73 Bytes

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

Anwendungsbeispiel: f [[3, 247],[7, 438],[11, 221]]-> 464.

Probieren Sie einfach alle Basen aus b(wobei bgrößer als das Maximum der Ziffern ist). Wählen Sie die erste wo x+y==z.

Edit: @xnor hat viele Bytes gespart, indem vor allem die import Data.Digits.

nimi
quelle
1
Wenn unDigits bdas, was ich denke, tut, sollte es kürzer sein, es als foldl(\x y->b*x+y)0oder gleichwertig zu implementieren foldl((+).(b*))0.
Xnor
1
Es ist kürzer die nehmen maximumnach dem Abflachen: b<-[1+(maximum$id=<<l)..].
Xnor
1
Oder der Test für maximumas b<-[1..],all(<b)$id=<<l.
Xnor
Funktioniert dies für Eingaben, bei denen Basis 1 die einzige Lösung ist? Ich kann dies mit den gefundenen Online-Compilern nicht ausführen, daher kann ich mich nicht selbst testen.
Denker
@DenkerAffe: Sollten die Ziffern deiner Basisnummer bnicht 0 <= d < bso sein , dass für die Basis 1die einzig mögliche Ziffer ist 0? f [[0],[0],[0,0]]bewertet zu 1.
Nimi
8

MATL , 20 Bytes

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

Die Eingabe erfolgt im Format (äußere geschweifte Klammern beachten):

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

Dies funktioniert in der aktuellen Version (15.0.0) .

Probieren Sie es online!

Erläuterung

`        % 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
quelle
8

MATL, 13 - 12 Bytes

--X>t~1G+hX>

Übersetzung meiner Octave-Antwort in MATL. (Meine erste MATL-Antwort!)

  • Eingabereihenfolge ist Z, X, Y(oder Z, Y, Xwenn Sie es vorziehen, bin ich einfach)
  • Eingabearrays werden auf gleiche Länge mit Nullen aufgefüllt
  • Nimmt als 1 unattraktiv

Probieren Sie es online!

Erläuterung

--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
Becherglas
quelle
3
Unary ist sehr unattraktiv von AutoCorrect in diesen Tagen
Charlie