6
\$\begingroup\$

your task is...

Given a string x and a positive integer y, to determine whether there is a positive integer b and an injective mapping from the distinct characters in x to the digits of base b which permit us to interpret x as an integer equal to y.

details:

   If there is more than one base which works, you don't have to output all of them, just one.
   The answer should be a function for those languages that support it, otherwise, code snippet
   Your program should accept 0-9 and (a-z or A-Z) which are 36 characters. You don't have to care about kanji or snowman.
   (e.g. 6 doesn't have to mean 6, it's just a symbol. basically you get a number in unknown base with unknown symbols and you have to substitute them to get y)

for example:

   (foo,4) returns either 2 or 3 because

  •    f=1, o=0 -> 1002=410
  •    f=0, o=1 -> 0113=410

   (10,10) any integer greater than 4 but not 9 because

  •    1=2, 0=0 -> 205=1010
  •    1=1, 0=4 -> 146=1010
  •    1=1, 0=3 -> 137=1010
  •    1=1, 0=2 -> 128=1010
  •    1=1, 0=0 -> 1010=1010
  •    1=0, 0=10 -> 0111=1010
  •    above base 10, 1=0, 0=10 -> 01x=1010 for every x > 10

   (611,1) returns 0 which means there is no possible base for 611 meaning 110

bonus:

   You have to output every possible base, not just one. I know it can be infinite,
   indicate it somehow. 2,3,... for example.
   Answers with bonus gain a 0.7 multiplier.

\$\endgroup\$
  • 1
    \$\begingroup\$ How can the number of bases be infinite, if we're only using 62 characters to represent digits? More importantly, how many characters is the bonus worth? Also it's slightly misleading that your example use the bonus output and not that of the core challenge. \$\endgroup\$ – Martin Ender Aug 16 '14 at 12:51
  • \$\begingroup\$ because in the (10,10) example 1=0,0=10 applies for base 1000 too. 0*1000^1+10*1000^0=10 etc. i try to make it clear. \$\endgroup\$ – bebe Aug 16 '14 at 12:55
  • \$\begingroup\$ So for the infinitely large bases it's just that we can only use 62 of the available digits? \$\endgroup\$ – Martin Ender Aug 16 '14 at 12:58
  • 3
    \$\begingroup\$ I find this to be a really clear question. I understand completely the concept of an infinite selection of bases. \$\endgroup\$ – Sparr Aug 16 '14 at 13:02
  • \$\begingroup\$ Sorry but 9 was not valid. Changing back. \$\endgroup\$ – bebe Aug 16 '14 at 13:26
1
\$\begingroup\$

Mathematica, 183 bytes * 0.7 = 128.1

f[s_,n_]:=(For[i=2,1>0,++i,d=(l=Length)@(g=IntegerDigits)[n,i];Which[Count[c=Characters@s,c[[-1]]]>1&&d==1,Return@0,l@c>=d&&And@@Unequal@@@(t=Thread)@Union@t@{g[n,i,l@c],c},Print@i]])

Less golf

f[s_, n_] := (
  For[i = 2, 1 > 0, ++i,
   d = (l = Length)@(g = IntegerDigits)[n, i];
   Which[
    Count[c = Characters@s, c[[-1]]] > 1 && d == 1,
    Return@0,
    l@c >= d && And @@
      Unequal @@@
       (t = Thread)@
        Union@
         t@
          {g[n, i, l@c], c},
    Print@i
    ]
   ]
  )

I don't actually recommend running this, because quick and infinite output is a bit tricky to abort in Mathematica sometimes. To get only the first result, change Print to Result (which is even a character longer). If you're using the version as is, a final 0 output will indicate that no further bases will be found (similar to the returning case).

The first part of the Which simply aborts the loop when no base can possibly be found (it might be possible to shorten this). The second loop is the interesting check. These are the steps taken:

  • Convert n to digits in the current base (Mathematica can handle arbitrarily large bases.)
  • Zip those digits up with the characters, basically creating the mapping at each position.
  • Union throws out duplicates - these are uninteresting because they just point to a consistent mapping.
  • Transpose the mapping, so I get a list of digits and a list of characters.
  • If there are no duplicates in either, we have an injective mapping and print the base.
\$\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.