31
\$\begingroup\$

Here's a nice easy challenge:

Given a string that represents a number in an unknown base, determine the lowest possible base that number might be in. The string will only contain 0-9, a-z. If you like, you may choose to take uppercase letters instead of lowercase, but please specify this. You must output this lowest possible base in decimal.

Here is a more concrete example. If the input string was "01234", it is impossible for this number to be in binary, since 2, 3, and 4 are all undefined in binary. Similarly, this number cannot be in base 3, or base 4. Therefore, this number must be in base-5, or a higher base, so you should output '5'.

Your code must work for any base between base 1 (unary, all '0's) and base 36 ('0-9' and 'a-z').

You may take input and provide output in any reasonable format. Base-conversion builtins are allowed. As usual, standard loopholes apply, and the shortest answer in bytes is the winner!

Test IO:

#Input          #Output
00000       --> 1
123456      --> 7
ff          --> 16
4815162342  --> 9
42          --> 5
codegolf    --> 25
0123456789abcdefghijklmnopqrstuvwxyz    --> 36
\$\endgroup\$
  • 8
    \$\begingroup\$ Can I output in base 36? \$\endgroup\$ – Leaky Nun Aug 23 '16 at 4:42
  • 9
    \$\begingroup\$ @LeakyNun Geez, I hope not. \$\endgroup\$ – Dennis Aug 23 '16 at 5:22
  • 4
    \$\begingroup\$ @LeakyNun You must output this lowest possible base in decimal. \$\endgroup\$ – DJMcMayhem Aug 23 '16 at 6:09
  • 3
    \$\begingroup\$ @RohanJhunjhunwala If that's your languages closest equivalent to a string, I don't see why not. \$\endgroup\$ – DJMcMayhem Aug 23 '16 at 6:16
  • 3
    \$\begingroup\$ Usually unary is all 1s, and leading zeros are not standard for any positional-based numeric system. \$\endgroup\$ – OrangeDog Aug 23 '16 at 10:35

34 Answers 34

16
\$\begingroup\$

Jelly, 4 bytes

ṀØBi

Requires uppercase. Try it online! or verify all test cases.

How it works

ṀØBi  Main link. Arguments: s (string)

Ṁ     Yield the maximum of s.
 ØB   Yield "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".
   i  Find the 1-based index of the maximum in that string.
\$\endgroup\$
  • 1
    \$\begingroup\$ It's actually 7 bytes, not 4. The first 2 chars are multi-byte. \$\endgroup\$ – Nicomak Aug 23 '16 at 9:08
  • 14
    \$\begingroup\$ @Nicomak This answer is encoded in the Jelly code page, where all of these characters are encoded as 1 byte each. \$\endgroup\$ – Loovjo Aug 23 '16 at 10:31
26
\$\begingroup\$

Python, 27 22 bytes

lambda s:(max(s)-8)%39

This requires the input to be a bytestring (Python 3) or a bytearray (Python 2 and 3).

Thanks to @AleksiTorhamo for golfing off 5 bytes!

Test it on Ideone.

How it works

We begin by taking the maximum of the string. This the code points of letters are higher than the code points of digits, this maximal character is also the maximal base 36 digit.

The code point of '0' – '9' are 48 – 57, so we must subtract 48 from their code points to compute the corresponding digits, or 47 to compute the lowest possible base. Similarly, the code points of the letters 'a' – 'z' are 97 – 122. Since 'a' represents the digit with value 10, we must subtract 87 from their code points to compute the corresponding digits, or 86 to compute the lowest possible base. One way to achieve this is as follows.

The difference between 97 and 58 (':', the character after '9') is 39, so taking the code points modulo 39 can achieve the subtraction. Since 48 % 39 = 9, and the desired result for the character '0' is 1, we first subtract 8 before taking the result modulo 39. Subtracting first is necessary since otherwise 'u' % 39 = 117 % 39 = 0.

