Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The Challenge

Given 3 numbers X, Y and Z in base B, find a B in which the addition of X and Y yields Z. The inputs x = 2 0, Y = 1 2 and Z = 3 2 could yield 5 because 2 0 + 1 2 = 3 2 in base 5.

  • You may assume that there will always be a base in which the addition is correct (there are cases where no base exists, thanks to@MasonWheeler and @NotthatCharles for some examples of that).
  • The digits of the input numbers will be non-negative integers.
  • The lowest possible base is 1. You may use 1s or 0s as the digits in unary, but you may not mix those.
  • You may assume that the input numbers contain leading zeros, so the have a specific (or all the same) length.
  • You may take the numbers in the most convenient format, as long as it's not preprocessed. This includes the overall format of the three input numbers and the format of the digits of each of those numbers. Please make it clear which format you use.
  • If there are multiple possible bases, you can output all or just one of them.
  • You may assume that the base and the input numbers will be within the numerical limits of your language.

Rules

Test cases

Input format here is a list of integers to represent each number. The three lists are separated by commas.
Note that there are sometimes multiple bases possible. Only one (random) solution is outputted here.

[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

You can generate additional test cases with this Pyth program. Enter a base on the first line and the decimal values for X and Y on the following two lines.
Also you can use this Pyth program to create multiple test cases at once by using random values. Just enter the desired amount of test cases in the input.

Happy Coding!

share|improve this question
4  
Very similar: Determine the Base where a Given Equation is True – Geobits Mar 24 at 18:15
up vote 8 down vote accepted

Jelly, 16 11 7 bytes

_/N,‘FṀ

This approach is heavily based on @beaker's Octave answer.

Input format is Z, Y, X, with little-endian digit order, using the digit 0 for unary.

Try it online! or run all test cases.

How it works

Rather than incrementally testing potential bases, this solves the polynomial that corresponds to the array P := X + Y - Z. This returns either the largest coefficient of P ≠ 0 – which has to be a root, since there is at least one valid base – or the highest digit of X, Y and Z, incremented by 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.
share|improve this answer
    
Sweet! I can't wait to see how it works! – beaker Mar 26 at 16:10

Pyth, 13 bytes

f!-FiRTQheSsQ

Expects Z, followed by X and Y.

Test suite

Essentially, we test every possible base, starting at one more than the largest digit. The test is that we convert each number to the base in question, then fold subtraction over the numbers, and logically negate the result.

share|improve this answer
3  
So this one takes unattractive as zeroes? – QPaysTaxes Mar 25 at 14:27
1  
@QPaysTaxes I'm guessing you meant unary, and yes. – Mego Mar 25 at 23:36
2  
@Mego I meant unary, autocorrect meant whatever it wanted to mean. – QPaysTaxes Mar 25 at 23:36

Haskell, 90 73 bytes

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

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

Simply try all bases b (where b is greater than the maximum of the digits). Pick the first one where x+y==z.

Edit: @xnor saved many bytes by primarily getting rid of the import Data.Digits.

share|improve this answer
1  
If unDigits b does what I think, it should be shorter to implement as foldl(\x y->b*x+y)0 or equivalently foldl((+).(b*))0. – xnor Mar 25 at 1:28
1  
It's shorter to take the maximum after flattening: b<-[1+(maximum$id=<<l)..]. – xnor Mar 25 at 1:41
1  
Or, the test for maximum as b<-[1..],all(<b)$id=<<l. – xnor Mar 25 at 1:50
    
Does this work for input where base 1 is the only solution? I can't execute this with the online compilers I found, so I can't test myself. – DenkerAffe Mar 25 at 10:15
    
@DenkerAffe: shouldn't the digits d of a base b number be 0 <= d < b, so for base 1 the only possible digit is 0? f [[0],[0],[0,0]] evaluates to 1. – nimi Mar 25 at 17:53

MATL, 20 bytes

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

Input is in the format (note outer curly braces):

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

This works in current version (15.0.0).

Try it online!

Explanation

`        % 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
share|improve this answer

Octave, 67 75 38 32 bytes

Because "loop over ALL the things" is too much work.

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

Requires 0 padding to make the input arrays the same size, e.g.:

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

Since 0 is used for padding, 1 is used as the token for unary.

(Thanks to @DenkerAffe for clarification in the question.)

Sample run on ideone.


Short Explanation:

Take a case involving no carries:

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

In this case there are no restrictions on base as long as it's greater than any "digit". Simply take the max element of z (as z >= x,y) and add 1 (or any positive integer).

In the case of a carry-out (with no carry-in), we've exceeded the base in one of the columns and the difference between x+y and z is the base:

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

If the second column's sum also exceeded the base, requiring a carry-out as well as the carry-in, its value would be base+(-1). We will have had a column somewhere to the right with a carry-out and no carry-in that has the correct (greater) base value.

share|improve this answer

MATL, 13 12 bytes

--X>t~1G+hX>

Translation of my Octave answer into MATL. (My first MATL answer!)

  • Input order is Z, X, Y (or Z, Y, X if you prefer, I'm easy)
  • Input arrays are zero-padded to equal lengths
  • Takes unattractives as 1

Try it online!

Explanation

--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
share|improve this answer
    
unary is very unattractive by AutoCorrect these days – Charlie Apr 3 at 0:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.