22
\$\begingroup\$

Given 3 integers, determine the lowest possible base for the first two integers to multiply into the third. If you think of the Answer to the Ultimate Question of Life, The Universe, and Everything, 6 * 9 == 42, is true in Base 13.

The inputs can include any numbers whose digits use the characters 0-9, a-z, and A-Z, where a equals 10 in Base 10, and Z is 61 in Base 10.

The inputs should be inputted in any way you like (except for hard-coding), and you can write either an individual function or an entire program.

The maximum base that must be considered is Base 62, and the minimum base is Base 2.

You can assume that the first two values are smaller than the third. You can also conclude that the minimum base is one greater than the highest digit/character from the inputs (for example, if the inputs are 3 1a 55, the minimum base would be Base 11, because a is the highest digit).

If there is no such base, return a junk value of your choice.

This is code golf, so the shortest code wins.

Test Cases

6 9 42     -->   13
a a 64     -->   16
aA bB 36jk -->   41
2 3 20     -->   <junk value>
10 10 100  -->   2
\$\endgroup\$
  • \$\begingroup\$ I think STDIN would probably be better, and either would be fine. \$\endgroup\$ – erdekhayser Oct 27 '14 at 12:17
  • \$\begingroup\$ @MartinBüttner So should I just allow input in either form? \$\endgroup\$ – erdekhayser Oct 27 '14 at 12:25
  • 1
    \$\begingroup\$ As a point of clarification what should be done if multiple bases are valid such as your last example (which has now been removed - it was 10*10=100) where it is also valid in base 10 and indeed any other base you care to mention... \$\endgroup\$ – Chris Oct 27 '14 at 17:28
  • 1
    \$\begingroup\$ @Kay If I define the positional system in base b in a general way like a_0 b^0 + a_1 b^1 + a_2 b^2 + ... (where a_0 is the least significant digit) than base 1 definitely makes sense. Furthermore, the OP's conclusion would also include base 1 in the search if the largest present digit is 0. \$\endgroup\$ – Martin Ender Oct 27 '14 at 17:44
  • 2
    \$\begingroup\$ About base 1, unary is a number system. en.m.wikipedia.org/wiki/Unary_numeral_system \$\endgroup\$ – erdekhayser Oct 27 '14 at 18:20
3
\$\begingroup\$

CJam, 52 51 48 bytes

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#

Test it here. The online tester doesn't support input via ARGV. The closest alternative is to put put the input like 6 9 42 into STDIN and use:

