X + Y = Z - mais dans quelle base?

20

Le défi

Étant donné 3 nombres X, Yet Zen base B, trouvez un Bas dans lequel l'addition de Xet Ydonne Z. Les intrants x = 20, Y = 12et Z = 32pourraient céder 5car 20 + 12 = 32en base 5.

  • Vous pouvez supposer qu'il y aura toujours une base dans laquelle l'addition est correcte (il y a des cas où aucune base n'existe, grâce à @ MasonWheeler et @ Not that Charles pour quelques exemples).
  • La base la plus basse possible est 1. Vous pouvez utiliser 1 ou 0 comme chiffres en unaire, mais vous ne pouvez pas les mélanger.

E / S

  • Les chiffres des nombres saisis seront des entiers non négatifs.
  • Vous pouvez supposer que les numéros d'entrée contiennent des zéros en tête, donc ils ont une longueur spécifique (ou tout de même).
  • Vous pouvez prendre les chiffres dans le format le plus pratique, tant qu'il n'est pas prétraité. Cela comprend le format général des trois numéros d'entrée et le format des chiffres de chacun de ces numéros. Veuillez indiquer clairement le format que vous utilisez.
  • S'il existe plusieurs bases possibles, vous pouvez générer toutes ou une seule d'entre elles.
  • Vous pouvez supposer que la base et les numéros d'entrée seront dans les limites numériques de votre langue.

Règles

Cas de test

Le format d'entrée est ici une liste d'entiers pour représenter chaque nombre. Les trois listes sont séparées par des virgules.
Notez qu'il existe parfois plusieurs bases possibles. Une seule solution (aléatoire) est sortie ici.

[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

Vous pouvez générer des cas de test supplémentaires avec ce programme Pyth . Entrez une base sur la première ligne et les valeurs décimales pour Xet Ysur les deux lignes suivantes.
Vous pouvez également utiliser ce programme Pyth pour créer plusieurs cas de test à la fois en utilisant des valeurs aléatoires. Entrez simplement la quantité souhaitée de cas de test dans l'entrée.

Codage heureux!

Denker
la source

Réponses:

12

Gelée, 16 11 7 octets

_/N,‘FṀ

Cette approche est fortement basée sur la réponse Octave de @ beaker .

Le format d'entrée est Z, Y, X , avec un ordre de chiffres en petit bout, en utilisant le chiffre 0 pour unaire.

Essayez-le en ligne! ou exécutez tous les cas de test .

Comment ça fonctionne

Plutôt que de tester de manière incrémentielle des bases potentielles, cela résout le polynôme qui correspond à la matrice P: = X + Y - Z . Cela renvoie soit le plus grand coefficient de P ≠ 0 - qui doit être une racine, car il existe au moins une base valide - soit le chiffre le plus élevé de X , Y et Z , incrémenté de 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
la source
11

Pyth, 13 octets

f!-FiRTQheSsQ

Attend Z, suivi de X et Y.

Suite de tests

Essentiellement, nous testons chaque base possible, en commençant à un de plus que le plus grand chiffre. Le test consiste à convertir chaque nombre en la base en question, puis à replier la soustraction sur les nombres et à annuler logiquement le résultat.

isaacg
la source
5
Donc celui-ci prend des zéros sans attrait?
Fund Monica's Lawsuit
3
@QPaysTaxes Je suppose que vous vouliez dire unaire, et oui.
Mego
4
@Mego, je voulais dire unaire, la correction automatique signifiait tout ce qu'elle voulait dire.
Fund Monica's Lawsuit
10

Octave, 67 75 38 32 octets

Parce que "boucler sur TOUTES les choses", c'est trop de travail.

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

Nécessite 0 padding pour rendre les tableaux d'entrée de la même taille, par exemple:

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

Depuis 0est utilisé pour le remplissage, 1est utilisé comme jeton pour unaire.

(Merci à @DenkerAffe pour la clarification de la question.)

Exemple de run sur ideone .


Brève explication:

Prenez un cas impliquant aucun portage:

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

Dans ce cas, il n'y a aucune restriction sur la base tant qu'elle est supérieure à n'importe quel "chiffre". Prenez simplement l'élément max de z(as z >= x,y) et ajoutez 1 (ou tout entier positif).

Dans le cas d'un report (sans report), nous avons dépassé la base dans l'une des colonnes et la différence entre x+yet zest la base:

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

Si la somme de la deuxième colonne dépassait également la base, nécessitant un report ainsi que le report, sa valeur serait base+(-1). Nous aurons eu une colonne quelque part à droite avec un report et aucun report qui a la valeur de base correcte (supérieure).

gobelet
la source
9

Haskell, 90 73 octets

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

Exemple d'utilisation: f [[3, 247],[7, 438],[11, 221]]-> 464.

Essayez simplement toutes les bases b(où best supérieur au maximum des chiffres). Choisissez le premier où x+y==z.

Edit: @xnor a sauvé de nombreux octets en se débarrassant principalement du import Data.Digits.

nimi
la source
1
Si unDigits bfait ce que je pense, il devrait être plus court à mettre en œuvre comme foldl(\x y->b*x+y)0ou de manière équivalente foldl((+).(b*))0.
xnor
1
Il est plus court de prendre l' maximumaprès aplatissement: b<-[1+(maximum$id=<<l)..].
xnor
1
Ou, le test pour maximumas b<-[1..],all(<b)$id=<<l.
xnor
Est-ce que cela fonctionne pour les entrées où la base 1 est la seule solution? Je ne peux pas exécuter cela avec les compilateurs en ligne que j'ai trouvés, donc je ne peux pas me tester moi-même.
Denker
@DenkerAffe: les chiffres dd'un bnuméro de base ne devraient-ils pas l' être 0 <= d < b, donc pour la base, 1le seul chiffre possible est 0? f [[0],[0],[0,0]]évalue à 1.
nimi
8

MATL , 20 octets

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

L'entrée est au format (notez les accolades extérieures):

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

Cela fonctionne dans la version actuelle (15.0.0) .

Essayez-le en ligne!

Explication

`        % 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
la source
8

MATL, 13 12 octets

--X>t~1G+hX>

Traduction de ma réponse Octave en MATL. (Ma première réponse MATL!)

  • L'ordre d'entrée est Z, X, Y(ou Z, Y, Xsi vous préférez, je suis facile)
  • Les tableaux d'entrée sont remplis de zéro à des longueurs égales
  • Prend sans attrait comme 1

Essayez-le en ligne!

Explication

--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
gobelet
la source
3
unary est très peu attrayant par la correction automatique ces jours-ci
Charlie