c    n    n-8    (n-8)%39
0    48    40     1
1    49    41     2
2    50    42     3
3    51    43     4
4    52    44     5
5    53    45     6
6    54    46     7
7    55    47     8
8    56    48     9
9    57    49    10
a    97    89    11
b    98    90    12
c    99    91    13
d   100    92    14
e   101    93    15
f   102    94    16
g   103    95    17
h   104    96    18
i   105    97    19
j   106    98    20
k   107    99    21
l   108   100    22
m   109   101    23
n   110   102    24
o   111   103    25
p   112   104    26
q   113   105    27
r   114   106    28
s   115   107    29
t   116   108    30
u   117   109    31
v   118   110    32
w   119   111    33
x   120   112    34
y   121   113    35
z   122   114    36
\$\endgroup\$
  • \$\begingroup\$ If you make it Python 3, and take the input as a byte string, you can drop the ord() and win by 3 bytes. :) \$\endgroup\$ – Aleksi Torhamo Aug 23 '16 at 2:22
  • \$\begingroup\$ Nice idea! Let me ask the OP. \$\endgroup\$ – Dennis Aug 23 '16 at 2:25
  • 3
    \$\begingroup\$ @AleksiTorhamo NOOOOOOOOOOOO y u do dis \$\endgroup\$ – Rɪᴋᴇʀ Aug 23 '16 at 2:42
20
\$\begingroup\$

Python, 25 bytes

lambda x:int(max(x),36)+1

