2
\$\begingroup\$

This challenge is a harder version of this one.

A variable number of trits is an array of 0 or more trits (a trit is a ternary digit). So [0, 2, 2, 1] is a variable number of trits, but so is [].

Write a function or program that, given an non-negative integer returns a variable number of trits such that every integer has a one-to-one (bijective) mapping with an array.

There are an infinite amount of such mappings, you are free to construct one as you please, but it must be one-to-one. Your mapping must conceptually be one-to-one for an arbitrarily sized integer, but it's OK if your implementation fails for large integers due to numerical limits of types in your preferred language (e.g. C's int).

As an example of what is not a one-to-one mapping, is simply listing the ternary digits of the integer. In such a system 5 becomes [1, 2] (because 1*3^1 + 2*3^0 = 5), but it's not one-to-one, because [0, 1, 2] also means 5 (because 0*3^2 + 1*3^1 + 2*3^0 = 5).

It should be fairly obvious that a mapping is not one-to-one if it skips an integer (e.g. it doesn't work for 5), but I'd like to make it clear that skipping a variable trit array is also not one-to-one. You must map to every possible variable trit array, including [].

Bonus challenge

You will be awarded the official Super Smaht® Award™ if your answer includes an algorithm (not necessarily in your golfed program) that not only works for base 2 or 3, but for all bases.


Shortest code in bytes wins.

\$\endgroup\$
2
  • \$\begingroup\$ input/output format? \$\endgroup\$
    – Leaky Nun
    Commented May 1, 2016 at 10:08
  • \$\begingroup\$ @KennyLau The standard stuff, you can write a program or function, taking a list of trits, or a string containing the trits (e.g. [1, 0, 2] or "102" or "1, 0, 2") and you must output a single integer to stdout, function return, etc. \$\endgroup\$
    – orlp
    Commented May 1, 2016 at 10:16

7 Answers 7

6
\$\begingroup\$

Pyth, 6 bytes

tjyhQ3

Explanation:

    Q    Input number.
   h     Add 1.
  y      Multiply by 2.
 j   3   Convert to base 3 as a list.
t        Remove the first element.

Test suite

Inverse function: Pyth, 14 bytes

t/i+-2%sQ2Q3 2

Explanation:

        Q        Input list.
       s         Sum.
      %  2       Modulo 2.
    -2           Subtract from 2.
   +      Q      Prepend to input list.
  i        3     Convert from base 3.
 /           2   Divide by 2.
t                Subtract 1.

Test suite

The bijection looks like this:

0: []
1: [1]
2: [0]
3: [2]
4: [0, 1]
5: [1, 0]
6: [1, 2]
7: [2, 1]
8: [0, 0]
9: [0, 2]
10: [1, 1]
11: [2, 0]
12: [2, 2]
13: [0, 0, 1]
14: [0, 1, 0]
15: [0, 1, 2]
16: [0, 2, 1]
17: [1, 0, 0]
18: [1, 0, 2]
19: [1, 1, 1]
⋮

General base

To make this work in any base b, simply replace 3 with b, 2 with (b − 1), and y with *(b − 1).

\$\endgroup\$
4
  • \$\begingroup\$ No way... how come the algorithm is so simple... \$\endgroup\$
    – Leaky Nun
    Commented May 1, 2016 at 10:44
  • \$\begingroup\$ Also, it would be interesting if you show the inverse function. \$\endgroup\$
    – orlp
    Commented May 1, 2016 at 10:52
  • \$\begingroup\$ @orlp Added the inverse function! \$\endgroup\$ Commented May 1, 2016 at 11:09
  • \$\begingroup\$ I think I can prove that this algorithm generalizes to all bases. \$\endgroup\$
    – Joe Z.
    Commented May 8, 2016 at 2:43
2
\$\begingroup\$

JavaScript, 24 bytes

f=n=>n?f(--n/3|0)+n%3:''

Try it online!

Implements the standard ternary bijective numeration, except with the digits reduced by 1.

How it works: First, check if n is 0, returning the empty string if so. Otherwise, n is pre-decremented, and that value is divided by 3 and rounded down (|0 is a short way to do the rounding) and passed recursively to f – the final digit will contribute 1, 2, or 3, while the rest contribute a multiple of 3, so \$\lfloor\frac{n-1}{3}\rfloor\$ is the value the non-final digits should represent on their own. Finally, n%3 appends the final digit, reduced by 1 from the standard (n having already been decremented).

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

Jelly, 3 bytes

ḃ3’

Try it online!

ḃ3   Convert to bijective base 3
  ’  Decrement all digits

Inverse, 3 bytes

‘ḅ3

Try it online!

‘    Increment all digits
 ḅ3  Convert from base 3

Both versions can be made to use an arbitrary base by removing the 3.

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

Jelly, 12 bytes

ḤR‘b3Ḣ’$Ðḟị@

There is no empty list in Jelly; it is represented as 0 (an integer not a list).

For other bases: change to ×n and b3 to bn, where n is the intended base.

Try it online!

Test suite.

For other bases

It only costs 11 bytes if given base as second input.

Try it online!

Test suite.

Algorithm

I thought of appending a 1 before the list and then convert it to a ternary.

That way, [0,0] will become 100 = 9 while [0,0,0] will become 1000 = 27.

However, a problem arises: that 2011 and 1011 both map to [0,1,1].

I only need numbers whose ternary representation starts with 1.

Therefore, I generated those whose ternary representation starts with 1, and then use their index instead.

That is, the list begins as [1, 3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Therefore:

  • 1 will be mapped to 1
  • 2 will be mapped to 3
  • 3 will be mapped to 4
  • 4 will be mapped to 5
  • 5 will be mapped to 9
  • n will be mapped to a(n) where a is that list.

There's another problem: both 0 and 1 are mapped to the empty list. Therefore, I removed 1 from the list, making a = [3, 4, 5, 9, 10, 11, 12, 13, 14, 15, 16, 17, ...].

Those are the integers whose ternary representation starts with 1, except 1.

The same algorithm can be applied to other bases.

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

Jelly, 6 bytes

‘Ḥb3ṫ2

Translation of Kaseorg's answer in Pyth.

Try it online!

Hardcoded base: try it online!

Given base: try it online!

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

CJam, 9 bytes

ri)_+3b(;

Translation of Kaseorg's answer in Pyth.

Try it online!

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

JavaScript (ES6), 31 bytes

n=>(n*2+2).toString(3).slice(1)

Since everyone else is translating @AndreasKaseorg's fine answer. Generic version (36 bytes):

b=>n=>(-~n*~-b).toString(b).slice(1)
\$\endgroup\$

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.