15
\$\begingroup\$

How, you can’t remember the 6 or 7-digit phone number that appeared on the TV screen for a second?! Using the special technique described below, you will turn into a walking phonebook!

Obviously, the number 402 is easier to remember than the number 110010010, and the number 337377 is easier to remember than the number 957472. This means that the memorized number, on the one hand, should contain as few digits as possible, and on the other hand, it is desirable that the number contains as many repeating numbers as possible.

As a criterion for the difficulty of remembering, we take the sum of the number of digits in number and the number of different digits in number. A memorized number can be written in another number system, perhaps then it will be easier to remember. For example, the number 65535 in the hexadecimal notation looks like FFFF.

Task

You need to write a program for selecting the base of the number system to minimize the complexity criterion. The base of the number system must be selected in the range from 2 to 36, then the numbers 0-9 and the English letters A-Z can be used to represent the number.

Input

The input contains a decimal integer from 1 to 999999999.

Output

The output must contain the base of the number system (from 2 to 36), minimizing the criterion of memorization complexity, and the number in the selected number system, separated by one space. If several bases give the same value for the criterion, then choose the smallest among them.

Notes

  • The letters must be uppercase(A-Z).

Test Cases

Input       Output

1              2 1

2              3 2

65535       16 FFFF

123          12 A3

\$\endgroup\$
  • 16
    \$\begingroup\$ Great challenge, but it needs more test cases. \$\endgroup\$ – Grimy Aug 12 at 11:18
  • 7
    \$\begingroup\$ Also, the output format is a bit too strict, you might want to allow e.g. an array of two elements, the base and the string, or allowing them in reverse order or separated by another character. Also, I assume that you add the sum of the digits to the number of digits, but you may want to clarify that. \$\endgroup\$ – Erik the Outgolfer Aug 12 at 11:37
  • 8
    \$\begingroup\$ Can I use a-z instead of A-Z? \$\endgroup\$ – Neil Aug 12 at 11:46
  • 4
    \$\begingroup\$ Can we just use the corresponding numbers instead of A-Z? \$\endgroup\$ – flawr Aug 12 at 11:57
  • 6
    \$\begingroup\$ @VerNick Next time you write a similar challenge I would suggest allowing both these requests, as they are just an unnecessary complication which are discouraged: see e.g. here. \$\endgroup\$ – flawr Aug 12 at 14:11

18 Answers 18

5
\$\begingroup\$

Python 2, 150 149 127 144 bytes

lambda n:min((len(c(n,b))+len(set(c(n,b))),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n/b,b,chr(n%b+48+7*(n%b>9))+s)or s or'0'

Try it online!


Python 3, 136 bytes

lambda n:min((len((*c(n,b),*{*c(n,b)})),b,c(n,b))for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!


Python 3.8 (pre-release), 131 bytes

lambda n:min((len((*(x:=c(n,b)),*{*x})),b,x)for b in range(2,37))[1:]
c=lambda n,b,s='':n and c(n//b,b,chr(n%b+48+7*(n%b>9))+s)or s

Try it online!


c converts a base 10 number to any base (2-36), and the first (anonymous) function finds the smallest result.

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

05AB1E, 16 14 bytes

-1 byte thanks to Kevin Cruijssen

₆LBāøΣнDÙìg}1è

Try it online!

Or add R)» at the end to conform exactly to the specified output format, but most other answers didn't bother.

Explanation:

₆L          # range 1..36
  B         # convert the input to each of those bases
   āø       # enumerate (pair each element with its 1-based index)
Σ     }     # sort by
     g      # length
 н          # of the first element
    ì       # concatenated to
  DÙ        # itself, uniquified
1è          # take the second entry (first will always be base 1)
\$\endgroup\$
  • 1
    \$\begingroup\$ -1 byte by using ₆L©B®ø instead of ₆LεBy‚} \$\endgroup\$ – Kevin Cruijssen Aug 12 at 12:11
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks! Another -1 by using ā, seems like you always forget about that one. \$\endgroup\$ – Grimy Aug 12 at 12:16
  • \$\begingroup\$ Lol, I indeed do.. I remembered it with this challenge earlier today, not that it helped in any way, haha xD \$\endgroup\$ – Kevin Cruijssen Aug 12 at 12:17
  • \$\begingroup\$ @recursive you don't seem to have read the answer. I link a version that complies with the strict output requirements, and explain why I didn't make that the main version. \$\endgroup\$ – Grimy Aug 13 at 10:12
  • \$\begingroup\$ @Grimy guilty as charged. Sorry to bother you. \$\endgroup\$ – recursive Aug 13 at 14:52
5
\$\begingroup\$

Perl 6, 55 54 bytes

-1 byte thanks to Jo King.

{~map({$^b,.base($b)},2..36).min:{@$_+.Set}o*[1].comb}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Damn, I didn't see this and got pretty much the exact same answer, except with @$_ instead of .[*] for minus one byte \$\endgroup\$ – Jo King Aug 13 at 2:11
4
\$\begingroup\$