Defines a lambda that takes the string x. Finds the largest digit in the string (sorted with letters above digits, by python's default), and converts to base 36. Adds 1, because 8 is not in base 8.

\$\endgroup\$
11
\$\begingroup\$

Haskell, 34 bytes

f s=length['\t'..maximum s]`mod`39

Uses the mod(ord(c)-8,39) idea from Dennis.

41 bytes

g '0'=1
g 'W'=1
g x=1+g(pred x)
g.maximum

45 bytes:

(`elemIndex`(['/'..'9']++['a'..'z'])).maximum

Outputs like Just 3.

\$\endgroup\$
6
\$\begingroup\$

Cheddar, 34 29 21 bytes

Saved 8 bytes thanks to Dennis!!!

s->(s.bytes.max-8)%39

Uses lowercase letters

Try it online

Explanation

s -> (      // Input is `s`
  s.bytes    // Returns array of char codes
   .max      // Get maximum item in array
) % 39      // Modulus 39
\$\endgroup\$
  • 1
    \$\begingroup\$ Or you could just put quotes around the input \$\endgroup\$ – DJMcMayhem Aug 23 '16 at 0:26
  • 12
    \$\begingroup\$ @DJMcMayhem .___. i didn't even know my own language could do that \$\endgroup\$ – Downgoat Aug 23 '16 at 0:37
  • \$\begingroup\$ How about (-)&8 instead of n->n-8? \$\endgroup\$ – Conor O'Brien Aug 23 '16 at 1:23
  • \$\begingroup\$ @ConorO'Brien >_>_>_> I haven't gotten to that yet. I was just planning to do it and then this challenge was posted. Bassically f&n bonds n to first arg of the function. \$\endgroup\$ – Downgoat Aug 23 '16 at 1:49
  • \$\begingroup\$ @Downgoat Oh. >_> \$\endgroup\$ – Conor O'Brien Aug 23 '16 at 1:49
6
\$\begingroup\$

05AB1E, 6 bytes

{¤36ö>

Takes letters in upper case.

Explanation

{       # sort
 ¤      # take last
  36ö   # convert from base 36 to base 10
     >  # increment

Try it online

\$\endgroup\$
  • \$\begingroup\$ Forgive my naivete with 05AB1E, but do you mean convert FROM base 36 (to base 10)? \$\endgroup\$ – Keeta Aug 23 '16 at 18:30
  • \$\begingroup\$ @Keeta You are of course correct. My bad. \$\endgroup\$ – Emigna Aug 23 '16 at 18:33
5
\$\begingroup\$

Actually, 6 bytes

M6²@¿u

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Julia, 22 bytes

!s=(maximum(s)-'')%39

There's a BS character (0x08) between the quotes. Try it online!

\$\endgroup\$
  • \$\begingroup\$ what does the -'' do? \$\endgroup\$ – Downgoat Aug 23 '16 at 0:53
  • \$\begingroup\$ It subtracts 8 from the code point and returns an integer. \$\endgroup\$ – Dennis Aug 23 '16 at 0:56
4
\$\begingroup\$

JavaScript (ES6), 41 37 bytes

s=>parseInt([...s].sort().pop(),36)+1

Edit: Saved 4 bytes thanks to @edc65.

\$\endgroup\$
  • \$\begingroup\$ use pop() to save 4 \$\endgroup\$ – edc65 Aug 23 '16 at 8:12
  • \$\begingroup\$ @edc65 I can't believe that's not under JavaScript tips. \$\endgroup\$ – Neil Aug 23 '16 at 8:31
3
\$\begingroup\$

Haskell, 55 40 bytes

f=(\y->mod(y-8)39).Data.Char.ord.maximum

Thanks @Dennis for his approach. (take that, @xnor ;))

\$\endgroup\$
  • \$\begingroup\$ I think you can remove f= for 38 bytes since f doesn't take explicit arguments. \$\endgroup\$ – Cyoce Aug 23 '16 at 15:00
3
\$\begingroup\$

Perl 6: 18 bytes

{:36(.comb.max)+1}

Defines a lambda that takes a single string argument, and returns an integer. It splits the string into characters, finds the "highest" one, converts it to base 36, adds 1.

{(.ords.max-8)%39}

This one uses the modulo approach from Dennis. Same length.

\$\endgroup\$
2
\$\begingroup\$

Retina, 28 bytes

O`.
.\B

{2`
$`
}T01`dl`_o
.

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

O`.

This sorts the characters of the input.

.\B

This removes all characters except the last, so the first two stages find the maximum character.

{2`
$`
}T01`dl`_o

These are two stages which form a loop. The first one duplicates the first character and the second one "decrements" it (replacing e.g. x with w, a with 9 and 1 with 0). The latter stage encounters a zero as the first character, it removes it instead. This is a standard technique for generating a range of characters, given the upper end. Hence, this generates all "digits" from 0 to the maximum digit.

.

Finally, we simply count the number of digits, which gives us the base.

\$\endgroup\$
2
\$\begingroup\$

R, 99 89 85 bytes

Look ! Less than 100 bytes !
Look ! 10 bytes off !
Look ! 4 bytes off !

ifelse((m=max(strsplit(scan(,''),"")[[1]]))%in%(l=letters),match(m,l)+10,strtoi(m)+1)

Ungolfed :

l=letters                  #R's built-in vector of lowercase letters

n=scan(what=characters())  #Takes an input from STDIN and convert it to characters

m=max(strsplit(n,"")[[1]]) #Splits the input and takes to max. 
                           #`letters` are considered > to numbers (i.e. a>1)


ifelse(m%in%l,match(m,l)+10,strtoi(m)+1) #If the max is in `letters`,
                                             #outputs the matching position of `m`in `letters` + 10 (because of [0-9]). 
                                             #Else, outputs `m` (as a number) + 1.

As often, this answer makes use of the ifelse function : ifelse(Condition, WhatToDoIfTrue, WhatToDoElse)

\$\endgroup\$
  • \$\begingroup\$ I love your version; however, treating letters and numbers separately creates those pesky extra bytes. Please have a look at my solution that uses a different method. \$\endgroup\$ – Andreï Kostyrka Aug 23 '16 at 13:05
  • \$\begingroup\$ Your answer is interesting indeed. I will use the your scan method to golf some bytes ;) \$\endgroup\$ – Frédéric Aug 23 '16 at 13:10
1
\$\begingroup\$

PHP, 51 38 bytes

(From Dennis) ^^

<?=(ord(max(str_split($argv[1])))-8)%39;

Other proposal without Dennis' trick

<?=($a=max(str_split($argv[1])))<a?$a+1:ord($a)-86;
  • Takes input as argument $argv[1];
  • Take max character (using ASCII) values
  • If it is a number (inferior to < 'a' ascii value) then output number+1
  • Else output ascii value -86 (97 for 'a' in ascii, -11 for 'a' is 11th base-digit)
\$\endgroup\$
  • \$\begingroup\$ It's too bad PHP has such verbose function names: <?=base_convert(max(str_split($argv[1])),36,10)+1 is an elegant solution, but at 49 bytes! \$\endgroup\$ – Yimin Rong Aug 23 '16 at 18:15
  • \$\begingroup\$ @YiminRong you can use intval() instead of base_convert() which shortens down to 38 bytes <?=intval(max(str_split($argn)),36)+1; tio: tio.run/##K8go@P/… \$\endgroup\$ – 640KB Jun 26 at 15:53
1
\$\begingroup\$

Octave, 20 bytes

@(a)mod(max(a)-8,39)
\$\endgroup\$
1
\$\begingroup\$

Pyke, 6 bytes

Seb36h

Try it here!

Se     -   sorted(input)[-1]
  b36  -  base(^, 36)
     h - ^ + 1
\$\endgroup\$
1
\$\begingroup\$

Java 7, 67 61 bytes

int c(char[]i){int m=0;for(int c:i)m=m>c?m:c;return(m-8)%39;}

(m-8)%39 is thanks to @Dennis' amazing answer.

Ungolfed & test code:

Try it here.

class Main{
  static int c(char[] i){
    int m = 0;
    for(int c : i){
      m = m > c
           ? m
           : c;
    }
    return (m-8) % 39;
  }

  public static void main(String[] a){
    System.out.println(c("00000".toCharArray()));
    System.out.println(c("123456".toCharArray()));
    System.out.println(c("ff".toCharArray()));
    System.out.println(c("4815162342".toCharArray()));
    System.out.println(c("42".toCharArray()));
    System.out.println(c("codegolf".toCharArray()));
    System.out.println(c("0123456789abcdefghijklmnopqrstuvwxyz".toCharArray()));
  }
}

Output:

1
7
16
9
5
25
36
\$\endgroup\$
  • 2
    \$\begingroup\$ Instead of Math.max() you can use m = m>c?m:c \$\endgroup\$ – RobAu Aug 23 '16 at 9:53
  • \$\begingroup\$ @RobAu Ah of course, thanks. Completely forgot about it.. Sometimes I forget the easiest codegolfing things in Java that are even mentioned multiple times in the Tips for Codegolfing in Java post. Thanks for the reminder. \$\endgroup\$ – Kevin Cruijssen Aug 23 '16 at 12:30
  • \$\begingroup\$ If you switch to Java 8 you can replace this whole function with a lambda that does a single reduce \$\endgroup\$ – BlueRaja - Danny Pflughoeft Aug 23 '16 at 12:32
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft I know, which is why I specifically mentioned it as Java 7. Feel free to post a Java 8 lambda as a separate answer. \$\endgroup\$ – Kevin Cruijssen Aug 23 '16 at 12:33
  • \$\begingroup\$ @BlueRaja-DannyPflughoeft I wonder if that would end up with less bytes.. \$\endgroup\$ – RobAu Aug 23 '16 at 13:46
1
\$\begingroup\$

C89, 55 53 52 50 bytes

f(s,b)char*s;{return*s?f(s+1,*s>b?*s:b):(b-8)%39;}

-8%39 shamelessly stolen from Dennis

Test

test(const char* input)
{
    printf("%36s -> %u\n", input, f((char*)input,0));
}

main()
{
    test("00000");
    test("123456");
    test("ff");
    test("4815162342");
    test("42");
    test("codegolf");
    test("0123456789abcdefghijklmnopqrstuvwxyz");
}

Output

                               00000 -> 1
                              123456 -> 7
                                  ff -> 16
                          4815162342 -> 9
                                  42 -> 5
                            codegolf -> 25
0123456789abcdefghijklmnopqrstuvwxyz -> 36

Saved 2 bytes thanks to Toby Speight

Saved 2 bytes thanks to Kevin Cruijssen

\$\endgroup\$
  • \$\begingroup\$ You can save 2 bytes with the non-prototype declaration: f(char*s,int b) becomes f(s,b)char*s;. \$\endgroup\$ – Toby Speight Aug 23 '16 at 14:13
  • \$\begingroup\$ You can save 3 bytes by removing the unnecessary parenthesis and space: f(s,b)char*s;{return*s?f(s+1,*s>b?*s:b):(b-8)%39;} \$\endgroup\$ – Kevin Cruijssen Aug 23 '16 at 14:24
  • \$\begingroup\$ @KevinCruijssen thx \$\endgroup\$ – YSC Aug 23 '16 at 14:46
1
\$\begingroup\$

C, 55 bytes

This answer assumes that the input is in ASCII (or identical in the numbers and letters, e.g. ISO-8859 or UTF-8):

m;f(char*s){for(m=0;*s;++s)m=m>*s?m:*s;return(m-8)%39;}

We simply iterate along the string, remembering the largest value seen, then use the well-known modulo-39 conversion from base-{11..36}.

Test program

int printf(char*,...);
int main(int c,char **v){while(*++v)printf("%s -> ",*v),printf("%d\n",f(*v));}

Test results

00000 -> 1
123456 -> 7
ff -> 16
4815162342 -> 9
42 -> 5
codegolf -> 25
0123456789abcdefghijklmnopqrstuvwxyz -> 36
\$\endgroup\$
  • \$\begingroup\$ Couldn't you remove the m=0? If m appears at the top level of the file, its extern which implies static which implies it is initialized to zero. \$\endgroup\$ – Batman Aug 24 '16 at 3:47
  • \$\begingroup\$ @Batman - yes, but only if you won't call f() more than once. I know that almost anything's fair game in golf, but my professional instincts regard that as too fragile! \$\endgroup\$ – Toby Speight Aug 24 '16 at 7:46
  • \$\begingroup\$ On further thought, I could make it an external requirement to reset m between calls to f(). Then my test program could still work. \$\endgroup\$ – Toby Speight Aug 24 '16 at 7:47
  • \$\begingroup\$ @Batman: on Code Golf Meta, the majority opinion on the question "Do function submissions have to be reusable?" seems to be against allowing single-use functions. So I'll stick with what I have. Thanks for the suggestion, anyway. \$\endgroup\$ – Toby Speight Aug 24 '16 at 8:03
1
\$\begingroup\$

Mathematica, 34 32 bytes

2 bytes saved thanks to Martin Ender

Max@Mod[ToCharacterCode@#-8,39]&

I decided the different method deserved a new answer.

method stolen inspired by Dennis' solution

\$\endgroup\$
  • 2
    \$\begingroup\$ Use some prefix notation: Max@Mod[ToCharacterCode@#-8,39]& (same goes for your other answer) \$\endgroup\$ – Martin Ender Aug 23 '16 at 7:43
  • 2
    \$\begingroup\$ Also, you need to add & to the end to indicate an anonymous function. \$\endgroup\$ – LegionMammal978 Aug 23 '16 at 11:43
  • \$\begingroup\$ You forgot one @ in both of your answers (ToCharacterCode@# and Characters@#). \$\endgroup\$ – Martin Ender Aug 23 '16 at 16:37
1
\$\begingroup\$

Mathematica, 34 32 bytes

saved 2 bytes thanks to Martin Ender

Max@BaseForm[Characters@#,36]+1&

Defines a pure function that takes a string as input.

Splits the input into characters, converts them to base 36 numbers, and returns the maximum +1.

\$\endgroup\$
  • \$\begingroup\$ Max@BaseForm[Characters@#,36]+1& \$\endgroup\$ – alephalpha Aug 23 '16 at 14:19
1
\$\begingroup\$

C# REPL, 17 bytes

x=>(x.Max()-8)%39

Just ported @Dennis's answer to C#.

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

CJam, 10 bytes

Thanks to Martin Ender for saving me a few bytes!

Uses Dennis's formula

q:e>8-i39%

Try it online

CJam, 18 16 btyes

Alternative solution:

A,s'{,97>+q:e>#)

Try it online

A,s'{,97>+       e# Push the string "0123456789abcdefghijklmnopqrstuvwxyz"
          q      e# Get the input
           :e>   e# Find the highest character in the input
              #  e# Find the index of that character in the string
               ) e# Increment
\$\endgroup\$
1
\$\begingroup\$

Scala, 25 bytes

print((args(0).max-8)%39)

Run it like:

$ scala whatbase.scala 0123456789abcdefghijklmnopqrstuvwxyz

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

R, 62 54 bytes

max(match(strsplit(scan(,''),"")[[1]],c(0:9,letters)))

Ungolfed:

max(
  match( # 2: Finds the respective positions of these characters
    strsplit(scan(,''),"")[[1]], # 1: Breaks the input into characters
                                c(0:9,letters)) # 3: In the vector "0123...yz"
                                                )

Update: shaved off 8 bytes due to the redundancy of na.rm=T under the assumption of input validity.

A 39% improvement in size compared to Frédéric's answer. Besides that, it runs a wee bit faster: 0.86 seconds for 100000 replications versus 1.09 seconds for the competing answer. So the one of mine is both smaller and more efficient.

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

Dyalog APL, 10 bytes

Prompts for uppercase input.

⌈/⍞⍳⍨⎕D,⎕A

⌈/ maximum

characters of input

⍳⍨ 1-indexed into

⎕D, all digits followed by

⎕A all characters

TryAPL online!

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

BASH 70

grep -o .|sort -r|head -c1|od -An -tuC|sed s/$/-86/|bc|sed s/-/39-/|bc

Input letters are lowercase.

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

JavaScript, 57 50 48 bytes

7 bytes saved thnks to @kamaroso97 2 bytes saved thanks to @Neil

n=>Math.max(...[...n].map(a=>parseInt(a,36))+1)

Original answer:

n=>n.split``.map(a=>parseInt(a,36)).sort((a,b)=>b-a)[0]+1
\$\endgroup\$
  • \$\begingroup\$ You can knock off 7 bytes with n=>Math.max(...n.split``.map(a=>parseInt(a,36)+1)). \$\endgroup\$ – kamoroso94 Aug 23 '16 at 5:45
  • \$\begingroup\$ @kamoroso94 I didn't realize Math.max existed. Thanks for telling me about it! \$\endgroup\$ – DanTheMan Aug 23 '16 at 5:52
  • \$\begingroup\$ [...s] is shorter than s.split``. \$\endgroup\$ – Neil Aug 23 '16 at 7:31
0
\$\begingroup\$

Perl, 30 27 bytes

Includes +1 for -p

Run with the input on STDIN, e.g.

base.pl <<< codegolf

base.pl:

#!/usr/bin/perl -p
\@F[unpack"W*"];$_=@F%39-9
\$\endgroup\$
0
\$\begingroup\$

LiveScript, 32 bytes

->1+parseInt (it/'')sort!pop!,36

A port of this answer in my favorite language that compile to JavaScript. If base~number operator worked with variables I could write ->1+36~(it/'')sort!pop! (23 bytes), but it conflicts with the function bind operator :/

\$\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.