7
\$\begingroup\$

The Challenge

Input: alphanumeric string. You can assume that the string will only contain the characters [0-9A-Z]. This can come from a parameter, command line, or STDIN. Digits are always before letters in terms of the base. Think like an extended version of HEX.

Output X,Y Such that Y is the minimum base required to parse the string and X is the decimal value of the input string in that base.

Examples

Input: "1"

Output: 1,2

Input: "HELLOWORLD"

Output: 809608041709942,33

Scoring: This is a golf, so shortest code in bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Borderline dupe of Base X to base Y conversion. (And probably one or more of the other 370 existing questions which talk about bases). \$\endgroup\$ – Peter Taylor Apr 17 '15 at 19:11
  • \$\begingroup\$ @PeterTaylor I would argue that this is different from the Base X to Y conversion, primarily because you are not supplied with the start base. It is an additional calculation the program must make. As for the search link, that is why this is specifically tagged as base-conversion. \$\endgroup\$ – tfitzger Apr 17 '15 at 20:03
  • \$\begingroup\$ I said it was borderline dupe, not identical (although it does only take 5 or 6 chars in golfing languages to extract the base, so it's not exactly a non-trivial difference), and held back from casting a supervote to see whether others agreed. Since no-one else has cast a close vote yet, I'll post an answer. \$\endgroup\$ – Peter Taylor Apr 17 '15 at 22:00
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/40416/21348 (should it be tagged base-conversion?) \$\endgroup\$ – edc65 Apr 18 '15 at 9:31

15 Answers 15

4
\$\begingroup\$

Pyth, 23 bytes

Jmx+jkUTGdrz2KheSJ,iJKK

Try it online: Pyth Compiler/Executor

      UT       create the list [0, 1, 2, ..., 9]
    jk         join them, creates the string "0123456789"
   +    G      G is initialized with the alphabet, add both strings
               creates "0123456789abcdefghijklmnopqrstuvwxyz"
 m        rz2  maps each charater d of input().lower() to: 
  x      d         the index of d in "012...xyz"
J              store the resulting list of indices in J

   SJ          sorted(J) (doesn't sort J in place, but gives you a sorted copy)
  e            last element (=maximum)
 h             + 1
K              store result in K

 iJK           convert J from base K to base 10
,   K          create the tuple (iJK, K) and prints

Pyth, 16 bytes (?)

I'm not sure if this counts. The functionality I'm using was in Pyth for quite a while, but didn't work because of one stupid little bug. So the following code didn't work when the question was asked, although the docs said that it does.

DeGJ1#~J1#R,iGJJ

This defines a function e. Try it online.

This one was based a submission by @Reticality. He uses a different algorithm now though.

DeG               Define a function e(G):
   J1               J = 1
     #              while True:
      ~J1             J += 1
         #            try:
            izJ         convert z (=input) from base J into base 10
          R,izJJ        return tuple(base_10, J)
                      if exception (converting failed) do nothing
\$\endgroup\$
7
\$\begingroup\$

Python 2, 74 64 56 55 53 bytes

def f(x):a=ord(max(x))-54;a+=7*(a<8);print int(x,a),a

Call the function (i.e. f("HELLOWORLD")) and outputs to stdout (809608041709942 33)

This is case-sensitive, requiring upper case letters, and crashes for invalid input (e.g. "$^$%!(&£%)())

This code gets the max letter in the string (z>x>y>...>b>a>9>8>...>2>1>0) and gets the largest base needed to represent it.

Change the 54 into a 76 to make it work for lowercase (but no longer upper case).

\$\endgroup\$
  • \$\begingroup\$ Does Python not have a ++ operator? That'd save you 2 bytes \$\endgroup\$ – Cole Johnson Apr 17 '15 at 17:47
  • \$\begingroup\$ @ColeJohnson It does not. \$\endgroup\$ – user34736 Apr 17 '15 at 17:49
  • \$\begingroup\$ You can shorten if a<8:a+=7 to a+=7*(a<8). \$\endgroup\$ – xnor Apr 17 '15 at 21:42
  • \$\begingroup\$ Would a+=7*(8>a=ord(max(x))-54); work? It does in PHP. \$\endgroup\$ – Titus Jul 3 '16 at 15:51
6
\$\begingroup\$

APL (24)

{(B⊥D-1),B←⌈/D←⍵⍳⍨⎕D,⎕A}

This is a function that takes a string and returns two values, the value and the base.

      {(B⊥D-1),B←⌈/D←⍵⍳⍨⎕D,⎕A} 'DEADBEEF'
3735928559 16

Explanation:

  • ⎕D,⎕A: digits followed by letters
  • D←⍵⍳⍨: store in D the 1-based index of each character of ⍵ in the string of digits followed by letters
  • B←⌈/D: store in B the highest value in D. (which is the base to use)
  • (B⊥D-1): subtract 1 from each value in D (making them the values of the digits), and decode them as a base-B number.
\$\endgroup\$
  • \$\begingroup\$ The question specified bytes but it looks like you've counted characters. \$\endgroup\$ – Hugh Allen Apr 18 '15 at 17:18
  • \$\begingroup\$ The APL character set fits in a byte with room to spare. Here's IBM's standard. They don't have to be Unicode bytes. \$\endgroup\$ – marinus Apr 18 '15 at 17:41
4
\$\begingroup\$

Pure Bash, 48

for((b=37;$[--b]#$1;)){ :;}
echo $[$[++b]#$1],$b

Output

$ ./minbase.sh HELLOWORLD
./minbase.sh: line 1: ((: 32#HELLOWORLD: value too great for base (error token is "32#HELLOWORLD")
809608041709942,33
$ ./minbase.sh HELLOWORLD 2>/dev/null
809608041709942,33
$ ./minbase.sh 1 2>/dev/null
1,2
$ 

I'm taking advantage of this meta answer - specifically that warnings output to STDERR may be ignored.

\$\endgroup\$
4
\$\begingroup\$

J - 50 char

Worry not, Martin, I have come to restore order.

(>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower)

The u:(47+i.11),65+i.26 portion creates the string /0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ, and we want the slash so that when we find the largest digit of HELLOWORLD with >./@i., we correct an off-by-one error at no extra charge.

Then we use J's built-in base conversion by evaling e.g. 33bhelloworld; J has this weird internal language for specifying numbers, so we exploit that to do the base interpretation for us.

   (>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower) 'HELLOWORLD'
809608041709942 33
   f =: (>./@i.(u:(47+i.11),65+i.26&)(,&.":,[)'b',tolower)
   f '1'
1 2
   f 'POTATO'
627732894 30
   f '1FISH2FISH'
22338345482731 29
\$\endgroup\$
4
\$\begingroup\$

J, 31 bytes

3&u:(-47+7*60<]@)(>./(#.,[)<:@)

Usage:

   f=.3&u:(-47+7*60<]@)(>./(#.,[)<:@)

   f 'POTATO'
627732894 30
   f '1FISH2FISH'
22338345482731 29

1 byte thanks to @FUZxxl.

Try it online here.

\$\endgroup\$
  • \$\begingroup\$ Use u: instead of a.&i. I guess. \$\endgroup\$ – FUZxxl Apr 18 '15 at 12:15
  • 1
    \$\begingroup\$ @FUZxxl Right, 3&u: works. (The self-written adverbs got my full attention. I just understood them properly and they are quite useful for golfing.) \$\endgroup\$ – randomra Apr 18 '15 at 18:16
3
\$\begingroup\$

CJam (25 chars)

q{i48-_9>7*-}%_:e>):Zb',Z

Online demo

It's 28 chars in GolfScript, mainly because base doesn't have a one-char alias:

{48-.9>7*-}%.$-1=):^base','^
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 55 bytes

Hmmm, beating J with Mathematica? Something's fishy...

Print[f=FromDigits;f[#,y=f/@Max@Characters@#+1],",",y]&

This defines an unnamed function, which takes the string as a parameter and prints the result. You can either give it a name or use it directly:

Print[f=FromDigits;f[#,y=f/@Max@Characters@#+1],",",y]&@"HELLOWORLD"

The idea is pretty simple. Mathematica's integer parser supports bases up to 36 out of the box, so we only need to figure out the minimum base. We do that with

y=f/@Max@Characters@#+1

where # is the function's parameter and we've defined f as an alias of FromDigits. Note that FromDigits normally reads things in base 10, but that doesn't change the value of a single digit. Then we just use that to parse the string with f[#,y...] and the print the result, a comma and y.

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

J (61)

Explicit funcions in J can be... Somewhat hard to read.

3 :'(+/i*b^|.x:i.#y),b=.>:>./i=.(y i.~a.{~(48+i.10),65+i.26)'

Example usage:

   f=: 3 :'(+/i*b^|.x:i.#y),b=.>:>./i=.(y i.~a.{~(48+i.10),65+i.26)'
   f 'POTATO'
627732894 30
\$\endgroup\$
1
\$\begingroup\$

Rust (1.0 beta), 81 80 bytes

let f=|a|loop{for i in 2..{if let Ok(m)=u64::from_str_radix(a,i){return(m,i)}}};

Test:

fn main() {
    let f=|a|loop{for i in 2..{if let Ok(m)=u64::from_str_radix(a,i){return(m,i)}}};
    assert_eq!(f("1"), (1, 2));
    assert_eq!(f("POTATO"), (627732894, 30));
    assert_eq!(f("HELLOWORLD"), (809608041709942, 33));
    println!("ok!");
}

This is similar to all other answers, we try to parse the string into an integer using the internal function u32::from_str_radix, and start from base 2 and return immediately.

Rust is static-typed, and it requires all reachable branches to return the same type of value. The for loop is not infinite, so Rust would require a return value after the for loop. In order to make the type-checker happer, an outer infinite loop is added to make sure there is no other exit point. This saves 1 byte compared with returning a default value.

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

JavaScript, 100 89 bytes

Thanks to nderscore for saving 10 bytes!

Works for base-2 to base-36; that's all bases JavaScript's parseInt supports.

function b(s){for(i=1;(x=parseInt(s,++i))!=x|!x.toString(i)[s.length-1];);return x+","+i}

The code uses a for loop starting from 1 and tries to parse the int on base-N (I use N here as i + 1; i is incremented before parsing the number) is the current number in the loop. It checks whether the parsed int is not NaN (x==x is the shortest way, and it works because NaN != NaN). It also checks that the integer converted to base-N equals the original string; this is necessary because when JavaScript parses an int, only the first part has to be valid, so parseInt would be able to parse "abc" on base-11 because "a" is a valid base-11 integer (while "b" and "c" are not). If the input cannot be parsed in base-N, then the for loop continues until it finds the correct base; after the for loop, the function returns the base-10 number and the original base.

Ungolfed code:

function getBase(str) {
    for (var base = 1;
    (parsed = parseInt(s, ++base)) != parsed | !parsed.toString(base)[str.length - 1];);
    return parsed + "," + base;
}
\$\endgroup\$
  • \$\begingroup\$ -10 bytes: function b(s){for(i=1;(x=parseInt(s,++i))!=x||!x.toString(i)[s.length-1];);return x+","+i} \$\endgroup\$ – nderscore Apr 18 '15 at 5:32
  • \$\begingroup\$ @nderscore Nice, thanks! Now I could actually get -11 bytes, because the || operator can be shortened to the bitwise | operator, which still gives the same results here. \$\endgroup\$ – ProgramFOX Apr 18 '15 at 7:13
1
\$\begingroup\$

JavaScript (ES6) 70 72

The base is 1 more than the biggest digit in the string, so sort and find it.

Edit Save 2 bytes thx @nderscore (particularly, shame on me for using >= instead of >)

F=s=>(b=[...s].sort().pop().charCodeAt()-47,[parseInt(s,b-=b>8&&7),b])
// TEST:
C.innerHTML=F('1') + '\n' + F('HELLOWORLD')+ '\n' + F('POTATO')
<pre id=C></pre>

\$\endgroup\$
  • \$\begingroup\$ -2: F=s=>(b=[...s].sort().pop().charCodeAt()-47,[parseInt(s,b-=b>8&&7),b]) \$\endgroup\$ – nderscore Apr 18 '15 at 14:58
0
\$\begingroup\$

Swift, 105

Not very short and can probably be improved

func n(x:String) {var m=64;for c in x.utf8{m=max(Int(c),m)};println("\(strtoul(x,nil,10+m-64)),\(m-54)")}
\$\endgroup\$
0
\$\begingroup\$

Haskell, 97 bytes

import Data.Char
j x|x>64=x-54|1<2=x-47
l=j.ord
m=l.maximum
f x=(foldl(\a b->a*m x+l b-1)0 x,m x)

Example run:

*Main> map f ["HELLOWORLD", "POTATO", "1"]
[(809608041709942,33),(627732894,30),(1,2)]

It's so long because I need do import Data.Char for ord and I don't have a built in read function for integers of arbitrary base.

\$\endgroup\$
0
\$\begingroup\$

PHP (>=5.4), 90

(-2 for an anoynomous function in PHP 7; 74 for a snippet)

function f($s){$b+=7*(8>$b=ord(max(str_split($s)))-54);return[base_convert($s,$b,10),$b];}

Thanks @user34736 for the -54(+8) idea; saved two bytes on my -54/-47 approach.

The function returns an array instead of printing the result. +/-0 for printing:

function f($s){$b+=7*(8>$b=ord(max(str_split($s)))-54);echo base_convert($s,$b,10),",$b";}

but a return value is easier to test:

function test($x,$y,$e){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>$x</td><td>$y</td><td>$e</td><td>",(strcmp($y,$e)?'N':'Y'),"</td></tr>";$h='';}
foreach([1=>'1,2','HELLOWORLD'=>'809608041709942,33','ILOVECODEGOLF'=>'21537319965321352644,32','POTATO'=>'627732894,30','1FISH2FISH'=>'22338345482731,29']as$x=>$e)test($x,implode(',',f($x)),$e);echo'</table>';
\$\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.