18
\$\begingroup\$

Balanced bases:

Balanced bases are essentially the same as normal bases, except that digits can be positive or negative, while in normal bases digits can only be positive.

From here on, balanced bases of base b may be represented as balb - so balanced base 4 = bal4.

In this challenge's definition, the range of digits in a balanced base of base b is from -(k - 1) to b - k, where

k = ceil(b/2)

Examples of the range of digits in various balanced bases:

bal10:
  k = ceil(10/2) = 5
  range = -(5 - 1) to 10 - 5 = -4 to 5
        = -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
bal5:
  k = ceil(5/2) = 3
  range = -(3 - 1) to 5 - 3 = -2 to 2
        = -2, -1, 0, 1, 2

Representations of numbers in balanced bases is basically the same as normal bases. For example, the representation of the number 27 (base 10) to bal4 (balanced base 4) is 2 -1 -1, because

  2 -1 -1 (bal4)
= 2 * 4^2 + -1 * 4 + -1 * 1
= 32 + (-4) + (-1)
= 27 (base 10)

Task:

Your task is, given three inputs:

  • the number to be converted (n)
    • this input can be flexible, see "I/O Flexibility"
  • the base which n is currently in (b)
  • the base which n is to be converted to (c)

Where 2 < b, c < 1,000.

Return the number in balanced base c representation of n. The output can also be flexible.

The program/function must determine the length of n from the input itself.

I/O Flexibility:

Your input n and output can be represented in these ways:

  • your language's definition of an array
  • a string, with any character as a separator (e.g. spaces, commas)

Examples:

Note that these use a Python array as n and the output. You may use whatever fits your language, as long as it fits within "I/O Flexibility"'s definition.

[2, -1, -1] 4 7 = [1, -3, -1]
[1, 2, 3, 4] 9 5 = [1, 2, 2, -1, 2]
[10, -9, 10] 20 5 = [1, 1, 1, -2, 1, 0]

This is , so shortest code in bytes wins!

\$\endgroup\$
3
  • \$\begingroup\$ In your first answer, 4 is not a legal bal7 digit; I believe the answer should be [1, -3, -1]. And I get different answers for the second test case ([1,2,2,-1,2]) and third test case ([1,1,0,-2,1,0]) as well...? \$\endgroup\$ – Greg Martin Jan 11 '17 at 5:42
  • \$\begingroup\$ @GregMartin Ah, whoops - I calculated those by hand, so there was bound to be some problems. Thanks for noticing! Can you double-check your solutions, just in case? \$\endgroup\$ – clismique Jan 11 '17 at 5:44
  • \$\begingroup\$ @GregMartin @Qwerp-Derp Third test case is [1,1,1,-2,1,0] \$\endgroup\$ – ngenisis Jan 11 '17 at 6:36
3
\$\begingroup\$

Mathematica, 85 bytes

#~FromDigits~#2~IntegerDigits~#3//.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}&

Explanation

#~FromDigits~#2

Convert #1 (1 is implied--input 1, a list of digits) into an integer base #2 (input 2).

... ~IntegerDigits~#3

Convert the resulting integer into base #3 (input 3), creating a list of digits.

... //.{p___,a_:0,b_,q___}/;b>⌊#3/2⌋:>{p,a+1,b-#3,q}

