10
\$\begingroup\$

An extension of Find the closest palindromic number mixed with Numbers Interpreted in Smallest Valid Base.

A number is a palindrome if its sequence of digits is the same when reading them from left to right as when reading from right to left. Usually, people think of base 10, but some numbers are palindromes in different bases. For example, 15 isn't palindromic in base 10, but in base 2, it's 1111, which is!

But if we're using arbitrary bases and given a random string, how do we know what base it's in? Let us interpret an alphanumeric string as if it were a number in some base, and the interpreted base \$b\$ of such a string is the smallest base where the string is still valid - that is, its highest digit plus one (151 is base 6, 238 is base 9). If the number has letters in it, interpret a as a digit representing 10, b as 11, and so on up to z as 35 (so 3ba is interpreted base 12, y2k is base 35, zz8 is base 36). If that number is a palindrome in that interpreted base, we'll call it base \$b\$ palindromic.

Given an alphanumeric string \$N\$ with interpreted base \$b\$, return an integer \$X\$, where \$|X|\$ is as small as possible, such that \$N+X\$ is base \$b\$ palindromic (that is, if \$N+X\$ is represented in base \$b\$, it is palindromic, and its highest digit in that base is \$b-1\$). If both \$X\$ and \$-X\$ are valid, you can return either (or both if it makes your code shorter).