JavaScript (ES6),  87 85  101 bytes

Edit: +16 useless bytes to comply with the strict output format

n=>(g=m=>--b>2?g(m<(v=new Set(s=n.toString(b)).size+s.length)?m:(o=b+' '+s.toUpperCase(),v)):o)(b=37)

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Ah, I missed that part \$\endgroup\$ – TFeld Aug 12 at 12:26
4
\$\begingroup\$

Japt v2.0a0 -gS, 24 23 bytes

Not pretty, but it does the job. +2 bytes for the completely unnecessary requirement that output be uppercase.

37o2@sX u ¸iXÃñÈÌiXÌâ)l

Try it

37o2@sX u ¸iXÃñÈÌiXÌâ)l     :Implicit input of integer
37o2                        :Range [2,37)
    @                       :Map
     sX                     :  Convert the input to a base-X string
        u                   :  Uppercase
          ¸                 :  Split on spaces (there are none, so this returns a singleton array)
           iX               :  Prepend X
             Ã              :End map
              ñ             :Sort by
               È            :Pass each X through the following function
                Ì           :  Last element of X
                 i          :  Prepend
                  XÌâ       :    Last element of X, deduplicated
                     )      :  End prepend
                      l     :  Length
                            :Implicit output of the first sub-array, joined with spaces
\$\endgroup\$
  • \$\begingroup\$ Yes, it works nice, but the letters must be uppercase. \$\endgroup\$ – Ver Nick Aug 12 at 16:36
  • 1
    \$\begingroup\$ @VerNick, why? That adds absolutely nothing to the challenge. \$\endgroup\$ – Shaggy Aug 12 at 16:53
  • \$\begingroup\$ ...I guess the next thing will be "separated by one space". Seems the output format has been made very strict on this challenge, and from the comments does not look like it will change. \$\endgroup\$ – Jonathan Allan Aug 12 at 17:23
  • \$\begingroup\$ @JonathanAllan, luckily I can "fix" that one with a change of flag. \$\endgroup\$ – Shaggy Aug 12 at 17:27
3
\$\begingroup\$

PHP, 124 119 bytes

for($i=36;$b=strtoupper(base_convert($argn,10,--$i));$o[strlen($b.count_chars($b,3))]="$i $b");krsort($o);echo end($o);

Try it online!

A shame about the +12 bytes in PHP to uppercase the output... but... anyway.

\$\endgroup\$
3
\$\begingroup\$

Zsh, 85 bytes