Repeatedly replace the list of digits; if a digit is greater than floor(#3/2), then subtract #3 from it and add 1 to the digit to the left. If there is nothing on the left, insert a 0 and add 1.

\$\endgroup\$
7
  • \$\begingroup\$ It's usually recommend to talk about your solution a little, and explain it for people who may not know Mathematica. \$\endgroup\$ – ATaco Jan 12 '17 at 1:34
  • \$\begingroup\$ @ATaco Added explanation! \$\endgroup\$ – JungHwan Min Jan 12 '17 at 3:20
  • \$\begingroup\$ I'm a little mystified by this. I've never seen optional patterns used anywhere but function definitions. You don't need the outer {...} since there's only one replacement rule. \$\endgroup\$ – ngenisis Jan 12 '17 at 3:34
  • 1
    \$\begingroup\$ @JungHwanMin True, I guess what's confusing me is how this affects the match for p___. Does this find the shortest p___ followed by either a_,b_ or b_, or does it check the whole pattern requiring each of the optional patterns and then progressively drop the optional patterns until it finds a match (or some third option)? \$\endgroup\$ – ngenisis Jan 12 '17 at 3:49
  • 1
    \$\begingroup\$ @ngenisis I believe I was wrong in the previous comment (deleted), observing the result of FixedPointList[k=#3;#/.{p___,a_:0,b_,q___}/;b>⌊k/2⌋:>{p,a+1,b-k,q}&, #~FromDigits~#2~IntegerDigits~#3]&. {p___,a_,b_,q___} is matched first (for all possible p), and then {p___,b_,q___} is matched. The second replacement only applies when b is at the beginning because if there is a b in the middle that satisfies the condition, {p___,a_,b_,q___} would match it instead. \$\endgroup\$ – JungHwan Min Jan 12 '17 at 4:12
3
+200
\$\begingroup\$

APL (Dyalog Unicode), 47 bytes

{z↓⍨⊥⍨0=⌽z←m+u⊤v-⍺⊥m←⌈.5×1-u←⍺⍴⍨1+⌈⍺⍟1⌈|v←⍺⍺⊥⍵}

Try it online!

A dop that takes n, b, c as three separate values. Call it like c (b f) n where f is the submission.

Dyalog APL has a dfns library function bt that does various arithmetic in balanced ternary. Part of it is encode/decode, i.e. conversion between balanced ternary and plain integer:

encode←{                            ⍝ balanced ternary from integer.
    digs←1+⌈3⍟1⌈|⍵                  ⍝ number of ternary digits.
    tlz ¯1+(digs⍴3)⊤⍵+3⊥digs⍴1      ⍝ vector of bt digits.
}                                   ⍝ :: ∇ num → bt
decode←{3⊥⍵}                        ⍝ integer from balanced ternary.

(the hidden function tlz trims leading zeros.)

This submission is just a generalization of the above code.

Ungolfed with comments

{                    ⍝ Input: ⍵←n, ⍺⍺←b, ⍺←c
    v←⍺⍺⊥⍵           ⍝ v← plain integer from base b

    u←⍺⍴⍨1+⌈⍺⍟1⌈|v   ⍝ u← copies of c with the size enough to fit the answer
              1⌈|v   ⍝ max(1,abs(v)) so that it works well with log(⍟)
           ⌈⍺⍟       ⍝ number of digits enough to fit v in plain base c
         1+          ⍝ ...enough to fit v in balanced base c
      ⍺⍴⍨            ⍝ that many copies of c

    m←⌈.5×1-u    ⍝ m← the minimum value in balanced base c with that many digits

    z←m+u⊤v-⍺⊥m  ⍝ z← n in balanced base c, possibly with leading zeros
            ⍺⊥m  ⍝ m as plain integer
          v-     ⍝ subtract from v (or, since m<0, add abs(m) to v)
        u⊤       ⍝ encode that value to plain base c, with that many digits
      m+         ⍝ revert the offset

    z↓⍨⊥⍨0=⌽z    ⍝ remove leading zeros from z and return it
       ⊥⍨0=⌽z    ⍝ count trailing zeros (⊥⍨) on reversed z
    z↓⍨          ⍝ drop that many items from z
}
\$\endgroup\$
2
  • \$\begingroup\$ I'm not sure if this will help you any, but If you calculate digs by first multiplying v by \$\frac{c-1}{\lfloor\frac{c}{2}\rfloor}\$, I don't think you need to trim leading zeroes \$\endgroup\$ – user Nov 27 '20 at 15:35
  • \$\begingroup\$ Okay, it turns out it's longer that way. You might be able to reduce it, though. \$\endgroup\$ – user Nov 27 '20 at 16:03
2
\$\begingroup\$

Perl 6, 121 bytes

->\n,\b,\c{sub f{sum [R,](@^n)Z*($^b X**0..*)}
first {f(b,n)==f c,$_},map {[$_-($_>floor c/2)*c for .base(c).comb]},0..*}

Slow brute-force solution.

How it works:

  • map {[ .base(c).comb]}, 0..* -- Generate the lazy infinite sequence of natural numbers in base c, with each number represented as an array of digits.
  • $_ - ($_ > floor c/2) * c -- Transform it by subtracting c from each digit that is greater than floor(c / 2).
  • first { f(b, n) == f(c, $_) }, ... -- Get the first array of that sequence which when interpreted as a base c number, equals the input array n interpreted as a base b number.
  • sub f { sum [R,](@^n) Z* ($^b X** 0..*) } -- Helper function that turns an array @^n into a number in base $^b, by taking the sum of the products yielded by zipping the reversed array with the sequence of powers of the base.
\$\endgroup\$
2
\$\begingroup\$

SageMath, 53 bytes

f=lambda a,b,c:ZZ(a[::-1],b).balanced_digits(c)[::-1]

I’d be (pleasantly) surprised if there is a more concise way to write this in Sage than the obvious one. The only complication here is that Sage represents numbers as lists of digits with the least-significant digit first, whereas this challenge assumes most-significant first. So the digit lists need to be reversed.

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

JavaScript (ES6), 89 bytes

(n,b,c,g=(n,d=n%c,e=d+d<c)=>[...(n=n/c+!e|0)?g(n):[],e?d:d-c])=>g(n.reduce((r,d)=>r*b+d))

100 bytes works for negative values of n.

(n,b,c,g=(n,d=(n%c+c)%c)=>[...(n-=d,n/=c,d+d<c||(d-=c,++n),n?g(n):[]),d])=>g(n.reduce((r,d)=>r*b+d))
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 118 114 bytes

IntegerDigits[#3~FromDigits~#2,k=⌊#/2⌋;#]//.{{a_,x___}/;a>k:>{1,a-#,x},{x___,a_,b_,y___}/;b>k:>{x,a+1,b-#,y}}&

and are the 3-byte characters U+230A and U+230B, respectively. Converts #3 to base 10 from base #2, then converts to base # (so the argument order is reversed from the examples). If any digit is greater than the maximum allowed digit k=⌊#/2⌋, decrement that digit by # and increment the next digit up (may need to prepend 1). Keep doing this until all the digits are less than k.

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

APL (Dyalog Unicode), 55 51 49 bytes

Saved 4 bytes thanks to ovs

{2↓((⊃(⊢,⍨⍵÷⍨-)x-⍨(⍵|(x←⌊⍵÷2)+⊃)),1∘↓)⍣(=⍥⊃)⍺⊥⍺⍺}

Try it online! (The has been replaced by a C in the link because TIO has an older version of APL).

Without a train, 55 54 52 bytes (SBCS)

Saved a byte here too thanks to ovs

{c←⍵⋄2↓{m←x-⍨c|⊃⍵+x←⌊c÷2⋄(c÷⍨⊃⍵-m),m,1↓⍵}⍣(=⍥⊃)⍺⊥⍺⍺}

Try it online!

There's already a better APL answer here, but here's mine anyway.

Can be invoked with b (n f) c.

⍺⊥⍺⍺ converts n from base b to base 10. (...)⍣(=⍥⊃) repeatedly takes a vector whose first element is the rest of the number to be converted and whose other elements are the digits of the result. It repeats until the first digit of the created vector is 0 (given by (=⍥⊃)).

The 2↓ at the beginning is because the function is applied one extra time, so there's 2 zeroes at the start of the vector.

In the top snippet, m represents the new leading digit. It's just \$(r + x (\mod c)) - x\$ where \$x\$ is \$\lfloor \frac{c}{2} \rfloor\$ and \$r\$ is the head of the vector, the leftover part from last time.

To get the new leftover part, it's \$\frac{(r - m)}{c}\$ (this is guaranteed to be an integer since \$r-m\$ is divisible by \$c\$). Then we join this leftover part with m and 1↓⍵ (to drop last time's leftovers).

\$\endgroup\$
4
  • 1
    \$\begingroup\$ One of the b's is still there. \$\endgroup\$ – Bubbler Nov 26 '20 at 23:33
  • \$\begingroup\$ @Bubbler Right, let me fix that \$\endgroup\$ – user Nov 26 '20 at 23:38
  • 1
    \$\begingroup\$ In both versions 0=(⊃⊣) can be shortened to 0=∘⊃⊣. And by removing two pairs of brackets, the train version can be 51 bytes. \$\endgroup\$ – ovs Nov 27 '20 at 12:51
  • \$\begingroup\$ @ovs Thanks! (pad) \$\endgroup\$ – user Nov 27 '20 at 15:05
1
\$\begingroup\$

R, 105 102 101 96 bytes

Edit: -5 bytes thanks to Giuseppe

function(a,b,c){x=a%*%b^(sum(a|1):1-1)
e={}
while(x){e=c(r<-x%%c-c*(x%%c>c/2),e);x=(x-r)%/%c}
e}

Try it online!

toFromBalBase=
function(a,b,c){
x=sum(a*b^(sum(a|1):1-1))   # get value x after conversion from balanced base b
e=NULL                      # initialze empty output vector of values
while(x){                   # repeat while x is not yet zero:
  e=c(...,e)                # prepend output vector with
    r<-(r=x%%c)             # define r as x mod c (base to convert to)
    -(r>c/2)*c              # adjusted to be balanced
  x=(x-r)%/%c}              # and update x to result of division,
                            # after accounting for possibly-negative remainder.  
e}                          # finally, output e = output vector with all positive and negative 
                            # remainders prepended
\$\endgroup\$
3
  • \$\begingroup\$ 96 bytes \$\endgroup\$ – Giuseppe Nov 30 '20 at 17:18
  • 1
    \$\begingroup\$ @Giuseppe - Thanks! Perhaps after another 10 hints I'll learn to finally remember about %*%... \$\endgroup\$ – Dominic van Essen Nov 30 '20 at 22:38
  • 1
    \$\begingroup\$ I've spent so much time doing SUMPRODUCTs in Excel lately (for work) that it's a relief to have something that's a lot shorter to type when I'm golfing in R... \$\endgroup\$ – Giuseppe Nov 30 '20 at 22:56

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.