1
\$\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\$
  • \$\begingroup\$ input/output format? \$\endgroup\$ – Leaky Nun May 1 '16 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 May 1 '16 at 10:16
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\$
  • \$\begingroup\$ No way... how come the algorithm is so simple... \$\endgroup\$ – Leaky Nun May 1 '16 at 10:44
  • \$\begingroup\$ Also, it would be interesting if you show the inverse function. \$\endgroup\$ – orlp May 1 '16 at 10:52
  • \$\begingroup\$ @orlp Added the inverse function! \$\endgroup\$ – Anders Kaseorg May 1 '16 at 11:09
  • \$\begingroup\$ I think I can prove that this algorithm generalizes to all bases. \$\endgroup\$ – Joe Z. May 8 '16 at 2:43
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, privacy policy and cookie policy

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