for b ({36..2})x=$[[#$b]$1]&&x=${x#*\#}&&a[$#x+${#${(us::)x}}]=$b\ $x
a=($a)
<<<$a[1]

For this number of statements inside the for loop, using ...&&...&&... is shorter than {...;...;...;}.

for b ({36..2})                   # order decreasing: smaller bases overwrite larger ones
    x=$[[#$b]$1] && \             # set x to [base]#[num] 
    x=${x#*\#} && \               # strip leading [base]#
    a[$#x+${#${(us::)x}}]=$b\ $x  # use score as index to store "[base] [number]"
#            ${(us::) }           # (s::)plit into characters, take (u)nique
a=($a)                            # remove empty elements from array
<<<$a[1]                          # print out the first element (smallest score)

Try it online!

Here's an 81-byte solution which prints in the form [base]#[num] instead:

for b ({36..2})x=$[[#$b]$1]&&y=${x#*\#}&&a[$#y+${#${(us::)y}}]=$x
a=($a)
<<<$a[1]

Try it online!

\$\endgroup\$
3
\$\begingroup\$

J, 67 bytes

(];'0123456789ABCDEF'{~b)[:(2+]i.<./)](#+#@~.)@(b=:#.inv~)"+2+i.@35

Try it online!

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

Charcoal, 38 bytes

Nθ≔EE³⁴↨θ⁺²ιL⁺ιΦι⁼λ⌕ικη≔⁺²⌕η⌊ηηIη ↥⍘θη

Try it online! Link is to verbose version of code. Explanation:

Nθ

Input the integer.

≔EE³⁴↨θ⁺²ι

Convert it from base 2 to base 36...

L⁺ιΦι⁼λ⌕ικη

... deduplicate, concatenate, and take the length.

≔⁺²⌕η⌊ηη

Take the index of the minimum complexity and add 2 to get the base.

Iη ↥⍘θη

Print the base and the integer converted to that base in upper case.

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

Stax, 19 bytes

Ç╛;ⁿY3█↕(╖S♪*ò▌?½╦l

Run and debug it

No fancy algorithm, just straightforward brute force. About a third of the program is format-wrangling for the precise output rules.

Bonus program: Output for [1..1000]

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

Jelly, 25 bytes

bⱮ36µQL+LN)Mḟ1Ḣ,ị‘ịØBʋ¥⁸K

Try it online!

A monadic link taking an integer as its argument and returning a Jelly string of the desired format. If a two-item list was acceptable output (as per most challenges), could save 2 bytes. If base 1 were acceptable for the edge case of 1 as input, could save a further 2 bytes.

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

Brachylog, 44 bytes

∧Y≜∧36≥Xℕ₂≜&ḃ↙X Zd,Zl≡Y∧XwṢwZ{-₁₀;Ạụᵗ∋₍|}ᵐwᵐ

Try it online!

This hurt a bit to write.

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

Japt v2.0a0, 32 bytes

T=2o37 ñ@sX Ê+UsX â ÊÃÎT+S+UsT u

Can save two bytes if I can reverse the order, and can save 2 more if uppercase wasn't required.

Try it

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

Perl 5, 161 bytes

sub f{$X=99;for$b(2..36){$_=c($_[0],$b);$x=uniq(/./g)+y///c;($X,$B,$C)=($x,$b,$_)if$x<$X}$B,$C}
sub c{my($n,$b)=@_;$n?c(int$n/$b,$b).chr(48+$n%$b+7*($n%$b>9)):''}

Try it online!

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

Python 2, 140 135 bytes

lambda n:min([(b,g(n,b))for b in range(2,36)],key=lambda(b,s):len(s)+len(set(s)))
g=lambda n,b:n and g(n/b,b)+chr(n%b+48+7*(n%b>9))or''

Try it online!

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

Perl 5 -Minteger -MList::Util=uniq,first -ap, 123 112 bytes

$"=$,;map{@r=();$t="@F";do{unshift@r,(0..9,A..Z)[$t%$_]}while$t/=$_;$a[@r+uniq@r]||="$_ @r"}2..36;$_=first{$_}@a

Try it online!

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

Wolfram Language (Mathematica), 109 111 bytes

Print[a=OrderingBy[#~IntegerDigits~Range@36,Tr[1^#]+Tr[1^Union@#]&,1][[1]]," ",ToUpperCase[#~IntegerString~a]]&

+2: fixed. Thanks for the catch @Roman

OrderingBy was introduced in Mathematica 12.0, which TIO does not seem to have updated to yet.

\$\endgroup\$
  • \$\begingroup\$ "If several bases give the same value for the criterion, then choose the smallest among them.": OrderingBy doesn't conform to this requirement. \$\endgroup\$ – Roman Aug 12 at 18:30
  • \$\begingroup\$ Maybe something with MinimalBy, like this? \$\endgroup\$ – Roman Aug 12 at 18:38
  • \$\begingroup\$ @Roman doesn't it? As far as I can tell, it preserves the relative order of two indices that have the same value.. \$\endgroup\$ – attinat Aug 13 at 2:52
  • 2
    \$\begingroup\$ With the argument 123, your solution prints 36 3F instead of the required 12 A3. From OrderingBy[123~IntegerDigits~Range@36, Tr[1^#] + Tr[1^Union@#] &] I get the answer {36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 6, 5, 11, 10, 9, 8, 7, 4, 3, 2, 1}, so the usual assumption of no re-ordering equivalent entries seems to be ignored here. My $Version is "12.0.0 for Mac OS X x86 (64-bit) (April 7, 2019)". \$\endgroup\$ – Roman Aug 13 at 7:04
  • \$\begingroup\$ Ah, you're right. My bad for not noticing that. \$\endgroup\$ – attinat Aug 14 at 2:39
1
\$\begingroup\$

C (clang), 165 bytes

n,i=2,j,p=99,r,m,x;char*g,*_,b[74][37];t(n){for(;g=b[i],i<37;r=j<p?_=g,p=j,i:r,++i)for(j=0,m=n;m;m/=i,*--g=x+=x>9?87:48)j+=b[i+36][x=m%i]++?1:2;printf("%i,%s",r,_);}

Try it online!

n//input

,i=2//iterator from base 2 to 36

,j//current complexity

,p=99//best complexity

,r//result = iterator

,m// temp copy of n

,x ;// m%i

char*g // current string ptr

,*_ // best str ptr

,b[74][37];//buffer

/* [37+37] = [strings obtained + test for used characters ] */

t(n){

for(; g=b[i], // move ptr

   i<37 ; 
   r=j<p?_=g,p=j,i:r, // save best solution

   ++i){//for every base

for( j=0,m=n; m ; m/=i, // extract digit

   *--g=x+=x>9?87:48)
   // move ptr backward for printf use and transform to ascii value

j+=b[i+36][x=m%i]++?1:2; // increment byte relative to the character

// and if it was 0 increments j by 2 : 1 for the new character used and 1 for digit count

// else incr only digits count + move pointer

//printf("%s - ",g);// test

// printf("r%i p%i j%i\n",r,p,j);// test

}

printf("%i,%s",r,_);//output

}

\$\endgroup\$
  • 1
    \$\begingroup\$ 163 bytes can be called more than once. \$\endgroup\$ – ceilingcat Aug 21 at 22:57

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.