Standard I/O rules apply. You may take input with uppercase letters instead of lowercase if you so desire (in which case A is 10, B is 11, and so on up to Z as 35, just like the lowercase letters). It is not necessary to handle both cases, nor mixed cases (you can assume you'll never get an input like 1lI, for example).

NEW: Per suggestions, you can choose to take input as a list of digits instead of as a string. If you do, you only need to handle digits up to 35 (just as if you had taken string input).

Examples

Sample inputs are given in lowercase. Sample outputs are shown in base 10.

Input | Digits         | In Base-10 (Base) | Output (Sum in Target Base)
777   | 7,7,7          | 511     (base 8)  | 0 (777)
10    | 1,0            | 2       (base 2)  | 1 (11) OR -1 (1) (either is valid)
a1b   | 10,1,11        | 1463    (base 12) | -26 (9b9)
hello | 17,14,21,21,24 | 6873049 (base 25) | 1693 (heoeh)

Take note of the last two examples: while you can subtract 1 from a1b to make it a1a in base 12, which is a palindrome, the highest digit is a (10), not b (11), so that string would have interpreted base-11 and thus isn't base-12 palindromic! Similarly, you can subtract 182 from hello to get heleh in base 25, but its highest digit is l (21), not o (24).

Improve this question
\$\endgroup\$
9
  • \$\begingroup\$ In case it helps anyone, $f(x)=\dfrac{c-x}{2|x-c|}-x+.5$ (where $c$ is any number in $(0,1)$, though $.5$ is probably the most convnient) is a function that when iterated generates the sequence $0,1,-1,2,-2,\ldots$ \$\endgroup\$ Commented Oct 7 at 23:44
  • \$\begingroup\$ In case it helps anyone, \$f(x)=\dfrac{c-x}{2|x-c|}-x+.5\$ (where \$c\$ ... in \$(0,1)\$, ... \$.5\$ ... convenient) ... sequence \$0,1,-1,2,-2,\ldots\$. \$\endgroup\$ Commented Oct 8 at 8:27
  • 3
    \$\begingroup\$ Could we accept a list of integers rather than the less natural alphanumeric string? (The letters seem tangential to the core challenge.) \$\endgroup\$ Commented Oct 8 at 11:52
  • 1
    \$\begingroup\$ @JonathanAllan that's an interesting point; implemented. I wish this had come up while it was in the sandbox, I might've let the digits go up arbitrarily if so haha \$\endgroup\$ Commented Oct 10 at 4:36
  • 1
    \$\begingroup\$ @KevinCruijssen clarified that 0 is accepted. \$\endgroup\$ Commented Oct 10 at 4:36

8 Answers 8

Reset to default
6
\$\begingroup\$

Lua, 304 269 bytes

Pain. Suffering. Being forced to implement index-to-radixed-string conversion manually. Uh…something something hardcoding the alphabet.
This only accepts uppercase letters for its input.

Addendum: OP managed to slash 35 characters by avoiding using a table at all.

a="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"n=io.read()i=0t={}n:gsub(".",function(c)table.insert(t,c)end)table.sort(t)b=a:find(t[#t])n=tonumber(n,b)while 1 do s=""v=n+i repeat s=a:sub(v%b+1,v%b+1)..s v=v//b until v==0if s==s:reverse()and s:find(a:sub(b,b))then print(i)break end j=.5-i i=j+j/2/math.abs(j)end

Versions

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ I really should've considered the difficulties of arbitrary base conversions up to 36 for languages that didn't have it natively (I've mainly golfed in Ruby) when making this challenge, huh... \$\endgroup\$ Commented Oct 8 at 4:06
  • \$\begingroup\$ I don't know Lua but I was thinking there's gotta be something better than gsub to populate a table and then sort it. string.byte could help, I got -35 with b=a:find(a.char(math.max(n:byte(1,#n)))) (moved i=0 as 0b errors) but maybe something else golfs better \$\endgroup\$ Commented Oct 8 at 7:13
  • \$\begingroup\$ The table is only used to find the "maximum" character anyway, so that optimization looks pretty good. No idea what it's actually doing, though. \$\endgroup\$ Commented Oct 8 at 14:21
  • \$\begingroup\$ I don't know Lua either—the only reason I've been using it is that all the good players avoid it. \$\endgroup\$ Commented Oct 8 at 14:26
  • \$\begingroup\$ Rules have been updated to let you take a table of digits as input. Not sure if it'd be shorter (you probably don't need that first string at least), but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:38
6
\$\begingroup\$

Vyxal, 31 27 25 24 22 19 bytes

?:G›~β„+Ȯτ:Ḃ⁼*G›=)N

Try it Online!

Uses a list of digits.

-1 byte after seeing DÂQ* in Kevin's 05AB1E answer

-2 bytes after seeing Kevin put the base conversion logic inside the "find integer" structure + after doing some stack manipulation stuff

-3 bytes after the rule change

Explained

This was the 25 byte explanation, but the approach is fundamentally the same.

Gkrḟ›:£β→λ←+¥τ₌‡Ḃ⁼G¥‹=*;N­⁡​‎‎⁡⁠⁡‏⁠‎⁡⁠⁤‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁣⁢‏⁠‎⁡⁠⁢⁢⁤‏⁠‎⁡⁠⁢⁣⁡‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁡‏⁠‎⁡⁠⁤⁢‏‏​⁡⁠⁡‌⁣⁡​‎‎⁡⁠⁤⁣‏⁠‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁣⁢​‎‎⁡⁠⁤⁤‏⁠‎⁡⁠⁢⁡⁡‏⁠‎⁡⁠⁢⁡⁢‏‏​⁡⁠⁡‌⁣⁣​‎‎⁡⁠⁢⁢⁣‏‏​⁡⁠⁡‌⁣⁤​‎‎⁡⁠⁢⁡⁣‏⁠‎⁡⁠⁢⁡⁤‏⁠‎⁡⁠⁢⁢⁡‏⁠‎⁡⁠⁢⁢⁢‏‏​⁡⁠⁡‌­
G  ḟ                       # ‎⁡Find the location of the biggest digit in the input in
 kr                        # ‎⁢"0-9a-zA-Z"
    ›                      # ‎⁣and add 1 to get the interpreted base
     :£                    # ‎⁤Store this interpreted base in the register
       β→                  # ‎⁢⁡and convert the input from this interpreted base to base 10, storing the result in the ghost variable. Call this X
         λ             ;N  # ‎⁢⁢Find the first whole number n (from [0, 1, -1, 2, -2, ...]) where:
          ←+               # ‎⁢⁣  Adding n to X
            ¥τ             # ‎⁢⁤  and converting back to the interpreted base
              ₌       *    # ‎⁣⁡  Holds true under:
               ‡Ḃ⁼         # ‎⁣⁢    Is palindrome?
                      *    # ‎⁣⁣  AND
                  G¥‹=     # ‎⁣⁤    max digit == (interpreted base - 1)
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
3
  • 3
    \$\begingroup\$ half life 2 when i can't find all the lambda graffiti: →λ← \$\endgroup\$ Commented Oct 8 at 8:51
  • \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:38
  • \$\begingroup\$ @ValueInk helped save 3 bytes :p \$\endgroup\$ Commented Oct 10 at 6:10
4
\$\begingroup\$

R, 126 125 123 bytes

\(x){b=which.min(m<-mapply(strtoi,x,2:36))+1
while(any(rev(q<-(n=m[b-1]+F)%/%b^(0:log(n,b))%%b)-q)|all(q-b+1))F=(F<1)-F
+F}

Attempt This Online!

Partly uses @Giuseppe's solution to the linked challenge.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:40
3
\$\begingroup\$

JavaScript (ES6), 128 bytes

-2 thanks to @l4m2

s=>(P=parseInt,g=k=>[...S=(P(s,b=P(c=[...s].sort().pop(),36)+1)+k).toString(b)].reverse().join``!=S|!S.match(c)?g((k<1)-k):k)(0)

Try it online!

Commented

s => (               // s = input string
  P = parseInt,      // P = alias for parseInt
  g = k =>           // g is a recursive function taking an integer k:
  [...               //
    S = (            //   define S as:
      P(             //
        s,           //     s parsed in base b
        b = P(       //     where b is:
          c = [...s] //       the highest digit c in s ...
            .sort()  //
            .pop(),  //
          36         //       ... parsed in base 36
        ) + 1        //       plus 1
      ) + k          //     plus k
    ).toString(b)    //     converted back to base b
  ].reverse()        //   if S reversed ...
  .join`` != S |     //   ... is not equal to itself
  !S.match(c) ?      //   or S doesn't contain c:
    g(               //     do a recursive call with:
      (k < 1) - k    //       either -k if k > 0 or 1 - k otherwise
                     //       (0 → 1 → -1 → 2 → -2 → …)
    )                //     end of recursive call
  :                  //   else:
    k                //     return k
)(0)                 // initial call to g with k = 0
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ k<0?-k:~k => (k<1)-k \$\endgroup\$ Commented Oct 9 at 8:05
  • 1
    \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:39
3
\$\begingroup\$

Charcoal, 43 42 bytes

≔⊕⍘⌈θφηＷ¬ⅉ«≔⍘⁺⍘θηⅈηζＦ∧⁼⌈θ⌈ζ⁼⮌ζζ⟦Ｉⅈ⟧Ｊ⁻‹ⅈ¹ⅈⅉ

Try it online! Link is to verbose version of code. Explanation: Uses the canvas x and y coordinates as they are initialised to zero saving three bytes per variable.

≔⊕⍘⌈θφη

Calculate b.

Ｗ¬ⅉ«

Repeat while y is zero.

≔⍘⁺⍘θηⅈηζ

Convert the input from base b, add on x, then convert back to base b.

Ｆ∧⁼⌈θ⌈ζ⁼⮌ζζ

If the result has the same interpreted base b and is palindromic, then...

⟦Ｉⅈ⟧

... print x while incrementing y.

Ｊ⁻‹ⅈ¹ⅈⅉ

Assign the next element of the sequence 0, 1, -1, 2, -2... to x without changing y.

39 bytes using the new import format of a numeric list:

Ｗ¬ⅉ«≔↨⁺↨θ⊕⌈θⅈ⊕⌈θηＦ∧⁼⌈θ⌈η⁼⮌ηη⟦Ｉⅈ⟧Ｊ⁻‹ⅈ¹ⅈⅉ

Try it online! Link is to verbose version of code. Explanation: Uses Base instead of BaseString and inlines Incremented(Maximum(q)) instead of precomputing b.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:40
  • \$\begingroup\$ @ValueInk Yes, I could save 3 bytes: Try it online! \$\endgroup\$ Commented Oct 10 at 7:17
  • \$\begingroup\$ Also, ⁻‹ⅈ¹ⅈ is a byte shorter than ±⁻ⅈ‹ⅈ¹... why did I not see that before? \$\endgroup\$ Commented Oct 10 at 7:19
3
\$\begingroup\$

Julia, 157 116 bytes

(b=max(s...)+1;n=foldl((a,x)->a*b+x,s);k=0;while(g=digits(n+k,base=b);g!=reverse(g)||max(g...)<b-1)k=-k+(k<1) end;k)

Attempt This Online!

This is much longer than pajonk's, but I thought it's different enough to warrant posting, albeit as a "footnote".

R, 173 169 154 bytes
\(s){b=max(s)+1
n=sum(s*b^(sum(s|1):1-1))
for(d in 0:n)for(e in d*-1:1){x=n+e;v=c()
while(x){v=c(x%%b,v);x=x%/%b}
if(!any(v-rev(v),max(v)-b+1))return(e)}}

Attempt This Online!

Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:41
  • \$\begingroup\$ @ValueInk thank you. That saved ~20 bytes and then some more optimization on top of it, made quite an improvement. \$\endgroup\$ Commented Oct 14 at 22:29
2
\$\begingroup\$

05AB1E, 24 bytes

∞<D(.ι.ΔžLRIkZ>©β+®вDÂQ*à®<Q

Input as a list of integers, with \$[10,35]\$ for a-z.

Try it online or verify all test cases (times out for the last test case).

Explanation:

∞             # Push an infinite positive list: [1,2,3,...]
 <            # Decrease each by 1 to make it non-negative: [0,1,2,...]
  D           # Duplicate it
   (          # Negate each value in the copy: [0,-1,-2,...]
    .ι        # Interleave the two lists: [0,0,1,-1,2,-2,...]
.Δ            # Pop and find the first value that's truthy for:
  I           #  Push the input-list
   Z          #  Push the maximum (without popping the list)
    >         #  Increase it by 1
     ©        #  Store this max+1 in variable `®` (without popping)
      β       #  Convert the base-® list to a base-10 integer
  +           #  Add it to the current value
   ®в         #  Convert it from a base-10 integer to a base-® list
     D        #  Duplicate it
      ÂQ      #  Check if it's a palindrome:
      Â       #   Bifurcate it; short for Duplicate & Reverse copy
       Q      #   Pop both and check if they're the same
        *     #  Multiply it to each value in the list
         à    #  Pop and push the maximum
          ®<Q #  Check that it equals the max, aka ®-1
              # (after which the found value is output implicitly)
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Rules have been updated to let you take a list of digits. Not sure if it'd be shorter for you, but letting you know that it's an option now. \$\endgroup\$ Commented Oct 10 at 4:40
  • \$\begingroup\$ @ValueInk Thanks for the heads up, that saves 4 bytes. \$\endgroup\$ Commented Oct 10 at 6:48
1
\$\begingroup\$

Ruby, 95 bytes

Putting in my own answer now that it's been a week. While not initially intended as such, optimizations have led to it becoming an adaptation of Jordan's solution to the original problem. Taking input as a character array because recombining into a string with (n*'') is one byte shorter than taking as a string and splitting with n.chars to find the max digit.

F=->n,d=0{a=n.max;s=((n*'').to_i(b=a.to_i(36)+1)+d).to_s b;s==s.reverse&&s[a]?d:F[n,d<0?-d:~d]}

Attempt This Online!

Improve this answer
\$\endgroup\$

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.