21
\$\begingroup\$

The Challenge

Given 3 numbers X, Y and Z in base B, find a Base in which the addition of X and Y yields Z. The inputs x = 20, Y = 12 and Z = 32 could yield 5 because 20 + 12 = 32 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 @Not that Charles for some examples of that).
  • The lowest possible base is 1. You may use 1s or 0s as the digits in unary, but you may not mix those.

I/O

  • The digits of the input numbers will be non-negative integers.
  • 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!

\$\endgroup\$
1

8 Answers 8

13
\$\begingroup\$

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.
\$\endgroup\$
0
11
\$\begingroup\$

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.

\$\endgroup\$
3
  • 5
    \$\begingroup\$ So this one takes unattractive as zeroes? \$\endgroup\$
    – anon
    Mar 25, 2016 at 14:27
  • 3
    \$\begingroup\$ @QPaysTaxes I'm guessing you meant unary, and yes. \$\endgroup\$
    – user45941
    Mar 25, 2016 at 23:36
  • 4
    \$\begingroup\$ @Mego I meant unary, autocorrect meant whatever it wanted to mean. \$\endgroup\$
    – anon
    Mar 25, 2016 at 23:36
10
\$\begingroup\$

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.

\$\endgroup\$
9
\$\begingroup\$

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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Mar 25, 2016 at 1:28
  • 1
    \$\begingroup\$ It's shorter to take the maximum after flattening: b<-[1+(maximum$id=<<l)..]. \$\endgroup\$
    – xnor
    Mar 25, 2016 at 1:41
  • 1
    \$\begingroup\$ Or, the test for maximum as b<-[1..],all(<b)$id=<<l. \$\endgroup\$
    – xnor
    Mar 25, 2016 at 1:50
  • \$\begingroup\$ 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. \$\endgroup\$
    – Denker
    Mar 25, 2016 at 10:15
  • \$\begingroup\$ @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. \$\endgroup\$
    – nimi
    Mar 25, 2016 at 17:53
8
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
1
  • 3
    \$\begingroup\$ unary is very unattractive by AutoCorrect these days \$\endgroup\$
    – Charlie
    Apr 3, 2016 at 0:24
2
+100
\$\begingroup\$

APL (Dyalog Unicode), 28 27 bytes (SBCS)

Saved 1 byte thanks to @Adám

{⍺←1+⌈/∊⍵⋄0=-/⍺⊥⍵:⍺⋄⍵∇⍨⍺+1}

Try it online!

Takes a matrix with columns x z y, with all of them padded with zeroes to have the same number of digits.

Explanation:

{
⍺←1+⌈/∊⍵                 ⍝ First base
      ∊⍵                ⍝ Flatten the input into a single vector of digits
     ⌈/                  ⍝ Maximum digit (reduce with max)
  1+                    ⍝Add one to that to get the lowest possible base

0=-/⍺⊥⍵                ⍝If this base works
 :⍺                     ⍝Return it
    ⍺⊥⍵                ⍝Convert to base ⍺
  -/                    ⍝Reduce with subtraction (x - (z - y)) = x + y - z
0=                      ⍝Check if it's 0 (the equation works)

⍵∇⍨⍺+1                  ⍝Otherwise, call itself (∇) with the next base
}
```
\$\endgroup\$
2
  • \$\begingroup\$ Take the input as a matrix instead of a vector of vectors to save a byte \$\endgroup\$
    – Adám
    Dec 23, 2020 at 0:00
  • \$\begingroup\$ @Adám Thanks. I have to go now, but I"ll update my answer when I have time \$\endgroup\$
    – user
    Dec 23, 2020 at 0:02
1
\$\begingroup\$

05AB1E (legacy), 6 bytes

ζÆ(I>M

Port of @Dennis's Jelly answer, so make sure to upvote him as well! The I/O is also in the same format, except with the input wrapped inside a list instead of three loose inputs: \$[Z,Y,X]\$, with little-endian digit order, using the digit \$0\$ for unary.

Try it online or verify all test cases.

The new 05AB1E version would require an additional leading 0 to overwrite the default space-filler of ζ. In the legacy 05AB1E version built in Python, the spaces are counted as 0 when we reduce by subtracting with Æ, though. Which would have given an error in the new version, which is built in Elixir.

Explanation:

        #  i.e. input = [[12,3],[88],[158,2]]
ζ       # Zip/transpose the (implicit) input-matrix, swapping rows/columns,
        # using a space filler by default if the rows doesn't have matching lengths
        #  STACK: [[12,88,158],[3," ",2]]
 Æ      # Reduce each inner-most list by subtracting, counting the spaces as 0
        #  STACK: [-234,1]
  (     # Negate each
        #  STACK: [234,-1]
   I>   # Push the input again, and increase each value by 1
        #  STACK: [234,-1],[[13,4],[89],[159,3]]
     M  # Push the largest value on the stack, which also looks inside (nested) lists
        #  STACK: [234,-1],[[13,4],[89],[159,3]],234
        # (after which this top value is output implicitly as result)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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