18
\$\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\$
9
  • 17
    \$\begingroup\$ Great challenge, but it needs more test cases. \$\endgroup\$
    – Grimmy
    Aug 12, 2019 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\$ Aug 12, 2019 at 11:37
  • 8
    \$\begingroup\$ Can I use a-z instead of A-Z? \$\endgroup\$
    – Neil
    Aug 12, 2019 at 11:46
  • 5
    \$\begingroup\$ Can we just use the corresponding numbers instead of A-Z? \$\endgroup\$
    – flawr
    Aug 12, 2019 at 11:57
  • 9
    \$\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, 2019 at 14:11

19 Answers 19

6
\$\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\$
3
  • 1
    \$\begingroup\$ You can replace @$_ with @_ and it still works. \$\endgroup\$
    – SirBogman
    Jan 26, 2020 at 20:51
  • 2
    \$\begingroup\$ @SirBogman This just happens to work with the very few test cases. \$\endgroup\$
    – nwellnhof
    Jan 27, 2020 at 13:12
  • \$\begingroup\$ That makes sense. It didn't feel quite right. \$\endgroup\$
    – SirBogman
    Jan 27, 2020 at 17:00
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\$
5
  • 1
    \$\begingroup\$ -1 byte by using ₆L©B®ø instead of ₆LεBy‚} \$\endgroup\$ Aug 12, 2019 at 12:11
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks! Another -1 by using ā, seems like you always forget about that one. \$\endgroup\$
    – Grimmy
    Aug 12, 2019 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\$ Aug 12, 2019 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\$
    – Grimmy
    Aug 13, 2019 at 10:12
  • \$\begingroup\$ @Grimy guilty as charged. Sorry to bother you. \$\endgroup\$
    – recursive
    Aug 13, 2019 at 14:52
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\$
1
  • \$\begingroup\$ Ah, I missed that part \$\endgroup\$
    – TFeld
    Aug 12, 2019 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 each X
     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\$
4
  • \$\begingroup\$ Yes, it works nice, but the letters must be uppercase. \$\endgroup\$
    – Ver Nick
    Aug 12, 2019 at 16:36
  • 1
    \$\begingroup\$ @VerNick, why? That adds absolutely nothing to the challenge. \$\endgroup\$
    – Shaggy
    Aug 12, 2019 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\$ Aug 12, 2019 at 17:23
  • \$\begingroup\$ @JonathanAllan, luckily I can "fix" that one with a change of flag. \$\endgroup\$
    – Shaggy
    Aug 12, 2019 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\$

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\$
5
  • \$\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, 2019 at 18:30
  • \$\begingroup\$ Maybe something with MinimalBy, like this? \$\endgroup\$
    – Roman
    Aug 12, 2019 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\$
    – att
    Aug 13, 2019 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, 2019 at 7:04
  • \$\begingroup\$ Ah, you're right. My bad for not noticing that. \$\endgroup\$
    – att
    Aug 14, 2019 at 2:39
1
\$\begingroup\$

Japt v2.0a0, 31 bytes

2o37 ñ@sX Ê+UsX â ÊÃÎ
+S+NÎsU u

Try it

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

Scala, 105 97 bytes

n=>{val(b,x)=2.to(36)map(b=>b->n.toString(b))minBy((_,x)=>(x++x.toSet).size);b+" "+x.toUpperCase}

Try it online!

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

C (clang), 165 161 bytes

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

Try it online!

  • Shortened and improved by @ceilingcat
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\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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