lS/:E;
63,{_E{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#

This prints -1 if no valid base up to 62 can be found.

Many thanks to Peter for the digit parsing code!

I fixed a lot of problems which added 14 bytes to the count. The following explanation is still for my original submission, and I'll update it some time tomorrow.

63,{_ea{i32b~\([G-35-9]=-_Xe>:X;}f%fbW%~*=\X>*}#
63,                                              "Push the array [0 1 .. 62].";
   {                                          }# "Find the first index for which the block returns
                                                  a truthy value.";
    _                                            "Duplicate the current base.";
     ea                                          "Read ARGV into an array of strings.";
       {                        }f%              "Apply this block to each character.";
        i32b                                     "Convert to code point, and then to base-32. The
                                                  most significant digit now identifies the 'type'
                                                  of digit.";
            ~\(                                  "Unwrap the array. Swap the digits. Decrement.";
               [G-35-9]                          "Push array [16 -35 -9] of digit offsets.";
                       =-                        "Select the relevant offset and subtract it from 
                                                  the least significant digit.";
                         _                       "Duplicate the current digit D.";
                          Xe>:X;                 "X := max(X,D). X is predefined as 1.";
                                   fb            "Convert all numbers to the current base.";
                                     W%          "Reverse the list of numbers.";
                                       ~         "Unwrap the array.";
                                        *=       "Multiply factors. Check equality with product.";
                                          \      "Swap result with current base.";
                                           X>    "Ensure base is greater than X.";
                                             *   "Multiply boolean results.";

The index is printed automatically at the end of the program.

\$\endgroup\$
  • \$\begingroup\$ In GS the digits can be parsed as 32base~\[-16.35 9]=+. I know CJam has shorter base conversion. \$\endgroup\$ – Peter Taylor Oct 27 '14 at 14:11
7
+200
\$\begingroup\$

APL (Dyalog Unicode), 30 bytesSBCS

⊢{3⊃e=×/2↑e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘,

Try it online!

Thanks to Adám for the help.

Explanation:

⊢{3⊃e=×/2↑e←⍵⊥⍺:⍵⋄⍺∇⍵+1}1+⌈/∘, ⍝ 
⊢                              ⍝ left argument ⍺: the vector (do nothing)
                        1+⌈/∘, ⍝ right argument ⍵: our starting base.
                             , ⍝             start by flattening the matrix of arguments                               ⌈/   ⍝             reduce by max (find the highest number)
                            ∘  ⍝             compose both of these together
                        1+     ⍝             increment by one
 {         ⍵⊥⍺         }       ⍝ convert inputs to the current base
 {       e←            }       ⍝ store the converted values in 3
 {      2↑             }       ⍝ take the first 2 values
 {    ×/               }       ⍝ multiply them together (reduce-multiply)
 {  e=                 }       ⍝ compare with e (the converted inputs)
 {3⊃                   }       ⍝ only keep the result of the comparison with the 3rd element (expected result)
 {             :⍵      }       ⍝ if truthy, return the current base.
 {               ⋄     }       ⍝ otherwise...
 {                ⍺∇⍵+1}       ⍝ ...recurse with the base incremented

We use a helper function, In, to receive the input into a more palatable format. Otherwise the input is received a matrix of 3 columns.

'3 9 42' would give, for example (read top-down then left-to-right):

0 0 4
3 9 2

And for 'aA bB 36jk' (same here. a is 10, b is 11, A is 36, etc)

 0  0  3
 0  0  6
10 11 19
36 37 20
\$\endgroup\$
2
\$\begingroup\$

Python 2 - 197 213

What a monster... (compared to CJam)

from string import*
I=raw_input()
x,y,z=I.split()
B=lambda s,b:sum(b**i*(digits+lowercase+uppercase).find(s[-i-1])for i in range(len(s)))
print([b for b in range(B(max(I),10)+1,62)if B(x,b)*B(y,b)==B(z,b)]+[0])[0]

Unfortunately int's base conversion can only handle bases up to 36. So I needed to implement it by myself. (See this wonderful solution.)

\$\endgroup\$
  • \$\begingroup\$ Does this make sure not to return a base less than or equal to the largest digits? \$\endgroup\$ – Martin Ender Oct 27 '14 at 17:04
  • \$\begingroup\$ @MartinBüttner: I'm not sure. At least not explicitly. Do you have a test case where this is an issue? (Actually, generating test cases should be taken care of by the OP...) \$\endgroup\$ – Falko Oct 27 '14 at 18:18
  • \$\begingroup\$ Try 2*3=20 which has base 3 in an error case. 3 is not a digit in a ternary numeral system. \$\endgroup\$ – kay Oct 27 '14 at 18:34
2
\$\begingroup\$

CJam, 53 bytes

lA,s'{,97>+'[,65>+f#_$W=1e>)63,>_@Wa/W%f{fb~*=}1#\0+=

Takes the three input from STDIN like

6 9 42

Prints 0 if product in any base is not possible

Will try to golf it further.

Try it here

\$\endgroup\$
1
\$\begingroup\$

JavaScript (E6) 129 139

Recursively try all bases from 2 up to 62, returning -1 if no value is ok.
JavaScript parseInt function works with base up to 36, so a little help is needed for greater bases.
Beware, the parameters x,y,z are strings, not numbers.
It's more difficult than it seems. Thanks to Martin for pointing out a basic bug in the first version.

F=(x,y,z,b=2,N=n=>[for(d of(t=0,n))t=(v=parseInt(d,36)+(d>'@'&d<'a')*26)<b?t*b+v:NaN]&&t)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1

Less golfed

F=(x,y,z,b=2,
   D=d=>parseInt(d,36)+(d>'@'&d<'a')*26, // parse a single digit
   N=n=>[for(d of(t=0,n))t=(v=D(d))<b?t*b+v:NaN]&&t // parse a string
)=>b<63?N(x)*N(y)!=N(z)?F(x,y,z,b+1):b:-1

Test In FireFox/FireBug console.
The test tries 1000 numbers with different bases (up to 36, not 62). It's worth noting that the found base could be correct but less than the base that generated the test case.

for(i=0;i<1000;i++)
{
   x=Math.random()*100|0,y=Math.random()*100|0,z=x*y,b=Math.random()*35+2|0
   bx=x.toString(b),by=y.toString(b),bz=z.toString(b),
   nb=F(bx,by,bz)
   nx=parseInt(bx,nb),ny=parseInt(by,nb),nz=parseInt(bz,nb)
   // if (nx*ny != nz) // uncomment to se output for errors only
     console.log(x,y,z,'base '+b,bx,by,bz, 'found base '+nb,nx,ny,nz,nx*ny)
}
\$\endgroup\$
  • \$\begingroup\$ @MartinBüttner the parameters are strings (as possible values are something like aA bB 36jk ...). Clarified in the answer. \$\endgroup\$ – edc65 Oct 28 '14 at 6:53
  • \$\begingroup\$ Oh right, that makes sense. \$\endgroup\$ – Martin Ender Oct 28 '14 at 6:57
1
\$\begingroup\$

Charcoal, 28 bytes

I⌊Φ…⊕⍘⌈⁺⁺θηζ⁶²¦⁶³⁼×⍘θι⍘ηι⍘ζι

Try it online! Link is to verbose version of code. Outputs None if no valid base can be found. Explanation:

         θ                      First input
        ⁺                       Concatenated with
          η                     Second input
       ⁺                        Concatenated with
           ζ                    Third input
      ⌈                         Maximum character (by ordinal)
     ⍘                          Converted from base
            ⁶²                  Literal 62
    ⊕                           Incremented
   …                            Range up to
               ⁶³               Literal 63
  Φ                             Filtered by
                    θ           First input
                   ⍘            Converted from base
                     ι          Current value
                  ×             Multiplied by
                       η        Second input
                      ⍘         Converted from base
                        ι       Current value
                 ⁼              Equals
                          ζ     Third input
                         ⍘      Converted from base
                           ι    Current value
 ⌊                              Minimum
I                               Cast to string
                                Implicitly print
\$\endgroup\$
  • \$\begingroup\$ Is it possible to have a TIO program that uses the actual code you posted? \$\endgroup\$ – mbomb007 Mar 6 at 19:18
  • \$\begingroup\$ @mbomb007 You can Try it online! but the AST generator seems to think is Any for some reason... \$\endgroup\$ – Neil Mar 6 at 21:14
0
\$\begingroup\$

Erlang (escript) - 200

main(X)->m(2,X).
m(63,_)->0;m(C,X)->try[F,G,I]=[c(0,C,Y)||Y<-X],I=F*G,io:fwrite("~p",[C])catch _:_->m(C+1,X)end.
c(A,B,[H|T])->D=H-if$A>H->$0;$a>H->29;0<1->87end,if D<B->c(A*B+D,B,T)end;c(A,_,_)->A.

Add two leading newlines which must be present.

In readable:

#!/usr/bin/env escript

main(Args) -> test(2, Args).

test(63, _) -> 0;
test(Base, Args) ->
    try
        [Factor1, Factor2, Product] = [convert(0, Base, Arg) || Arg <- Args],
        Product = Factor1 * Factor2,
        io:fwrite("~p", [Base])
    catch _:_ ->
        test(Base + 1, Args)
    end.

convert(Accumulator, Base, [Head|Tail]) ->
    Digit = Head - if Head < $A -> $0;
                      Head < $a -> $A - 10 - 26;
                      true      -> $a - 10
                   end,
    if Digit < Base ->
        convert(Accumulator * Base + Digit, Base, Tail)
    end;
convert(Accumulator, _, _) -> Accumulator.

Invocation:

$ escript x.erl 6 9 42
13
$ escript -i x.erl a a 64
16
$ escript -i x.erl aA bB 36jk
41
$ escript -i x.erl 2 3 20
(no output)
$ escript -i x.erl 10 10 100
2
\$\endgroup\$
  • \$\begingroup\$ Does this make sure not to return a base less than or equal to the largest digits? \$\endgroup\$ – Martin Ender Oct 27 '14 at 17:07
  • \$\begingroup\$ Yes, the if Digit < Base -> … end part takes care of it. If an if block has no true branch, then an exception is thrown, which gets caught in try … catch _:_ -> … end. \$\endgroup\$ – kay Oct 27 '14 at 17:10
0
\$\begingroup\$

Haskell 216 char (177?)

Tried to golf this as much as possible. If imports are counted, then this is my shortest code (216)

import Data.Char
import Data.List
m=maximum
j[]=0;j(x:_)=x
f=reverse.map(\x->ord x-48)
g[]_=0;g(m:n)x=m+x*g n x
main=do
l<-getLine
let k@[x,y,z]=words l
print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]

However, were imports not counted, then this is my best version (177):

import Data.Char
import Data.List
import Control.Applicative
m=maximum
j[]=0;j(x:_)=x
f=reverse.map(\x->ord x-48)
g[]_=0;g(m:n)x=m+x*g n x
main=words<$>getLine>>= \k@[x,y,z]->print$j[n|n<-[2..62],g(f x)n*g(f y)n==g(f z)n,n>(m.map(m.f)$k)]

This treats each number as a polynomial P(x) where x is the base, on condition that no coefficient is larger than x; I then evaluate the polynomials over each possible base, stopping when I reach one that satisfies the equality P(x)*Q(x)=R(x). The 'base is bigger than largest digit' rule is enforced with the last guard in the pattern match, namely n>(m.map(m.f)$k). I know that different golfing challenges and different challenge-makers have different policies regarding imports vis-a-vis scoring, so take the second one with a grain of salt.

\$\endgroup\$
  • \$\begingroup\$ The solutions are actually 216 and 177 bytes/characters, respectively. But the second solution is invalid, because imports are counted unless the OP explicitly specifies otherwise, which is not the case here as far as I can tell. \$\endgroup\$ – nyuszika7h Oct 27 '14 at 20:24
0
\$\begingroup\$

Prolog - 195 bytes

Basically the same idea as my Erlang answer:

:-use_module(library(main)).
main(A):-between(2,62,B),maplist(x(B),A,[F,G,P]),0is F*G-P,write(B).
c(I,B,Q,O):-Q=[H|T]->(H<65->D=48;H<97->D=29;D=87),H-D<B,c(I*B+H-D,B,T,O);O=I.
c(B)-->name,c(0,B).

In readable:

:- use_module(library(main)).

main(Args) :-
    between(2, 62, Base),
    maplist(convert(Base), Args, [Factor1, Factor2, Product]),
    0 is Factor1 * Factor2 - Product,
    write(Base).

convert(Accumulator, Base, List, Output) :-
    List = [Head|Tail] ->
        (   Head < 65 -> Offset = 48;
            Head < 97 -> Offset = 29;
                         Offset = 87),
        Head - Offset < Base,
        convert(Accumulator * Base + Head - Offset, Base, Tail, Output);
    Output = Accumulator.

convert(Base, Input, Output) :-
    name(Input, List),
    convert(0, Base, List, Output).

Invocation:

$ swipl -qg main x.pl 6 9 42
13
$ swipl -qg main x.pl aA bB 36jk
41
$ swipl -qg main x.pl 2 3 20
ERROR: Unknown message: goal_failed(main([2,3,20]))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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