Minimum base to count to a string

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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','^

Answer 8

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.

Answer 9

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

Answer 10

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.

Answer 11

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;
}

Answer 12

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>

Answer 13

Vyxal, 74 bits^v2, 9.25 bytes

⇩:fGkrḟ›…β,

Try it Online!

Answer 14

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)")}

Answer 15

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.

Answer 16

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>';

Answer 17

Pascal, 217 B

Extended Pascal (as specified by ISO standard 10206) allows you to write (in your source code) integer literals up to base 36 (for example −16#fF denotes the value −255 decimal). To be functionally consistent, all number literals that are allowed in Pascal source code are allowed as user input, too: Therefore the built‑in procedures read/readLn/readStr accept strings constituting valid number literals in your Pascal source (and in fact all numeric representations defined by ISO standard 6093). The task can be boiled down to determining the minimal base:

program p(input,output);var U,P:string(65);Y,X:integer;begin read(U);Y:=2;for X:=1 to length(U)do
Y:=card([1..Y,1..index('0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ',U[X])]);writeStr(P,Y:1,'#',U);readStr(P,X);write(X,Y)end.

Ungolfed:

program minimumBaseToCountToAString(input, output);
    const
        { Pascal does not make any assertion with regard to character encoding
          (except that `'A' < 'Z'`/`'a' < 'z'` (subject to availability) and
          digit characters `'0'` through `'9'` are consecutive and ascending).
          Hence another mechanism needs to be sought. }
        digit = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
    type
        { A `type` range restriction will cause an error
          should we attempt to assign values outside of this range. }
        base = 2‥36;
    var
        unprocessed: string(62);
        { This size is sufficient for `'2#1010…0101'` on a 64‑bit system.
          However, it will not prevent `'36#ZZZ…ZZZ'` overflow mistakes. }
        prefixed: string(65);
        { Stores the value of the largest digit found + 1 (a. k. a. base). } 
        minimumBase: base value 2;
        { Cannot reuse variable since `minimumBase` needs to be printed, too. }
        number: integer;
    begin
        { Reads up to `unprocessed.capacity` characters from `input`
          and discards the remainder of the line. }
        readLn(unprocessed);
        { In Pascal `string` indices are `1`-based. }
        for number ≔ 1 to length(unprocessed) do
        begin
            { Determines the maximum of two values without calculating
              the potential new maximum multiple times.
              The Extended Pascal function `index` returns `0`
              if `representation[number]` is not found in `digit`. }
            minimumBase ≔ card([1‥minimumBase,
                                1‥index(digit, unprocessed[number])]);
        end;
        { The `:1` is necessary so the base specification does not get padded
          with an implementation-defined default number of space characters
          (possibly causing /trailing/ characters to spill over). }
        writeStr(prefixed, minimumBase:1, '#', unprocessed);
        { This performs the actual conversion honoring `minimumBase`. }
        readStr(prefixed, number);
        { I can count to potato! }
        writeLn(number, minimumBase);
    end.

Answer 18

Ruby -n, 46 bytes

x=0
1until(x=Integer($_,$.+=1)rescue p)
p x,$.

Attempt This Online!