Die Herausforderung
In Anbetracht 3 Zahlen X
, Y
und Z
in der Basis B
, einen findet B
ase , in dem die Zugabe X
und Y
Ausbeuten Z
. Die Eingänge x = 20
, Y = 12
und Z = 32
könnten ergeben , 5
weil 20 + 12 = 32
in 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 Code-Golf , 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 X
und Y
in 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!
Antworten:
Jelly,
16117 BytesDieser 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 .
quelle
Pyth, 13 Bytes
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.
quelle
Oktave,
67753832 BytesWeil "Schleife über ALLE Dinge" zu viel Arbeit ist.
Erfordert ein Auffüllen mit 0, um die Eingabearrays gleich groß zu machen, z. B .:
Da
0
wird zum Auffüllen verwendet,1
wird 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:
In diesem Fall gibt es keine Basisbeschränkungen, solange es größer als eine "Ziffer" ist. Nehmen Sie einfach das Element max von
z
(asz >= 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+y
undz
ist die Basis: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.quelle
Haskell,
9073 BytesAnwendungsbeispiel:
f [[3, 247],[7, 438],[11, 221]]
->464
.Probieren Sie einfach alle Basen aus
b
(wobeib
größer als das Maximum der Ziffern ist). Wählen Sie die erste wox+y==z
.Edit: @xnor hat viele Bytes gespart, indem vor allem die
import Data.Digits
.quelle
unDigits b
das, was ich denke, tut, sollte es kürzer sein, es alsfoldl(\x y->b*x+y)0
oder gleichwertig zu implementierenfoldl((+).(b*))0
.maximum
nach dem Abflachen:b<-[1+(maximum$id=<<l)..]
.maximum
asb<-[1..],all(<b)$id=<<l
.d
einer Basisnummerb
nicht0 <= d < b
so sein , dass für die Basis1
die einzig mögliche Ziffer ist0
?f [[0],[0],[0,0]]
bewertet zu1
.MATL , 20 Bytes
Die Eingabe erfolgt im Format (äußere geschweifte Klammern beachten):
Dies funktioniert in der aktuellen Version (15.0.0) .
Probieren Sie es online!
Erläuterung
quelle
MATL,
13 -12 BytesÜbersetzung meiner Octave-Antwort in MATL. (Meine erste MATL-Antwort!)
Z, X, Y
(oderZ, Y, X
wenn Sie es vorziehen, bin ich einfach)Probieren Sie es online!
Erläuterung
quelle